结构定义：
将一个链表类型定义为一个指向一个链表节点LNode的指针，LNode分为数据域和指针域，代码实现如下：
1
2
3
4
5
6
7typedef int ElementType; typedef struct LNode* List; struct LNode { ElementType Data; List Next; };
求表长：
只要当前指针非空，就不断指向下一个节点，并将计数器++即可，最后返回计数器的值。易知该操作时间复杂度为O(n)，代码实现如下：
1
2
3
4
5
6
7
8
9
10int Length(List PtrL) { int j = 0; List p = PtrL; while (p) { p = p->Next; j++; } return j; }
按序号查找：
跟求表长操作类似，只要当前指针非空并且计数器值<序号值，就不断指向下一个节点。检查跳出循环时计数器的值，如果等于序号，说明找到了，返回节点的指针；否则说明没找到，返回NULL。查找的时间复杂度为O(n)，代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13List FindKth(List PtrL, int k) { List p = PtrL; int i = 1; while (p != NULL && i < k) { p = p->Next; i++; } if (i == k) return p; else return NULL; }
按值查找：
循环过程中检查p指向的节点的数据是否等于被查找元素的值即可，时间复杂度为O(n)，代码实现如下：
1
2
3
4
5
6
7List Find(ElementType x, List PtrL) { List p = PtrL; while (p != NULL && p->Data != x) p = p->Next; return p; }
插入操作：
如果插入位置为1，说明插入位置在第一个：
首先申请节点空间，然后将数据x装填进去，最后令Next指向原来的链表，返回新申请的节点地址即可；
否则：
则需要用FindKth函数找到插入位置的前驱节点p，然后新申请一块空间s并装填数据，接着令s的Next指向p的Next，p的Next指向s，注意操作顺序，最后返回原链表指针即可。
插入操作的时间复杂度为O(n)，时间主要花在了FindKth查找插入位置上，代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21List Insert(ElementType x, int i, List PtrL) { List s, p; if (i == 1) { List s = (List)malloc(sizeof(struct LNode)); s->Data = x; s->Next = PtrL; return s; } p = FindKth(PtrL, i - 1); if (!p) { printf("参数i错n"); return NULL; } else { List s = (List)malloc(sizeof(struct LNode)); s->Data = x; s->Next = p->Next; p->Next = s; return PtrL; } }
删除指定元素：
如果要删除第一个元素：
如果指针为空，则说明是空表，返回NULL即可；
否则，用s指向第一个节点，然后PtrL指向PtrL->Next，这样就跳过了第一个节点，最后释放掉第一个节点的内存，返回新的表头节点指针。
否则，找到第i个节点的前驱p：
如果p为空，说明前驱不存在，报错返回；
如果p的Next为空，说明前驱是最后一个节点，也就是要删除的节点不存在，报错返回。
否则，令s指向待删除的节点，p的Next指向s的Next，然后释放掉s的内存，返回原链表指针即可。
删除操作的时间复杂度也为O(n)，同样的，其时间也是花在了查找元素上。代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27List Delete(int i, List PtrL) { List s, p; if (i == 1) { if (!PtrL) { return NULL; } else { s = PtrL; PtrL = PtrL->Next; free(s); return PtrL; } } p = FindKth(PtrL, i - 1); if (p == NULL) { printf("第%d节点不存在n", i - 1); return NULL; } else if (p->Next == NULL) { printf("第%d节点不存在n", i); return NULL; } else { s = p->Next; p->Next = s->Next; free(s); return PtrL; } }
销毁链表：
为避免产生内存泄露，线性表不用了的话归还申请的空间，代码实现如下：
1
2
3
4
5
6
7
8
9
10
11void Destory(List PtrL) { List p = PtrL; List s; while (p) { s = p; p = p->Next; free(s); } return; }
最后
以上就是繁荣微笑最近收集整理的关于基础数据结构与算法之链表-C语言实现的全部内容，更多相关基础数据结构与算法之链表-C语言实现内容请搜索靠谱客的其他文章。
![【数据结构与算法】线性表的链式表示和实现，超详细【C语言版】链式存储结构2.5.1 单链表的定义和实现2.5.2 单链表基本操作的实现链表的运算时间效率分析单链表的建立（前插法）单链表的建立（尾插法）单链表基本操作的代码实现 [C语言]2.5.3 循环链表](/uploads/reation/bcimg3.png)
发表评论 取消回复