鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu)。它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。它可以根據(jù)需要開辟內(nèi)存單元。鏈表有一個(gè)“頭指針”變量，以head表示，它存放一個(gè)地址。該地址指向一個(gè)元素。鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)包括兩個(gè)部分：一為用戶需要用的實(shí)際數(shù)據(jù)，二為下一個(gè)結(jié)點(diǎn)的地址。因此，head指向第一個(gè)元素：第一個(gè)元素又指向第二個(gè)元素；……，直到最后一個(gè)元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個(gè)“NULL”（表示“空地址”），鏈表到此結(jié)束。
        鏈表的各類操作包括：學(xué)習(xí)單向鏈表的創(chuàng)建、刪除、  插入（無序、有序）、輸出、  排序（選擇、插入、冒泡）、反序等等。

       單向鏈表的圖示：
       ---->[NULL]
      head

      圖1：空鏈表

       ---->[p1]---->[p2]...---->[pn]---->[NULL]
      head   p1->next  p2->next   pn->next

      圖2：有N個(gè)節(jié)點(diǎn)的鏈表

      創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表的函數(shù)為：

 

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

 1 #include "stdlib.h" 2 #include "stdio.h" 3  4 #define NULL 0 5 #define LEN sizeof(struct student) 6  7 struct student 8 { 9     int num;              //學(xué)號(hào) 10     float score;          //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段11     struct student *next;        //指向下一節(jié)點(diǎn)的指針12 };13 14 int n;    //節(jié)點(diǎn)總數(shù) 15 /*16 ==========================17 功能：創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表18 返回：指向鏈表表頭的指針19 ==========================20 */21 struct student *Create()22 {23     struct student *head;        //頭節(jié)點(diǎn)24     struct student *p1 = NULL;    //p1保存創(chuàng)建的新節(jié)點(diǎn)的地址25     struct student *p2 = NULL;    //p2保存原鏈表最后一個(gè)節(jié)點(diǎn)的地址26 27     n = 0;            //創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表28     p1 = (struct student *) malloc (LEN);    //開辟一個(gè)新節(jié)點(diǎn)29     p2 = p1;            //如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來以備后用30 31     if(p1==NULL)        //節(jié)點(diǎn)開辟不成功32     {33         printf ("\nCann't create it, try it again in a moment!\n");34         return NULL;35     }36     else                //節(jié)點(diǎn)開辟成功37     {38         head = NULL;        //開始head指向NULL39         printf ("Please input %d node -- num,score: ", n + 1);40         scanf ("%d %f", &(p1->num), &(p1->score));    //錄入數(shù)據(jù)41     }42     while(p1->num != 0)        //只要學(xué)號(hào)不為0，就繼續(xù)錄入下一個(gè)節(jié)點(diǎn)43     {44         n += 1;            //節(jié)點(diǎn)總數(shù)增加1個(gè)45         if(n == 1)        //如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p146         {47             head = p1;48             p2->next = NULL;  //此時(shí)的p2就是p1,也就是p1->next指向NULL。49         }50         else51         {52             p2->next = p1;    //指向上次下面剛剛開辟的新節(jié)點(diǎn)53         }54 55         p2 = p1;            //把p1的地址給p2保留，然后p1產(chǎn)生新的節(jié)點(diǎn)56 57         p1 = (struct student *) malloc (LEN);58         printf ("Please input %d node -- num,score: ", n + 1);59         scanf ("%d %f", &(p1->num), &(p1->score));60     }61     p2->next = NULL;        //此句就是根據(jù)單向鏈表的最后一個(gè)節(jié)點(diǎn)要指向NULL62 63     free(p1);            //p1->num為0的時(shí)候跳出了while循環(huán)，并且釋放p164     p1 = NULL;            //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針65     return head;        //返回創(chuàng)建鏈表的頭指針 66 }

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

 

輸出鏈表中節(jié)點(diǎn)的函數(shù)為：

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

 1 /* 2 =========================== 3  功能：輸出節(jié)點(diǎn) 4  返回： void 5 =========================== 6 */ 7 void Print(struct student *head) 8 { 9     struct student *p;10     printf ("\nNow , These %d records are:\n", n);11     p = head;12     if(head != NULL)        //只要不是空鏈表，就輸出鏈表中所有節(jié)點(diǎn)13     {14         printf("head is %o\n", head);     //輸出頭指針指向的地址15         do16         {17             /*18             輸出相應(yīng)的值：當(dāng)前節(jié)點(diǎn)地址、各字段值、當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)地址。19             這樣輸出便于讀者形象看到一個(gè)單向鏈表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，和我們20             設(shè)計(jì)的圖示是一模一樣的。21             */22             printf ("%o   %d   %5.1f   %o\n", p, p->num, p->score, p->next);23             p = p->next;        //移到下一個(gè)節(jié)點(diǎn)24         }25         while (p != NULL);26     }27 }/*28 ===========================29  功能：輸出節(jié)點(diǎn)30  返回： void31 ===========================32 */33 void Print(struct student *head)34 {35     struct student *p;36     printf ("\nNow , These %d records are:\n", n);37     p = head;38     if(head != NULL)        //只要不是空鏈表，就輸出鏈表中所有節(jié)點(diǎn)39     {40         printf("head is %o\n", head);     //輸出頭指針指向的地址41         do42         {43             /*44             輸出相應(yīng)的值：當(dāng)前節(jié)點(diǎn)地址、各字段值、當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)地址。45             這樣輸出便于讀者形象看到一個(gè)單向鏈表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，和我們46             設(shè)計(jì)的圖示是一模一樣的。47             */48             printf ("%o   %d   %5.1f   %o\n", p, p->num, p->score, p->next);49             p = p->next;        //移到下一個(gè)節(jié)點(diǎn)50         }51         while (p != NULL);52     }53 }

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

單向鏈表的刪除圖示：
       ---->[NULL]
       head

       圖3：空鏈表

      從圖3可知，空鏈表顯然不能刪除

      ---->[1]---->[2]...---->[n]---->[NULL]（原鏈表）
      head   1->next  2->next   n->next

      ---->[2]...---->[n]---->[NULL]（刪除后鏈表）
      head   2->next   n->next

      圖4：有N個(gè)節(jié)點(diǎn)的鏈表，刪除第一個(gè)節(jié)點(diǎn)
      結(jié)合原鏈表和刪除后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
      1、你要明白head就是第1個(gè)節(jié)點(diǎn)，head->next就是第2個(gè)節(jié)點(diǎn)；
       2、刪除后head指向第2個(gè)節(jié)點(diǎn)，就是讓head=head->next,OK這樣就行了。
       ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原鏈表）
       head   1->next  2->next  3->next   n->next

       ---->[1]---->[3]...---->[n]---->[NULL]（刪除后鏈表）
      head   1->next  3->next   n->next

      圖5：有N個(gè)節(jié)點(diǎn)的鏈表，刪除中間一個(gè)（這里圖示刪除第2個(gè)）
      結(jié)合原鏈表和刪除后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
      1、你要明白head就是第1個(gè)節(jié)點(diǎn)，1->next就是第2個(gè)節(jié)點(diǎn)，2->next就是第3個(gè)節(jié)點(diǎn)；
      2、刪除后2，1指向第3個(gè)節(jié)點(diǎn)，就是讓1->next=2->next。

      刪除指定學(xué)號(hào)的節(jié)點(diǎn)的函數(shù)為：

 

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

 1 /* 2 ========================== 3  功能：刪除指定節(jié)點(diǎn) 4   (此例中是刪除指定學(xué)號(hào)的節(jié)點(diǎn)) 5  返回：指向鏈表表頭的指針 6 ========================== 7 */ 8 struct student *Del (struct student *head, int num) 9 {10     struct student *p1;        //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址11     struct student *p2;        //p2保存當(dāng)前檢查過的節(jié)點(diǎn)的地址12     if (head == NULL)        //是空鏈表（結(jié)合圖3理解）13     {14         printf ("\nList is null!\n");15         return head;16     }17 18     //定位要?jiǎng)h除的節(jié)點(diǎn)19     p1 = head;20     while (p1->num != num && p1->next != NULL)    //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，就繼續(xù)往下找21     {22         p2 = p1;            //保存當(dāng)前節(jié)點(diǎn)的地址23         p1 = p1->next;        //后移一個(gè)節(jié)點(diǎn)24     }25 26     if(p1->num==num)        //找到了。（結(jié)合圖4、5理解）27     {28         if (p1 == head)        //如果要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)29         {30             head = p1->next;    //頭指針指向第一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，也就是第二個(gè)節(jié)點(diǎn)。這樣第一個(gè)節(jié)點(diǎn)就不在鏈表中，即刪除31         }32         else            //如果是其它節(jié)點(diǎn)，則讓原來指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個(gè)節(jié)點(diǎn)，完成刪除33         {34             p2->next = p1->next;35         }36 37         free (p1);        //釋放當(dāng)前節(jié)點(diǎn)38         p1 = NULL;39         printf ("\ndelete %ld success!\n", num);40         n -= 1;            //節(jié)點(diǎn)總數(shù)減1個(gè)41     }42     else                //沒有找到43     {44         printf ("\n%ld not been found!\n", num);45     }46 47     return head;48 }

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

 

單向鏈表的插入圖示：
       ---->[NULL]（原鏈表）
      head

      ---->[1]---->[NULL]（插入后的鏈表）
      head   1->next

      圖7 空鏈表插入一個(gè)節(jié)點(diǎn)
      結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
     1、你要明白空鏈表head指向NULL就是head=NULL；
     2、插入后head指向第1個(gè)節(jié)點(diǎn)，就是讓head=1,1->next=NULL,OK這樣就行了。

     ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原鏈表）
     head   1->next  2->next  3->next   n->next

     ---->[1]---->[2]---->[x]---->[3]...---->[n]---->[NULL]（插入后的鏈表）
     head   1->next  2->next  x->next  3->next   n->next

     圖8：有N個(gè)節(jié)點(diǎn)的鏈表，插入一個(gè)節(jié)點(diǎn)（這里圖示插入第2個(gè)后面）
     結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
    1、你要明白原1->next就是節(jié)點(diǎn)2，2->next就是節(jié)點(diǎn)3；
    2、插入后x指向第3個(gè)節(jié)點(diǎn),2指向x，就是讓x->next=2->next,1->next=x。

    插入指定節(jié)點(diǎn)的后面的函數(shù)為：

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

 1 /* 2 ========================== 3  功能：插入指定節(jié)點(diǎn)的后面 4   (此例中是指定學(xué)號(hào)的節(jié)點(diǎn)) 5  返回：指向鏈表表頭的指針 6 ========================== 7 */ 8 struct student *Insert (struct student *head, int num, struct student *node) 9 {10     struct student *p1;        //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址11     if (head == NULL)        //（結(jié)合圖示7理解）12     {13         head = node;14         node->next = NULL;15         n += 1;16         return head;17     }18 19     p1 = head;20     while(p1->num != num && p1->next != NULL)     //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，繼續(xù)往下找21     {22         p1 = p1->next;        //后移一個(gè)節(jié)點(diǎn)23     }24 25     if (p1->num==num)        //找到了（結(jié)合圖示8理解）26     {27         node->next = p1->next;    //顯然node的下一節(jié)點(diǎn)是原p1的next28         p1->next = node;        //插入后，原p1的下一節(jié)點(diǎn)就是要插入的node29         n += 1;            //節(jié)點(diǎn)總數(shù)增加1個(gè)30     }31     else32     {33         printf ("\n%ld not been found!\n", num);34     }35     return head;36 }

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

單向鏈表的反序圖示：
       ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（原鏈表）
       head   1->next  2->next  3->next   n->next

      [NULL]<----[1]<----[2]<----[3]<----...[n]<----（反序后的鏈表）
                1->next  2->next  3->next   n->next  head

          圖9：有N個(gè)節(jié)點(diǎn)的鏈表反序
          結(jié)合原鏈表和插入后的鏈表，就很容易寫出相應(yīng)的代碼。操作方法如下：
          1、我們需要一個(gè)讀原鏈表的指針p2,存反序鏈表的p1=NULL（剛好最后一個(gè)節(jié)點(diǎn)的next為NULL）,還有一個(gè)臨時(shí)存儲(chǔ)變量p；
          2、p2在原鏈表中讀出一個(gè)節(jié)點(diǎn)，我們就把它放到p1中，p就是用來處理節(jié)點(diǎn)放置順序的問題；
          3、比如，現(xiàn)在我們?nèi)〉靡粋€(gè)2,為了我們繼續(xù)往下取節(jié)點(diǎn)，我們必須保存它的next值，由原鏈表可知p=2->next;
          4、然后由反序后的鏈表可知，反序后2->next要指向1，則2->next=1;
          5、好了，現(xiàn)在已經(jīng)反序一個(gè)節(jié)點(diǎn)，接著處理下一個(gè)節(jié)點(diǎn)就需要保存此時(shí)的信息：
          p1變成剛剛加入的2，即p1=2;p2要變成它的下一節(jié)點(diǎn)，就是上面我們保存的p,即p2=p。

          反序鏈表的函數(shù)為：

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

 1 /* 2 ========================== 3  功能：反序節(jié)點(diǎn) 4   (鏈表的頭變成鏈表的尾，鏈表的尾變成頭) 5  返回：指向鏈表表頭的指針 6 ========================== 7 */ 8  9 struct student *Reverse (struct student *head)10 {11     struct student *p;        //臨時(shí)存儲(chǔ)12     struct student *p1;        //存儲(chǔ)返回結(jié)果13     struct student *p2;        //源結(jié)果節(jié)點(diǎn)一個(gè)一個(gè)取14 15     p1 = NULL;            //開始顛倒時(shí)，已顛倒的部分為空16     p2 = head;            //p2指向鏈表的頭節(jié)點(diǎn)17     while(p2 != NULL)18     {19         p = p2->next;20         p2->next = p1;21         p1 = p2;22         p2 = p;23     }24     head = p1;25     return head;26 }

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

  對(duì)鏈表進(jìn)行選擇排序的基本思想就是反復(fù)從還未排好序的那些節(jié)點(diǎn)中，選出鍵值（就是用它排序的字段，我們?nèi)W(xué)號(hào)num為鍵值）最小的節(jié)點(diǎn)，依次重新組合成一個(gè)鏈表。

         我認(rèn)為寫鏈表這類程序，關(guān)鍵是理解：head存儲(chǔ)的是第一個(gè)節(jié)點(diǎn)的地址，head->next存儲(chǔ)的是第二個(gè)節(jié)點(diǎn)的地址；任意一個(gè)節(jié)點(diǎn)p的地址，只能通過它前一個(gè)節(jié)點(diǎn)的next來求得。

        單向鏈表的選擇排序圖示：
         ---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原鏈表）
         head   1->next  3->next  2->next   n->next

         ---->[NULL]（空鏈表）
        first
        tail

         ---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序后鏈表）
         first   1->next  2->next  3->next   tail->next

         圖10：有N個(gè)節(jié)點(diǎn)的鏈表選擇排序

        1、先在原鏈表中找最小的，找到一個(gè)后就把它放到另一個(gè)空的鏈表中；
        2、空鏈表中安放第一個(gè)進(jìn)來的節(jié)點(diǎn)，產(chǎn)生一個(gè)有序鏈表,并且讓它在原鏈表中分離出來（此時(shí)要注意原鏈表中出來的是第一個(gè)節(jié)點(diǎn)還是中間其它節(jié)點(diǎn)）；
        3、繼續(xù)在原鏈表中找下一個(gè)最小的，找到后把它放入有序鏈表的尾指針的next,然后它變成其尾指針；

        對(duì)鏈表進(jìn)行選擇排序的函數(shù)為：

Android培訓(xùn),安卓培訓(xùn),手機(jī)開發(fā)培訓(xùn),移動(dòng)開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

http://www.cnblogs.com/ECJTUACM-873284962/p/7144465.html