链表的初始化
创建一个链表需要做如下工作：
1.声明一个头指针（如果有必要，可以声明一个头节点）；
2.创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；
比如创建一个存储{1,2,3}且无头结点的链表,C语言实现代码如下
link * initLink(){
link * p=NULL;//创建头指针
link * temp = (link*)malloc(sizeof(link));//创建首元节点
//首元节点先初始化
temp->elem = 1;
temp->next = NULL;
p = temp;//头指针指向首元节点
//从第二个节点开始创建
for (int i=2; i<5; i++) {
//创建一个新节点并初始化
link *a=(link*)malloc(sizeof(link));
a->elem=i;
a->next=NULL;
//将temp节点与新建立的a节点建立逻辑关系
temp->next=a;
//指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对
temp=temp->next;
}
//返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
return p;
}
如果想创建一个存储{1,2,3}并且有头结点的链表,C语言实现如下
link * initLink(){
link * p=(link*)malloc(sizeof(link));//创建一个头结点
link * temp=p;//声明一个指针指向头结点，
//生成链表
for (int i=1; i<5; i++) {
link *a=(link*)malloc(sizeof(link));
a->elem=i;
a->next=NULL;
temp->next=a;
temp=temp->next;
}
return p;
}
链表插入元素
向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：
1.插入到链表的头部（头节点之后），作为首元节点；
2.插入到链表中间的某个位置；
3.插入到链表的最末端，作为链表中最后一个数据元素；
链表插入元素的操作是固定的,分一下两步:
1.将新结点的 next 指针指向插入位置后的结点；
2.将插入位置前结点的 next 指针指向插入结点；
Snip20190130_17.png
C语言实现如下
//p为原链表，elem表示新数据元素，add表示新元素要插入的位置
link * insertElem(link * p,int elem,int add){
link * temp=p;//创建临时结点temp
//首先找到要插入位置的上一个结点
for (int i=1; i<add; i++) {
if (temp==NULL) {
printf("插入位置无效\n");
return p;
}
temp=temp->next;
}
//创建插入结点c
link * c=(link*)malloc(sizeof(link));
c->elem=elem;
//向链表中插入结点
c->next=temp->next;
temp->next=c;
return p;
}
链表删除元素
从链表中删除元素有两个操作
1.将节点中链表中摘下来
2.手动释放节点,回收被节点占用的空间
例如从链表{1,2,3,4}中删除元素3,实际操作效果如下
Snip20190130_18.png
C语言代码实现
//p为原链表，add为要删除元素的值
link * delElem(link * p,int add){
link * temp=p;
//temp指向被删除结点的上一个结点
for (int i=1; i<add; i++) {
temp=temp->next;
}
link * del=temp->next;//单独设置一个指针指向被删除结点，以防丢失
temp->next=temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
free(del);//手动释放该结点，防止内存泄漏
return p;
}
链表查找元素
最常用的方法是遍历链表中的各个节点,用被查找元素跟各个节点数据域中存储的数据元素进行对比
//p为原链表，elem表示被查找元素、
int selectElem(link * p,int elem){
//新建一个指针t，初始化为头指针 p
link * t=p;
int i=1;
//由于头节点的存在，因此while中的判断为t->next
while (t->next) {
t=t->next;
if (t->elem==elem) {
return i;
}
i++;
}
//程序执行至此处，表示查找失败
return -1;
}
链表更新元素
更新链表中的元素,只需要遍历链表找到存储的节点,对节点中的数据域的元素进行更新即可
//更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值
link *amendElem(link * p,int add,int newElem){
link * temp=p;
temp=temp->next;//在遍历之前，temp指向首元结点
//遍历到被删除结点
for (int i=1; i<add; i++) {
temp=temp->next;
}
temp->elem=newElem;
return p;
}
