LoopDLink.cpp 源码 1 /* Copyright (C++) 2019 * Ltd. All rights reserved. 2 * Create date : 2019-08-27 11:41:04 3 *================================================ */ 4 5 /* 6 2018.8.15 7 注意三点： 8 1.不要将循环写成if //很尴尬
LoopDLink.cpp 源码
1 /* Copyright (C++) 2019 * Ltd. All rights reserved. 2 * Create date : 2019-08-27 11:41:04 3 *================================================*/ 4 5 /* 6 2018.8.15 7 注意三点： 8 1.不要将循环写成if //很尴尬，主要是我犯了这个错误，找了半天还没找出来，第二天看的时候才发现，非常的尴尬 9 2.循环链表的判空操作是 p->next != *L 10 3.p = *L，循环体中用p->next做条件 这种写法便于对当前结点的前一结点操作，插入、删除、修改操作使用这种形式 11 p = *L->next，循环体中用p做条件 这种写法便于对当前结点操作，查找、遍历使用这种形式 12 4.双向链表在插入与删除时，要处理好前驱指针和后继指针，切不可遗忘。尤其是插入时，要将新点之后的结点的前驱指向新结点，这里容易被忽略 13 */ 14 15 #include <stdio.h> 16 #include<malloc.h> 17 #include<stdlib.h> 18 #include<time.h> 19 typedef int ElemType; //元素类型 20 typedef int Status; //返回类型 21 #define OK 1; //函数运行成功返回值 22 #define ERROR 0; //函数运行失败返回值 23 24 typedef struct Node 25 { 26 struct Node *prior; //指向前一结点的指针 27 ElemType date; //结点元素 28 struct Node *next; //指向后一结点的指针 29 }Node, *LoopDList; 30 31 32 /* 33 循环双链表的创建 34 */ 35 Status CreatList(LoopDList &L, int *arr, int n) 36 { 37 int i; //计数器 38 L = (LoopDList)malloc(sizeof(Node)); //创建头结点 39 L->next = L; 40 L->prior = L; 41 42 LoopDList s,p; //s用于开辟新结点,p指向表尾 43 p = L; //指向表尾结点 44 45 for(i = 0; i < n; i++) 46 { 47 s = (LoopDList)malloc(sizeof(Node)); //开辟新结点 48 s->date = arr[i]; //为新结点赋值 49 p->next = s; //让表尾结点的后继结点指向新结点 50 s->prior = p; //让新结点的前驱结点指向p 51 p = s; //表尾结点指针后移 52 } 53 p->next = L; //使表尾结点的后继指针指向头结点 54 L->prior = p; //头指针的前驱结点指向表尾结点 55 return OK; 56 } 57 58 /* 59 循环双向链表的插入操作 60 */ 61 Status LoopInsert(LoopDList &L, int i, ElemType e) 62 { 63 int j = 1; //计数器，记录当前位置 64 LoopDList p = L; //指向L //此种写法便于对当前结点的上一结点进行操作 65 LoopDList s; //用于创建新结点 66 // while(p->next && j < i) //判非空 判位置索引合理 //循环链表的判断非空不是这样的 2018.8.15 67 while(p->next != L && j < i) 68 { 69 p = p->next; //指针后移 70 j++; //计数器加1 71 } 72 if(p->next == L || j > i) //判空 判位置索引不合理 73 return ERROR; 74 s = (LoopDList)malloc(sizeof(Node)); //开辟新结点s 75 s->date = e; //为s的数据域赋值 76 77 s->prior = p->prior; 78 s->next = p; 79 p->prior->next = s; 80 p->prior = s; 81 82 83 #if 0 84 p->next->prior= s; //使插入结点后的下一结点的前驱指向s 85 s->next = p->next; //使s的后继结点等于p的后继结点 86 s->prior= p; //使s的前驱结点等于p 87 p->next = s; //使p得后继结点等于s 88 #endif 89 return OK; 90 } 91 92 /* 93 循环双向链表的删除操作 94 */ 95 Status DelList(LoopDList &L, int i, ElemType *e) 96 { 97 int j = 1; //记录当前位置 98 LoopDList p = L; //指向链表 99 LoopDList s; //用于释放要删除的结点 100 while(p->next != L && j < i) //判非空 判索引位置有效 101 { 102 p = p->next; //指针后移 103 j++; //计数器加1 104 } 105 if(p->next == L || j > i) //判空 判索引位置无效 106 return ERROR; 107 s = p->next; //使s指向p 108 *e = s->date; //将要删除的结点数据赋值给e 109 p->next = s->next; //使p的后继结点等于r的后继结点 110 s->next->ppiop = r; //使s的后继的前驱结点等于r 111 free(s); //释放s结点 112 return OK; 113 } 114 115 /* 116 循环双链表的修改操作 117 */ 118 Status UpdateList(LoopDList *L, int i, ElemType e) 119 { 120 int j = 1; //记录当前位置 121 LoopDList r = (*L)->next; //指向第一个结点 //此种写法便于岁当前结点操作 122 while(r != *L && j < i) //判非空 判位置索引有效 123 { 124 r = r->next; //指针后移 125 j++; //计数器加1 126 } 127 if(r == *L || j > i) //判空 判位置索引无效 128 return ERROR; 129 r->date = e; //使r的数据域等于 e 130 return OK; 131 } 132 133 /* 134 循环双链表的查找 135 */ 136 Status GetElem(LoopDList L, int i, ElemType *e) 137 { 138 int j = 0; //计数器 139 LoopDList p = L->next; //指向第一个结点 140 while(p != L && j < i) //判非空 判位置索引有效 141 { 142 p = p->next; //指针后移 143 j++; //计数器加1 144 } 145 if(p == L || j > i) //判空 判位置索引无效 146 return ERROR; 147 *e = p->date; //将p的数据域内容赋值给e 148 return OK; 149 } 150 151 /* 152 循环双链表的正序遍历 153 */ 154 void PrintList1(LoopDList L) 155 { 156 LoopDList p = L->next; //指向L第一个结点 157 if(p == L) //判空 158 printf("表空\n"); 159 while(p != L) //判非空 160 { 161 if(p->next != L) 162 printf("[%d] -> ", p->date); 163 else 164 printf("[%d]",p->date); 165 p = p->next; 166 } 167 printf("\n"); 168 } 169 170 /* 171 循环双链表的倒序遍历 172 */ 173 void PrintList2(LoopDList L) 174 { 175 LoopDList p = L->prior; //指向L倒数第一个结点 176 if(p == L) //判空 177 printf("表空\n"); 178 while(p != L) //判非空 179 { 180 if(p->prior != L) 181 printf("[%d] -> ", p->date); 182 else 183 printf("[%d]",p->date); 184 p = p->prior; 185 } 186 printf("\n"); 187 } 188 189 190 int main() 191 { 192 LoopDList L = NULL; //创建链表L 193 int i, e; //i为元素位置，e为元素内容 194 195 int n = 0; 196 int arr[10] = {0,1,2,3,4,5,6,7,8,9}; 197 n = sizeof(arr)/sizeof(arr[0]); 198 199 200 while(true) 201 { 202 printf("请选择对线性链表的操作：\n"); 203 printf("1.创建\n"); 204 printf("2.插入\n"); 205 printf("3.删除\n"); 206 printf("4.查找\n"); 207 printf("5.修改\n"); 208 printf("6.正序输出\n"); 209 printf("7.倒序输出\n"); 210 printf("8.退出\n"); 211 int a; 212 scanf("%d", &a); 213 switch(a) 214 { 215 case 1: 216 if(CreatList(L, arr, n)) 217 printf("创建成功\n"); 218 else 219 printf("创建失败\n"); 220 break; 221 case 2: 222 printf("请输入需要插入的位置："); 223 scanf("%d", &i); 224 printf("请输入需要插入的元素："); 225 scanf("%d", &e); 226 if(LoopInsert(L, i, e)) 227 printf("插入成功\n"); 228 else 229 printf("插入失败\n"); 230 break; 231 case 3: 232 printf("请输入需要删除的位置："); 233 scanf("%d", &i); 234 if(DelList(&L, i, &e)) 235 printf("删除成功\n"); 236 else 237 printf("删除失败\n"); 238 break; 239 case 4: 240 printf("请输入需要查找的位置："); 241 scanf("%d", &i); 242 GetElem(L, i, &e); 243 printf("第%d个元素为%d\n",i,e); 244 break; 245 case 5: 246 printf("请输入需要修改的位置："); 247 scanf("%d", &i); 248 printf("请输入新的的元素："); 249 scanf("%d", &e); 250 if(UpdateList(&L, i, e)) 251 printf("修改成功\n"); 252 else 253 printf("修改失败\n"); 254 break; 255 case 6: 256 if(L == NULL) 257 { 258 printf("表还未创建\n"); 259 break; 260 } 261 PrintList1(L); 262 break; 263 case 7: 264 if(L == NULL) 265 { 266 printf("表还未创建\n"); 267 break; 268 } 269 PrintList2(L); 270 break; 271 case 8: 272 return -1; 273 default: 274 printf("选择错误\n"); 275 break; 276 } 277 } 278 return 0; 279 }View Code
参考
双链表实现1 实现2
图解链表
循环单链表