链表的基本操作，用链表实现线性表

链表
增删改查
指针指向等于地址赋值
定义一个链表结构体

1. typedef struct _NODE_ {
2.         int number;
3.         struct _NODE* next;
4. }Node,*Lintlist;

复制代码

这里的node是对节点命名时的数据类型
Linklist是对该链表命名时的数据类型
初始化
1.建立一个链表
2.申请一个头节点

1. Linklist init(Linklist l) {
2.         Node* head = (Node*)malloc(sizeof(Node));
3.         if (head == NULL) {
4.                 printf("内存分配失败");
5.                 return NULL;
6.         }
7.         head->next = NULL;
8.         return head;
9. }

复制代码

在主函数中调用是

1. Linklist l=NULL;
2. l = init(l);

复制代码

也可以
Linklist l=init(l);
当然在这里也可以这样来
在这里函数的参数有没有都可以，因为其本质要的是申请的这个节点的地址也就是head的值
在主函数中他会把这个返回值赋值给l；
包括这里的函数类型也可以换成Node*如下

1. Node* init() {
2.         Node* head = (Node*)malloc(sizeof(Node));
3.         if (head == NULL) {
4.                 printf("内存分配失败");
5.                 return NULL;
6.         }
7.         head->next = NULL;
8.         return head;
9. }

复制代码

在主函数中调用就是
Linklist l=init();
增加操作
分为三种，分别为头插法，尾插法，以及在指定位置增加，
这里分为三种操作的一个原因就是增加可读性
还有一个原因是这样能帮助我们写代码
不需要判断各种临界情况
代码不会复杂，相对简单。
头插法

1. Linklist head_add(Linklist l, int m) {
2.         Node* s = (Node*)malloc(sizeof(Node));
3.         if (s == NULL) {
4.                 printf("内存分配失败");
5.                 return l;
6.         }
7.         s->next = l->next;
8.         s->number = m;
9.         l->next = s;
10.         return l;
11. }

复制代码

在这里有两个点需要注意
第一点，头指针的指针域数值在改变的时候不能让链表断裂，比如

1. l->next = s;
2. s->next = l->next;

复制代码

在这里我们先让头指针的指针域指向了s
但这里就会导致一个问题，我们原本在这个指针域里面存储的地址丢了
我们再执行
s->next = l->next;
就会 让s的next指向自己
就会导致后续链表的断裂
所以我们在改变链表的指针域时，最重要的就是不能让链表断裂，即不能让数据丢失
第二点
在返回值上，我们其实可以让返回值为void
因为在这个函数里面其实我们没有动l的值
l里面是一个指针，而这个指针指向了一个我们声明的结构体类型的数据
我们是根据这个指针访问这个结构体类型的数据，然后更改这个结构体内的一些数据
我们并没有对l这个变量里面存储的数据进行改变
所以我们可以用void
而在上面我们用Link list这个作为返回值的原因是
在我们对l的理解中，l指的是这个链表
对于这个链表实际上是发生了变化的
所以我们在这里用了返回值
接下来的尾插法和指定位置插入都有这个问题。
尾插法
1.找到未节点
2.构建一个节点插在为节点后面

1. Linklist rear_add(Linklist l, int m) {
2.         Node* p = l;
3.         while (p->next) {
4.                 p = p->next;
5.         }
6.        
7.        
8.         Node* s = (Node*)malloc(sizeof(Node));
9.         if (s == NULL) {
10.                 printf("内存分配失败");
11.                
12.                 return l;
13.         }
14.         s->number = m;
15.         s->next = NULL;
16.         p->next = s;
17.         return l;
18. }

复制代码

指定位置插入
1.找到指定位置（这里可以来一个find函数）
接下来的操作是基于find函数进行的
find函数在后面紧挨着
2.通过find函数的返回值确认后续操作
3，如果是NULL则没有找的该数据，无法执行插入操作
4.找到之后，就构建新的节点插入

1. Linklist rear_add(Linklist l, int m) {
2.         Node* p = l;
3.         while (p->next) {
4.                 p = p->next;
5.         }
6.        
7.        
8.         Node* s = (Node*)malloc(sizeof(Node));
9.         if (s == NULL) {
10.                 printf("内存分配失败");
11.                 return l;
12.         }
13.         s->number = m;
14.         s->next = NULL;
15.         p->next = s;
16.         return l;
17. }

复制代码

查，
找到指定数据的节点，然后根据查找结果确定返回值

1. Node* find(Linklist l, int k) {
2.        
3.         Node* q = l->next;
4.         while (q && q->number != k) {
5.        
6.                 q = q->next;
7.         }
8.         return q;
9. }

复制代码

删，
删除指定数据，在这里不能通过查找函数，是因为在删除操作里我们要涉及前面的一个节点的指针域
在双向链表中就可以通过find函数进行查找了，因为在双向链表中，节点内包含着前节点的地址

1. Linklist delet(Linklist l, int k) {
2.         //k为删减的值
3.         Node* p = l;
4.         Node* q = l->next;
5.         while (q && q->number != k) {
6.                 p = q;
7.                 q = q->next;
8.         }
9.         if (q==NULL) {
10.                 printf("未找到该数据，不能执行删除操作\n");
11.                 return l;
12.         }
13.         p->next = q->next;
14.        
15.         free(q);
16.         q = NULL;
17.         return l;
18. }

复制代码

改，
最简单的操作，可以选择通过find函数也可以直接查找，因为这个函数不涉及指针的改变

1. Linklist change(Linklist l, int k,int m) {
2.         Node* p = find(l, k);
3.         if (p == NULL) {
4.                 printf("未找到该数据，不能实行数据更改操作\n");
5.                 return l;
6.         }
7.         p->number = m;
8.         return l;
9. }

复制代码

输出函数
输出链表值

1. void printff(Linklist l) {
2.         Node* p = l->next;
3.         while (p) {
4.                 printf("%d ", p->number);
5.                 p = p->next;
6.         }
7.         printf("\n");
8. }

复制代码

下面时主函数的调用

1. int main()
2. {
3.         Linklist l=NULL;
4.         l = init(l);
5.         l = head_add(l, 3);
6.         l = head_add(l, 9);
7.         l = head_add(l, 5);
8.         printff(l);
9.         l = rear_add(l, 8);
10.         l = rear_add(l, 4);
11.         l = rear_add(l, 6);
12.         printff(l);
13.         l = inadd(l,3, 15);
14.         l = inadd(l, 10, 16);
15.         l = inadd(l, 9, 12);
16.         printff(l);
17.         l = delet(l, 4);
18.         l = delet(l, 8);
19.         l = delet(l, 16);
20.         printff(l);
21.         l = change(l, 4, 43);
22.         printff(l);
23.         return 0;
24. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！