「C語言」單鏈表/雙向鏈表的建立/遍歷/插入/刪除，單鏈表遍歷

「C語言」單鏈表/雙向鏈表的建立/遍歷/插入/刪除，單鏈表遍歷

    最近臨近期末的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呢（指向上面的結點和指向下面的結點）？

    這樣就構成了形象的二維鏈表而不是一維鏈表了。

    當然，在物理內存上這些鏈表依然是線性關系。

    理論可以實現，那麼三維鏈表呢？

    畫面太美，有待自己下學期大二學數據結構的時候再拓展。