//CList.h
//結構體定義以及函數聲明

#ifndef CLIST_H #define CLIST_H#include <stdio.h> #include <assert.h> #include <malloc.h> #include <iostream>typedef int ElemType;typedef struct Node {ElemType data;struct Node *next; }Node, *PNode;typedef struct List {PNode head;PNode tail;int size; }List,*PList;bool InitList(PList list); void Create_t(PList list,ElemType x); //尾插 void Create_h(PList list,ElemType x); //頭插 void del_back(PList list); //尾刪 void del_front(PList list); //頭刪 void sortList(PList list); //排序 void insert_val(PList list,ElemType x); //按值插 PNode find(PList list,ElemType x); void del_val(PList list,ElemType x); void modify(PList list,ElemType x1,ElemType x2); void clear(PList list); void destroy(PList list); void reserve(PList list); int length(PList list); void menu(); void showList(PList list); void show_tail(PList list); ElemType next(PList list,ElemType x); ElemType prio(PList list,ElemType x); PNode prev(PList list,PNode p);#endif

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46

//CList.cpp
//函數實現

#include"CList.h"void menu() //提供選項的菜單函數 {printf("***************************************************************\n");printf("* [0] quit_system [1] Create_t [2] Create_h [3] showList *\n");printf("* [4] del_back [5] del_front [6] insert_val [7] show_tail*\n");printf("* [8] find [9] del_val [10] sortList [11] modify *\n");printf("* [12]clear [13]destroy [14] resver [15]length *\n");printf("* [16] next [17]prio *\n");printf("***************************************************************\n"); } bool InitList(PList list) {list->head = (PNode)malloc(sizeof(Node)); /初始化一個頭結點assert(list->head != NULL); //斷言，表達式為真，接著往下執行list->head->next = list->head; //初始化head和tail指針，使其都指向頭節點list->tail = list->head;list->size = 0; //長度初始化為0return true; }void Create_t(PList list,ElemType x) //尾插法 {PNode s = (PNode)malloc(sizeof(Node));assert(s != NULL);s->data = x; //填充數據域list->tail->next = s; //tail指向最后一個節點，把新建立的節點鏈接到鏈表的最后s->next = list->head; //單循環鏈表，新節點的next指向頭結點 list->tail = s; //改變尾指針的指向list->size++; } void showList(PList list) //鏈表顯示函數 {if(1>list->size){printf("--鏈表為空\n");return ;}PNode p = list->head->next;while(list->head != p) //逐個遍歷鏈表{printf("%d ",p->data);p=p->next;}printf("\n"); } void Create_h(PList list,ElemType x) //頭插法 {PNode s = (PNode)malloc(sizeof(Node));assert(s != NULL);s->data = x; //填充數據域s->next = list->head->next; //新節點指向第一個節點 list->head->next = s; //頭節點的next指向新節點sif(list->size == 0) //如果是第一次頭插，需改變尾指針和尾節點的next指向，之后都不改變{list->tail = s;list->tail->next = list->head; }list->size++; //插入一個，長度加1 }void del_back(PList list) //尾刪 {if(0==list->size)return;PNode p = list->head;while(list->head != p->next->next) //找到倒數第二個節點{p = p->next;} p->next = list->head; //把最后一個節點分離free(list->tail); //釋放最后一個節點list->tail = p; //尾指針指向原來的倒數第二個節點（現在倒數第一）printf("--尾節點已刪除\n");list->size--; }void del_front(PList list) //頭刪 {if(0==list->size)return;else{PNode p = list->head->next;if(1==list->size) { //只有一個節點，若刪去，需改變尾指針list->tail = list->head;list->head->next = list->head;}else{ list->head->next = p->next; //頭指針指向第二個節點 }free(p); //釋放第一個節點} printf("--頭節點已刪除\n");list->size--; }void show_tail(PList list) //為測試尾指針是否正確改變，需顯示最后一個節點 {printf("--鏈表的尾節點是：》%d \n",list->tail->data); }void sortList(PList list) // 對無序鏈表進行從小到大排序 {if(2>list->size)return ;PNode p = list->head->next;PNode q = p->next;for(int i = 0;i<list->size-1;i++,p = list->head->next,q = p->next) //n個數比較n-1趟{for(int j = 0;j<list->size-1-i;j++,p=q,q=q->next) //第i趟比較n-i次{if(p->data > q->data) //如果前面的數大于后面，則交換{p->data = p->data + q->data;q->data = p->data - q->data;p->data = p->data - q->data;}}} }void insert_val(PList list,ElemType x) //鏈表有序的前提下，給一個值插入 {PNode p = list->head->next,q = list->head;while(list->head != p) //找到能插入的位置，會在p、q之間{ if(x<p->data)break;q = p;p = p->next;}PNode s = (PNode)malloc(sizeof(Node)); //初始化新節點s->data = x;q->next = s; //把新節點插入到鏈表中（在p,q之間插入）s->next = p;if(list->head == p) //如果新節點的值最大，即尾插，需改變尾指針和尾節點的next指向{list->tail = s;list->tail->next=list->head;}list->size++; }PNode find(PList list,ElemType x) //返回要查找元素的前面一個的地址 {PNode p = list->head;while(list->tail != p && list->head != p->next && x != p->next->data){p = p->next; //循環結束，p指向x的前面一個元素} if(list->head == p->next) //如果p指向最后一個元素，說明沒有找到{printf("--沒找到！\n");return NULL;}return p; }void del_val(PList list,ElemType x) //刪除指定的值x {if(0 == list->size)return ;PNode p = find(list,x);PNode q = NULL;if(NULL != p){q = p->next; //q指向要刪除的節點 if(q == list->tail) //若刪除最后一個節點，需改變尾指針{p->next = list->head;list->tail = p;}else{p->next = q->next;}free(q); //釋放要刪除的節點list->size--;printf("--%d已刪除!\n",x);}return ; }void modify(PList list,ElemType x1,ElemType x2) //把原有的x1修改成x2 {PNode p = find(list,x1);if(NULL != p)p->next->data = x2;elsereturn ; }void clear(PList list) //刪除鏈表的所有節點，但不刪除頭結點 {PNode p = list->head->next;PNode q = p;while(list->head != p) {p = p->next; //p依次后移，跟屁蟲q依次釋放節點free(q);q = p;}list->tail = list->head; //修改尾指針和鏈表長度list->head->next = list->head;list->size = 0;printf("--鏈表已被清空！\n"); }void destroy(PList list) //摧毀鏈表，包括所有節點和頭結點 {clear(list);free(list->head);list->head = NULL;list->tail = NULL;printf("--鏈表已被摧毀！\n"); }PNode prev(PList list,PNode p) //返回p指向的前面一個節點 {if(p != list->head){PNode q = list->head->next;while(q != list->head && q->next != p) //依次往后移，知道尾指針的前面一個節點q=q->next;if(q->next == p)return q;}return NULL; } void reserve(PList list) //逆置鏈表 {PNode s = (PNode)malloc(sizeof(Node)); //建立一個節點s->next = list->tail;PNode p = list->tail;while(list->tail != list->head->next) //把原鏈表的尾節點到第一個節點依次連接到新節點上{list->tail = prev(list,list->tail);list->tail->next = list->head;p->next = list->tail;p=p->next;}p->next = s; //p指向第一個節點，即新鏈表的最后一個節點，尾指針的next指向頭結點s，鏈表結束free(list->head); //釋放原來的頭結點list->head = s; //把s變成新的頭指針 }int length(PList list) //求鏈表的長度 {return list->size; }ElemType next(PList list,ElemType x) //返回x的后繼 {PNode p = find(list,x); if(NULL == p) return -1;if(p->next == list->tail) //因為是單循環鏈表，尾節點的下一個元素是第一個節點{return list->head->next->data; }p=p->next;return p->next->data; } ElemType prio(PList list,ElemType x) //返回x的前驅 {PNode p = find(list,x);if(NULL != p){if(p == list->head || p == list->tail){return list->tail->data;}return p->data;}return -1; }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106
• 107
• 108
• 109
• 110
• 111
• 112
• 113
• 114
• 115
• 116
• 117
• 118
• 119
• 120
• 121
• 122
• 123
• 124
• 125
• 126
• 127
• 128
• 129
• 130
• 131
• 132
• 133
• 134
• 135
• 136
• 137
• 138
• 139
• 140
• 141
• 142
• 143
• 144
• 145
• 146
• 147
• 148
• 149
• 150
• 151
• 152
• 153
• 154
• 155
• 156
• 157
• 158
• 159
• 160
• 161
• 162
• 163
• 164
• 165
• 166
• 167
• 168
• 169
• 170
• 171
• 172
• 173
• 174
• 175
• 176
• 177
• 178
• 179
• 180
• 181
• 182
• 183
• 184
• 185
• 186
• 187
• 188
• 189
• 190
• 191
• 192
• 193
• 194
• 195
• 196
• 197
• 198
• 199
• 200
• 201
• 202
• 203
• 204
• 205
• 206
• 207
• 208
• 209
• 210
• 211
• 212
• 213
• 214
• 215
• 216
• 217
• 218
• 219
• 220
• 221
• 222
• 223
• 224
• 225
• 226
• 227
• 228
• 229
• 230
• 231
• 232
• 233
• 234
• 235
• 236
• 237
• 238
• 239
• 240
• 241
• 242
• 243
• 244
• 245
• 246
• 247
• 248
• 249
• 250
• 251
• 252
• 253
• 254
• 255
• 256
• 257
• 258
• 259
• 260
• 261
• 262
• 263
• 264
• 265
• 266
• 267
• 268
• 269
• 270
• 271
• 272
• 273
• 274
• 275
• 276
• 277
• 278
• 279
• 280
• 281
• 282
• 283

//main.cpp
//測試函數

#include "CList.h"int main() {List mylist;InitList(&mylist);ElemType item = 0;int pos = 0;int chose = 1;PNode p = NULL;while(chose){menu();printf("給出想要操作的序號：\n");scanf("%d",&chose);switch(chose){case 0:destroy(&mylist);chose = 0;break;case 1:printf("輸入要尾插的數據[-1結束]：\n");while(scanf("%d",&item),item!=-1){Create_t(&mylist,item);}break;case 2:printf("輸入要頭插的數據：\n");while(scanf("%d",&item),item!=-1){Create_h(&mylist,item);}break;case 3:showList(&mylist);break;case 4:del_back(&mylist);break;case 5:del_front(&mylist);break;case 6:printf("給出要插入的數：\n");scanf("%d",&item);insert_val(&mylist,item);break;case 7:show_tail(&mylist);break;case 8:printf("輸入要查找的數：\n");scanf("%d",&item);p = find(&mylist,item);if(NULL!=p)printf("%d\n",p->next->data);break;case 9:printf("輸入要刪除的數：\n");scanf("%d",&item);del_val(&mylist,item);break;case 10:sortList(&mylist);break;case 11:printf("輸入要修改的數和修改后的數\n");scanf("%d %d",&item,&pos);modify(&mylist,item,pos);break;case 12:clear(&mylist);break; case 13:destroy(&mylist);break;case 14:reserve(&mylist);break;case 15:printf("鏈表長度為：%d\n",length(&mylist));break;case 16:printf("輸入想要找哪個一數的后繼：\n");scanf("%d",&item);printf("%d 的后繼是：%d\n",item,next(&mylist,item));break;case 17:printf("輸入想要找哪個一數的前驅：\n");scanf("%d",&item);printf("%d 的前驅是：%d\n",item,prio(&mylist,item));break;default:printf("重新輸入\n");break;} }return 0; }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103

版權聲明：本文為博主原創文章，未經博主允許不得轉載。 http://blog.csdn.net/Chengzi_comm/article/details/51387151

總結

以上是生活随笔為你收集整理的单循环链表（C语言实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。