数据结构代码练习

 

 

数据结构代码练习

循环队列的6个基本操作https://haokan.baidu.com/v?vid=4145113523493725579&pd=bjh&fr=bjhauthor&type=video

出队:Q.front=(Q.front+1)%MAXSIZE

入队:Q.rear=(Q.rear+1)%MAXSIZE

队列初始化:Q.front=Q.rear=NULL

队空:Q.rear=Q.front

队满:(Q.rear+1)%MAXSIZE=Q.front

个数:(Q.rear-Q.front+MAXSIZE)%MAXSIZE

数据结构代码练习

 

 

 

归并排序(https://haokan.baidu.com/v?vid=9368202192256111816&pd=bjh&fr=bjhauthor&type=video)

数据结构代码练习
 1 /*归并排序*/
 2 void Merge_Sort(int* arr, int* temparr, int start, int mid, int end)
 3 {
 4     int left_start = start;
 5     int left_end = mid;
 6 
 7     int right_start = mid + 1;
 8     int right_end = end;
 9 
10     int index = start;
11 
12     while (left_start <= left_end && right_start <= right_end)
13     {
14         if (arr[left_start] > arr[right_start])
15             temparr[index++] = arr[right_start++];
16         else
17             temparr[index++] = arr[left_start++];
18     }
19 
20     while (left_start <= left_end)
21         temparr[index++] = arr[left_start++];
22 
23     while (right_start <= right_end)
24         temparr[index++] = arr[right_start++];
25 
26     for (index = start; index <= end; ++index)
27         arr[index] = temparr[index];
28 }
29 void Sort_Message(int* arr, int* temparr, int start, int end)
30 {
31     if (start < end)
32     {
33         int mid = (start + end) / 2;
34         Sort_Message(arr, temparr, start, mid);
35         Sort_Message(arr, temparr, mid + 1, end);
36         Merge_Sort(arr, temparr, start, mid, end);
37     }
38 }
39 
40 int main()
41 {
42     int a[] = { 9,2,5,3,7,4,8,0 };
43     int n = sizeof(a) / sizeof(a[0]);
44     int i, temp[8];
45 
46     printf("原序列为:");
47     for (i = 0; i < n; ++i)
48         printf("%d ", a[i]);
49     printf("\n");
50 
51     Sort_Message(a, temp, 0, n - 1);
52 
53     printf("\n排后序列:");
54     for (i = 0; i < n; ++i)
55         printf("%d ", a[i]);
56     printf("\n");
57     return 0;
58 }
View Code

冒泡排序 

数据结构代码练习
 1 #include <stdio.h>
 2 #define N 7
 3 
 4 void Bubble(int a[],int n)
 5 {
 6     int i, j = 0;
 7     int temp;
 8     for(i=0;i<n-1;i++)
 9         for(j=0;j<n-1-i;j++)
10             if (a[j] > a[j+1])
11             {
12                 temp = a[j];
13                 a[j] = a[j+1];
14                 a[j+1] = temp;
15             }
16 }
17 
18 void main()
19 {
20     int a[] = { 2,9,7,8,6,5,3};
21     int i;
22     void Bubble(int a[], int);
23     printf("排序前:\n");
24     for (i = 0; i < N; i++)
25         printf("%d ", a[i]);
26     Bubble(a, N);
27     printf("\n\n\n排序后:\n");
28     for (i = 0; i < N; i++)
29         printf("%d ", a[i]);
30 }
View Code

希尔排序

 

数据结构代码练习

 

 

数据结构代码练习
 1 //希尔排序
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 int test_tab[] = { 0,4,9,5,7,1,3,9,6,4,5,6,7,7,8,8,1,0,3,2 };
 5 
 6 void Shell_Sort(int* dat, int len)
 7 {
 8     int i, j, k, t;
 9     int n = 0;
10 
11     k = len / 2;
12 
13     while (k > 0)
14     {
15         for (i = k; i < len; i++)
16         {
17             t = dat[i];
18             j = i - k;
19             while ((j >= 0) && (t < dat[j]))
20             {
21                 dat[j + k] = dat[j];
22                 j = j - k;
23                 n++;
24             }
25 
26             dat[j + k] = t;
27         }
28 
29         k /= 2;
30     }
31     printf("循环的次数是:%d \r\n", n);
32 }
33 int main(int argc, char* argv[])
34 {
35     int i = 0;
36     int len = sizeof(test_tab) / sizeof(test_tab[0]);
37 
38     Shell_Sort(test_tab, sizeof(test_tab) / sizeof(test_tab[0]));
39     for (i = 0; i < len; i++)
40         printf("%d ", test_tab[i]);
41     system("PAUSE");
42     return 0;
43 }
View Code

快速排序

数据结构代码练习
 1 #include<stdio.h>
 2 
 3 
 4 
 5 void quicksort(int a[], int n) {
 6 
 7     int i, j;
 8 
 9     int pivot = a[0];    //设置基准值 
10 
11     i = 0;
12 
13     j = n - 1;
14 
15     while (i < j) {
16 
17         //大于基准值者保持在原位置 
18 
19         while (i < j && a[j] > pivot) { j--; }
20 
21         if (i < j) {
22 
23             a[i] = a[j];
24 
25             i++;
26 
27         }
28 
29         //不大于基准值者保持在原位置 
30 
31         while (i < j && a[i] <= pivot) { i++; }
32 
33         if (i < j) {
34 
35             a[j] = a[i];
36 
37             j--;
38 
39         }
40 
41     }
42 
43     a[i] = pivot;    //基准元素归位 
44 
45     if (i > 1) {
46 
47         //递归地对左子序列 进行快速排序
48 
49         quicksort(a, i);
50 
51     }
52 
53     if (n - i - 1 > 1) {
54 
55         quicksort(a + i + 1, n - i - 1);
56 
57     }
58 
59 }
60 
61 
62 
63 int main() {
64 
65     int i, arr[] = { 23,56,9,75,18,42,11,67 };
66 
67     quicksort(arr, 8);
68 
69     for (i = 0; i < sizeof(arr) / sizeof(int); i++)
70 
71         printf("%d\t", arr[i]);
72 
73     return 0;
74 
75 }
View Code

插入排序

数据结构代码练习
 1 #include<stdio.h>
 2 int number[100000000];     //在外面定义数组 
 3 void insertion_sort(int* number, int n)    //定义一个插入函数"insertion_sort" 
 4 {
 5     int i = 0, ii = 0, temp = 0;
 6     for (i = 1; i < n; i++)  //循环遍历 
 7     {
 8         temp = number[i];  //将temp每一次赋值为number[i] 
 9         ii = i - 1;
10         while (ii >= 0 && temp < number[ii])   //这里改顺序 (temp后的)"<"为小到大,">"为大到小 !!!
11         {
12             number[ii + 1] = number[ii];    //将大的元素往前放 
13             ii--;
14         }
15         number[ii + 1] = temp;   //与"number[ii+1]=number[ii];"一起意为 
16     }              //如果插入的数比之前的大,将number[ii]与number[ii+1]互换 
17 }
18 int main()
19 {
20     int i = 0, n;
21     printf("输入数字个数:\n");
22     scanf("%d", &n);       //输入要排序的数字的个数 
23     printf("输入%d个数:\n", n);
24     for (int j = 0; j < n; j++)       //将所有数全放入number数组中 
25         scanf("%d", &number[j]);
26     insertion_sort(number, n);   //引用插入函数 
27     for (i = 0; i < n - 1; i++)    //循环输出 
28         printf("%d ", number[i]);    //格式需要  
29     printf("%d\n", number[i]);
30     return 0;
31 }
View Code

选择排序

数据结构代码练习
 1 #include<stdio.h>
 2 int number[100000000];    //在主函数外定义数组可以更长多了 
 3 void select_sort(int R[], int n)    //定义选择排序函数"select_sort" 
 4 {
 5     int i, j, k, index;    //定义变量 
 6     for (i = 0; i < n - 1; i++)   //遍历 
 7     {
 8         k = i;
 9         for (j = i + 1; j < n; j++)    //j初始不为0,冒泡初始为0,所以选排比冒泡快,但不稳定 
10         {
11             if (R[j] < R[k])   //顺序从这里改顺序 小到大"<",大到小">" !!!
12                 k = j;      //这里是区分冒泡排序与选择排序的地方,冒泡没这句 
13         }
14         if (k != j)    //为了严谨,去掉也行 
15         {
16             index = R[i];   //交换R[i]与R[k]中的数 
17             R[i] = R[k];    //简单的交换c=a,a=b,b=c 
18             R[k] = index;
19         }
20     }
21 }
22 
23 int main()     //主程序 
24 {
25     int i, n;
26     printf("输入数字个数:\n");
27     scanf("%d", &n);     //输入要排序的数字的个数 
28     printf("输入%d个数:\n", n);
29     for (int j = 0; j < n; j++)     //将所有数全放入number数组中 
30         scanf("%d", &number[j]);
31     select_sort(number, n);   //引用选择排序select_sort的函数 
32     for (i = 0; i < n - 1; i++)    //用for循环输出排完排完序的数组 
33         printf("%d ", number[i]);   //这样写是为了格式(最后一个数后面不能有空格)                                  
34     printf("%d\n", number[i]);
35     return 0;   //好习惯 
36 }
37 //ENDING
View Code

堆排序

数据结构代码练习
 1 #include <stdio.h>
 2 #define NA -1
 3 void swap(int *a,int *b)//该函数用于交换两个变量的值
 4 {
 5     int temp=*a;
 6     *a=*b;
 7     *b=temp;
 8 }
 9 void HeapAdjust(int H[],int start,int end)//堆调整,将start和end之间的元素调整为最大堆
10 {
11     int temp=H[start];
12     int parent=start,child;
13     while(2*parent<=end)
14     {
15         child=2*parent;
16         if(child!=end&&H[child]<H[child+1])++child;
17         if(temp>H[child])break;
18         else H[parent]=H[child];
19         parent=child;
20     }
21     H[parent]=temp;
22 }
23 void HeapSort(int H[],int L,int R)
24 {
25     for(int i=(R-L+1)/2;i>=L;--i)//调整整个二叉树为最大堆
26         HeapAdjust(H,i,R);
27     for(int i=R;i>=L;--i)
28     {
29         swap(&H[L],&H[i]);
30         HeapAdjust(H,L,i-1);
31     }
32 }
33 
34 int main(){
35     int A[]={NA,1,3,63,5,78,9,12,52,8};//从1开始存入数据
36     printf("Previous Arrary:");
37     for(int i=1;i<=9;++i)
38         printf(" %d",A[i]);
39     HeapSort(A,1,9);
40     printf("\nSorted Arrary:");
41     for(int i=1;i<=9;++i)
42         printf(" %d",A[i]);
43     printf("\n");
44     return 0;
45 }
46 
47 //原文链接:https://blog.csdn.net/gl486546/article/details/54707307
View Code

 顺序队列

数据结构代码练习

 

 

数据结构代码练习
 1 //队列
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 #include<malloc.h>
 6 #define MAXSIZE 10
 7 
 8 typedef struct Queue {
 9 
10     int* queue;
11     int front;//队头
12     int rear;//队尾
13     int count;//计数
14 }QUEUE,*LPQUEUE;
15 
16 void CreateQueue(LPQUEUE Q)
17 {
18     Q->queue = (int*)malloc(sizeof(int) * MAXSIZE);
19     Q->front = Q->rear = Q->count = 0;
20 }
21 
22 int IsEmptyQueue(LPQUEUE Q)
23 {
24     if (Q->count == 0)
25         return 1;
26     return 0;
27 }
28 
29 void push(LPQUEUE Q, int theElement)
30 {
31     if (Q->count == MAXSIZE)
32     {
33         printf("队列满无法入队\n");
34         return;
35     }
36     Q->queue[Q->rear++] = theElement;
37     Q->count++;
38 }
39 void pop(LPQUEUE Q)
40 {
41     if (IsEmptyQueue(Q))
42     {
43         printf("队列为空\n");
44     }
45     Q->queue[Q->front++];
46     Q->count--;
47 }
48 
49 int getfront(LPQUEUE Q)
50 {
51     return Q->queue[Q->front];
52 }
53 
54 
55 
56 int main()
57 {
58     LPQUEUE Q = (LPQUEUE)malloc(sizeof(QUEUE));
59         CreateQueue(Q);
60         push(Q, 1);
61         push(Q, 2);
62         push(Q, 3);
63         while (!IsEmptyQueue(Q))
64         {
65             printf("%d", getfront(Q));
66             pop(Q);
67         }
68         system("pause");
69         return 0;
70 }
View Code

 

链式队列

数据结构代码练习

 

 

数据结构代码练习数据结构代码练习
 1 //链式队列
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<malloc.h>
 5 
 6 typedef struct SingleList
 7 {
 8     int data;
 9     struct SingleList * next;
10 
11 }LIST,*LPLIST;
12 LPLIST CreateNode(int data)
13 {
14     LPLIST Node = (LPLIST)malloc(sizeof(LIST));
15     Node->data = data;
16     Node->next = NULL;
17     return Node;
18 }
19 typedef struct queue
20 {
21     LPLIST front;
22     LPLIST rear;
23     int queueSize;
24 }QUEUE,*LPQUEUE;
25 void CreateQueue(LPQUEUE Q) {
26     Q->front = Q->rear = NULL;
27     Q->queueSize = 0;
28 }
29 
30 int IsEmptyQueue(LPQUEUE Q)
31 {
32     if (Q->queueSize == 0)
33         return 1;
34     return 0;
35 }
36 //入队列
37 void push(LPQUEUE Q, int theElement)
38 {
39 
40 
41         LPLIST newNode = CreateNode(theElement);
42         if (Q->front == NULL)
43         {
44             Q->front = newNode;//队列为空时, newNode 成为队头
45         }
46         else
47         {
48             Q->rear->next = newNode;
49         }
50         Q->rear = newNode;
51         Q->queueSize++;
52 }
53 
54 int getfront(LPQUEUE Q)
55 {
56     if (IsEmptyQueue(Q))
57     {
58         printf("无法获取队头元素,队为空\n");
59         return -1;
60     }
61 
62     return Q->front->data;
63 }
64 void pop(LPQUEUE Q)
65 {
66     if (IsEmptyQueue(Q))
67     {
68         printf("无法出兑,队为空");
69             return;
70     }
71     LPLIST nextNode = Q->front->next;
72     free(Q->front);
73     Q->front = nextNode;
74     Q->queueSize--;
75 }
76 
77 int main()
78 {
79         LPQUEUE Q = (LPQUEUE)malloc(sizeof(QUEUE));
80             CreateQueue(Q);
81             push(Q, 1);
82             push(Q, 2);
83             push(Q, 3);
84             while (!IsEmptyQueue(Q))
85             {
86                 printf("%d", getfront(Q));
87                 pop(Q);
88             }
89             system("pause");
90 
91 }
View Code

数据结构代码练习
 1 //数组实现栈
 2 #include <stdio.h>
 3 #include<stdlib.h>
 4 #include<malloc.h>
 5 
 6 #define MAXSIZE 10
 7 
 8 typedef struct arraystack {
 9 
10     int* stack;
11     int top;
12 }STACK,*LPSTACK;
13 //创建过程--初始化基本数据成员
14 void CreateStack(LPSTACK S)
15 {
16     S->stack = (int*)malloc(sizeof(int) * MAXSIZE);
17     if (S->stack == NULL)
18     {
19         printf("创建失败\n");
20     }
21     S->top = -1;
22 }
23 
24 //判断是否为空;
25 
26 int IsEmptyStack(LPSTACK S)
27 {
28     if (S->top == -1)
29         return 1;
30         return 0;
31 }
32 //入栈
33 void push(LPSTACK S, int theElement) {
34     
35     if (S->top == MAXSIZE - 1)
36     {
37         printf("栈满无法入栈\n");
38         exit(0);
39     }
40     S->stack[++S->top] = theElement;
41 }
42 
43 void pop(LPSTACK S)
44 {
45     if (IsEmptyStack(S))
46     {
47         printf("无法出栈,栈为空\n");
48     }
49     S->stack[--S->top];
50 }
51 int getTop(LPSTACK S)
52 {
53     if (IsEmptyStack(S))
54     {
55 
56         printf("无法出栈,栈为空\n");
57         return -1;
58     }
59 
60     return S->stack[S->top];
61 
62 }
63 
64 int main()
65 {
66     LPSTACK S = (LPSTACK)malloc(sizeof(STACK));
67     CreateStack(S);
68     push(S, 1);
69     push(S, 2);
70     push(S, 3);
71     while (!IsEmptyStack(S))
72     {
73         printf("%d", getTop(S));
74         pop(S);
75     }
76     return 0;
77 }
View Code

单链表创建,打印,删除以及插入

 

数据结构代码练习
  1 //单向链表创建
  2 
  3 
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 
  7 struct link* AppendNode(struct link* head);
  8 void DisplyNode(struct link* head);
  9 void DeletMemory(struct link* head);
 10 
 11 struct link
 12 {
 13     int data;
 14     struct link* next;
 15 };
 16 
 17 int main(void)
 18 {
 19     int i = 0;
 20     char c;
 21     struct link* head = NULL;    //链表头指针
 22     printf("Do you want to append a new node(Y/N)?");
 23     scanf_s(" %c", &c);
 24     while (c == 'Y' || c == 'y')
 25     {
 26         head = AppendNode(head);//向head为头指针的链表末尾添加节点
 27         DisplyNode(head);        //显示当前链表中的各节点的信息
 28         printf("Do your want to append a new node(Y/N)");
 29         scanf_s(" %c", &c);
 30         i++;
 31     }
 32     printf("%d new nodes have been apended", i);
 33     DeletMemory(head);    //释放所有动态分配的内存
 34 
 35     return 0;
 36 }
 37 /* 函数功能:新建一个节点并添加到链表末尾,返回添加节点后的链表的头指针 */
 38 struct link* AppendNode(struct link* head)
 39 {
 40     struct link* p = NULL, * pr = head;
 41     int data;
 42     p = (struct link*)malloc(sizeof(struct link));//让p指向新建的节点
 43     if (p == NULL)        //若新建节点申请内存失败,则退出程序
 44     {
 45         printf("No enough memory to allocate\n");
 46         exit(0);
 47     }
 48     if (head == NULL)    //若原链表为空表
 49     {
 50         head = p;        //将新建节点置为头节点
 51     }
 52     else                //若原链表为非空,则将新建节点添加到表尾
 53     {
 54         while (pr->next != NULL)//若未到表尾,则移动pr直到pr指向表尾
 55         {
 56             pr = pr->next;        //让pr指向下一个节点
 57         }
 58         pr->next = p;            //让末节点的指针指向新建的节点
 59     }
 60     printf("Input node data\n");
 61     scanf_s("%d", &data); //输入节点数据
 62     p->data = data;        //将新建节点的数据域赋值为输入的节点数据值
 63     p->next = NULL;        //将新建的节点置为表尾
 64     return head;        //返回添加节点后的链表的头指针
 65 }
 66 /* 函数的功能:显示链表中所有节点的节点号和该节点中的数据项的内容*/
 67 void DisplyNode(struct link* head)
 68 {
 69     struct link* p = head;
 70     int j = 1;
 71     while (p != NULL)  //若不是表尾,则循环打印节点的数值
 72     {
 73         printf("%5d%10d\n", j, p->data);//打印第j个节点数据
 74         p = p->next;  //让p指向下一个节点
 75         j++;
 76     }
 77 }
 78 //函数的功能:释放head所指向的链表中所有节点占用的内存
 79 void DeletMemory(struct link* head)
 80 {
 81     struct link* p = head, * pr = NULL;
 82     while (p != NULL)  //若不是表尾,则释放节点占用的内存
 83     {
 84         pr = p;        //在pr中保存当前节点的指针
 85         p = p->next;//让p指向下一个节点
 86         free(pr);    //释放pr指向的当前节点占用的内存
 87     }
 88 }
 89 //单向链表的删除操作实现
 90 struct link* DeleteNode(struct link* head, int nodeData)
 91 {
 92     struct link* p = head, * pr = head;
 93 
 94     if (head == NULL)
 95     {
 96         printf("Linked table is empty!\n");
 97         return 0;
 98     }
 99     while (nodeData != p->data && p->next != NULL)
100     {
101         pr = p;            /* pr保存当前节点 */
102         p = p->next;    /* p指向当前节点的下一节点 */
103     }
104     if (nodeData == p->data)
105     {
106         if (p == head)    /* 如果待删除为头节点 (注意头指针和头结点的区别)*/
107         {
108             head = p->next;
109         }
110         else            /* 如果待删除不是头节点 */
111         {
112             pr->next = p->next;
113         }
114         free(p);        /* 释放已删除节点的内存 */
115     }
116     else            /* 未发现节点值为nodeData的节点 */
117     {
118         printf("This Node has not been found");
119     }
120 
121     return head;
122 }
123 
124 /* 函数功能:向单向链表中插入数据 按升序排列*/
125 struct link* InsertNode(struct link* head, int nodeData)
126 {
127     struct link* p = head, * pr = head, * temp = NULL;
128 
129     p = (struct link*)malloc(sizeof(struct link));
130     if (p == NULL)
131     {
132         printf("No enough meomory!\n");
133         exit(0);
134     }
135     p->next = NULL;        /* 待插入节点指针域赋值为空指针 */
136     p->data = nodeData;
137 
138     if (head == NULL)    /* 若原链表为空 */
139     {
140         head = p;        /* 插入节点作头结点 */
141     }
142     else        /* 原链表不为空 */
143     {
144         while (pr->data < nodeData && pr->next != NULL)
145         {
146             temp = pr;        /* 保存当前节点的指针 */
147             pr = pr->next;    /* pr指向当前节点的下一节点 */
148         }
149         if (pr->data >= nodeData)
150         {
151             if (pr == head)        /* 在头节点前插入新节点 */
152             {
153                 p->next = head;    /* 新节点指针域指向原链表头结点 */
154                 head = p;        /* 头指针指向新节点 */
155             }
156             else
157             {
158                 pr = temp;
159                 p->next = pr->next;        /* 新节点指针域指向下一节点 */
160                 pr->next = p;            /* 让前一节点指针域指向新节点 */
161             }
162         }
163         else        /* 若在表尾插入新节点 */
164         {
165             pr->next = p;    /* 末节点指针域指向新节点*/
166         }
167     }
168 
169     return head;
170 }
171 
172 
173 //有表头结点
174 #include <stdio.h>
175 #include <stdlib.h>
176 
177 struct link* AppendNode(struct link* head);
178 void DisplyNode(struct link* head);
179 void DeletMemory(struct link* head);
180 struct link* init(struct link* head);
181 
182 struct link
183 {
184     int data;
185     struct link* next;
186 };
187 int main(void)
188 {
189     int i = 0;
190     char c;
191     struct link* head = NULL;        //链表头指针
192 
193     head = init(head);        /* 初始化队列 */
194     printf("Do you want to append a new node(Y/N)?");
195     scanf_s(" %c", &c);   //%c前有一个空格
196     while (c == 'Y' || c == 'y')
197     {
198         head = AppendNode(head);//向head为头指针的链表末尾添加节点
199         DisplyNode(head);        //显示当前链表中的各节点的信息
200         printf("Do your want to append a new node(Y/N)");
201         scanf_s(" %c", &c);        //%c前有一个空格
202         i++;
203     }
204     printf("%d new nodes have been apended", i);
205     DeletMemory(head);    //释放所有动态分配的内存
206 
207     return 0;
208 }
209 
210 //函数功能:初始化链表,即新建一个头结点(此处头结点不放数据,原则上不放,实际还是可以放数据)
211 struct link* init(struct link* head)
212 {
213     struct link* p = NULL;
214 
215     p = (struct link*)malloc(sizeof(struct link));
216     if (p == NULL)
217     {
218         printf("初始化链表失败\n");
219         exit(0);
220     }
221     head = p;
222     p->next = NULL;
223 
224     return head;
225 }
226 
227 //函数功能:新建一个节点并添加到链表末尾,返回添加节点后的链表的头指针
228 struct link* AppendNode(struct link* head)
229 {
230     struct link* p = NULL, * pr = head;
231     int data;
232     p = (struct link*)malloc(sizeof(struct link));//让p指向新建的节点
233     if (p == NULL)        //若新建节点申请内存失败,则退出程序
234     {
235         printf("No enough memory to allocate\n");
236         exit(0);
237     }
238     if (head->next == NULL)    //若原链表为空表(只有头节点,头节点不存储数据为空表)
239     {
240         printf("Input node data");
241         scanf_s("%d", &data);
242         head->next = p;        /* 让头结点的指针指向新建节点 */
243         p->data = data;
244         p->next = NULL;        /* 新建结点置为表尾 */
245         return head;
246     }
247     else    //若原链表为非空,则将新建节点添加到表尾
248     {
249         while (pr->next != NULL)//若未到表尾,则移动pr直到pr指向表尾
250         {
251             pr = pr->next;    //让pr指向下一个节点
252         }
253         pr->next = p;        //让末节点的指针指向新建的节点
254 
255         printf("Input node data");
256         scanf_s("%d", &data); //输入节点数据
257         p->data = data; //将新建节点的数据域赋值为输入的节点数据值
258         p->next = NULL;//将新建的节点置为表尾
259         return head;  //返回添加节点后的链表的头指针
260     }
261 }
262 //函数的功能:显示链表中所有节点的节点号和该节点中的数据项的内容
263 void DisplyNode(struct link* head)
264 {
265     struct link* p = head;
266     int j = 1;
267 
268     p = p->next;
269     while (p != NULL)  //若不是表尾,则循环打印节点的数值
270     {
271         printf("%5d%10d\n", j, p->data);//打印第j个节点数据
272         p = p->next;  //让p指向下一个节点
273         j++;
274     }
275 }
276 //函数的功能:释放head所指向的链表中所有节点占用的内存
277 void DeletMemory(struct link* head)
278 {
279     struct link* p = head, * pr = NULL;
280     while (p != NULL)  //若不是表尾,则释放节点占用的内存
281     {
282         pr = p;  //在pr中保存当前节点的指针
283         p = p->next;//让p指向下一个节点
284         free(pr); //释放pr指向的当前节点占用的内存
285     }
286 }
View Code

 双向循环链表

数据结构代码练习
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 //代码量
 4 struct doubleList
 5 {
 6     int data;
 7     struct doubleList* front;
 8     struct doubleList* tail;
 9 };
10 
11 struct doubleList* createList()
12 {
13     //环 
14     struct doubleList* headNode = (struct doubleList*)malloc(sizeof(struct doubleList));
15     headNode->front = headNode->tail = headNode;
16     return headNode;
17 }
18 struct doubleList* createNode(int data)
19 {
20     struct doubleList* newNode = (struct doubleList*)malloc(sizeof(struct doubleList));
21     //创建过程--->描述最初状态--->初始化结构变量中的成员
22     newNode->data = data;
23     newNode->front = NULL;
24     newNode->tail = NULL;
25     return newNode;
26 }
27 
28 void insertNodeByHeadOrTail(struct doubleList* headNode, int data)
29 {
30     struct doubleList* newNode = createNode(data);
31     //采用表尾插入
32     struct doubleList* tailNode = headNode->front;
33     tailNode->tail = newNode;
34     newNode->front = tailNode;
35     headNode->front = newNode;
36     newNode->tail = headNode;
37 }
38 void printList(struct doubleList* headNode)
39 {
40     struct doubleList* pMove = headNode->tail;
41     while (pMove->front != headNode->front)
42     {
43         printf("%d->", pMove->data);
44         pMove = pMove->tail;
45     }
46     printf("\n"); 
47 }
48 
49 void  deleteListTailNode(struct doubleList * headNode)
50 {
51     //一定要判断是否为空
52     struct doubleList* tailNode = headNode->front;
53     //上一个结点是:tailNode->front;
54     tailNode->front->tail = headNode;
55     headNode->front = tailNode->front;
56     free(tailNode);
57 }
58 
59 
60 int main()
61 {
62     struct doubleList* list = createList();
63     insertNodeByHeadOrTail(list, 1);
64     insertNodeByHeadOrTail(list, 2);
65     insertNodeByHeadOrTail(list, 3);
66     printList(list);
67     deleteListTailNode(list);
68     printList(list);
69     deleteListTailNode(list);
70     printList(list);
71     deleteListTailNode(list);
72     printList(list);
73     system("pause");
74     return 0;
75 }
View Code

 

 

 

 

 链式栈

数据结构代码练习
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define Empty 0        /* 栈空 */
  4 #define Avail 1        /* 栈可用 */
  5 
  6 typedef struct SNode
  7 {
  8     int data;
  9     struct SNode *next;
 10 }StackNode;
 11 typedef struct LStack
 12 {
 13     StackNode *top;        /* 栈顶指针 */
 14     StackNode *bottom;    /* 栈底指针 */
 15     int height;            /* 链式栈高度 */
 16 }LinkStack;
 17 
 18 LinkStack InitStack (LinkStack pStack);    /* 栈顶指针、栈底指针、栈高度初始化*/
 19 LinkStack Push (LinkStack pStack);        /* 入栈 */
 20 LinkStack Pop (LinkStack pStack);        /* 出栈 */
 21 int StackEmpty (LinkStack pStack);        /* 判断栈是否为空 */
 22 LinkStack DeletStack (LinkStack pStack);/* 清空栈 */
 23 void DisplyStack (LinkStack pStack);    /* 遍历栈----自顶至底*/
 24 
 25 int main()
 26 {
 27     LinkStack p;
 28     char ch;
 29 
 30     p.height = 0;        /* 栈高度初始化为零 */
 31     p = InitStack (p); /* 栈初始化 */
 32     printf("Do you want to push stack(Y/N)?");
 33     scanf(" %c", &ch);
 34     while (ch == 'Y' || ch == 'y')
 35     {
 36         p = Push(p);    /* 入栈 */
 37         DisplyStack(p);    /* 遍历栈 */
 38         printf("Do you want to push stack(Y/N)?");
 39         scanf(" %c", &ch);
 40     }
 41     printf("Do you want to pop stack(Y/N)?");
 42     scanf(" %c", &ch);
 43     while (ch == 'Y' || ch == 'y')
 44     {
 45         p = Pop(p);        /* 出栈 */
 46         DisplyStack(p);    /* 遍历栈 */
 47         printf("Do you want to pop stack(Y/N)?");
 48         scanf(" %c", &ch);
 49     }
 50 
 51     return 0;
 52 }
 53 /* Function: 初始化栈顶、栈底、栈高度*/
 54 LinkStack InitStack (LinkStack pStack)
 55 {
 56     pStack.top = pStack.bottom = NULL;
 57     pStack.height = 0;
 58 
 59     return pStack;
 60 }
 61 
 62 /* Function: 判断栈是否为空 */
 63 int StackEmpty (LinkStack pStack)
 64 {
 65     if (pStack.top == NULL && pStack.bottom == NULL)
 66     {
 67         return Empty;
 68     }
 69     else
 70     {
 71         return Avail;
 72     }
 73 }
 74 
 75 /* Function: 入栈 */
 76 LinkStack Push (LinkStack pStack)
 77 {
 78     int data;
 79     StackNode *temp;
 80 
 81     if ((temp = (StackNode *)malloc(sizeof(StackNode))) == NULL)
 82     {
 83         printf("内存空间不足\n");
 84         return pStack;
 85     }
 86     if (StackEmpty(pStack) == Empty)    /* 如果栈为空 */
 87     {
 88         pStack.top = pStack.bottom = temp;    /* 栈顶、栈底指针都指向新建节点 */
 89         temp->next = NULL;                /* 节点指针域为空 */
 90         printf("Please input data");
 91         scanf("%d", &data);
 92         pStack.top->data = data;
 93         pStack.height++;
 94 
 95         return pStack;
 96     }
 97     else        /* 栈不为空 */
 98     {
 99         temp->next = pStack.top;/* 新建节点指向原来的栈顶 */
100         pStack.top = temp;        /* 栈顶指针指向新建节点 */
101         printf("Please input data");
102         scanf("%d", &data);
103         pStack.top->data = data;
104         pStack.height++;
105 
106         return pStack;
107     }
108 }
109 
110 /* Function: 出栈 */
111 LinkStack Pop (LinkStack pStack)
112 {
113     StackNode *Second;
114 
115 
116     if (StackEmpty(pStack) == Empty)    /* 判断栈是否为空 */
117     {
118         printf("栈为空,无法出栈\n");
119         return pStack;
120     }
121     if (pStack.top == pStack.bottom)    /* 如果出栈的元素为最后一个元素 */
122     {
123         printf("出栈元素为%d\n", pStack.top->data);
124         free(pStack.top);
125         pStack.top = pStack.bottom = NULL; /* 栈顶、栈底都指针都置为空 */
126         pStack.height--;
127 
128         return pStack;
129     }
130     printf("出栈元素为%d\n", pStack.top->data);
131     Second = pStack.top->next;    /* 指向栈顶的前一个元素*/
132 
133     free(pStack.top);    /* 释放栈顶节点 */
134     pStack.top = Second;/* 将头指针移动到新的栈顶节点 */
135     pStack.height--;
136 
137     return pStack;
138 }
139 
140 /* Function: 遍历栈 自顶到底*/
141 void DisplyStack (LinkStack pStack)
142 {
143     if (StackEmpty(pStack) == Empty)
144     {
145         printf("栈为空,无法遍历\n");
146         return ;
147     }
148     printf("栈中元素[");
149     while (pStack.top != NULL)
150     {
151         printf("%d->", pStack.top->data);
152         pStack.top = pStack.top->next;
153     }
154     printf("]\n");
155 }
156 
157 /* Function: 清空栈 */
158 LinkStack DeletStack (LinkStack pStack)
159 {
160     StackNode *del;
161 
162     while (pStack.top != NULL)
163     {
164         del = pStack.top->next;    /* 栈顶节点的前一个节点 */
165         free(pStack.top);        /* 释放节点 */
166         pStack.top = del;        /* 栈顶指针移动到新栈顶 */
167     }
168 
169     return pStack;
170 }
View Code

 

上一篇:算法笔记--栈


下一篇:数据结构与算法(23)——表达式解析