学习⼼得：链表的操作（C语⾔实现）
今天将给⼤家讲述链表的学习⼼得。学习数据结构，⽏庸置疑链表必须学好，后⾯的栈、队列、树、图都是以链表为基础的；链表的种类很多，有单链表、双链表、循环链表、⾮循环链表；在此，我们以⾮循环单链表为例，来讲链表的创建、求长度、排序、插⼊和排序。
1.什么是链表
链表我的理解要包含以下特征：（1）.由n个节点离散分配；（2）.每个节点通过指针连接（3）每⼀个节点由⼀个前驱节点和⼀个后驱节点（4）.⾸节点没有前驱节点，尾节点没有后驱节点；
满⾜上⾯的4条，我们就称为链表；链表既然由很多个节点，那节点⼜由什么组成？节点由两个部分组成，⼀是数据域，⽤来存放有效数据；⼆是指针域，⽤来指向下⼀个节点；下⾯⽤C语⾔来构建链表数据结构，⾸先应该构造出节点，然后再把所有的节点连起来，就构成了链表；
（1）节点的构造
typedef struct Node
{
int data;//数据域，⽤来存放数据域；
struct Node *pNext;//定义⼀个结构体指针，指向下⼀次个与当前节点数据类型相同的节点
}NODE,*PNODE;  //NODE等价于 struct Node; PNODE等价于struct Node *；此处⽤⼤写是为了与变量区分，可以让⼈容易变出是个数据类型
typedef 只是给数据类型取个别名，即 typedef  数据类型  别名；我们知道struct Node 是我们定义的数据类型；
（2）链表的创建
在创建链表之前，我们需要需要了解⼀下专业术语：
⾸节点：存放第⼀个有效数据的节点；
尾节点：存放最后⼀个有效数据的节点；
头节点：头节点的数据类型与⾸节点的数据类型相同，并且头节点是⾸节点前⾯的那个节点，并不存放有效数据；头节点的存在只是为了⽅便链表的操作。
头指针：指向头节点的指针；
尾指针：指向尾节点的指针；
⾸先，我们应该创建⼀个头节点，并⽤头指针指向它，⽤C语⾔描述：⽤malloc向计算机申请⼀块内存，并定义⼀个指向与头节点数据类型相同的指针（⼀定要判断申请内存是否成功）；
然后，要知道要创建链表的长度，⽤⼀个循环来每次创建⼀个节点，并把每个节点连在⼀起；
假如我们要在头节点phead后⾯插⼊节点p：
（1）把头节点的指针域指向P节点，即pHead->pNext=p;
（2）把p节点的指针域指向NULL，即p->pNext=NULL;
这样就可以了吗？ 想想我们就可以发现，当我们要插⼊多个节点时，头节点始终指向最后添加的⼀个数据，以前的节点通过头指针此时已经不到了；我们定义⼀个尾指针pTail，始终⽤来指向链表的结尾，每次只在pTail后⾯添加节点。
伪算法：
（1）定义⼀个尾指针pTail，并初始化，使它指向头节点，即pTail=pHead；
（2）在pTail后⾯添加节点，修改指针：
pTail->pNext=p;
p->pNext=NULL;
pTail=p;              //使pTail指向链表最后⼀个元素
PNODE Create_List(void)
{
int len;  //存放链表的长度
int i;  //循环变量
int val;//⽤来临时存放⽤户输⼊的结点的值
PNODE List;
PNODE pHead=(PNODE)malloc(sizeof(NODE));//分配⼀个头节点
if(NULL==pHead)
{
printf("Memory allocation failure");
exit(-1);
}
else
{  PNODE pTail=pHead;
pHead->pNext=NULL;
printf("please input the length of list: ");  //需要⼀个指针始终指向链表的结尾  scanf("%d",&len);
for(i=0;i<len;i++)
{
PNODE p=(PNODE)malloc(sizeof(NODE));
if(NULL==p)
{
printf("Memory allocation failure");
exit(-1);
}
else
{
printf("please input the value of list: ");
scanf("%d",&val);
p->data=val;
pTail->pNext=p;
p->pNext=NULL;
pTail=p;
}
}
}
return pHead;
}
2.向链表中插⼊元素
sizeof 指针
假如要在节点2的前⾯插⼊节点p，我们⾸先要到节点2的前驱节点1，假设现在q指针指向节点1，则
（1）p->pNext=q->pNext;
（2）q->pNext=p;
程序代码如下：
//链表的第pos有效元素前⾯插⼊元素val，⾸先我们应该到第pos个元素前⾯⼀个元素的位置；
//当链表有3个元素时，pos=4，将不会进⾏插⼊操作
bool Insert_List(PNODE pHead,int pos,int val)
{
int i=0;
PNODE p=pHead;
while((NULL!=p)&&(i<pos-1)) //
{
p=p->pNext;
i++;
}
if(p==NULL||i>pos-1)  //把链表为空的情况考虑进去了；i>pos-1 可以防⽌⽤户输⼊错误；
return false;
//程序执⾏到这之后，i=pos-1；p指针指向链表第pos个有效节点的前驱，即指向第pos-1节点；
PNODE q=(PNODE)malloc(sizeof(NODE));
q->data=val;
q->pNext=p->pNext;
p->pNext=q;
}
3.删除链表中的元素
假如要删除节点2，只需要把节点1指针域指针指向节点3，但不要忘记释放节点2所占的内存，否则将会造成内存泄漏；⾸先必须到节点2的前驱节点1，假设p指向节点1。
（1）q=p->pNext;  //⾸先⽤q保存要删除节点的地址；
（2）p->pNext=q->pNext;  //q->pNext=p->pNext->pNext;  修改指针使节点1指向节点3；
（3）free(q);  //释放节点2所占的内存；
bool Delete_List(PNODE pHead,int pos,int *val)
{
int i=0;
PNODE p=pHead;
while((NULL!=p)&&(i<pos-1))
{
p=p->pNext;
i++;
}
if(p==NULL||i>pos-1)  //把链表为空的情况考虑进去了；i>pos-1 可以防⽌⽤户输⼊错误；
return false;
//程序执⾏到这之后，i=pos-1；
PNODE q=p->pNext;  //q指向待删除的节点；
*val=q->data;
p->pNext=q->pNext; //修改链表指针指向；
free(q);          //释放q所指向节点的内存；
q=NULL;//千万不可以忘记，否则会出现野指针；
}
4.链表元素的排序
快速排序和冒泡排序的思想对于链表这个数据结构同样适⽤，下⾯是⼀个⽤选择排序来实现链表的排序；
//链表有效元素的个数
int Length_List(PNODE pHead)
{  int len=0;  //定义变量要记得初始化；
PNODE p=pHead->pNext;
while(NULL!=p)
{
len++;
p=p->pNext;
}
return len;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。