(•̀ᴗ•́)و ̑̑ 單鏈表/雙向鏈表的建立/遍歷/插入/刪除實例 迴圈鏈表的概念 ...
最近臨近期末的C語言課程設計比平時練習作業一下難了不止一個檔次，第一次接觸到了C語言的框架開發，瞭解了View（界面層）、Service（業務邏輯層）、Persistence（持久化層）的分離和耦合，一種面向過程的MVC的感覺。
而這一切的基礎就在於對鏈表的創建、刪除、輸出、寫入文件、從文件讀出......
本篇文章在於鞏固鏈表的基礎知識（整理自《C語言程式設計教程--人民郵電出版社》第十章——指針與鏈表），只對鏈表的概念及增刪改查作出探討，歡迎指教。
一、鏈表結構和靜態/動態鏈表
二、單鏈表的建立與遍歷
三、單鏈表的插入與刪除
四、雙向鏈表的概念
五、雙向鏈表的建立與遍歷
六、雙向鏈表的元素查找
七、迴圈鏈表的概念
八、合併兩個鏈表的實例
九、影片信息管理系統
拓展思維、拉到最後去看看 (•̀ᴗ•́)و ̑̑
一、鏈表結構和靜態/動態鏈表
鏈表是一種常見的數據結構——與數組不同的是：
1.數組首先需要在定義時聲明數組大小，如果像這個數組中加入的元素個數超過了數組的長度時，便不能正確保存所有內容；鏈表可以根據大小需要進行拓展。
2.其次數組是同一數據類型的元素集合，在記憶體中是按一定順序連續排列存放的；鏈表常用malloc等函數動態隨機分配空間，用指針相連。
鏈表結構示意圖如下所示：
在鏈表中，每一個元素包含兩個部分；數據部分和指針部分。數據部分用來存放元素所包含的數據，指針部分用來指向下一個元素。最後一個元素的指針指向NULL，表示指向的地址為空。整體用結構體來定義，指針部分定義為指向本結構體類型的指針類型。
靜態鏈表需要數組來實現，即把線性表的元素存放在數組中。數組單元存放鏈表結點，結點的鏈域指向下一個元素的位置，即下一個元素所在數組單元的下標。這些元素可能在物理上是連續存放的，也有可能是不連續的，它們之間通過邏輯關係來連接——這就要涉及到數組長度定義的問題，實現無法預知定義多大的數組，動態鏈表隨即出現。
動態鏈表指在程式執行過程中從無到有地建立起一個鏈表，即一個一個地開闢結點和輸入各結點的數據，並建立起前後相連的關係。
二、單鏈表的建立與遍歷
單鏈表中，每個結點只有一個指針，所有結點都是單線聯繫，除了末為結點指針為空外，每個結點的指針都指向下一個結點，一環一環形成一條線性鏈。
接下來在源碼中建立並遍歷輸出一個單鏈表。
#include <stdio.h> #include <stdlib.h> #include <malloc.h> /*單向鏈表*/ struct Student/*建立學生信息結構體模型*/ { char cName[20];/*學生姓名*/ int iNumber;/*學生學號*/ struct student *next;/*指向本結構體類型的指針類型*/ }; int iCount;/*全局變數表示鏈表長度*/ struct Student *Create();/*創建鏈表函數聲明*/ void print(struct Student *);/*遍歷輸出鏈表函數聲明*/ int main() { int insert_n=2;/*定義並初始化要插入的結點號*/ int delete_n=2;/*定義並初始化要刪除的結點號*/ struct Student *pHead;/*聲明一個指向學生信息結構體的指針作pHead為頭結點傳遞*/ pHead=Create();/*創建鏈表，返回鏈表的頭指針給pHead*/ print(pHead);/*將指針pHead傳入輸出函數遍歷輸出*/ return 0; } struct Student *Create() { struct Student *pHead=NULL;/*初始化鏈表，頭指針為空*/ struct Student *pEnd,*pNew; iCount=0;/*初始化鏈表長度*/ pEnd=pNew=(struct Student *)malloc(sizeof(struct Student));/*動態開闢一個學生信息結構體類型大小的空間，使得pEnd和pNew同時指向該結構體空間*/ scanf("%s",pNew->cName);/*從輸入流獲取第一個學生姓名*/ scanf("%d",&pNew->iNumber);/*從輸入流獲取第一個學生學號*/ while(pNew->iNumber!=0)/*設定迴圈結束條件——學號不為0時*/ { iCount++;/*鏈表長度+1，即學生信息個數+1*/ if(iCount==1)/*如果鏈表長度剛剛加為1，執行*/ { pNew->next=pHead;/*使指針指向為空*/ pEnd=pNew;/*跟蹤新加入的結點*/ pHead=pNew;/*頭結點指向首結點*/ } else/*如果鏈表已經建立，長度大於等於2時，執行*/ { pNew->next=NULL;/*新結點的指針為空*/ pEnd->next=pNew;/*原來的結點指向新結點*/ pEnd=pNew;/*pEnd指向新結點*/ } pNew=(struct Student *)malloc(sizeof(struct Student));/*再次分配結點的記憶體空間*/ scanf("%s",pNew->cName);/*從輸入流獲取第一個學生姓名*/ scanf("%d",&pNew->iNumber);/*從輸入流獲取第一個學生學號*/ } free(pNew);/*釋放結點空間*/ return pHead;/*返回創建出的頭指針*/ } void print(struct Student *pHead) { struct Student *pTemp;/*定義指向一個學生信息結構體類型的臨時指針*/ int iIndex=1;/*定義並出事哈變數iIndex，用來標識第幾個學生（信息）*/ printf("總共%d個學生（信息）：\n",iCount); pTemp=pHead;/*指針得到首結點的地址*/ while(pTemp!=NULL)/*當臨時指針不指向NULL時*/ { printf("第%d個學生信息：\n",iIndex); printf("姓名：%s",pTemp->cName); /*輸出姓名*/ printf("學號：%d",pTemp->iNumber);/*輸出學號*/ pTemp=pTemp->next;/*移動臨時指針到下一個結點*/ iIndex++;/*進行自加運算*/ } }
三、單鏈表的插入與刪除
在本實例中，插入時根據傳遞來的學號，插入到其後。
刪除時根據其所在鏈表的位置，刪除並釋放該空間。
主函數增加如下：
int main() { int insert_n=2;/*定義並初始化要插入的結點號*/ int delete_n=2;/*定義並初始化要刪除的結點號*/ struct Student *pHead;/*聲明一個指向學生信息結構體的指針作pHead為頭結點傳遞*/ pHead=Create();/*創建鏈表，返回鏈表的頭指針給pHead*/ pHead=Insert(pHead,insert_n);/*將指針pHead和要插入的結點數傳遞給插入函數*/ print(pHead);/*將指針pHead傳入輸出函數遍歷輸出*/ Delete(pHead,delete_n);/*將指針pHead和要刪除的結點數傳遞給刪除函數*/ print(pHead);/*將指針pHead傳入輸出函數遍歷輸出*/ return 0; }
插入函數：
struct Student *Insert(struct Student *pHead,int number) { struct Student *p=pHead,*pNew;/*定義pNew指向新分配的空間*/ while(p&&p->iNumber!=number) p=p->next;/*使臨時結點跟蹤到要插入的位置（該實例必須存在學號為number的信息，插入其後，否則出錯）*/ printf("姓名和學號：\n"); /*分配記憶體空間，返回該記憶體空間的地址*/ pNew=(struct Student *)malloc(sizeof(struct Student)); scanf("%s",pNew->cName); scanf("%d",&pNew->iNumber); pNew->next=p->next;/*新結點指針指向原來的結點*/ p->next=pNew;/*頭指針指向新結點*/ iCount++;/*增加鏈表結點數量*/ return pHead;/*返回頭指針*/ }
刪除函數：
void Delete(struct Student *pHead,int number) { int i; struct Student *pTemp;/*臨時指針*/ struct Student *pPre;/*表示要刪除結點前的結點*/ pTemp=pHead;/*得到鏈表的頭結點*/ pPre=pTemp; for(i=0;i<number;i++) {/*通過for迴圈使得Temp指向要刪除的結點*/ pPre=pTemp; pTemp=pTemp->next; } pPre->next=pTemp->next;/*連接刪除結點兩邊的結點*/ free(pTemp);/*釋放要刪除結點的記憶體空間*/ iCount--;/*減少鏈表中的結點個數*/ }
四、雙向鏈表的概念
雙向鏈表基於單鏈表。單鏈表是單向的，有一個頭結點，一個尾結點，要訪問任何結點，都必須知道頭結點，不能逆著進行。而雙鏈表添加了一個指針域，通過兩個指針域，分別指向結點的前結點和後結點。這樣的話，可以通過雙鏈表的任何結點，訪問到它的前結點和後結點。
在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接後繼結點的地址，一般稱為右鏈域；一個存儲直接前驅結點地址，一般稱之為左鏈域。
雙向鏈表結構示意圖：
五、雙向鏈表的建立與遍歷
雙向鏈表的源碼實戰和單鏈表類似，只是多了第二個指針域的控制，這裡直接貼上沒有註釋的源代碼。
#include <stdio.h>
#include <stdlib.h> #include <malloc.h> #define N 10 typedef struct Node { char name[20]; struct Node *llink,*rlink; }STUD; STUD *creat(int);void print(STUD *); int main() { int number; char studname[20]; STUD *head,*searchpoint; number=N; head=creat(number); print(head); printf("請輸入你要查找的人的姓名："); scanf("%s",studname); searchpoint=search(head,studname); printf("你所要查找的人的姓名是：%s",*&searchpoint->name); return 0; } STUD *creat(int n) { STUD *p,*h,*s; int i; if((h=(STUD *)malloc(sizeof(STUD)))==NULL) { printf("不能分配記憶體空間"); exit(0); } h->name[0]='\0'; h->llink=NULL; h->rlink=NULL; p=h; for(i=0;i<n;i++) { if((s=(STUD *)malloc(sizeof(STUD)))==NULL) { printf("不能分配記憶體空間"); exit(0); } p->rlink=s; printf("請輸入第%d個人的姓名",i+1); scanf("%s",s->name); s->llink=p; s->rlink=NULL; p=s; } h->llink=s; p->rlink=h; return(h); }
void print(STUD *h) { int n; STUD *p; p=h->rlink; printf("數據信息為：\n"); while(p!=h) { printf("%s ",&*(p->name)); p=p->rlink; } printf("\n"); }
六、雙向鏈表的元素查找
查找函數 STUD *search(STUD *,char *);
STUD *search(STUD *h,char *x) { STUD *p; char *y; p=h->rlink; while(p!=h) { y=p->name; if(strcmp(y,x)==0) return(p); else p=p->rlink; } printf("沒有查到該數據！"); }
七、迴圈鏈表的概念
類似於單鏈表，迴圈鏈表也是一種鏈式的存儲結構，由單鏈表演化而來。
單鏈表的最後一個結點的指針指向NULL，而迴圈鏈表的最後一個結點的指針指向鏈表頭結點。
這樣頭尾相連，形成了一個環形的數據鏈。
迴圈鏈表的建立不需要專門的頭結點。
判斷迴圈鏈表是否為尾結點時，只需判斷該節點的指針域是否指向鏈表頭節點。
八、合併兩個鏈表的實例
建立兩個帶頭節點的學生鏈表，每個節點包含學號、姓名和成績，鏈表都按學號升序排列，將它們合併為一個鏈表仍按學號升序排列。
演算法分析：
合併鏈表用merge()函數實現。函數中定義3個工作指針a、b、c，其中a、b分別指向La鏈表、Lb鏈表的當前結點，C指向合併後的鏈表尾結點。合併後鏈表的頭結點共用La鏈表的頭結點。
①合併前，先讓a和b分別指向兩個鏈表的第一個結點，c指向La鏈表的頭結點。
②合併時應該分3種情況討論，即La和Lb都沒有處理完；La沒處理完，但Lb處理完畢；Lb沒處理完，但La處理完畢。
③合併過程中應始終將La和Lb鏈表中較小的一個鏈接在Lc中，方能保持有序。
void merge(struct stud *La,struct stud *Lb) { struct stud *a,*b,*c; c=La; a=La->next;/* 合併前 */ b=Lb->next; while(a!=NULL && b!=NULL)/* La和Lb都沒處理完 */ { if(a->num <= b->num) { c->next=a; c=a; a=a->next; } else { c->next=b; c=b; b=b->next; } } if(a!=NULL) c->next=a;/* 若La沒有處理完 */ else c->next=b;/* 若Lb沒有處理完 */ free(Lb); /* 釋放Lb的頭結點 */ }
九、影片信息管理系統
拓展思維、(•̀ᴗ•́)و ̑̑
既然雙向鏈表可以多出一個指針域用來指向前一個結點，用llink和rlink區分這兩個指針域；
那麼有沒有可能再多幾個指針域來放ulink和dlink呢（指向上面的結點和指向下麵的結點）？
這樣就構成了形象的二維鏈表而不是一維鏈表了。
當然，在物理記憶體上這些鏈表依然是線性關係。
理論可以實現，那麼三維鏈表呢？
畫面太美，有待自己下學期大二學數據結構的時候再拓展。
