数据结构

数据结构学习笔记

数据：
信息的载体，能够输入到计算机中，并且能被计算机识别，存储和处理的符号的总称

数据元素：
数据元素是数据的基本单位，称为记录

数据项:
数据元素由多个数据项组成

结构：
逻辑结构：
集合结构：数据元素之间除了属于同一个集合外，没有其他任何关系

线性结构：数据元素之间具有一对一的关系

树形结构：数据元素之间具有一对多的关系

图形结构：数据元素具有多对多的关系

存储结构（物理结构）：
顺序存储结构：数据元素存储在连续分配的地址空间中

链式存储结构：数据元素存储在任意合法的地址空间中，地址空间可以连续也可以不连续

索引存储结构：数据元素在存储时建立附加的索引表

散列（哈希）存储结构：很据key值，和特定的函数计算出数据元素的存储位置
数据的操作：
增、删、改、查

程序 = 数据结构 + 算法

算法：
为了解决特定问题的步骤的描述

算法的特性：
输入、输出、有穷性、确定性、可行性

算法的设计要求：
正确性、可读性、健壮性、时间效率高和存储量低

算法的时间复杂度：
随着输入规模n的增加，算法的执行时间的增长率和算法执行次数的增长率保持一致。
我们称为算法的渐近时间复杂度，简称算法的时间复杂度

大O推导：
1.使用常数1替代表达式中的加法常数项
2.在修改后的表达式中，只保留最高阶次项
3.如果最高阶次项存在且不为1，去掉最高阶次项的系数

冒泡排序：
T(n) = O(n^2)

算法的空间复杂度：

线性表：
表中的数据元素具有线性结构（一对一）

直接前驱：直接相邻的前一个数据元素
直接后继：直接相邻的后一个数据元素

特性：（非空表）
1.a1是表头，没有直接前驱
2.an是表尾，没有直接后继
3.除了表头表尾外的数据元素有且只有一个直接前驱和一个直接后继

顺序表：
线性表的顺序存储结构
list.c：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define SIZE 20
  4 
  5 typedef struct list
  6 {
  7     int data[SIZE];//存数据元素
  8     int last;//表中最后一位有效数据元素的位置（下标）
  9 }list_t;//顺序表的类型
 10 //struct list == list_t  (int)
 11 
 12 //创建
 13 list_t * creat_list()
 14 {
 15     //申请空间
 16     list_t * list = malloc(sizeof(list_t));//    void *   list_t *
 17     if(list == NULL)
 18     {
 19         printf("空间申请失败!\n");
 20         return NULL;
 21     }
 22 
 23     //空表的初始化
 24     list->last = -1;
 25 
 26     //返回堆区申请的空间首地址
 27     return list;
 28 }
 29 
 30 //判满
 31 int isfull(list_t * list)
 32 {
 33     return list->last == (SIZE - 1);
 34 #if 0
 35     if(list->last == (SIZE - 1))
 36     {
 37         return 1;
 38     }
 39     else
 40     {
 41         return 0;
 42     }
 43 #endif
 44 }
 45 
 46 //判空
 47 int isnull(list_t * list)
 48 {
 49     return list->last == -1;
 50 }
 51 
 52 //从头增加
 53 int ins_head_list(list_t * list, int data)
 54 {
 55     //判满
 56     if(isfull(list))
 57     {
 58         printf("表为满，无法执行头增操作!\n");
 59         return -1;
 60     }
 61 
 62     //挪,从最后位置开始挪，将值赋值给后一个
 63     int i;
 64     for(i = list->last; i >= 0; i--)
 65     {
 66         list->data[i+1] = list->data[i];
 67     }
 68 
 69     //存入数据
 70     list->data[0] = data;
 71 
 72     //修改last的值
 73     list->last++;
 74     
 75     return 0;
 76 }
 77 
 78 //指定位置增加数据
 79 int ins_index_list(list_t * list, int data, int index)
 80 {
 81     //判断实施条件
 82     if(isfull(list) || index < 0 || index > list->last+1)//last+1：实现的是尾部增加数据
 83     {
 84         printf("增加数据，指定位置出错!\n");
 85         return -1;
 86     }
 87 
 88     //挪,从最后位置开始挪，到指定位置结束
 89     int i;
 90     for(i = list->last; i >= index; i--)
 91     {
 92         list->data[i+1] = list->data[i];
 93     }
 94 
 95     //存入数据
 96     list->data[index] = data;
 97 
 98     //修改last的值
 99     list->last++;
100 
101     return 0;
102 }
103 //从头删除
104 int del_head_list(list_t * list)
105 {
106     //判空
107     if(isnull(list))
108     {
109         printf("表为空，无法执行头删操作!\n");
110         return -1;
111     }
112 
113     //挪（删除）,从头开始挪，将后面的值给前面
114     int i;
115     for(i = 0; i < list->last; i++)
116     {
117         list->data[i] = list->data[i+1];
118     }
119 
120     //修改last值
121     list->last--;
122 
123     return 0;
124 }
125 
126 //指定位置删除数据
127 int del_index_list(list_t * list, int index)
128 {
129     //判断实施条件
130     if(isnull(list) || index < 0 || index > list->last)
131     {
132         printf("删除数据，指定位置出错!\n");
133         return -1;
134     }
135 
136     //挪（删除数据）
137     int i;
138     for(i = index; i < list->last; i++)
139     {
140         list->data[i] = list->data[i+1]; 
141     }
142 
143     //修改last的值
144     list->last--;
145 
146     return 0;
147 }
148 //打印
149 int print_list(list_t * list)
150 {
151     //判空
152     if(isnull(list))
153     {
154         printf("表为空，无法执行打印操作!\n");
155         return -1;
156     }
157 
158     //打印数据
159     int i;
160     for(i = 0; i <= list->last; i++)
161     {
162         printf("%d ", list->data[i]);
163     }
164     printf("\n");
165 
166     return 0;
167 }
168 
169 //指定位置修改数据
170 int change_list(list_t * list, int data, int index)
171 {
172     //判断实施条件
173     if(isnull(list) || index < 0 || index > list->last)
174     {
175         printf("修改数据，指定位置出错!\n");
176         return -1;
177     }
178 
179     //指定位置修改数据
180     list->data[index] = data;
181 
182     return 0;
183 }
184 
185 //查找数据
186 int locate_list(list_t * list, int data)
187 {
188     //判空
189     if(isnull(list))
190     {
191         printf("表为空，无法执行查找操作!\n");
192         return -1;
193     }
194 
195     //遍历查找，返回下标
196     int i;
197     for(i = 0; i <= list->last; i++)
198     {
199         if(list->data[i] == data)
200         {
201             return i;
202         }
203     }
204 
205     //如果没找到，提示操作者
206     printf("表中没有该数据!\n");
207     return -1;
208 }
209 
210 //清空
211 int clean_list(list_t * list)
212 {
213     list->last = -1;
214     return 0;
215 }
216 
217 //销毁
218 int dis_list(list_t * list)
219 {
220     free(list);
221 
222     return 0;
223 }
224 int main(int argc, const char *argv[])
225 { 
226     list_t * list = creat_list();//调用创建函数
227     if(list == NULL)
228     {
229         printf("creat_list()执行出错!\n");
230         return -1;
231     }
232 
233     int i;
234     for(i = 1; i <= 20; i++)
235     {
236         if(    ins_head_list(list, i*10) == 0)//执行20次从头增加数据函数
237             print_list(list);
238     }
239     //print_list(list);
240 
241     for(i = 1; i <= 10; i++)
242     {
243         del_head_list(list);//执行10次从头删除函数
244     }
245     print_list(list);//打印函数
246 
247     ins_index_list(list, 666, 6);//调用指定位置增加数据函数
248     print_list(list);
249 
250     del_index_list(list, 6);
251     print_list(list);
252 
253     change_list(list, 666, 6);
254     print_list(list);
255 
256     int ret = locate_list(list, 666);
257     printf("ret:%d\n", ret);
258 
259     clean_list(list);
260     print_list(list);
261 
262     dis_list(list);
263     return 0;
264 }

list

创建表、判空、判满、增（头增、指定位置增）、删（头删、指定位置删）、改、查、清空、销毁
list_size.c（指定大小的顺序表）

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 
  5 typedef struct list
  6 {
  7     int * data;//存数据元素
  8     int size;//记录数据元素的个数
  9     int last;//表中最后一位有效数据元素的位置（下标）
 10 }list_t;//顺序表的类型
 11 //struct list == list_t  (int)
 12 
 13 //创建
 14 list_t * creat_list(int size)
 15 {
 16     //申请空间
 17     list_t * list = malloc(sizeof(list_t));//    void *   list_t *
 18     if(list == NULL)
 19     {
 20         printf("空间申请失败!\n");
 21         return NULL;
 22     }
 23     
 24     list->data = malloc(sizeof(int) * size);
 25     if(list->data == NULL)
 26     {
 27         return NULL;
 28     }
 29 
 30     list->size = size;//记录数据元素的个数
 31 
 32     //空表的初始化
 33     list->last = -1;
 34 
 35     //返回堆区申请的空间首地址
 36     return list;
 37 }
 38 
 39 //判满
 40 int isfull(list_t * list)
 41 {
 42     return list->last == (list->size - 1);
 43 #if 0
 44     if(list->last == (list->size - 1))
 45     {
 46         return 1;
 47     }
 48     else
 49     {
 50         return 0;
 51     }
 52 #endif
 53 }
 54 
 55 //判空
 56 int isnull(list_t * list)
 57 {
 58     return list->last == -1;
 59 }
 60 
 61 //从头增加
 62 int ins_head_list(list_t * list, int data)
 63 {
 64     //判满
 65     if(isfull(list))
 66     {
 67         printf("表为满，无法执行头增操作!\n");
 68         return -1;
 69     }
 70 
 71     //挪,从最后位置开始挪，将值赋值给后一个
 72     int i;
 73     for(i = list->last; i >= 0; i--)
 74     {
 75         list->data[i+1] = list->data[i];
 76     }
 77 
 78     //存入数据
 79     list->data[0] = data;
 80 
 81     //修改last的值
 82     list->last++;
 83     
 84     return 0;
 85 }
 86 
 87 //指定位置增加数据
 88 int ins_index_list(list_t * list, int data, int index)
 89 {
 90     //判断实施条件
 91     if(isfull(list) || index < 0 || index > list->last+1)//last+1：实现的是尾部增加数据
 92     {
 93         printf("增加数据，指定位置出错!\n");
 94         return -1;
 95     }
 96 
 97     //挪,从最后位置开始挪，到指定位置结束
 98     int i;
 99     for(i = list->last; i >= index; i--)
100     {
101         list->data[i+1] = list->data[i];
102     }
103 
104     //存入数据
105     list->data[index] = data;
106 
107     //修改last的值
108     list->last++;
109 
110     return 0;
111 }
112 //从头删除
113 int del_head_list(list_t * list)
114 {
115     //判空
116     if(isnull(list))
117     {
118         printf("表为空，无法执行头删操作!\n");
119         return -1;
120     }
121 
122     //挪（删除）,从头开始挪，将后面的值给前面
123     int i;
124     for(i = 0; i < list->last; i++)
125     {
126         list->data[i] = list->data[i+1];
127     }
128 
129     //修改last值
130     list->last--;
131 
132     return 0;
133 }
134 
135 //指定位置删除数据
136 int del_index_list(list_t * list, int index)
137 {
138     //判断实施条件
139     if(isnull(list) || index < 0 || index > list->last)
140     {
141         printf("删除数据，指定位置出错!\n");
142         return -1;
143     }
144 
145     //挪（删除数据）
146     int i;
147     for(i = index; i < list->last; i++)
148     {
149         list->data[i] = list->data[i+1]; 
150     }
151 
152     //修改last的值
153     list->last--;
154 
155     return 0;
156 }
157 //打印
158 int print_list(list_t * list)
159 {
160     //判空
161     if(isnull(list))
162     {
163         printf("表为空，无法执行打印操作!\n");
164         return -1;
165     }
166 
167     //打印数据
168     int i;
169     for(i = 0; i <= list->last; i++)
170     {
171         printf("%d ", list->data[i]);
172     }
173     printf("\n");
174 
175     return 0;
176 }
177 
178 //指定位置修改数据
179 int change_list(list_t * list, int data, int index)
180 {
181     //判断实施条件
182     if(isnull(list) || index < 0 || index > list->last)
183     {
184         printf("修改数据，指定位置出错!\n");
185         return -1;
186     }
187 
188     //指定位置修改数据
189     list->data[index] = data;
190 
191     return 0;
192 }
193 
194 //查找数据
195 int locate_list(list_t * list, int data)
196 {
197     //判空
198     if(isnull(list))
199     {
200         printf("表为空，无法执行查找操作!\n");
201         return -1;
202     }
203 
204     //遍历查找，返回下标
205     int i;
206     for(i = 0; i <= list->last; i++)
207     {
208         if(list->data[i] == data)
209         {
210             return i;
211         }
212     }
213 
214     //如果没找到，提示操作者
215     printf("表中没有该数据!\n");
216     return -1;
217 }
218 
219 //清空
220 int clean_list(list_t * list)
221 {
222     list->last = -1;
223     return 0;
224 }
225 
226 //销毁
227 int dis_list(list_t * list)
228 {
229     free(list->data);
230     free(list);
231 
232     return 0;
233 }
234 
235 int dis_list1(list_t ** list)
236 {
237     free((*list)->data);
238     free(*list);
239     *list = NULL;
240 
241     return 0;
242 }
243 
244 int main(int argc, const char *argv[])
245 { 
246     list_t * list = creat_list(20);//调用创建函数
247     if(list == NULL)
248     {
249         printf("creat_list()执行出错!\n");
250         return -1;
251     }
252 
253     int i;
254     for(i = 1; i <= 20; i++)
255     {
256         if(    ins_head_list(list, i*10) == 0)//执行20次从头增加数据函数
257             print_list(list);
258     }
259     //print_list(list);
260 
261     for(i = 1; i <= 10; i++)
262     {
263         del_head_list(list);//执行10次从头删除函数
264     }
265     print_list(list);//打印函数
266 
267     ins_index_list(list, 666, 6);//调用指定位置增加数据函数
268     print_list(list);
269 
270     del_index_list(list, 6);
271     print_list(list);
272 
273     change_list(list, 666, 6);
274     print_list(list);
275 
276     int ret = locate_list(list, 666);
277     printf("ret:%d\n", ret);
278 
279     clean_list(list);
280     print_list(list);
281 
282 //  dis_list(list);
283     dis_list1(&list);
284     printf("%p\n", list);
285     return 0;
286 }

list_size

链表：
线性表的链式存储结构
link.c（单向链表）

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct node
  5 {
  6     int data;//数据域
  7     struct node * next;//指针域，存放下一个结点的地址
  8 }link_t;//单链中结点的类型
  9 
 10 //创建
 11 link_t * creat_link()
 12 {
 13     //申请头结点的空间
 14      link_t * head = malloc(sizeof(link_t));
 15      if(head == NULL)
 16      {
 17          printf("头结点申请失败!\n");
 18         return NULL;
 19      }
 20 
 21      head->next = NULL;//头结点中的指针域初始化
 22 
 23      return head;//返回申请的头结点的地址
 24 }
 25 
 26 //判空
 27 int isnull(link_t * head)
 28 {
 29     return head->next == head;
 30 }
 31 
 32 //头增
 33 int ins_head_link(link_t * head, int data)
 34 {
 35     //申请新结点的空间
 36     link_t * newnode = malloc(sizeof(link_t));
 37     
 38     //存入数据
 39     newnode->data = data;
 40 
 41     //将新结点连入到链表中
 42     newnode->next = head->next;//先修改新结点的后继
 43     head->next = newnode;//修改头结点的后继
 44     
 45     return 0;
 46 }
 47 
 48 //指定位置（相对位置）增加数据
 49 int ins_index_link(link_t * head, int data, int index)
 50 {
 51     if(index < 0)
 52     {
 53         printf("增加数据，指定位置过小!\n");
 54         return -1;
 55     }
 56 
 57     //偏移到指定位置到前一个结点处
 58     while(index--)
 59     {
 60         head = head->next;
 61         if(head == NULL) 
 62         {
 63             printf("增加数据，指定位置过大!\n");
 64             return -1;
 65         }
 66     }
 67 
 68     ins_head_link(head,data);//直接调用头增函数
 69 
 70     return 0;
 71 }
 72 
 73 //头删
 74 int del_head_link(link_t * head)
 75 {
 76     //判空
 77     if(isnull(head))
 78     {
 79         printf("表为空，无法执行删除操作!\n");
 80         return -1;
 81     }
 82 
 83     //备份要删除的结点
 84     link_t * temp = head->next;
 85 
 86     //删除
 87     head->next = temp->next;//head->next = head->next->next;
 88 
 89     //释放
 90     free(temp);
 91 
 92     return 0;
 93 }
 94 
 95 //指定位置删除
 96 int del_index_link(link_t * head, int index)
 97 {
 98     //判断实施条件
 99     if(isnull(head) || index < 0)
100     {
101         printf("删除数据，指定位置过小!\n");
102         return -1;
103     }
104     
105     //偏移
106     while(index--)
107     {
108         head = head->next;
109         if(head->next == NULL)//判断偏移后结点的下一个结点是否存在
110         {
111             printf("删除数据，指定位置过大!\n");
112             return -1;
113         }
114     }
115 
116     //删除数据
117     del_head_link(head);
118 
119     return 0;
120 }
121 //打印
122 int print_link(link_t * head)
123 {
124     if(isnull(head))//判空
125     {
126         printf("表为空，无法执行打印操作!\n");
127         return -1;
128     }
129 
130     head = head->next;//跳过头结点
131     while(head != NULL)//判断不为空就打印数据域里面的值
132     {
133         printf("%d ", head->data);
134         head = head->next;
135     }
136     printf("\n");
137 
138     return 0;
139 }
140 
141 //指定位置修改数据
142 int change_link(link_t * head, int data, int index)
143 {
144     //指定位置过小
145     if(isnull(head) || index < 0)
146     {
147         printf("修改数据，指定位置过小!\n");
148         return -1;
149     }
150 
151     //偏移
152     while(index--)
153     {
154         head = head->next;
155         if(head->next == NULL)
156         {
157             printf("修改数据，指定位置过大!\n");
158             return -1;
159         }
160     }
161 
162     //修改
163     head->next->data = data;
164 
165     return 0;
166 }
167 
168 //查找数据
169 link_t * locate_link(link_t * head, int data)
170 {
171     //判空
172     if(isnull(head))
173     {
174         printf("表为空，无法执行查找操作!\n");
175         return NULL;
176     }
177 
178     //遍历查找,返回前一个结点的地址，方便进行对结点数据操作
179     while(head->next != NULL)
180     {
181         if(head->next->data == data)
182         {
183             return head;
184         }
185         head = head->next;//量的改变
186     }
187 
188     //没有找到
189     printf("表中没有该数据!\n");
190 
191     return NULL;
192 }
193 
194 //清空
195 int clean_link(link_t * head)
196 {
197     while(!isnull(head))
198     {
199         del_head_link(head);
200     }
201     return 0;
202 }
203 
204 //销毁
205 int dis_link(link_t * head)
206 {
207     clean_link(head);
208     free(head);
209     return 0;
210 }
211 
212 //逆向输出（临时链表）
213 int reprint_link(link_t * head)
214 {
215     //创建临时链表
216     link_t * temp = creat_link();
217 
218     //判断原链表数据结点不为空，执行临时链表从头增加数据
219     while(head->next != NULL)
220     {
221         ins_head_link(temp, head->next->data);
222         head = head->next;
223     }
224 
225     //打印临时链表
226     print_link(temp);
227 
228     //销毁临时链表
229     dis_link(temp);
230 
231     return 0;
232 }
233 
234 //递归实现逆向输出
235 void reprint_link1(link_t * head)
236 {
237     //递归结束条件
238     if(head->next == NULL)
239     {
240         return ;
241     }
242     //自己调用自己
243     reprint_link1(head->next);
244 
245     //打印
246     printf("%d ",head->next->data);
247 }
248 
249 int main(int argc, const char *argv[])
250 {
251     link_t * link = creat_link();
252     if(link == NULL)
253     {
254         return -1;
255     }
256 
257     int i;
258     for(i = 1; i <= 20; i++)
259     {
260         ins_head_link(link, i*10);
261     }
262     print_link(link);
263 
264     for(i = 1; i <= 10; i++)
265     {
266         del_head_link(link);
267     }
268     print_link(link);
269 
270     ins_index_link(link, 666, 6);
271     print_link(link);
272 
273     del_index_link(link, 6);
274     print_link(link);
275     
276     change_link(link, 666, 6);
277     print_link(link);
278 
279     link_t * ret = locate_link(link, 666);
280     if(ret != NULL)
281     {
282         del_head_link(ret);
283     }
284     print_link(link);
285 
286     printf("逆向输出1：");
287     reprint_link(link);
288 
289     printf("逆向输出2：");
290     reprint_link1(link);
291     printf("\n");
292 
293 
294     clean_link(link);
295     print_link(link);
296 
297     dis_link(link);
298 
299     return 0;
300 }

link

dblink.c(双向链表)

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct node
 5 {
 6     int data;//数据域
 7     struct node * front;//指针域，指向前一个结点
 8     struct node * next;//指向后一个结点
 9 }dblink_t;//双向链表的结点类型
10 
11 
12 //创建
13 dblink_t * creat_dblink()
14 {
15     //申请头尾结点空间
16     dblink_t * head = malloc(sizeof(dblink_t));
17     if(head == NULL)
18     {
19         printf("头结点申请失败!\n");
20         return NULL;
21     }
22 
23     dblink_t * tail = malloc(sizeof(dblink_t));    
24     if(tail == NULL)
25     {
26         printf("尾结点申请失败!\n");
27         return NULL;
28     }
29 
30     //初始化
31     head->next = tail;
32     head->front = NULL;
33     tail->next = NULL;
34     tail->front = head;
35 
36     //返回申请空间的首地址
37     return head;
38 }
39 
40 
41 int main(int argc, const char *argv[])
42 {
43     dblink_t * dblink = creat_dblink();
44     if(dblink == NULL)
45     {
46         return -1;
47     }
48 
49     
50     return 0;
51 }

dblink

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct node
  5 {
  6     int data;//数据域
  7     struct node * front;//指针域，指向前一个结点
  8     struct node * next;//指向后一个结点
  9 }dblink_t;//双向链表的结点类型
 10 
 11 
 12 //创建
 13 dblink_t * creat_dblink()
 14 {
 15     //申请头尾结点空间
 16     dblink_t * head = malloc(sizeof(dblink_t));
 17     if(head == NULL)
 18     {
 19         printf("头结点申请失败!\n");
 20         return NULL;
 21     }
 22 
 23     dblink_t * tail = malloc(sizeof(dblink_t));    
 24     if(tail == NULL)
 25     {
 26         printf("尾结点申请失败!\n");
 27         return NULL;
 28     }
 29 
 30     //初始化
 31     head->next = tail;
 32     head->front = NULL;
 33     tail->next = NULL;
 34     tail->front = head;
 35 
 36     //返回申请空间的首地址
 37     return head;
 38 }
 39 
 40 //判空
 41 int isnull(dblink_t * head)
 42 {
 43     return head->next->next == NULL;
 44 }
 45 
 46 //头增
 47 int ins_head_dblink(dblink_t * head, int data)
 48 {
 49     //新节点申请空间
 50     dblink_t * newnode = malloc(sizeof(dblink_t));
 51 
 52     //存入数据
 53     newnode->data = data;
 54 
 55     //将新结点连入到链表中
 56     newnode->next = head->next; //修改新结点的后继
 57     newnode->front = head;//修改新结点的前驱
 58     
 59     head->next->front = newnode;//1.修改head->next的前驱
 60     head->next = newnode;//修改head的后继
 61 
 62 #if 0
 63     head->next = newnode;//2
 64     newnode->next->front = newnode;
 65 
 66     newnode->next->front = newnode;//3   1,2,3所对应的2句话可以互换
 67     newnode->front->next = newnode;
 68 
 69 #endif
 70     return 0;
 71 }
 72 
 73 //头删
 74 int del_head_dblink(dblink_t * head)
 75 {
 76     //判空
 77     if(isnull(head))
 78     {
 79         printf("表为空，无法执行删除操作!\n");
 80         return -1;
 81     }
 82 
 83     //备份
 84     dblink_t * temp = head->next;
 85 
 86     //删除
 87     head->next = temp->next;
 88     temp->next->front = head;
 89 
 90     //释放
 91     free(temp);
 92 
 93     return 0;
 94 }
 95 //打印
 96 int print_dblink(dblink_t * head)
 97 {
 98     if(isnull(head))
 99     {
100         printf("表为空，无法执行打印操作!\n");
101         return -1;
102     }
103 
104     //正向打印
105     printf("正向打印：");
106     while(head->next->next != NULL)
107     {
108         head = head->next;
109         printf("%d ", head->data);
110     }
111     printf("\n");
112     
113     //逆向打印    
114     printf("逆向打印：");
115     while(head->front != NULL)
116     {
117         printf("%d ",head->data);
118         head = head->front;
119     }
120     printf("\n");
121 
122 
123     return 0;
124 }
125 
126 //修改
127 int change_dblink(dblink_t * head, int data, int index)
128 {
129     //判断
130     if(isnull(head) || index < 0)
131     {
132         printf("修改数据，指定位置过小!\n");
133         return -1;
134     }
135 
136     //偏移
137     while(index--)//while(index);index = index-1;
138     {
139         head = head->next;
140         if(head->next->next == NULL)
141         {
142             printf("修改数据，指定位置过大!\n");
143             return -1;        
144         }
145     }
146 
147     //修改
148     head->next->data = data;
149 
150     return 0;
151 }
152 
153 //查找
154 dblink_t * locate_dblink(dblink_t * head, int data)
155 {
156     //判空
157     if(isnull(head))
158     {
159         printf("表为空，无法执行查找操作!\n");
160         return NULL;
161     }
162 
163     //遍历查找，返回前一个结点的地址
164     while(head->next->next != NULL)
165     {
166         if(head->next->data == data)
167         {
168             return head;
169         }
170         head = head->next;
171     }
172 
173     //没有找到
174     printf("表中没有该数据!\n");
175     return NULL;
176 }
177 
178 //清空
179 int clean_dblink(dblink_t * head)
180 {
181     while(!isnull(head))
182     {
183         del_head_dblink(head);
184     }
185     return 0;
186 }
187 
188 //销毁
189 int dis_dblink(dblink_t * head)
190 {
191     clean_dblink(head);
192     free(head->next);
193     free(head);
194 
195     return 0;
196 }
197 int main(int argc, const char *argv[])
198 {
199     dblink_t * dblink = creat_dblink();
200     if(dblink == NULL)
201     {
202         return -1;
203     }
204 
205     int i;
206     for(i = 1; i <= 20; i++)
207     {
208         ins_head_dblink(dblink, i * 10);
209     }
210     print_dblink(dblink);
211     
212     for(i = 1; i <= 10; i++)
213     {
214         del_head_dblink(dblink);
215     }
216     print_dblink(dblink);
217 
218     change_dblink(dblink, 666, 6);    
219     print_dblink(dblink);
220 
221     dblink_t * ret = locate_dblink(dblink, 666);
222     if(ret != NULL)
223     {
224         del_head_dblink(ret);
225     }
226     print_dblink(dblink);
227 
228     clean_dblink(dblink);
229     print_dblink(dblink);
230 
231     dis_dblink(dblink);
232 
233     return 0;
234 }

dblink2

link_c.c（单向循环链表）

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 typedef struct node
 4 {
 5     int data;
 6     struct node * next;
 7 }link_t;
 8 
 9 //创建
10 link_t * creat_link()
11 {
12     //申请空间
13     link_t * head = malloc(sizeof(link_t));
14     if(head == NULL)
15     {
16         printf("头结点空间申请失败!\n");
17         return NULL;
18     }
19 
20     //初始化
21     head->next = head;
22 
23     return head;
24 }
25 
26 //判空
27 int isnull(link_t * head)
28 {
29     return head->next == head;
30 }
31 
32 //头增
33 int ins_head_link(link_t * head, int data)
34 {
35     //申请空间
36     link_t * newnode = malloc(sizeof(link_t));
37 
38     //存入数据
39     newnode->data = data;
40 
41     //将新节点连入链表中
42     newnode->next = head->next;
43     head->next = newnode;
44 
45     return 0;
46 }
47 
48 //打印
49 int print_link(link_t * head)
50 {
51     //判空
52     if(isnull(head))
53     {
54         printf("表为空，无法执行打印操作!\n");
55         return -1;
56     }
57 
58     //标记头结点
59     link_t * temp = head;
60 
61     //跳过头结点
62     head = head->next;
63 
64     //遍历打印
65     while(head != temp)
66     {
67         printf("%d ", head->data);
68         head = head->next;    
69     }
70     printf("\n");
71 
72     return 0;
73 }
74 int main(int argc, const char *argv[])
75 {
76     link_t * link = creat_link();
77     if(link == NULL)
78     {
79         return -1;
80     }
81 
82     int i;
83     for(i = 1; i <= 20; i++)
84     {
85         ins_head_link(link, i*10);
86     }
87     print_link(link);
88 
89     return 0;
90 }

link_c

栈：
栈具有先进后出（FILO）/后进先出（LIFO）的线性结构
栈顶：允许进行入栈、出栈的一端
栈底：固定的一端

入栈、压栈（增加数据）
出栈、弹栈（删除数据）

顺序栈：
栈的顺序存储结构（尾入尾出）
stack.c

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 typedef struct 
  4 {
  5     int *data;//存数据
  6     int size;//记录数据元素的个数
  7     int top;//标记栈顶元素的位置
  8 }stack_tt;//栈的数据类型
  9 
 10 //创建
 11 stack_tt * creat_stack(int size)
 12 {
 13     //申请结构体空间
 14     stack_tt * stack = malloc(sizeof(stack_tt));
 15     if(stack == NULL)
 16     {
 17         return NULL;
 18     }
 19     //申请数据空间
 20     stack->data = malloc(sizeof(int) * size);
 21     if(stack->data == NULL)
 22     {
 23         return NULL;
 24     }
 25 
 26     //初始化
 27     stack->size = size;
 28 
 29     stack->top = -1;
 30 
 31     //返回申请空间首地址
 32     return stack;
 33 }
 34 //判满
 35 int isfull(stack_tt * stack)
 36 {
 37     return stack->top == (stack->size - 1);
 38 }
 39 
 40 //判空
 41 int isnull(stack_tt * stack)
 42 {
 43     return stack->top == -1;
 44 }
 45 
 46 //入栈
 47 int push_stack(stack_tt * stack, int data)
 48 {
 49     //判满
 50     if(isfull(stack))
 51     {
 52         printf("栈为满，无法执行入栈操作!\n");
 53         return -1;
 54     }
 55 
 56     //入栈
 57     stack->data[stack->top+1] = data;
 58 
 59     //修改栈顶位置
 60     stack->top++;
 61 
 62     return 0;
 63 }
 64 //出栈
 65 int pop_stack(stack_tt * stack, int * data)
 66 {
 67     //判空
 68     if(isnull(stack))
 69     {
 70         printf("栈为空，无法执行出栈操作!\n");
 71         return -1;
 72     }
 73 
 74     //获取出栈的数据
 75     *data = stack->data[stack->top];
 76 
 77     //删除栈顶数据
 78     stack->top--;
 79 
 80     return 0;
 81 }
 82 //获取栈顶数据
 83 int get_top(stack_tt * stack, int *data)
 84 {
 85     //判空
 86     if(isnull(stack))
 87     {
 88         printf("栈为空，无法执行获取栈顶数据!\n");
 89         return -1;
 90     }
 91 
 92     //获取栈顶数据
 93     *data = stack->data[stack->top];
 94 
 95     return 0;
 96 }
 97 
 98 //打印
 99 int print_stack(stack_tt * stack)
100 {
101     //判空
102     if(isnull(stack))
103     {
104         printf("栈为空，无法执行打印操作!\n");
105         return -1;
106     }
107 
108     //循环遍历打印（栈顶开始打印）
109     printf("栈顶\n");
110     int i;
111     for(i = stack->top; i >= 0; i--)
112     {
113         printf("%d\n",stack->data[i]);
114     }
115     printf("栈底\n");
116 
117     return 0;
118 }
119 //清空
120 int clean_stack(stack_tt * stack)
121 {
122     stack->top = -1;
123     return 0;
124 }
125 
126 //销毁
127 int dis_stack(stack_tt * stack)
128 {
129     free(stack->data);
130     free(stack);
131     return 0;
132 }
133 
134 int main(int argc, const char *argv[])
135 {
136     stack_tt * stack = creat_stack(10);
137     if(stack == NULL)
138     {
139         return -1;
140     }
141 
142     int i;
143     for(i = 1; i <= 10; i++)
144     {
145         push_stack(stack, i*10);
146     }
147     print_stack(stack);
148 
149     int data;
150     for(i = 1; i <= 3; i++)
151     {
152         pop_stack(stack,&data );
153         printf("pop_data:%d\n", data);
154         print_stack(stack);
155     }
156 
157     int get_top_data;
158     get_top(stack, &get_top_data);
159     printf("get_top_data:%d\n", get_top_data);
160     
161     clean_stack(stack);
162     print_stack(stack);
163 
164     dis_stack(stack);
165 
166     return 0;
167 }

stack

链式栈：
栈的链式存储结构（头入头出）
linkstack.c

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct node
  5 {
  6     int data;
  7     struct node * next;
  8 }linkstack_t;
  9 
 10 //创建
 11 linkstack_t * creat_linkstack()
 12 {
 13     //申请空间
 14     linkstack_t * head = malloc(sizeof(linkstack_t));
 15     if(head == NULL)
 16     {
 17         printf("空间申请失败 !\n");
 18         return NULL;
 19     }
 20 
 21     //初始化
 22     head->next = NULL;
 23 
 24     //返回首地址
 25     return head;
 26 }
 27 
 28 //判空
 29 int isnull(linkstack_t * head)
 30 {
 31     return head->next == NULL;
 32 }
 33 
 34 //入栈
 35 int push_linkstack(linkstack_t * head, int data)
 36 {
 37     //申请空间
 38     linkstack_t * newnode = malloc(sizeof(linkstack_t));
 39     
 40     //存入数据
 41     newnode->data = data;
 42     
 43     //将新结点连入到栈中
 44     newnode->next = head->next;
 45     head->next = newnode;
 46 
 47     return 0;
 48 }
 49 
 50 //出栈
 51 int pop_linkstack(linkstack_t * head, int *data)
 52 {
 53     //判空
 54     if(isnull(head))
 55     {
 56         printf("栈为空，无法执行出栈操作!\n");
 57         return -1;
 58     }
 59     //备份
 60     linkstack_t * temp = head->next;
 61 
 62     //获取出栈数据
 63     *data = temp->data;
 64     
 65     //删除
 66     head->next = temp->next;
 67 
 68     //释放
 69     free(temp);
 70     return 0;
 71 }
 72 
 73 //获取栈顶数据
 74 int get_top(linkstack_t * head, int *data)
 75 {
 76     //判空
 77     if(isnull(head))
 78     {
 79         printf("栈为空，无法执行获取栈顶数据!\n");
 80         return -1;
 81     }
 82 
 83     //获取栈顶数据
 84     *data = head->next->data;
 85 
 86     return 0;
 87 }
 88 
 89 //打印
 90 int print_linkstack(linkstack_t * head)
 91 {
 92     //判空
 93     if(isnull(head))
 94     {
 95         printf("栈为空，无法执行打印操作!\n");
 96         return -1;
 97     }
 98 
 99     //遍历打印
100     head = head->next;//跳过头结点
101 
102     printf("栈顶\n");
103     while(head != NULL)
104     {
105         printf("%d\n", head->data);
106         head = head->next;
107     }
108     printf("栈底\n");
109     
110     return 0;
111 }
112 //清空
113 int clean_linkstack(linkstack_t * head)
114 {
115     int temp;
116     while(!isnull(head))
117     {
118         pop_linkstack(head,&temp );
119     }
120 
121     return 0;
122 }
123 
124 //销毁
125 int dis_linkstack(linkstack_t * head)
126 {
127     clean_linkstack(head);
128     free(head);
129 
130     return 0;
131 }
132 
133 int main(int argc, const char *argv[])
134 {
135     linkstack_t * linkstack = creat_linkstack();
136     if(linkstack == NULL)
137     {
138         return -1;
139     }
140 
141     int i;
142     for(i = 1; i <= 10; i++)
143     {
144         push_linkstack(linkstack, i*10);
145     }
146     print_linkstack(linkstack);
147 
148     int data;
149     for(i = 1; i <= 3; i++)
150     {
151         pop_linkstack(linkstack, &data);
152         printf("pop_data:%d\n", data);
153         print_linkstack(linkstack);
154     }
155 
156     int get_top_data;
157     get_top(linkstack, &get_top_data);
158     printf("get_top_data:%d\n", get_top_data);
159 
160     clean_linkstack(linkstack);
161     print_linkstack(linkstack);
162 
163     dis_linkstack(linkstack);
164     return 0;
165 }

linkstack

队列：
队列具有先进先出/后进后出的线性结构
队列允许在两端进行操作，一端入队一端出队

入队:(数据的增加)
出队:(数据的删除)

链式队列：
linkqueue.c（尾入头出）

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef int data_t;
  5 
  6 typedef struct node
  7 {
  8     data_t data;//数据域
  9     struct node * next;//指针域，指向下一个结点
 10 }node_t;//结点的类型
 11 
 12 
 13 typedef struct queue
 14 {
 15     node_t * head;//头指针，指向头结点
 16     node_t * tail;//尾指针,指向尾巴结点
 17 }queue_t;//队列的类型
 18 
 19 //创建
 20 queue_t * creat_queue()
 21 {
 22     node_t * head = malloc(sizeof(node_t));//申请头结点
 23     if(head == NULL)
 24     {
 25         printf("头结点空间申请失败!\n");
 26         return NULL;
 27     }
 28     head->next = NULL;
 29     
 30     queue_t * queue = malloc(sizeof(queue_t));//申请队列标识
 31     if(queue == NULL)
 32     {
 33         return NULL;
 34     }
 35 
 36     queue->head = head;//头指针指向头结点
 37     queue->tail = head;//尾指针初始状态也指向头结点（约定尾指针指向尾巴结点）
 38 
 39     return queue;//返回队列标识
 40 }
 41 
 42 //判空
 43 int isnull(queue_t * queue)
 44 {
 45     return queue->head == queue->tail;
 46     //return queue->head->next == NULL;
 47 }
 48 
 49 //入队
 50 int in_queue(queue_t * queue, data_t data)
 51 {
 52     //申请新节点空间
 53     node_t * newnode = malloc(sizeof(node_t));
 54 
 55     //存入数据
 56     newnode->data = data;
 57 
 58     //入队
 59     newnode->next = queue->tail->next;//修改新节点的后继
 60     queue->tail->next = newnode;//修改尾指针指向的尾巴结点的后继
 61 
 62     //修改tail的指向
 63     queue->tail = newnode;
 64 
 65     return 0;
 66 }
 67 
 68 //出队
 69 int out_queue(queue_t * queue, data_t * data)
 70 {
 71     //判空
 72     if(isnull(queue))
 73     {
 74         printf("表为空，无法执行出队操作!\n");
 75         return -1;
 76     }
 77 
 78     //备份
 79     node_t * temp = queue->head->next;
 80     
 81     //获取出队数据
 82     *data = temp->data;
 83 
 84     //删除
 85     queue->head->next = temp->next;
 86 
 87     //释放
 88     free(temp);
 89 
 90     //如果出队数据后，队列为空，找回尾指针的指向
 91     if(queue->head->next == NULL)
 92     {
 93         queue->tail = queue->head;
 94     }
 95 
 96     return 0;
 97 }
 98 
 99 //打印
100 int print_queue(queue_t * queue)
101 {
102     //判空
103     if(isnull(queue))
104     {
105         printf("队列为空，无法执行打印操作!\n");
106         return -1;
107     }
108 
109     //标记头结点
110     node_t * head = queue->head;
111 
112     //跳过头结点
113     head = head->next;
114 
115     //打印
116     printf("队头：");
117     while(head != NULL)
118     {
119         printf("%d ", head->data);
120         head = head->next;    
121     }
122     printf("队尾\n");
123     
124     return 0;
125 }
126 
127 //获取队列长度
128 int get_length(queue_t * queue)
129 {
130     //判空
131     if(isnull(queue))
132     {
133         printf("队列为空，长度为0!\n");
134         return 0;
135     }
136     
137     int  len = 0;
138 
139     //标记头结点
140     node_t * head = queue->head;
141 
142     //跳过头结点
143     head = head->next;
144 
145     //循环遍历，计算长度
146     while(head != NULL)
147     {
148         len++;
149         head = head->next;
150     }
151 
152     //返回长度
153     return len;
154 }
155 
156 //清空
157 int clean_queue(queue_t * queue)
158 {
159     data_t temp;
160     while(!isnull(queue))
161     {
162         out_queue(queue, &temp);
163     }
164 
165     return 0;
166 }
167 //销毁
168 int dis_queue(queue_t * queue)
169 {
170     clean_queue(queue);
171     free(queue->head);//先释放头结点
172     free(queue);//再释放结构体标识
173     return 0;
174 }
175 
176 //队列逆向输出（利用2个顺序栈实现）
177 int reprint_queue(queue_t * queue)
178 {
179     //创建2个临时顺序栈
180     data_t * stack1 = malloc(sizeof(data_t)*get_length(queue));
181     int top1 = -1;
182 
183     data_t * stack2 = malloc(sizeof(data_t)*get_length(queue));
184     int top2 = -1;
185 
186     //当队列不为空，出队列，进栈1
187     data_t data;
188     while(!isnull(queue))
189     {
190         out_queue(queue, &data);
191         stack1[++top1] = data;
192     }
193 
194     //当栈1不为空，出栈1，出来一个打印一个，将数据进栈2
195     while(top1 != -1)
196     {
197         data = stack1[top1--];
198         printf("%d ", data);
199         stack2[++top2] = data;
200     }
201     printf("\n");
202 
203     //当栈2不为空，出栈2，进队列
204     while(top2 != -1)
205     {
206         data = stack2[top2--];
207         in_queue(queue, data);
208     }
209 
210     //销毁2个临时顺序栈
211     free(stack1);
212     free(stack2);
213 
214     return 0;
215 }
216 
217 int main(int argc, const char *argv[])
218 {
219     queue_t * queue = creat_queue();
220     if(queue == NULL)
221     {
222         printf("creat_queue()执行失败!\n");
223         return -1;
224     }
225     
226     int i;
227     for(i = 1; i <= 20; i++)
228     {
229         in_queue(queue, i*10);
230     }
231     print_queue(queue);
232 
233     data_t data;
234     for(i = 1; i <= 10; i++)
235     {
236         out_queue(queue,&data);
237         printf("out_data:%d\n", data);
238     }
239     print_queue(queue);
240 
241     int ret = get_length(queue);
242     printf("长度:%d\n", ret);
243 
244     printf("逆向打印：");
245     reprint_queue(queue);
246 
247     clean_queue(queue);
248     print_queue(queue);
249 
250     dis_queue(queue);
251 
252     return 0;
253 }

linkqueue

顺序循环队列：
queue.c（尾入头出）

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef int data_t;
  5 
  6 typedef struct queue
  7 {
  8     data_t * data;//存数据
  9     int size;//标记数据元素个数
 10     int head;//即将要取数据的位置
 11     int tail;//即将要存数据的位置
 12 }queue_t;//顺序循环队列的类型
 13 
 14 //创建
 15 queue_t * creat_queue(int size)
 16 {
 17     queue_t * queue = malloc(sizeof(queue_t));//申请队列标识
 18     if(queue == NULL)
 19     {
 20         printf("申请失败!\n");
 21         return NULL;
 22     }
 23 
 24     queue->data = malloc(sizeof(data_t) * size);//申请存储数据空间
 25     if(queue->data == NULL)
 26     {
 27         printf("申请失败!\n");
 28         return NULL;
 29     }
 30 
 31     //初始化
 32     queue->size = size;
 33     
 34     queue->head = 0;
 35     queue->tail = 0;
 36 
 37     return queue;
 38 }
 39 
 40 //判空
 41 int isnull(queue_t * queue)
 42 {
 43     return queue->head == queue->tail;
 44 }
 45 
 46 //判满
 47 int isfull(queue_t * queue)
 48 {
 49     return (queue->tail + 1) % queue->size  == queue->head;
 50 }
 51 
 52 //入队
 53 int in_queue(queue_t * queue, data_t data)
 54 {
 55     //判满
 56     if(isfull(queue))
 57     {
 58         printf("队列为满，无法执行入队操作!\n");
 59         return -1;
 60     }
 61 
 62     //入队数据,尾入
 63     queue->data[queue->tail] = data;
 64 
 65     //修改tail的值
 66     queue->tail = (queue->tail + 1) % queue->size;
 67 
 68     return 0;
 69 }
 70 
 71 //出队
 72 int out_queue(queue_t * queue, data_t * data)
 73 {
 74     //判空
 75     if(isnull(queue))
 76     {
 77         printf("队列为空，无法执行出队操作!\n");
 78         return -1;
 79     }
 80 
 81     //获取出队数据
 82     *data = queue->data[queue->head];
 83 
 84     //出队数据，修改head的值
 85     queue->head = (queue->head + 1) % queue->size;
 86 
 87     return 0;
 88 }
 89 
 90 //打印
 91 int print_queue(queue_t * queue)
 92 {
 93     //判空
 94     if(isnull(queue))
 95     {
 96         printf("队列为空，无法执行打印操作!\n");
 97         return -1;
 98     }
 99 
100     //循环遍历打印
101     int i;
102     printf("队头：");
103     for(i = queue->head; i != queue->tail; i = (i+1)%queue->size)
104     {
105         printf("%d ", queue->data[i]);
106     }
107     printf("队尾\n");
108 
109     return 0;
110 }
111 
112 //获取队列长度
113 int get_length(queue_t * queue)
114 {
115     return (queue->tail + queue->size - queue->head) % queue->size;
116 }
117 
118 //清空
119 int clean_queue(queue_t * queue)
120 {
121     queue->head = 0;
122     queue->tail = 0;
123 
124     return 0;
125 }
126 
127 //销毁
128 int dis_queue(queue_t * queue)
129 {
130     free(queue->data);
131     free(queue);
132 
133     return 0;
134 }
135 int main(int argc, const char *argv[])
136 {
137     queue_t * queue = creat_queue(10);
138     if(queue == NULL)
139     {
140         return -1;
141     }
142 
143     int i;
144     for(i = 1; i <= 9; i++)
145     {
146         in_queue(queue, i*10);
147     }
148     print_queue(queue);
149 
150     data_t data;
151     for(i = 1; i <= 3; i++)
152     {
153         out_queue(queue, &data);
154         printf("出队数据:%d\n", data);
155     }
156     print_queue(queue);
157 
158     int ret = get_length(queue);
159     printf("get_length:%d\n", ret);
160 
161     clean_queue(queue);
162     print_queue(queue);
163 
164     dis_queue(queue);
165 
166         
167     return 0;
168 }

queue

树的实现
tree.c

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct node
 5 {
 6     int data;//编号
 7     struct node * lchild;//保存左孩子的地址
 8     struct node * rchild;//保存右孩子的地址
 9 }tree_t;//树的结点类型
10 
11 //创建
12 tree_t * creat_tree(int num)
13 {
14     //创建
15     if(num > 6)
16     {
17         return NULL;
18     }
19     tree_t * root = malloc(sizeof(tree_t));//申请空间
20     
21     //初始化编号、左孩子、右孩子
22     root->data = num;//存入编号
23     printf("%d ", root->data);
24 
25     root->lchild = creat_tree(num*2);//保存左孩子的地址
26     root->rchild = creat_tree(num*2+1);//保存右孩子的地址
27 
28     return root;//返回申请空间的地址
29 }
30 
31 int main(int argc, const char *argv[])
32 {
33     tree_t * tree = creat_tree(1);
34 
35 
36     
37     return 0;
38 }

tree

先序：根左右
中序：左根右
后序：左右根

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct node
  5 {
  6     int data;//编号
  7     struct node * lchild;//保存左孩子的地址
  8     struct node * rchild;//保存右孩子的地址
  9 }tree_t;//树的结点类型
 10 
 11 //创建
 12 tree_t * creat_tree(int num)
 13 {
 14     //创建
 15     if(num > 6)
 16     {
 17         return NULL;
 18     }
 19     tree_t * root = malloc(sizeof(tree_t));//申请空间
 20     
 21     //初始化编号、左孩子、右孩子
 22     root->data = num;//存入编号
 23 //    printf("%d ", root->data);
 24 
 25     root->lchild = creat_tree(num*2);//保存左孩子的地址
 26     root->rchild = creat_tree(num*2+1);//保存右孩子的地址
 27 
 28     return root;//返回申请空间的地址
 29 }
 30 
 31 //先序遍历(根左右)
 32 void pre_tree(tree_t * root)
 33 {
 34     //结束条件
 35     if(root == NULL)
 36     {
 37         return ;
 38     }
 39     
 40     //访问自己（根节点）
 41     printf("%d ",root->data );
 42 
 43     //访问左孩子
 44     pre_tree(root->lchild);
 45 
 46     //访问右孩子
 47     pre_tree(root->rchild);
 48 
 49 }
 50 
 51 //中序遍历(左根右)
 52 void mid_tree(tree_t * root)
 53 {
 54     //结束条件
 55     if(root == NULL)
 56     {
 57         return ;
 58     }
 59 
 60     //访问左孩子
 61     mid_tree(root->lchild);
 62 
 63     //访问自己（根节点）
 64     printf("%d ", root->data);
 65 
 66     //访问右孩子
 67     mid_tree(root->rchild);
 68 
 69 }
 70 //后序遍历(左右根)
 71 void post_tree(tree_t * root)
 72 {
 73     //结束条件
 74     if(root == NULL)
 75     {
 76         return ;
 77     }
 78 
 79     //访问左孩子
 80     post_tree(root->lchild);
 81 
 82     //访问右孩子
 83     post_tree(root->rchild);
 84 
 85     //访问自己（根节点）
 86     printf("%d ", root->data);
 87 
 88 }
 89 
 90 //层次遍历(顺序队列实现)
 91 int levev_tree(tree_t * root)
 92 {
 93     //创建临时顺序队列(尾入头出)
 94     tree_t * queue[20];
 95     int head = 0;
 96     int tail = 0;
 97 
 98     //创建临时变量存放出队结点
 99     tree_t * temp;
100 
101     //入队根结点
102     queue[tail++] = root;
103 
104     //判断队列是否为空,不为空，出队，打印其编号，判断其是否有左右孩子，有入队，没有跳过
105     while(head != tail)
106     {
107         //出队队头结点
108         temp = queue[head++];
109         
110         //打印出队结点编号
111         printf("%d ", temp->data);
112 
113         //判断出队结点是否有左孩子，有入队
114         if(temp->lchild != NULL)
115         {
116             queue[tail++] = temp->lchild;
117         }
118 
119         //判断出队结点是否有右孩子，有入队
120         if(temp->rchild != NULL)
121         {
122             queue[tail++] = temp->rchild;
123         }
124 
125     }
126 
127     printf("\n");
128     
129     return 0;
130 }
131 
132 //销毁函数
133 void free_tree(tree_t * root)
134 {
135     //结束条件
136     if(root == NULL)
137     {
138         return ;
139     }
140 
141     free_tree(root->lchild);
142     free_tree(root->rchild);
143     free(root);
144 
145 }
146 
147 int main(int argc, const char *argv[])
148 {
149     tree_t * tree = creat_tree(1);
150 
151     printf("先序遍历:");
152     pre_tree(tree);
153     printf("\n");
154 
155     printf("中序遍历:");
156     mid_tree(tree);
157     printf("\n");
158 
159     printf("后序遍历:");
160     post_tree(tree);
161     printf("\n");
162 
163     printf("层次遍历:");
164     levev_tree(tree);
165     
166     free_tree(tree);
167     levev_tree(tree);
168 
169 
170     
171     return 0;
172 }

tree2

递归函数

 1 #include <stdio.h>
 2 
 3 int n_njc(int n)
 4 {
 5     if(n == 1)
 6         return 1;
 7     return n*n_njc(n-1);
 8 }
 9 
10 #if 0
11 
12 递归就是说函数本身直接调用自己。
13 递归在使用的时候耗费的内存很高，一旦代码实现错误，导致无限的递归，就会造成栈空间的不足。
14 所以在执行递归的时候，一定要有递归结束的条件
15 关于递归它是分为两个阶段的：
16      一个是递推阶段、
17      一个是回归阶段 
18 
19 #endif
20 
21 int main(int argc, const char *argv[])
22 {
23     int x;
24     scanf("%d",&x);
25     int ret = n_njc(x);
26     printf("%d\n",ret);
27     
28     return 0;
29 }

递归函数