資料結構-鏈表
新手學習，代碼還很死板，不靈活，期待改進，
環境：vc6
語言：c
運行結果： $ 為結束符號，不會讀入$
qwe$ 全部元素為:qwe 一共有:3個元素 查找節點的內容,元素序號為:2 2:w 查找節點的位置，內容為:e e:3 洗掉節點，節點的位置:1 洗掉內容為：q 剩余元素為:we 在i插入e:2r 全部元素為:wre 排序后元素為:erw 新鏈表q:ert$ q合并p后:全部元素為:erwert Press any key to continue
全部代碼：
1 #include "stdio.h" 2 #include "malloc.h" 3 #include "string.h" 4 5 typedef struct Node 6 { 7 char data; 8 struct Node * next; 9 }Node, *LinkList;/* LinkList為結構指標型別*/ 10 11 //創建一個鏈表 12 LinkList CreateFromHead();//頭插 13 LinkList CreateFromTail(); //尾插/*將新增的字符追加到鏈表的末尾*/ 14 15 int ListLength(LinkList L); //L為帶頭結點的鏈表求長度 16 //查找 17 Node * Get2(LinkList L, int i);//按元素序號查找 18 Node *Locate2(LinkList L,char key);//按元素值查找 19 void Get1(LinkList L, int i);//按元素序號查找 20 void Locate1(LinkList L,char key);//按元素值查找 21 //更改 22 23 //洗掉 24 void DelList(LinkList L,int i,char *e);//洗掉結點 序號 25 //插入 26 void InsList(LinkList L,int i,char e);//插入結點 27 //合并 28 LinkList Merge(LinkList LA, LinkList LB); 29 //排序 30 void sore(LinkList head); 31 //列印 32 void printList(LinkList L); 33 34 //合并 有序 35 LinkList MergeLinkList(LinkList LA, LinkList LB);//兩個從小到大有序鏈表合并成為有序鏈表 LC 36 37 int main() 38 { /* LinkList為結構指標型別*/ 39 Node *p, *q; 40 char c, e; 41 int i; 42 43 p = (Node*)malloc(sizeof(Node)); 44 p = CreateFromTail(); 45 46 printf("全部元素為:"); 47 printList(p); 48 printf("\n一共有:%d個元素\n", ListLength(p)); 49 50 //查找 51 printf("查找節點的內容,元素序號為:"); 52 scanf("%d", &i); 53 Get1(p, i); 54 printf("查找節點的位置，內容為:"); 55 scanf(" %c", &c); 56 Locate1(p,c); 57 //洗掉 58 printf("洗掉節點，節點的位置:"); 59 scanf("%d", &i); 60 DelList(p,i,&e); 61 printf("洗掉內容為：%c\n", e); 62 printf("剩余元素為:"); 63 printList(p); 64 printf("\n"); 65 //插入 66 printf("在i插入e:"); 67 scanf("%d%c", &i, &e); 68 InsList(p,i,e); 69 printf("全部元素為:"); 70 printList(p); 71 printf("\n"); 72 73 //排序 74 sore(p); 75 printf("排序后元素為:"); 76 printList(p); 77 printf("\n"); 78 79 printf("新鏈表q:"); 80 q = (Node*)malloc(sizeof(Node)); 81 q = CreateFromTail(); 82 83 //合并 84 printf("q合并p后:"); 85 //q 為NULL !! 86 p = Merge(p, q); 87 88 printf("全部元素為:"); 89 printList(p); 90 printf("\n"); 91 /* 92 //有序合并 93 p = MergeLinkList(q, p); 94 printf("合并后全部元素為:");//(原來的兩個鏈表本來就有序,p長度短) 95 printList(p); 96 printf("\n"); 97 */ 98 99 return 0; 100 } 101 102 103 104 105 106 //頭插 107 LinkList CreateFromHead() 108 { 109 int flag=1; 110 LinkList L; 111 Node *s; 112 char c; 113 L=(LinkList)malloc(sizeof(Node)); 114 L->next=NULL; 115 116 while(flag) //因為flag是1，所以進入回圈體執行 117 { 118 scanf("%c", &c); 119 //c = getchar(); //假設用戶輸入ab$,首先讀入‘a’ 120 if(c !='$') //‘a’不等于‘$’,因此判斷成立 121 { 122 s=(Node*)malloc(sizeof(Node)); 123 s->data=https://www.cnblogs.com/yvtingwang/p/c; 124 s->next=L->next; 125 L->next=s; 126 } 127 } 128 return L; 129 } 130 //尾插 131 LinkList CreateFromTail() /*將新增的字符追加到鏈表的末尾*/ 132 { 133 char c; 134 LinkList L; 135 Node *r, *s; 136 L=(LinkList)malloc(sizeof(Node)); 137 L->next=NULL; 138 r=L; /*r指標始終動態指向鏈表的當前表尾*/ 139 fflush(stdin); 140 c=getchar(); 141 while(c!='$')/*輸入“$”時flag為0，建表結束*/ 142 { 143 144 s=(LinkList)malloc(sizeof(Node)); 145 s->data=https://www.cnblogs.com/yvtingwang/p/c; 146 r->next=s; 147 r=s; 148 c=getchar(); 149 } 150 r->next=NULL; 151 return L; 152 } 153 //按元素序號查找 154 void Get1(LinkList L, int i) 155 { //假設開始的情況是： 156 Node *p; 157 int j=0; 158 p=L; 159 while((p->next!=NULL)&&(j<i)) 160 { 161 p=p->next; 162 j++; 163 } 164 // p->next是NULL 165 if(i==j) 166 { 167 printf("%d:%c\n", i,p->data); 168 } 169 else //不滿足判斷條件，因此執行else部分 170 printf("未找到"); 171 } 172 173 //按元素值查找 174 void Locate1(LinkList L,char key) 175 { 176 int i = 1; 177 Node *p; 178 p=L->next; 179 while(p !=NULL) 180 { 181 if(p->data != key) 182 { 183 i++; 184 p=p->next; 185 } 186 else 187 { 188 printf("%c:%d\n", key, i); 189 break; 190 } 191 } 192 } 193 194 195 //按元素序號查找 196 Node *Get2(LinkList L, int i) 197 { //假設開始的情況是： 198 Node *p; 199 int j=0; 200 p=L; 201 while((p->next!=NULL)&&(j<i)) 202 { //滿足條件，因此進入回圈體執行 203 p=p->next; 204 j++; 205 } 206 // p->next是NULL，不滿足條件，因此不再執行回圈體 207 if(i==j) 208 { 209 printf("%d:%c\n", i,p->data); 210 return p; 211 } 212 else //不滿足判斷條件，因此執行else部分 213 return NULL; 214 } 215 216 //按元素值查找 217 Node *Locate2(LinkList L,char key) 218 { 219 int i = 1; 220 Node *p; 221 p=L->next; 222 while(p !=NULL) 223 { 224 if(p->data != key) 225 { 226 i++; 227 p=p->next; 228 } 229 else 230 { 231 printf("%c:%d\n", key, i); 232 break; 233 } 234 } 235 return p; 236 } 237 238 //洗掉結點 239 void DelList(LinkList L,int i,char *e) 240 { 241 Node *p,*r; 242 int k =0; 243 p=L; 244 while(p->next != NULL && k < i-1) 245 { 246 p=p->next; 247 k=k+1; 248 } 249 if(k!=i-1) 250 { 251 printf("無此節點"); 252 } 253 else 254 { 255 r=p->next; 256 p->next=p->next->next; 257 *e=r->data;//通過變數e回傳刪掉的元素值 258 free(r); //r這個變數及值都沒有變動，但是不能再使用r指向的那個空間（因為已經釋放）， 259 } 260 } 261 //插入結點 262 void InsList(LinkList L,int i,char e) 263 { 264 Node *pre,*s; 265 int k=0; 266 pre=L; 267 while(pre!=NULL&&k<i-1) /*先找到第i-1個資料元素的存盤位置,使指標pre指向它*/ 268 { 269 pre=pre->next; 270 k=k+1; 271 } 272 if(k!=i-1) 273 { 274 printf("插入位置不合理！"); 275 return; 276 } 277 s=(Node*)malloc(sizeof(Node));/*為e申請一個新的結點*/ 278 s->data=https://www.cnblogs.com/yvtingwang/p/e; /*將待插入結點的值e賦給s的資料域*/ 279 s->next=pre->next; 280 pre->next=s; 281 } 282 283 284 285 //求長度 286 int ListLength(LinkList L) /*L為帶頭結點的鏈表*/ 287 { 288 Node *p; 289 int j=0; /*用來存放鏈表的長度*/ 290 p=L->next; 291 while(p!=NULL) 292 { 293 p=p->next; 294 j++; 295 } 296 return j; 297 } 298 299 300 //合并 301 LinkList Merge(LinkList LA, LinkList LB) 302 { 303 LinkList p; 304 p = LA->next; 305 while(p->next) 306 p = p->next; 307 p->next = LB->next; 308 free(LB); 309 return LA; 310 } 311 //兩個從小到大有序鏈表合并成為有序鏈表 LC 312 LinkList MergeLinkList(LinkList LA, LinkList LB) 313 { 314 Node *pa,*pb; 315 LinkList LC; 316 LinkList r; 317 318 pa=LA->next; 319 pb=LB->next; 320 LC=LA; 321 LC->next=NULL; 322 r=LC; 323 324 while(pa!=NULL && pb!=NULL) 325 { 326 if(pa->data <= pb->data) 327 { 328 r->next=pa; 329 r=pa; 330 pa=pa->next; 331 } 332 else 333 { 334 r->next=pb; 335 r=pb; 336 pb=pb->next; 337 } 338 } 339 if(pa != NULL) 340 r->next=pa; 341 //return NULL; 342 else// 343 r->next=pb; 344 free(LB); 345 return (LC); 346 } 347 /* 348 bcd$ 349 新鏈表q:aef$ 350 合并后全部元素為:abcdef 351 bc$ 352 新鏈表q:adef$ 353 合并后全部元素為:abcdef 354 acdg$ 355 新鏈表q:be$ 356 合并后全部元素為:abcdeg 357 */ 358 //排序 359 void sore(LinkList head) 360 { 361 LinkList pre,cur,next,end, temp; 362 end = NULL; 363 while(head->next != end) 364 { 365 //初始化三個指標 ; 判斷是否到達結束位置 ; 三個指標集體后移 366 for(pre=head,cur=pre->next,next=cur->next; next!=end; pre=pre->next,cur=cur->next,next=next->next) 367 { 368 if(cur->data > next->data) //從小到大 369 { 370 pre->next=next; 371 cur->next=next->next; 372 next->next=cur; 373 //此時next變前一項，cur變后一項 交換next cur 374 temp=cur; 375 cur=next; 376 next=temp; 377 } 378 } 379 //一輪回圈結束 最后一項已經排好 end提前一項 (冒泡原理) 380 end = cur; 381 } 382 } 383 384 void printList(LinkList L) 385 { 386 Node *p = L; 387 while(p->next) 388 { 389 p = p->next; 390 if(p->data >= 'a' || p->data <='z') 391 printf("%c", p->data); 392 //printf(" ", p->data); 393 } 394 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/240743.html
標籤：C
上一篇：C語言中的錯誤處理