数据结构入门：顺序表/链表/栈/队列/堆(原理+实现)

一、开篇引入

作为计算机专业的学生，顺序表、链表、栈、队列、堆是《数据结构》课程的核心基础，也是算法刷题、工程开发的"必备工具",但新手刚接触时,常容易混淆各结构的特性，也难以用C语言实现，本文就从概念原理出发，用C语言完成这些数据结构的实现，手把手帮助新手彻底搞懂这些核心结构。
二、数据结构的实现

1.顺序表

顺序表是线性表的一种，满足逻辑结构和物理结构双线性
逻辑结构:数组元素之间呈"一对一"的先后顺序，是逻辑上的线性结构，可能与实际结构并不相同
物理结构:底层基于数组实现，数组的内存空间是连续且不可分割，因此数据在物理存储上也连续
1.1.顺序表的结构:

点击查看代码

1. typedef struct SeqList {
2.         SLdatatype* data;//数组的指针
3.         int size;//有效数据的个数
4.         int capacity;//数组的实际空间
5. }SL;

复制代码

1.2.顺序表的接口:

点击查看代码

1. //初始化顺序表
2. void InitSL(SL* ps);
3. //销毁顺序表
4. void DestroySL(SL* ps);
5. //申请空间
6. void SLbuy(SL* ps, SLdatatype x);
7. //打印
8. void SLprint(SL ps);
9. //头插
10. void SLpushfront(SL* ps, SLdatatype x);
11. //尾插
12. void SLpushback(SL* ps, SLdatatype x);
13. //在指定位置之前插入数据
14. void SLInsert(SL* ps, int pos, SLdatatype x);
15. //尾删
16. void SLpopback(SL* ps);
17. //头删
18. void SLpopfront(SL* ps);
19. //删除指定位置的数据
20. void SLErase(SL* ps, int pos);
21. //查找
22. int SLFind(SL* ps, SLdatatype x);

复制代码

1.3.顺序表的实现:

点击查看代码

1. //初始化
2. void InitSL(SL* ps) {
3.         ps->data = NULL;
4.         ps->capacity = ps->size = 0;
5. }
6. //销毁
7. void DestroySL(SL* ps) {
8.         if (ps->data) {
9.                 free(ps->data);
10.         }
11.         ps->data = NULL;
12.         ps->capacity = ps->size = 0;
13. }
14. //打印顺表表中的元素
15. void SLprint(SL s) {
16.         for (int i = 0; i < s.size; i++) {
17.                 printf("%d", s.data[i]);
18.         }
19.         printf("\n");
20. }
21. //申请空间
22. void SLbuy(SL* ps) {
23.     //如果不这样capacity = 0 时，capacity就永远为0
24.         int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
25.     //这里是relloc(扩容)，如果是malloc就是重新开辟了一块空间，那么原来的数据就丢失了
26.         SLdatatype* tmp = (SLdatatype*)realloc(ps->data, newcapacity * sizeof(SLdatatype));
27.         if (tmp == NULL) {
28.                 perror("SLpushback():realloc Fail");
29.                 exit(1);
30.         }
31.     //这里申请完空间后注意重新赋值capacity
32.         ps->capacity = newcapacity;
33.         ps->data = tmp;
34. }
35. //尾插
36. void SLpushback(SL* ps,SLdatatype x) {
37.         assert(ps);
38.         if (ps->capacity == ps->size) {
39.                 SLbuy(ps);
40.         }
41.     //push完size++
42.         ps->data[ps->size++] = x;
43. }
44. //头插
45. void SLpushfront(SL* ps, SLdatatype x) {
46.         assert(ps);
47.         if (ps->capacity == ps->size) {
48.                 SLbuy(ps);
49.         }
50.         for (int i = ps->size; i > 0; i--) {
51.                 ps->data[i] = ps->data[i - 1];
52.         }
53.     //push完size++
54.         ps->data[0] = x;
55.         ps->size++;
56. }
57. //任意位置插入
58. void SLInsert(SL* ps, int pos, SLdatatype x) {
59.         assert(ps);
60.     //防止越界的问题
61.         assert(pos >= 0 && pos <= ps->size);
62.         if (ps->capacity == ps->size) {
63.                 SLbuy(ps);
64.         }
65.         for (int i = ps->size; i > pos; i--) {
66.                 ps->data[i] = ps->data[i - 1];
67.         }
68.         ps->data[pos] = x;
69.         ps->size++;
70. }
71. //尾删
72. void SLpopback(SL* ps) {
73.         assert(ps);
74.         assert(ps->size);
75.     //删完后size--
76.         --(ps->size);
77. }
78. //头删
79. void SLpopfront(SL* ps) {
80.         assert(ps);
81.         assert(ps->size);
82.         for (int i = 0; i < ps->size - 1; i++) {
83.                 ps->data[i] = ps->data[i + 1];
84.         }
85.         --(ps->size);
86. }
87. //任意位置删
88. void SLErase(SL* ps, int pos) {
89.         assert(ps);
90.         assert(pos >= 0 && pos < ps->size);
91.         for (int i = pos; i<ps->size-1; i++) {
92.                 ps->data[i] = ps->data[i + 1];
93.         }
94.         ps->size--;
95. }
96. int SLFind(SL* ps, SLdatatype x) {
97.         assert(ps);
98.         for (int i = 0; i < ps->size; i++) {
99.                 if (ps->data[i] == x) {
100.                         return i;
101.                         break;
102.                 }
103.         }
104.     //只要返回无效的下标就行
105.         return -1;
106. }

复制代码

2.链表

逻辑结构线性，物理结构离散
逻辑结构:数据元素之间通过指针建立"一对一"的先后顺序，逻辑上呈线性。
物理结构:节点的内存地址并不连续，不能连续访问
2.1.链表的结构:

点击查看代码

1. typedef int SlDatatype;
2. typedef struct Slistnode {
3.         SlDatatype data;
4.         struct Slistnode* next;
5. }Slnode;

复制代码

2.2.链表的接口:

点击查看代码

1. //链表的申请空间
2. Slnode* SlistBuy(SlDatatype x);
3. //链表的打印
4. void SlistPrint(Slnode* phead);
5. //链表的尾插
6. void SlistPushback(Slnode** phead, SlDatatype data);
7. //链表的头插
8. void SlistPushhead(Slnode** pphead, SlDatatype data);
9. //链表的尾删
10. void Slistdeleteback(Slnode** pphead);
11. //链表的头删
12. void Slistdeletehead(Slnode** pphead);
13. //链表的查找
14. Slnode* SlistFind(Slnode** pphead, SlDatatype x);
15. //链表指定位置之前插入节点
16. void Slistinert(Slnode** pphead, Slnode* pos, SlDatatype x);
17. //链表指定位置之后插入节点
18. void Slistinertback(Slnode* pos, SlDatatype x);
19. //链表指定位置删除节点
20. void SlistErase(Slnode** pphead, Slnode* pos);
21. //链表指定位置之后删除节点
22. void SlistsEraseBack(Slnode* pos);

复制代码

2.3.链表的实现:

点击查看代码

1. //申请空间
2. Slnode* SlistBuy(SlDatatype x) {
3.         Slnode* newnode = (Slnode*)malloc(sizeof(Slnode));
4.         if (newnode == NULL) {
5.                 perror("malloc fail");
6.                 exit(1);
7.         }
8.         newnode->data = x;
9.         newnode->next = NULL;
10.         return newnode;
11. }
12. //链表的打印
13. void SlistPrint(Slnode* phead) {
14.         Slnode* tmp = phead;
15.         while (tmp) {
16.                 printf("%d->", tmp->data);
17.                 tmp=tmp->next;
18.         }
19.         printf("NULL\n");
21. }
22. //链表的尾插->传二级指针，因为只要涉及改变参数的都要地址拷贝
23. void SlistPushback(Slnode** pphead, SlDatatype data) {
24.         //寻找尾部
25.         assert(pphead);
26.         Slnode* tmp = *pphead;
27.         Slnode*newnode = SlistBuy(data);
28.         if (tmp== NULL) {
29.                 *pphead = newnode;
30.         }
31.         else {
32.                 while (tmp->next) {
33.                         tmp=tmp->next;
34.                 }
35.                 tmp->next = newnode;
36.                 newnode->data = data;
37.                 newnode->next = NULL;
38.         }
39. }
40. //链表的头插
41. void SlistPushhead(Slnode** pphead, SlDatatype data) {
42.         assert(pphead);
43.         Slnode* tmp = *pphead;
44.         Slnode* newnode = SlistBuy(data);
45.         if (tmp == NULL) {
46.                 *pphead= newnode;
47.         }
48.         else {
49.                 *pphead = newnode;
50.                 newnode->data = data;
51.                 newnode->next = tmp;
52.         }
53. }
54. //链表的尾删
55. void Slistdeleteback(Slnode** pphead) {
56.         assert(pphead && *pphead);
57.         Slnode* tmp = *pphead;
58.         Slnode* prev = *pphead;
59.         if (tmp -> next ==NULL) {
60.                 free(*pphead);
61.                 *pphead = NULL;
62.         }
63.         else {
64.                 while (tmp->next) {
65.                         prev = tmp;
66.                         tmp = tmp->next;
67.                 }
68.         }
69.         free(tmp);
70.         tmp = NULL;
71.         prev->next = NULL;
72. }
73. void Slistdeletehead(Slnode** pphead) {
74.         assert(pphead && *pphead);
75.         Slnode* cmp = *pphead;
76.         *pphead = cmp->next;
77.         free(cmp);
78.         cmp = NULL;
79. }
80. void Slistinert(Slnode** pphead, Slnode* pos, SlDatatype x) {
81.         assert(pphead&&pos&&*pphead);
82.         Slnode* newnode = SlistBuy(x);
83.         Slnode* prev = *pphead;
84.         Slnode* pur = *pphead;
85.         if (pos == *pphead) {
86.                 SlistPushhead(pphead, x);
87.         }
88.         else {
89.                 while (pur != pos) {
90.                         prev = pur;
91.                         pur = pur->next;
92.                 }
93.                 prev->next = newnode;
94.                 newnode->next = pur;
95.         }
96. }
97. Slnode* SlistFind(Slnode** pphead, SlDatatype x) {
98.         assert(pphead && *pphead);
99.         int Flag = 0;
100.         Slnode* tmp = *pphead;
101.         while (tmp) {
102.                 if (tmp->data == x) {
103.                         Flag = 1;
104.                         return tmp;
105.                 }
106.                 tmp = tmp->next;
107.         }
108.         if (Flag == 0) {
109.                 return NULL;
110.         }
111. }
112. void Slistinertback(Slnode* pos, SlDatatype x) {
113.         assert(pos);
114.         Slnode* newnode = SlistBuy(x);
115.         newnode->next = pos->next;
116.         pos->next = newnode;
117. }
118. void SlistErase(Slnode** pphead, Slnode* pos) {
119.         assert(pphead && pos);
120.         Slnode* prev = *pphead;
121.         Slnode* pur = *pphead;
122.         if (pos == *pphead) {
123.                 Slnode* toDel = *pphead;
124.                 *pphead = toDel->next;
125.                 free(toDel);
126.                 return;
127.         }
129.         while (pur != pos) {
130.                 prev = pur;
131.                 pur = pur->next;
132.         }
133.         prev->next = pur->next;
134.         free(pur);
135.         pur = NULL;
136. }
137. void SlistsEraseBack(Slnode* pos) {
138.         assert(pos&&pos->next);
139.         Slnode* tmp = pos->next;
140.         pos->next = tmp->next;
141.         free(tmp);
142.         tmp = NULL;
143. }

复制代码

简单总结一下链表和顺序表的不同点:

缓存:由于CPU的运行速率超快，与内存不同频，需要把内存中的内容先转到寄存器中，而寄存器由于空间有限，所以要先转到缓存器中，然后等寄存器运行结束后，再将缓存器中的内容转到寄存器中。(简单的理解)
顺序表的缓存利用率高:数组由于空间连续，缓存器一次取顺序表的内容就可以一大片一大片的取，缓存命中率就高，而链表由于空间不一定连续，所以就只能一次一次的取，效率就慢，缓存命中率就低。
3.栈

栈是一种后进先出的线性表，仅允许在栈顶进行插入和删除
3.1.栈的实现选择:如果是用链表实现，我们就需要频繁的找尾，而每次找尾的时间复杂度为O(N)，并且再删除尾部的时候还要保存上一节点，操作繁琐。所以我们选择了更易操作的数组实现。

3.2.栈的结构:

点击查看代码

1. typedef int STdatatype;
2. typedef struct Stack {
3.         STdatatype* a;
4.         int top;
5.         int capacity;
6. }ST;

复制代码

3.3.栈的接口:

点击查看代码

1. //栈的初始化
2. void STinit(ST* pst);
3. //栈的销毁
4. void STdestroy(ST* pst);
5. //入栈
6. void STpush(ST* pst,STdatatype x);
7. //出栈
8. void STpop(ST* pst);
9. //取栈顶数据
10. STdatatype STtop(ST* pst);
11. //判空
12. int STempty(ST* pst);
13. //获取数据个数
14. int STsize(ST* pst);

复制代码

3.4.栈的实现:

点击查看代码

1. void STinit(ST* pst) {
2.         pst->a = NULL;
3.         pst->capacity = pst->top = 0;
4. }
5. void STdestroy(ST* pst) {
6.         assert(pst);
7.         free(pst->a);
8.         pst->a = NULL;
9.         pst->capacity = pst->top = 0;
10. }
11. void STpush(ST* pst,STdatatype x) {
12.         assert(pst);
13.         if (pst->capacity == pst->top) {
14.                 int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
15.                 STdatatype* tmp = (STdatatype*)realloc(pst->a,newcapacity*sizeof(STdatatype));
16.                 if (tmp == NULL) {
17.                         perror("STPush():realloc():Fail");
18.                         return;
19.                 }
20.                 pst->capacity = newcapacity;
21.                 pst->a = tmp;
22.         }
23.         pst->a[pst->top++] = x;
24. }
25. void STpop(ST* pst) {
26.         assert(pst);
27.         assert(pst->top);
28.         pst->top--;
29. }
30. STdatatype STtop(ST* pst) {
31.         assert(pst);
32.         assert(pst->top);
33.         return pst->a[pst->top - 1];
34. }
35. int STempty(ST* pst) {
36.         assert(pst);
37.         return pst->top == 0;
38. }
39. int STsize(ST* pst) {
40.         assert(pst);
41.         int size = pst->top;
42.         return size;
43. }

复制代码

利用栈可以解决经典算法题(https://leetcode.cn/problems/valid-parentheses/)

思路:
1.若遇到左括号就入栈
2.若遇到右括号就尝试与栈顶的左括号匹配
代码实现:
点击查看代码

1. bool isValid(char* s) {
2.     ST st;
3.     STinit(&st);
4.     //遍历字符串
5.     while(*s){
6.         //如果是左括号就入栈
7.         if(*s == '(' || *s == '[' || *s == '{'){
8.             STpush(&st,*s);
9.         }
10.         //如果是右括号就尝试与左括号匹配
11.         else{
12.             if(STempty(&st)){
13.                 STdestroy(&st);
14.                 return false;
15.             }
16.             char top = STtop(&st);
17.             STpop(&st);
18.             if((top == '(' && *s != ')') ||
19.             (top == '[' && *s != ']') ||
20.             (top == '{' && *s != '}')){
21.                 STdestroy(&st);
22.                 return false;
23.             }
24.         }
25.         ++s;
26.     }
27.     bool ret = STempty(&st);
28.     STdestroy(&st);
29.     return ret;   
30. }

复制代码

4.队列

队列是一种先进先出的线性表，在队头删除，在队尾插入
4.1.队列的应用:医院抽号机，还有社交平台上的好友推荐

4.2.队列的实现选择:如果用数组实现，每次删除的是首元素，这样首元素后面的元素就得向前移动，时间复杂度为O(N)，所以我们用链表更易实现

4.3.队列的结构:特殊点:额外用一个结构体封装了它的头节点，尾节点，以及大小，这样传参数的时候就能只传一个参数了

点击查看代码

1. typedef int Qdatatype;
2. typedef struct QueueNode {
3.         struct QueueNode* next;
4.         Qdatatype val;
5. }QNode;
7. typedef struct Queue {
8.         QNode* phead;
9.         QNode* ptail;
10.         int size;
11. }Queue;

复制代码

4.4.队列的接口:

点击查看代码

1. //队列的初始化
2. void QueueInit(Queue* pq);
3. //队列的销毁
4. void QueueDestroy(Queue* pq);
5. //队头数据的删除
6. void QueuePop(Queue* pq);
7. //队尾插入数据
8. void QueuePush(Queue* pq, Qdatatype x);
9. //获取队头的数据
10. Qdatatype QueueFront(Queue* pq);
11. //获取队尾的数据
12. Qdatatype QueueBack(Queue* pq);
13. //队列的长度
14. int QueueSize(Queue* pq);
15. //队列的判空
16. bool QueueEmpty(Queue* pq);

复制代码

4.5.队列的实现:

点击查看代码

1. void STinit(ST* pst) {
2.         pst->a = NULL;
3.         pst->capacity = pst->top = 0;
4. }
5. void STdestroy(ST* pst) {
6.         assert(pst);
7.         free(pst->a);
8.         pst->a = NULL;
9.         pst->capacity = pst->top = 0;
10. }
11. void STpush(ST* pst,STdatatype x) {
12.         assert(pst);
13.         if (pst->capacity == pst->top) {
14.                 int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
15.                 STdatatype* tmp = (STdatatype*)realloc(pst->a,newcapacity*sizeof(STdatatype));
16.                 if (tmp == NULL) {
17.                         perror("STPush():realloc():Fail");
18.                         return;
19.                 }
20.                 pst->capacity = newcapacity;
21.                 pst->a = tmp;
22.         }
23.         pst->a[pst->top++] = x;
24. }
25. void STpop(ST* pst) {
26.         assert(pst);
27.         assert(pst->top);
28.         pst->top--;
29. }
30. STdatatype STtop(ST* pst) {
31.         assert(pst);
32.         assert(pst->top);
33.         return pst->a[pst->top - 1];
34. }
35. int STempty(ST* pst) {
36.         assert(pst);
37.         return pst->top == 0;
38. }
39. int STsize(ST* pst) {
40.         assert(pst);
41.         int size = pst->top;
42.         return size;
43. }

复制代码

学了队列可以尝试一下这道题(https://leetcode.cn/problems/design-circular-queue/description/)

总结一下栈和队列的区别

栈和队列的核心区别就是:一个后进先出，一个先进先出
用两个队列实现栈(https://leetcode.cn/problems/implement-stack-using-queues/)
用两个栈实现队列(https://leetcode.cn/problems/implement-queue-using-stacks/)
思路如下:

5.堆


特殊的完全二叉树,分为大堆和小堆
大堆:父节点>=子节点
小堆:父节点a = NULL;        php->capacity = php->size = 0;}void HeapDestroy(Heap* php) {        assert(php);        php->a = NULL;        php->capacity = php->size = 0;}void Swap(Hpdatatype* hp1, Hpdatatype* hp2) {        assert(hp1 && hp2);        Hpdatatype tmp = *hp1;        *hp1 = *hp2;        *hp2 = tmp;}void HeapPush(Heap* php, Hpdatatype x) {        //实现小堆        int child = php->size;        int parent = (child - 1) / 2;        //判断空间够不够        if (php->capacity == php->size) {                int newcapacity = php->capacity == 0 ? 4 : 2 * (php->capacity);                Hpdatatype* tmp = (Hpdatatype*)realloc(php->a,newcapacity * sizeof(Hpdatatype));                if (tmp == NULL) {                        perror("HeapPush():realloc():fail");                        return;                }                php->capacity = newcapacity;//变化过后capacity没有改变                php->a = tmp;        }        php->a[child] = x;        php->size++;        //当child = 0 的时候停止        AdjustUp(php->a, child);}void HeapPop(Heap* php) {        //每次pop的意义是把次小的数推上堆顶        assert(php);        assert(php->size);        //首先先将堆顶的数据与堆尾的数据交换        Swap(&php->a[0], &php->a[php->size - 1]);        --php->size;        //再使用向下查找算法        AdjustDown(php->a, php->size, 0);}Hpdatatype HeapTop(Heap* php) {        assert(php);        assert(php->size);        return php->a[0];}bool HeapEmpty(Heap* php) {        assert(php);        return php->size == 0;}void AdjustUp(Hpdatatype* a, int child){        //向上和向下调整法的时间复杂度都为O(N)        int parent = (child - 1) / 2;        while (child > 0) {                //如果不满足就重复交换child 和 parent 的值                if (a[child] < a[parent]) {                        Swap(&a[child], &a[parent]);                        child = parent;                        parent = (child - 1) / 2;                }                //当child > parent 的时候停止                else {                        break;                }        }}void AdjustDown(Hpdatatype * a, int size, int parent) {        int lesschild = 2 * parent + 1;        //结束条件是到达叶子        while (lesschild < size) {                //假设法找到字节点中较小的那个                if (lesschild + 1 a[lesschild + 1]) {                        lesschild++;                }                //将较小的子节点与父节点相比较                if (a[lesschild] < a[parent]) {                        Swap(&a[lesschild], &a[parent]);                        parent = lesschild;                        lesschild = 2 * parent + 1;                }                else {                        break;                }        }}[/code]5.5.堆排序:

点击查看代码

1. typedef int Hpdatatype;
3. //堆(完全二叉树)的底层还是一个数组
4. typedef struct Heap {
5.         Hpdatatype* a;
6.         int size;
7.         int capacity;
8. }Heap;

复制代码

三、结语

数据结构是计算机学科的基石，掌握顺序表、链表、栈、队列、堆的核心特性和实现，是后续学习树、图、排序算法的基础。建议结合LeetCode算法题反复练习，将理论转化为实战能力。

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

谢谢分享，辛苦了

这个好，看起来很实用

感谢分享

这个好，看起来很实用

懂技术并乐意极积无私分享的人越来越少。珍惜