# include<stdio.h>
# include<malloc.h>
# include<stdlib.h>
typedef struct Node
{
int data;//数据域
struct Node * pNext; //指针域
}NODE, *PNODE; //BODE等价于struct Node PNODE等价于strucr Node *
PNODE create_list(void); //函数声明
void traverse_list(PNODE pHead); //对链表输出
bool is_empty(PNODE pHead); //判断链表能否为空
int length_list(PNODE ); //返回值为链表的长度
bool insert_list(PNODE, int, int); //在第几个节点前插入一个节点,第一个int表示节点得位置第二个int表示数值
bool delete_list(PNODE, int, int); //删除第几个节点,第一个int是节点的位置,第二个int表示节点的值
void sort_list(PNODE); //对链表排序
int main(void)
{
PNODE pHead = NULL; //等价于strucr Node *pHead = NULL,这里的pHead是头结点的地址
pHead = create_list(); // create_list()功能:创建一个非循环单链表,并将该链表的头结点的地址返回
//traverse_list(pHead); // traverse_list功能:输出链表中的每一个元素
//sort_list(pHead); //小到大排序
//insert_list(pHead, 3, 222); //在第三个节点前插入222
//traverse_list(pHead); // traverse_list功能:输出链表中的每一个元素
//int len = length_list(pHead);
delete_list(pHead, 3, 0);
traverse_list(pHead);
return 0;
}
PNODE create_list(void) //创建一个非循环单链表, 不需要参数,返回PNODE类型
{
int len; //用来存放有效节点的个数
int i;
int val; //用来临时存放用户输入的结点的值
PNODE pHead = (PNODE)malloc(sizeof(NODE)); // PNODE等价于strucr Node * 分配一个不存放有效数据的节点,既 头结点
if (NULL == pHead)
{
printf(“分配失败,程序终止”);
exit(-1); //终止所在函数的程序,并返回-1,与return不同的是return只会终止同一级的程序
}
//分配动态内存后,要养成检测能否分配成功的习惯
PNODE pTail = pHead; //把头结点的地址赋给pTail
pTail->pNext = NULL; //将pTail的指针域定义为空,此时这个链表只要头结点,即这是一个空链表
printf(“请您输入生成的链表的节点个数: len = “);
scanf(“%d”, &len);
for (i=0; i < len; i++)
{
printf(“请输入第%d个节点的值:” , i+1);
scanf(” %d”,&val);
PNODE pNew = (PNODE)malloc(sizeof(NODE)); //定义一个NODE型数据变量,并分配动态内存
if (NULL == pNew)
{
printf(“分配失败,程序终止\n”);
exit(-1); //终止所在函数的程序,并返回-1
}
//分配动态内存后,要养成检测能否分配成功的习惯
pNew->data = val; //pNew为一个有效节点,此处为这个节点的数据域赋值
pTail->pNext = pNew; //执行此处后pTail指向pNew这个节点
pNew->pNext = NULL; //将NULL赋给pNew这个节点的指针域
pTail = pNew; //此时pTail这个节点等价于 pNew这个节点
//通过这四步的循环,每循环一次增加一个节点,并且将尾节点的指针域赋为空值
}
return pHead; //原因是通过链表的头结点能确定整个链表故返回链表的头节点地址
}
void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext ; //定义PNODE型变量p,将pHead->pNext 赋给p
while (NULL != p) //若p不为空,则输出它的数据域
{
printf(“%d “,p->data );
p = p->pNext ; //将P向后移一个节点
}
printf(“\n”);
return;
}
int length_list(PNODE pHead) //接收头结点地址pHead
{
int len = 0;
PNODE p = pHead->pNext ;
while ( p != NULL) //判断节点指针域部位空
{
++len; //若不为空,长度加一
p = p->pNext ; //指针往后移一个节点
}
printf(“链表的长度为%d\n”,len);
return len;
}
void sort_list(PNODE pHead) //表示接受PNODE类型变量的同时定义PNODE性变量pHead
{
int i, j, t;
PNODE p, q; //定义定义变量
int len = length_list(pHead); //普通函数之间可以相互调用,这里定义了int型变量
for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext )
{
for (j =i+1,q=p->pNext; j<len; ++j,q=q->pNext )
{
if (p->data > q->data ) //相似于数组(a[i] > a[j])
{
t= p->data; //相似于数组t = a[i];
p->data = q->data; //相似于数组a[i] = a[j];
q->data = t; //相似于数组a[j] = t;
}
}
/*根据冒泡排序改编,若把链表排序写得和数组排序非常相似,我们可以理解为泛型*/
}
return;
}
bool insert_list(PNODE pHead, int pos, int val)
{
int i =0;
PNODE p = pHead;
while (p != NULL && i < pos-1)//次循环功能为将p指向pos-1个节点,若不能则结束程序
{
p = p->pNext ;
++i; //p没向后一一个节点i就加一
} //到此处p指向pos-1个节点或p-Next为空
if (i>pos-1 || p==NULL) //若P为空或i>pos-1则结束程序
return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));//为变量pNew分配动态内存
if (NULL == pNew)
{
printf(“内存分配失败”);
exit(-1);
} //判断动态内存能否分配成功
pNew->data = val; //这四步将一个新的节点出入链表
PNODE q = p->pNext ;
p->pNext = pNew;
pNew->pNext = q;
return true;
}
bool delete_list(PNODE pHead, int pos, int val)
{
int i =0;
PNODE p = pHead;
while (p != NULL && i < pos-1)//次循环功能为将p指向pos-1个节点,若不能则结束程序
{
p = p->pNext ;
++i; //p每后向后移一次个节点i就加一
} //到此处p指向pos-1个节点或p-Next为空
if (i>pos-1 || p==NULL) //若P为空或i>pos-1则结束程序
return false;
PNODE q = p->pNext; //q指向第pos个节点
/* val = q->data; //将要删除的值写入val
q = q->pNext; //此时q指向pos+1个元素,p指向pos-1个元素
p->pNext = q;*/ //运行后p指向Q
/*注释掉的方法没有释放删除节点的内存会造成内存泄漏*/
val = q->data;
p->pNext = p->pNext->pNext;//pos-1个节点 == pos+1个节点,所以此时pos个节点过后是pos+1个节点
free(q);//释放删除节点的内存
q = NULL;
printf(“你删除的元素是 %d\n”, val);
return true;
}
# include<malloc.h>
# include<stdlib.h>
typedef struct Node
{
int data;//数据域
struct Node * pNext; //指针域
}NODE, *PNODE; //BODE等价于struct Node PNODE等价于strucr Node *
PNODE create_list(void); //函数声明
void traverse_list(PNODE pHead); //对链表输出
bool is_empty(PNODE pHead); //判断链表能否为空
int length_list(PNODE ); //返回值为链表的长度
bool insert_list(PNODE, int, int); //在第几个节点前插入一个节点,第一个int表示节点得位置第二个int表示数值
bool delete_list(PNODE, int, int); //删除第几个节点,第一个int是节点的位置,第二个int表示节点的值
void sort_list(PNODE); //对链表排序
int main(void)
{
PNODE pHead = NULL; //等价于strucr Node *pHead = NULL,这里的pHead是头结点的地址
pHead = create_list(); // create_list()功能:创建一个非循环单链表,并将该链表的头结点的地址返回
//traverse_list(pHead); // traverse_list功能:输出链表中的每一个元素
//sort_list(pHead); //小到大排序
//insert_list(pHead, 3, 222); //在第三个节点前插入222
//traverse_list(pHead); // traverse_list功能:输出链表中的每一个元素
//int len = length_list(pHead);
delete_list(pHead, 3, 0);
traverse_list(pHead);
return 0;
}
PNODE create_list(void) //创建一个非循环单链表, 不需要参数,返回PNODE类型
{
int len; //用来存放有效节点的个数
int i;
int val; //用来临时存放用户输入的结点的值
PNODE pHead = (PNODE)malloc(sizeof(NODE)); // PNODE等价于strucr Node * 分配一个不存放有效数据的节点,既 头结点
if (NULL == pHead)
{
printf(“分配失败,程序终止”);
exit(-1); //终止所在函数的程序,并返回-1,与return不同的是return只会终止同一级的程序
}
//分配动态内存后,要养成检测能否分配成功的习惯
PNODE pTail = pHead; //把头结点的地址赋给pTail
pTail->pNext = NULL; //将pTail的指针域定义为空,此时这个链表只要头结点,即这是一个空链表
printf(“请您输入生成的链表的节点个数: len = “);
scanf(“%d”, &len);
for (i=0; i < len; i++)
{
printf(“请输入第%d个节点的值:” , i+1);
scanf(” %d”,&val);
PNODE pNew = (PNODE)malloc(sizeof(NODE)); //定义一个NODE型数据变量,并分配动态内存
if (NULL == pNew)
{
printf(“分配失败,程序终止\n”);
exit(-1); //终止所在函数的程序,并返回-1
}
//分配动态内存后,要养成检测能否分配成功的习惯
pNew->data = val; //pNew为一个有效节点,此处为这个节点的数据域赋值
pTail->pNext = pNew; //执行此处后pTail指向pNew这个节点
pNew->pNext = NULL; //将NULL赋给pNew这个节点的指针域
pTail = pNew; //此时pTail这个节点等价于 pNew这个节点
//通过这四步的循环,每循环一次增加一个节点,并且将尾节点的指针域赋为空值
}
return pHead; //原因是通过链表的头结点能确定整个链表故返回链表的头节点地址
}
void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext ; //定义PNODE型变量p,将pHead->pNext 赋给p
while (NULL != p) //若p不为空,则输出它的数据域
{
printf(“%d “,p->data );
p = p->pNext ; //将P向后移一个节点
}
printf(“\n”);
return;
}
int length_list(PNODE pHead) //接收头结点地址pHead
{
int len = 0;
PNODE p = pHead->pNext ;
while ( p != NULL) //判断节点指针域部位空
{
++len; //若不为空,长度加一
p = p->pNext ; //指针往后移一个节点
}
printf(“链表的长度为%d\n”,len);
return len;
}
void sort_list(PNODE pHead) //表示接受PNODE类型变量的同时定义PNODE性变量pHead
{
int i, j, t;
PNODE p, q; //定义定义变量
int len = length_list(pHead); //普通函数之间可以相互调用,这里定义了int型变量
for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext )
{
for (j =i+1,q=p->pNext; j<len; ++j,q=q->pNext )
{
if (p->data > q->data ) //相似于数组(a[i] > a[j])
{
t= p->data; //相似于数组t = a[i];
p->data = q->data; //相似于数组a[i] = a[j];
q->data = t; //相似于数组a[j] = t;
}
}
/*根据冒泡排序改编,若把链表排序写得和数组排序非常相似,我们可以理解为泛型*/
}
return;
}
bool insert_list(PNODE pHead, int pos, int val)
{
int i =0;
PNODE p = pHead;
while (p != NULL && i < pos-1)//次循环功能为将p指向pos-1个节点,若不能则结束程序
{
p = p->pNext ;
++i; //p没向后一一个节点i就加一
} //到此处p指向pos-1个节点或p-Next为空
if (i>pos-1 || p==NULL) //若P为空或i>pos-1则结束程序
return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));//为变量pNew分配动态内存
if (NULL == pNew)
{
printf(“内存分配失败”);
exit(-1);
} //判断动态内存能否分配成功
pNew->data = val; //这四步将一个新的节点出入链表
PNODE q = p->pNext ;
p->pNext = pNew;
pNew->pNext = q;
return true;
}
bool delete_list(PNODE pHead, int pos, int val)
{
int i =0;
PNODE p = pHead;
while (p != NULL && i < pos-1)//次循环功能为将p指向pos-1个节点,若不能则结束程序
{
p = p->pNext ;
++i; //p每后向后移一次个节点i就加一
} //到此处p指向pos-1个节点或p-Next为空
if (i>pos-1 || p==NULL) //若P为空或i>pos-1则结束程序
return false;
PNODE q = p->pNext; //q指向第pos个节点
/* val = q->data; //将要删除的值写入val
q = q->pNext; //此时q指向pos+1个元素,p指向pos-1个元素
p->pNext = q;*/ //运行后p指向Q
/*注释掉的方法没有释放删除节点的内存会造成内存泄漏*/
val = q->data;
p->pNext = p->pNext->pNext;//pos-1个节点 == pos+1个节点,所以此时pos个节点过后是pos+1个节点
free(q);//释放删除节点的内存
q = NULL;
printf(“你删除的元素是 %d\n”, val);
return true;
}
解决方案
40
防止后面不小心又使用了已经释放了的内存,这是一种习惯,当然也可以不写