C语言之数据结构与算法

一、数据结构与算法：线性表

1、顺序表

实现代码：

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef int E;  //定义顺序表存储的数据为int
6. struct List
7. {
8.     E *array;    //实现顺序表的底层数组
9.     int capacity;   //表示底层数组的容量
10.     int size;   //已存多少数据
11. };
13. //插入元素
14. _Bool insertList(struct List *list, E element, int index){
15.     if (index < 1 || index > list->size + 1) return 0;  //index可能非法
16.     if(list->size == list->capacity){   //判断顺序表是否满了，若满，则扩容。
17.         int newCapacity = list->capacity + (list->capacity >> 1);   //>>1 相当于/2
18.         E * newList = realloc(list->array, newCapacity*sizeof(E));
19.         if(newList == NULL) return 0;
20.         list->array = newList;
21.         list->capacity = newCapacity;
22.     }
23.     for (int i = list->size; i>=index; --i){
24.         list->array[i] = list->array[i-1];
25.     }
26.     list->array[index - 1] = element;
27.     list->size++;
28.     return 1;
29. }
31. //删除元素
32. _Bool deleteList(struct List *list,int index){
33.     if(index < 1 || index > list->size) return 0;
35.     for(int i = index - 1; i < list->size - 1; ++i){
36.         list->array[i] = list->array[i+1];
37.     }
39.     list->size--;
41. }
43. //活得顺序表大小
44. int sizeList(struct List *list){
45.     return list->size;
46. }
48. //获得元素
49. E * getList(struct List *list, int index){
50.     if(index < 1 || index > list->size) return NULL;
51.     return &list->array[index-1];
52. }
54. //查找元素
55. int findList(struct List *list,E element){
56.     for(int i = 0; i < list->size; i++){
57.         if(list->array[i] == element) return i + 1;
58.     }
59.     return -1;
60. }
62. /*
63. **
64. **
65. */
66. _Bool initList(struct List *list ){
67.     list->array = malloc(sizeof(E)*10); //malloc开辟的内存在堆区，函数生命周期结束后还存在（需要手动释放或程序结束后由系统释放）。
68.     if (list->array == NULL) return 0;  //若申请内存空间失败，则返回0.
69.     list->capacity = 10;
70.     list->size = 0;
71.     return 1;
72. }
74. void printList(struct List *list){
75.     for(int i = 0; i<list->size; ++i){
76.         printf("%d ", list->array[i]);
77.     }
78.     printf("\n");
79. }
81. int main(int argc,int* argv)
82. {
83.     struct List * list = malloc(sizeof(struct List *));
84.     /*结构体指针初始化，首先不能 “= NULL”，因为指针指向一个安全的区域，不能解析。
85.     **也不能，不初始化，因为指针可能指向未知地址，对其操作造成的后果是未知的，
86.     **初始化方式有：一、在堆区开辟一个空间；二、先定义一个结构体，用指针指向他；
87.     */
88.     if(initList(list)){
89.         for(int i = 0; i<10; ++i){
90.             insertList(list,i*10,i+1);
91.         }
92.         deleteList(list,2);
93.         printList(list);
94.         printf("%d \n",*getList(list,2));
95.         printf("%d",findList(list,30));
96.     }
97.     else{
98.         printf("shibai");
99.     }
100.     free(list);
101. }

复制代码

链表表是一种顺序访问的存储结构。
3、双向链表

4、循环链表w

5、堆栈（Stack）

先进后出
6、队列（Queue）

先进先出
实战1、反转链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解法一

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef int E;  //定义顺序表存储的数据为int
6. struct ListNode{
7.     E element;
8.     struct ListNode *next;
9. };
11. typedef struct ListNode* Node;
13. void initList(Node node){
14.     node->next = NULL;
16. }
18. _Bool insertList(Node head, E element, int index){
19.     if(index < 0) return 0;
20.     while(--index){
21.         head = head->next;
22.         if(head == NULL) return 0;
23.     }
24.     Node node = malloc(sizeof(struct ListNode));
25.     if(node == NULL) return 0;
26.     node->element = element;
27.     node->next = head->next;
28.     head->next = node;
29.     return 1;
30. }
33. _Bool deleteList(Node head, int index){
34.     if(index < 1) return 0;
35.     while(--index){
36.         head = head->next;
37.         if(head == NULL) return 0;
38.     }
39.     if(head->next == NULL) return 0;
40.     Node node = head->next;
41.     head->next = head->next->next;
42.     free(node);
43.     return 1;
44. }
46. //获得元素；
47. E *getList(Node head, int index){
48.     if(index < 1) return 0;
49.     if (head->next == NULL) return NULL;    //若为空表，则返回为空；
50.     do{
51.         head = head->next;
52.         if(head == NULL) return NULL;
53.     }while(--index);
54.     return &head->element;
55. }
57. //寻找元素下标
58. int findList(Node head, E element){
59.     int i = 1;
60.     if(head->next == NULL) return -1;   //判断是否为空表
61.     do{
62.         head = head->next;
63.         if(head->element == element) return i;
64.         i++;
65.     }while(head->next);
66.     return -1;
67. }
69. int sizeList(Node head){
70.     int i = 0;
71.     while(head->next){
72.         i++;
73.         head = head->next;
74.     }
75.     return i;
76. }
78. //函数都是值传递，传值，值不变；传指针，指针不变；传指针，值会变
79. //对head->element或者head->next操作会改变值
80. void printfList(Node head){
81.     while(head->next){
82.         head = head->next;
83.         printf("%d ",head->element);
84.     }
85.     printf("\n");
86. }
88. int main()
89. {
90.     Node p1;
91.     struct ListNode head;
92.     initList(&head);
93.     for(int i = 0; i < 3; ++i){
94.         insertList(&head,i*10, i+1);
95.     }
96.     printfList(&head);
97.     printf("%d",sizeList(&head));
98.    
99. }

复制代码

解法二:递归

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef int E;  //定义顺序表存储的数据为int
6. struct ListNode{
7.     int val;
8.     struct ListNode *next;
9. };
11. struct ListNode* reverseList(struct ListNode* head)
12. {
13.     struct ListNode *tmp,*newHead = NULL;
14.     while (head)
15.     {
16.         //假设前面已被反转。
17.         tmp = head->next;        //保存第二个节点，用于当作下一个节点的头结点。
18.         head->next = newHead;        //指向前节点
19.         newHead = head;        //更新前节点
20.         head = tmp;        //新链表
21.     }
22.     return newHead;
23. }

复制代码

实战2、匹配字符串

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
  
• 左括号必须以正确的顺序闭合。
  
• 每个右括号都有一个对应的相同类型的左括号。
  

方法：栈的应用

方法1：自己的

1. #include <stdio.h>
2. #include <stdlib.h>
7. typedef int E;  //定义顺序表存储的数据为int
9. struct ListNode{
10.     int val;
11.     struct ListNode *next;
12. };
14. struct ListNode* reverseList(struct ListNode* head) {
15.     if (head == NULL || head->next == NULL) {
16.         return head;
17.     }
18.     struct ListNode* newHead = reverseList(head->next);
19.     head->next->next = head;
20.     head->next = NULL;
21.     return newHead;
22. }

复制代码

方法2：更快

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>>
5. #define true 1
6. #define false 0
8. typedef char E;
10. struct LNode {
11.     E val;
12.     struct LNode *next;
13. };
15. typedef struct LNode* Node;
17. void initStack(Node head){
18.     head->next = NULL;
19. }
21. void printStack(Node head){
22.     printf("| ");
23.     head = head->next;
24.     while (head){
25.         printf("%d ", head->val);
26.         head = head->next;
27.     }
28.     printf("\n");
29. }
31. //入栈
32. _Bool pushStack(Node head, E val){
33.     Node node = malloc(sizeof(struct LNode));
34.     if(node == NULL) return 0;
35.     node->next = head->next;
36.     node->val = val;
37.     head->next = node;
38.     return 1;
39. }
41. //出栈
42. E popStack(Node head){
43.     if(head->next == NULL) return 0;
44.     Node node;
45.     node = head->next;
46.     E val = node->val;
47.     head->next = head->next->next;
48.     free(node);
49.     return val;
50. }
51.    
52. _Bool isValid(char* s) {
53.     struct LNode head;
54.     initStack(&head);
55.     unsigned int len = strlen(s);
56.     if(len % 2 == 1) return false;
57.     pushStack(&head,s[0]);
58.     for(int i = 1; i < len; i++){
59.         E top = popStack(&head);
60.         if(top != 0)pushStack(&head,top);
61.         if(top == '('){
62.             if(s[i] == ')') popStack(&head);
63.             else pushStack(&head,s[i]);
64.         }
65.         else if(top == '['){
66.             if(s[i] == ']') popStack(&head);
67.             else pushStack(&head,s[i]);
68.         }
69.         else if(top == '{'){
70.             if(s[i] == '}') popStack(&head);
71.             else pushStack(&head,s[i]);
72.         }
73.         else  pushStack(&head,s[i]);
74.     }
75.     if(head.next == NULL) return true;
76.     else return false;
77. }
79. int main(){
80.     char *s = "()[]{}";
81.     printf("%d ",isValid(s));
82. }

复制代码

方法三：更快

1. #include <stdlib.h>
2. #include <stdbool.h>
3. #include <string.h>
5. typedef char E;
7. struct LNode {
8.     E element;
9.     struct LNode * next;
10. };
12. typedef struct LNode * Node;
14. void initStack(Node head){
15.     head->next = NULL;
16. }
18. _Bool pushStack(Node head, E element){
19.     Node node = malloc(sizeof(struct LNode));
20.     if(node == NULL) return 0;
21.     node->next = head->next;
22.     node->element = element;
23.     head->next = node;
24.     return 1;
25. }
27. _Bool isEmpty(Node head){
28.     return head->next == NULL;
29. }
31. E popStack(Node head){
32.     Node top = head->next;
33.     head->next = head->next->next;
34.     E e = top->element;
35.     free(top);
36.     return e;
37. }
39. bool isValid(char * s){
40.     unsigned long len = strlen(s);
41.     if(len % 2 == 1) return false;  //如果长度不是偶数，那么一定不能成功匹配
42.     struct LNode head;
43.     initStack(&head);
44.     for (int i = 0; i < len; ++i) {
45.         char c = s[i];
46.         if(c == '(' || c == '[' || c == '{') {
47.             pushStack(&head, c);
48.         }else {
49.             if(isEmpty(&head)) return false;
50.             if(c == ')') {
51.                 if(popStack(&head) != '(') return false;
52.             } else if(c == ']') {
53.                 if(popStack(&head) != '[') return false;
54.             } else {
55.                 if(popStack(&head) != '{') return false;
56.             }
57.         }
58.     }
59.     return isEmpty(&head);
60. }

复制代码

二、数据结构与算法：树

1、树：理论

• 我们一般称位于最上方的结点为树的根结点（Root）；
  
• 每个结点连接的子结点数目（分支的数目），我们称为结点的度（Degree），而各个结点度的最大值称为树的度；
  
• 每个结点延伸下去的下一个结点都可以称为一棵子树（SubTree）；
  
• 每个结点的层次（Level）按照从上往下的顺序，树的根结点为1，每向下一层+1，比如G的层次就是3，整棵树中所有结点的最大层次，就是这颗树的深度（Depth）；
  
• 与当前结点直接向下相连的结点，我们称为子结点（Child）；相反即为父节点；
  
• 如果某个节点没有任何的子结点（结点度为0时）那么我们称这个结点为叶子结点；
  
• 如果两个结点的父结点是同一个，那么称这两个节点为兄弟结点（Sibling）；
  
• 从根结点开始一直到某个结点的整条路径的所有结点，都是这个结点的祖先结点（Ancestor）；
  

2、二叉树的性质

• 性质一： 对于一棵二叉树，第i层的最大结点数量为 个2^i - 1;
  
• 一棵深度为k的二叉树最大结点数量为 n = 2^k*−1，顺便得出，结点的边数为 E = n - 1。
  
• 于任何一棵二叉树，如果其叶子结点个数为 n0，度为2的结点个数为 n2 ，那么两者满足以下公式：n0 = n2+1;
  
• n个结点的完全二叉树深度为 k = log2^n + 1 ;
  
• 
  

3、二叉树遍历：前序、中序、后序遍历

前序遍历结果为：ABDECF；
中序遍历结果为：DBEACF；
后序遍历结果为：DEBFCA；

1. char pairs(char a) {
2.     if (a == '}') return '{';
3.     if (a == ']') return '[';
4.     if (a == ')') return '(';
5.     return 0;
6. }
8. bool isValid(char* s) {
9.     int n = strlen(s);
10.     if (n % 2 == 1) {
11.         return false;
12.     }
13.     int stk[n + 1], top = 0;
14.     for (int i = 0; i < n; i++) {
15.         char ch = pairs(s[i]);
16.         if (ch) {
17.             if (top == 0 || stk[top - 1] != ch) {
18.                 return false;
19.             }
20.             top--;
21.         } else {
22.             stk[top++] = s[i];
23.         }
24.     }
25.     return top == 0;
26. }

复制代码

4、二叉树遍历：层序遍历

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>>
5. typedef char E;
7. struct TreeNode{
8.     E element;
9.     struct TreeNode *left;
10.     struct TreeNode *right;
11. };
13. typedef struct TreeNode* Node;
15. //前序递归，利用函数栈的特性，不断出栈入栈
16. void preOrder(Node root){
17.     if(root == NULL) return;   
18.     printf("%c", root->element);
19.     preOrder(root->left);
20.     preOrder(root->right);
21. }
23. //中序遍历
24. void inOrder(Node root){
25.     if(root == NULL) return;
26.     inOrder(root->left);
27.     printf("%c",root->element);
28.     inOrder(root->right);
29. }
31. //后序遍历
32. void afOrder(Node root){
33.     if(root == NULL) return;
34.     afOrder(root->left);
35.     afOrder(root->right);
36.     printf("%c",root->element);
37. }
39. int main(){
40.     Node a = malloc(sizeof(struct TreeNode));
41.     Node b = malloc(sizeof(struct TreeNode));
42.     Node c = malloc(sizeof(struct TreeNode));
43.     Node d = malloc(sizeof(struct TreeNode));
44.     Node e = malloc(sizeof(struct TreeNode));
45.     Node f = malloc(sizeof(struct TreeNode));
46.     a->element = 'A';
47.     b->element = 'B';
48.     c->element = 'C';
49.     d->element = 'D';
50.     e->element = 'E';
51.     f->element = 'F';
53.     a->left = b;
54.     a->right = c;
55.     b->left = d;
56.     b->right = e;
57.     c->right = f;
58.     c->left = NULL;
59.     d->left = e->right = NULL;
60.     e->left = e->right = NULL;
61.     f->left = f->right = NULL;
63.     afOrder(a);
64. }

复制代码

5、二叉树的线索化(以前序为例)

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
5. typedef char E;
7. typedef struct TreeNode {
8.     E element;    //存放元素
9.     struct TreeNode * left;   //指向左子树的指针
10.     struct TreeNode * right;   //指向右子树的指针
11. } *Node;
13. typedef struct initNode{   //定义队列初始节点
14.     Node element;
15.     struct initNode *next;
16. } *INode;
18. struct Queue{   //队列头尾指针
19.     INode front,rear;
20. };
22. typedef struct Queue* LinkedQueue;
24. _Bool initQueue(LinkedQueue queue){
25.     INode node = malloc(sizeof(struct initNode));
26.     if(node == NULL) return 0;
27.     node->next = NULL;
28.     queue->front = queue->rear = node;
29. }
31. //入队
32. _Bool enQueue(LinkedQueue quene, Node element){
33.     INode node = malloc(sizeof(struct initNode));
34.     if(node == NULL) return 0;
35.     node->next = NULL;
36.     node->element = element;
37.     quene->rear->next = node;
38.     quene->rear = node;
39.     return 1;
40. }
42. // 出队
43. Node deQueue(LinkedQueue queue){
44.     Node val = queue->front->next->element;
45.     INode node;
46.     node = queue->front->next;
47.     queue->front->next = queue->front->next->next;
48.     if(queue->rear == node) queue->rear = queue->front;
49.     free(node);
50.     return val;
51. }
53. _Bool isEmpty(LinkedQueue queue){
54.     return (queue->front == queue->rear);
55. }
57. void levelQueue(Node root){
58.     struct Queue queue;
59.     initQueue(&queue);
60.     enQueue(&queue,root);
61.     while(!isEmpty(&queue)){
62.         Node node = deQueue(&queue);
63.         printf("%c",node->element);
64.         if(node->left) enQueue(&queue,node->left);
65.         if(node->right) enQueue(&queue,node->right);
66.     }
67. }
69. int main(){
70.     Node a = malloc(sizeof(struct TreeNode));
71.     Node b = malloc(sizeof(struct TreeNode));
72.     Node c = malloc(sizeof(struct TreeNode));
73.     Node d = malloc(sizeof(struct TreeNode));
74.     Node e = malloc(sizeof(struct TreeNode));
75.     Node f = malloc(sizeof(struct TreeNode));
76.     a->element = 'A';
77.     b->element = 'B';
78.     c->element = 'C';
79.     d->element = 'D';
80.     e->element = 'E';
81.     f->element = 'F';
83.     a->left = b;
84.     a->right = c;
85.     b->left = d;
86.     b->right = e;
87.     c->right = f;
88.     c->left = NULL;
89.     d->left = e->right = NULL;
90.     e->left = e->right = NULL;
91.     f->left = f->right = NULL;
93.     levelQueue(a);
94. }

复制代码

六、二叉搜索树（二叉查找树）

七、平衡二叉树

三、数据结构与算法：哈希表

1、哈希表

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
5. typedef char E;
7. typedef struct TreeNode {
8.     E element;    //存放元素
9.     struct TreeNode * left;   //指向左子树的指针
10.     struct TreeNode * right;   //指向右子树的指针
11.     char leftFlag,rightFlag     //线索化标志位
12. } *Node;
14. Node pre = NULL;  //这里我们需要一个pre来保存后续结点的指向
15. void treeOrdered(Node root){
16.     if(root == NULL) return;
19.     //线索化规则：结点的左指针，指向其当前遍历顺序的前驱结点；结点的右指针，指向其当前遍历顺序的后继结点。
20.     if(root->left == NULL){ //判断当前节点的左节点是否为空，若为空，则指向上一个节点。
21.         root->leftFlag = 1;
22.         root->left = pre;
24.     }
25.     if(pre && pre->right == NULL){  //判断上一个节点的右节点是否为空，若为空，则指向当前节点
26.         pre->right = root;
27.         pre->rightFlag = 1;
28.     }
30.     pre = root;
31.     if(root->leftFlag == 0) treeOrdered(root->left);    //判断左节点是否是线索化的，若不是，才能继续。
32.     if(root->rightFlag == 0) treeOrdered(root->right);  //判断可略，因为，我们对右节点的线索化，是在后面执行的
33. }
35. void preOrder(Node root){
36.     while (root) {   //到头为止
37.         printf("%c", root->element);   //因为是前序遍历，所以直接按顺序打印就行了
38.         if(root->leftFlag == 0)
39.             root = root->left;   //如果是左孩子，那么就走左边
40.         else
41.             root = root->right;   //如果左边指向是线索，那么就直接走右边。
42.     }
43. }
45. Node createNode(E element){   //单独写了个函数来创建结点
46.     Node node = malloc(sizeof(struct TreeNode));
47.     node->left = node->right = NULL;
48.     node->rightFlag = node->leftFlag = 0;
49.     node->element = element;
50.     return node;
51. }
53. int main() {
54.     Node a = createNode('A');
55.     Node b = createNode('B');
56.     Node c = createNode('C');
57.     Node d = createNode('D');
58.     Node e = createNode('E');
60.     a->left = b;
61.     b->left = d;
62.     a->right = c;
63.     b->right = e;
65.     treeOrdered(a);
66.     preOrder(a);
67. }

复制代码

2、哈希冲突（链地址法）

1. #include<stdio.h>
2. #include<stdlib.h>
4. #define SIZE 9
7. //结构体指针，直接用E->key访问，避免用*E访问
8. typedef struct Element {   //这里用一个Element将值包装一下
9.     int key;    //这里元素设定为int
10. } * E;
12. typedef struct HashTable{   //这里把数组封装为一个哈希表
13.     E * table;
14. } * HashTable;
16. int hash(int key){   //哈希函数
17.     return key % SIZE;
18. }
20. void init(HashTable hashTable){   //初始化函数
21.     hashTable->table = malloc(sizeof(struct Element) * SIZE);
22.     for (int i = 0; i < SIZE; ++i)
23.         hashTable->table[i] = NULL;
24. }
26. void insert(HashTable hashTable, E element){   //插入操作，为了方便就不考虑装满的情况了
27.     int hashCode = hash(element->key);   //首先计算元素的哈希值
28.     hashTable->table[hashCode] = element;   //对号入座
29. }
32. _Bool find(HashTable hashTable, int key){
33.     int hashCode = hash(key);   //首先计算元素的哈希值
34.     if(!hashTable->table[hashCode]) return 0;   //如果为NULL那就说明没有
35.     return hashTable->table[hashCode]->key == key;  //如果有，直接看是不是就完事
36. }
38. E create(int key){    //创建一个新的元素
39.     E e = malloc(sizeof(struct Element));
40.     e->key = key;
41.     return e;
42. }
44. int main() {
45.     struct HashTable hashTable;
46.     init(&hashTable);
47.     insert(&hashTable, create(10));
48.     insert(&hashTable, create(7));
49.     insert(&hashTable, create(13));
50.     insert(&hashTable, create(29));
52.     printf("%d\n", find(&hashTable, 1));
53.     printf("%d\n", find(&hashTable, 13));
54. }

复制代码

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