|
鏈表概述 鏈表是一種常見的重要的數(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)建、刪除、 插入(無(wú)序、有序)、輸出、 排序(選擇、插入、冒泡)、反序等等。 單向鏈表的圖示： ---->[NULL] head 復(fù)制代碼 圖1：空鏈表 ---->[p1]---->[p2]...---->[pn]---->[NULL] head p1->next p2->next pn->next 復(fù)制代碼 圖2：有N個(gè)節(jié)點(diǎn)的鏈表 創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表的函數(shù)為： #include "stdlib.h" #include "stdio.h" #define NULL 0 #define LEN sizeof(struct student) struct student { int num; //學(xué)號(hào) float score; //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段 struct student *next; //指向下一節(jié)點(diǎn)的指針 }; int n; //節(jié)點(diǎn)總數(shù) /* ========================== 功能：創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表 返回：指向鏈表表頭的指針 ========================== */ struct student *Create() { struct student *head; //頭節(jié)點(diǎn) struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點(diǎn)的地址 struct student *p2 = NULL; //p2保存原鏈表最后一個(gè)節(jié)點(diǎn)的地址 n = 0; //創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表 p1 = (struct student *) malloc (LEN); //開辟一個(gè)新節(jié)點(diǎn) p2 = p1; //如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來以備后用 IF(p1==NULL) //節(jié)點(diǎn)開辟不成功 { printf ("\nCann't create it, try it again in a moment!\n"); return NULL; } else //節(jié)點(diǎn)開辟成功 { head = NULL; //開始head指向NULL printf ("Please input %d node -- num,score: ", n + 1); scanf ("%d %f", &(p1->num), &(p1->score)); //錄入數(shù)據(jù) } while(p1->num != 0) //只要學(xué)號(hào)不為0，就繼續(xù)錄入下一個(gè)節(jié)點(diǎn) { n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè) if(n == 1) //如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p1 { head = p1; p2->next = NULL; //此時(shí)的p2就是p1,也就是p1->next指向NULL。 } else { p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點(diǎn) } p2 = p1; //把p1的地址給p2保留，然后p1產(chǎn)生新的節(jié)點(diǎn) p1 = (struct student *) malloc (LEN); printf ("Please input %d node -- num,score: ", n + 1); scanf ("%d %f", &(p1->num), &(p1->score)); } p2->next = NULL; //此句就是根據(jù)單向鏈表的最后一個(gè)節(jié)點(diǎn)要指向NULL free(p1); //p1->num為0的時(shí)候跳出了while循環(huán)，并且釋放p1 p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針 return head; //返回創(chuàng)建鏈表的頭指針 } 復(fù)制代碼 輸出鏈表中節(jié)點(diǎn)的函數(shù)為： /* =========================== 功能：輸出節(jié)點(diǎn) 返回： void =========================== */ void Print(struct student *head) { struct student *p; printf ("\nNow , These %d records are:\n", n); p = head; if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點(diǎn) { printf("head is %o\n", head); //輸出頭指針指向的地址 do { /* 輸出相應(yīng)的值：當(dāng)前節(jié)點(diǎn)地址、各字段值、當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)地址。 這樣輸出便于讀者形象看到一個(gè)單向鏈表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，和我們 設(shè)計(jì)的圖示是一模一樣的。 */ printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next); p = p->next; //移到下一個(gè)節(jié)點(diǎn) } while (p != NULL); } } 復(fù)制代碼 單向鏈表的刪除圖示： ---->[NULL] head 復(fù)制代碼 圖3：空鏈表 從圖3可知，空鏈表顯然不能刪除 ---->[1]---->[2]...---->[n]---->[NULL](原鏈表) head 1->next 2->next n->next ---->[2]...---->[n]---->[NULL](刪除后鏈表) head 2->next n->next 復(fù)制代碼 圖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 復(fù)制代碼 圖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ù)為： /* ========================== 功能：刪除指定節(jié)點(diǎn) (此例中是刪除指定學(xué)號(hào)的節(jié)點(diǎn)) 返回：指向鏈表表頭的指針 ========================== */ struct student *Del (struct student *head, int num) { struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址 struct student *p2; //p2保存當(dāng)前檢查過的節(jié)點(diǎn)的地址 if (head == NULL) //是空鏈表(結(jié)合圖3理解) { printf ("\nList is null!\n"); return head; } //定位要?jiǎng)h除的節(jié)點(diǎn) p1 = head; while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，就繼續(xù)往下找 { p2 = p1; //保存當(dāng)前節(jié)點(diǎn)的地址 p1 = p1->next; //后移一個(gè)節(jié)點(diǎn) } if(p1->num==num) //找到了。(結(jié)合圖4、5理解) { if (p1 == head) //如果要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn) { head = p1->next; //頭指針指向第一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，也就是第二個(gè)節(jié)點(diǎn)。這樣第一個(gè)節(jié)點(diǎn)就不在鏈表中，即刪除 } else //如果是其它節(jié)點(diǎn)，則讓原來指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個(gè)節(jié)點(diǎn)，完成刪除 { p2->next = p1->next; } free (p1); //釋放當(dāng)前節(jié)點(diǎn) p1 = NULL; printf ("\ndelete %ld success!\n", num); n -= 1; //節(jié)點(diǎn)總數(shù)減1個(gè) } else //沒有找到 { printf ("\n%ld not been found!\n", num); } return head; } 復(fù)制代碼 單向鏈表的插入圖示： ---->[NULL](原鏈表) head ---->[1]---->[NULL](插入后的鏈表) head 1->next 復(fù)制代碼 圖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 復(fù)制代碼 圖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ù)為： /* ========================== 功能：插入指定節(jié)點(diǎn)的后面 (此例中是指定學(xué)號(hào)的節(jié)點(diǎn)) 返回：指向鏈表表頭的指針 ========================== */ struct student *Insert (struct student *head, int num, struct student *node) { struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址 if (head == NULL) //(結(jié)合圖示7理解) { head = node; node->next = NULL; n += 1; return head; } p1 = head; while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，繼續(xù)往下找 { p1 = p1->next; //后移一個(gè)節(jié)點(diǎn) } if (p1->num==num) //找到了(結(jié)合圖示8理解) { node->next = p1->next; //顯然node的下一節(jié)點(diǎn)是原p1的next p1->next = node; //插入后，原p1的下一節(jié)點(diǎn)就是要插入的node n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè) } else { printf ("\n%ld not been found!\n", num); } return head; } 復(fù)制代碼 單向鏈表的反序圖示： ---->[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 復(fù)制代碼 圖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ù)為： /* ========================== 功能：反序節(jié)點(diǎn) (鏈表的頭變成鏈表的尾，鏈表的尾變成頭) 返回：指向鏈表表頭的指針 ========================== */ struct student *Reverse (struct student *head) { struct student *p; //臨時(shí)存儲(chǔ) struct student *p1; //存儲(chǔ)返回結(jié)果 struct student *p2; //源結(jié)果節(jié)點(diǎn)一個(gè)一個(gè)取 p1 = NULL; //開始顛倒時(shí)，已顛倒的部分為空 p2 = head; //p2指向鏈表的頭節(jié)點(diǎn) while(p2 != NULL) { p = p2->next; p2->next = p1; p1 = p2; p2 = p; } head = p1; return head; } 復(fù)制代碼 對(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 復(fù)制代碼 圖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ù)為： ========================== */ struct student *SelectSort (struct student *head) { struct student *first; //排列后有序鏈的表頭指針 struct student *tail; //排列后有序鏈的表尾指針 struct student *p_min; //保留鍵值更小的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針 struct student *min; //存儲(chǔ)最小節(jié)點(diǎn) struct student *p; //當(dāng)前比較的節(jié)點(diǎn) first = NULL; while(head != NULL) //在鏈表中找鍵值最小的節(jié)點(diǎn) { //注意：這里for語(yǔ)句就是體現(xiàn)選擇排序思想的地方 for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時(shí)最小的節(jié)點(diǎn) { if (p->next->num < min->num) //找到一個(gè)比當(dāng)前min小的節(jié)點(diǎn) { p_min = p; //保存找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：顯然p->next的前驅(qū)節(jié)點(diǎn)是p min = p->next; //保存鍵值更小的節(jié)點(diǎn) } } //上面for語(yǔ)句結(jié)束后，就要做兩件事;一是把它放入有序鏈表中;二是根據(jù)相應(yīng)的條件判斷，安排它離開原來的鏈表 //第一件事 if (first == NULL) //如果有序鏈表目前還是一個(gè)空鏈表 { first = min; //第一次找到鍵值最小的節(jié)點(diǎn) tail = min; //注意：尾指針讓它指向最后的一個(gè)節(jié)點(diǎn) } else //有序鏈表中已經(jīng)有節(jié)點(diǎn) { tail->next = min; //把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它 tail = min; //尾指針也要指向它 } //第二件事 if (min == head) //如果找到的最小節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn) { head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個(gè)節(jié)點(diǎn)，就OK } else //如果不是第一個(gè)節(jié)點(diǎn) { p_min->next = min->next; //前次最小節(jié)點(diǎn)的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表 } } if (first != NULL) //循環(huán)結(jié)束得到有序鏈表first { tail->next = NULL; //單向鏈表的最后一個(gè)節(jié)點(diǎn)的next應(yīng)該指向NULL } head = first; return head; } 復(fù)制代碼 對(duì)鏈表進(jìn)行直接插入排序的基本思想就是假設(shè)鏈表的前面n-1個(gè)節(jié)點(diǎn)是已經(jīng)按鍵值(就是用它排序的字段，我們?nèi)W(xué)號(hào)num為鍵值)排好序的，對(duì)于節(jié)點(diǎn)n在這個(gè)序列中找插入位置，使得n插入后新序列仍然有序。按照這種思想，依次對(duì)鏈表從頭到尾執(zhí)行一遍，就可以使無(wú)序鏈表變?yōu)橛行蜴湵怼?/p> 單向鏈表的直接插入排序圖示： ---->[1]---->[3]---->[2]...---->[n]---->[NULL](原鏈表) head 1->next 3->next 2->next n->next ---->[1]---->[NULL](從原鏈表中取第1個(gè)節(jié)點(diǎn)作為只有一個(gè)節(jié)點(diǎn)的有序鏈表) head 復(fù)制代碼 圖11 ---->[3]---->[2]...---->[n]---->[NULL](原鏈表剩下用于直接插入排序的節(jié)點(diǎn)) first 3->next 2->next n->next 復(fù)制代碼 圖12 ---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后鏈表) head 1->next 2->next 3->next n->next 復(fù)制代碼 圖13：有N個(gè)節(jié)點(diǎn)的鏈表直接插入排序 1、先在原鏈表中以第一個(gè)節(jié)點(diǎn)為一個(gè)有序鏈表，其余節(jié)點(diǎn)為待定節(jié)點(diǎn)。 2、從圖12鏈表中取節(jié)點(diǎn)，到圖11鏈表中定位插入。 3、上面圖示雖說畫了兩條鏈表，其實(shí)只有一條鏈表。在排序中，實(shí)質(zhì)只增加了一個(gè)用于指向剩下需要排序節(jié)點(diǎn)的頭指針first罷了。 這一點(diǎn)請(qǐng)讀者務(wù)必搞清楚，要不然就可能認(rèn)為它和上面的選擇排序法一樣了。 對(duì)鏈表進(jìn)行直接插入排序的函數(shù)為： /* ========================== 功能：直接插入排序(由小到大) 返回：指向鏈表表頭的指針 ========================== */ struct student *InsertSort (struct student *head) { struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針 struct student *t; //臨時(shí)指針變量：插入節(jié)點(diǎn) struct student *p,*q; //臨時(shí)指針變量 first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12來理解 head->next = NULL; //只含有一個(gè)節(jié)點(diǎn)的鏈表的有序鏈表：可根據(jù)圖11來理解 while(first != NULL) //遍歷剩下無(wú)序的鏈表 { //注意：這里for語(yǔ)句就是體現(xiàn)直接插入排序思想的地方 for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無(wú)序節(jié)點(diǎn)在有序鏈表中找插入的位置 //退出for循環(huán)，就是找到了插入的位置，應(yīng)該將t節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，q節(jié)點(diǎn)之前 //注意：按道理來說，這句話可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3條，就知道了 //下面的插入就是將t節(jié)點(diǎn)即是first節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，已經(jīng)改變了first節(jié)點(diǎn)，所以first節(jié)點(diǎn)應(yīng)該在被修改之前往后移動(dòng)，不能放到下面注釋的位置上去 first = first->next; //無(wú)序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中 if (q == head) //插在第一個(gè)節(jié)點(diǎn)之前 { head = t; } else //p是q的前驅(qū) { p->next = t; } t->next = q; //完成插入動(dòng)作 //first = first->next; } return head; } 復(fù)制代碼 對(duì)鏈表進(jìn)行冒泡排序的基本思想就是對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部節(jié)點(diǎn)，自上而下對(duì)相鄰的兩個(gè)節(jié)點(diǎn)依次進(jìn)行比較和調(diào)整，讓鍵值(就是用它排 序的字段，我們?nèi)W(xué)號(hào)num為鍵值)較大的節(jié)點(diǎn)往下沉，鍵值較小的往上冒。即：每當(dāng)兩相鄰的節(jié)點(diǎn)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。 單向鏈表的冒泡排序圖示： ---->[1]---->[3]---->[2]...---->[n]---->[NULL](原鏈表) head 1->next 3->next 2->next n->next ---->[1]---->[2]---->[3]...---->[n]---->[NULL](排序后鏈表) head 1->next 2->next 3->next n->next 復(fù)制代碼 圖14：有N個(gè)節(jié)點(diǎn)的鏈表冒泡排序 任意兩個(gè)相鄰節(jié)點(diǎn)p、q位置互換圖示: 假設(shè)p1->next指向p，那么顯然p1->next->next就指向q, p1->next->next->next就指向q的后繼節(jié)點(diǎn)，我們用p2保存 p1->next->next指針。即：p2=p1->next->next，則有： [ ]---->[p]---------->[q]---->[ ](排序前) p1->next p1->next->next p2->next 復(fù)制代碼 圖15 [ ]---->[q]---------->[p]---->[ ](排序后) 復(fù)制代碼 圖16 1、排序后q節(jié)點(diǎn)指向p節(jié)點(diǎn)，在調(diào)整指向之前，我們要保存原p的指向節(jié)點(diǎn)地址，即：p2=p1->next->next; 2、順著這一步一步往下推,排序后圖16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next; 3、在圖15中p2->next原是q發(fā)出來的指向，排序后圖16中q的指向要變?yōu)橹赶騪的，而原來p1->next是指向p的，所以p2->next=p1->next; 4、在圖15中p1->next原是指向p的，排序后圖16中p1->next要指向q,原來p1->next->next(即p2)是指向q的，所以p1->next=p2; 5、至此，我們完成了相鄰兩節(jié)點(diǎn)的順序交換。 6、下面的程序描述改進(jìn)了一點(diǎn)就是記錄了每次最后一次節(jié)點(diǎn)下沉的位置，這樣我們不必每次都從頭到尾的掃描，只需要掃描到記錄點(diǎn)為止。 因?yàn)楹竺娴亩家呀?jīng)是排好序的了。 對(duì)鏈表進(jìn)行冒泡排序的函數(shù)為： /* ========================== 功能：冒泡排序(由小到大) 返回：指向鏈表表頭的指針 ========================== */ struct student *BubbleSort (struct student *head) { struct student *endpt; //控制循環(huán)比較 struct student *p; //臨時(shí)指針變量 struct student *p1,*p2; p1 = (struct student *) malloc (LEN); p1->next = head; //注意理解：我們?cè)黾右粋€(gè)節(jié)點(diǎn)，放在第一個(gè)節(jié)點(diǎn)的前面，主要是為了便于比較。因?yàn)榈谝粋€(gè)節(jié)點(diǎn)沒有前驅(qū)，我們不能交換地址 head = p1; //讓head指向p1節(jié)點(diǎn)，排序完成后，我們?cè)侔裵1節(jié)點(diǎn)釋放掉 for (endpt = NULL; endpt != head; endpt = p) //結(jié)合第6點(diǎn)理解 { for (p = p1 = head; p1->next->next != endpt; p1 = p1->next) { if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點(diǎn)鍵值比后面節(jié)點(diǎn)的鍵值大，則交換 { p2 = p1->next->next; //結(jié)合第1點(diǎn)理解 p1->next->next = p2->next; //結(jié)合第2點(diǎn)理解 p2->next = p1->next; //結(jié)合第3點(diǎn)理解 p1->next = p2; //結(jié)合第4點(diǎn)理解 p = p1->next->next; //結(jié)合第6點(diǎn)理解 } } } p1 = head; //把p1的信息去掉 head = head->next; //讓head指向排序后的第一個(gè)節(jié)點(diǎn) free (p1); //釋放p1 p1 = NULL; //p1置為NULL，保證不產(chǎn)生“野指針”，即地址不確定的指針變量 return head; } 復(fù)制代碼 有序鏈表插入節(jié)點(diǎn)示意圖： ---->[NULL](空有序鏈表) head 復(fù)制代碼 圖18：空有序鏈表(空有序鏈表好解決，直接讓head指向它就是了。) 以下討論不為空的有序鏈表。 ---->[1]---->[2]---->[3]...---->[n]---->[NULL](有序鏈表) head 1->next 2->next 3->next n->next 復(fù)制代碼 圖18：有N個(gè)節(jié)點(diǎn)的有序鏈表 插入node節(jié)點(diǎn)的位置有兩種情況：一是第一個(gè)節(jié)點(diǎn)前，二是其它節(jié)點(diǎn)前或后。 ---->[node]---->[1]---->[2]---->[3]...---->[n]---->[NULL] head node->next 1->next 2->next 3->next n->next 復(fù)制代碼 圖19：node節(jié)點(diǎn)插在第一個(gè)節(jié)點(diǎn)前 ---->[1]---->[2]---->[3]...---->[node]...---->[n]---->[NULL] head 1->next 2->next 3->next node->next n->next 復(fù)制代碼 插入有序鏈表的函數(shù)為： /* ========================== 功能：插入有序鏈表的某個(gè)節(jié)點(diǎn)的后面(從小到大) 返回：指向鏈表表頭的指針 ========================== */ struct student *Sortinsert (struct student *head, struct student *node) { struct student *p; //p保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址 struct student *t; //臨時(shí)指針變量 if (head == NULL) //處理空的有序鏈表 { head = node; node->next = NULL; n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加 return head; } p = head; //有序鏈表不為空 while(p->num < node->num && p != NULL) //p指向的節(jié)點(diǎn)的學(xué)號(hào)比插入節(jié)點(diǎn)的學(xué)號(hào)小，并且它不等于NULL { t = p; //保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，以便后面判斷后處理 p = p->next; //后移一個(gè)節(jié)點(diǎn) } if (p == head) //剛好插入第一個(gè)節(jié)點(diǎn)之前 { node->next = p; head = node; } else //插入其它節(jié)點(diǎn)之后 { t->next = node; //把node節(jié)點(diǎn)加進(jìn)去 node->next = p; } n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加1 return head; } 復(fù)制代碼 綜上所述，鏈表的各類操作函數(shù)的完整代碼如下： #include "stdlib.h" #include "stdio.h" #define NULL 0 #define LEN sizeof(struct student) struct student { int num; //學(xué)號(hào) float score; //分?jǐn)?shù)，其他信息可以繼續(xù)在下面增加字段 struct student *next; //指向下一節(jié)點(diǎn)的指針 }; int n; //節(jié)點(diǎn)總數(shù) /* ========================== 功能：創(chuàng)建n個(gè)節(jié)點(diǎn)的鏈表 返回：指向鏈表表頭的指針 ========================== */ struct student *Create() { struct student *head; //頭節(jié)點(diǎn) struct student *p1 = NULL; //p1保存創(chuàng)建的新節(jié)點(diǎn)的地址 struct student *p2 = NULL; //p2保存原鏈表最后一個(gè)節(jié)點(diǎn)的地址 n = 0; //創(chuàng)建前鏈表的節(jié)點(diǎn)總數(shù)為0：空鏈表 p1 = (struct student *) malloc (LEN); //開辟一個(gè)新節(jié)點(diǎn) p2 = p1; //如果節(jié)點(diǎn)開辟成功，則p2先把它的指針保存下來以備后用 if(p1==NULL) //節(jié)點(diǎn)開辟不成功 { printf ("\nCann't create it, try it again in a moment!\n"); return NULL; } else //節(jié)點(diǎn)開辟成功 { head = NULL; //開始head指向NULL printf ("Please input %d node -- num,score: ", n + 1); scanf ("%d %f", &(p1->num), &(p1->score)); //錄入數(shù)據(jù) } while(p1->num != 0) //只要學(xué)號(hào)不為0，就繼續(xù)錄入下一個(gè)節(jié)點(diǎn) { n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè) if(n == 1) //如果節(jié)點(diǎn)總數(shù)是1，則head指向剛創(chuàng)建的節(jié)點(diǎn)p1 { head = p1; p2->next = NULL; //此時(shí)的p2就是p1,也就是p1->next指向NULL。 } else { p2->next = p1; //指向上次下面剛剛開辟的新節(jié)點(diǎn) } p2 = p1; //把p1的地址給p2保留，然后p1產(chǎn)生新的節(jié)點(diǎn) p1 = (struct student *) malloc (LEN); printf ("Please input %d node -- num,score: ", n + 1); scanf ("%d %f", &(p1->num), &(p1->score)); } p2->next = NULL; //此句就是根據(jù)單向鏈表的最后一個(gè)節(jié)點(diǎn)要指向NULL free(p1); //p1->num為0的時(shí)候跳出了while循環(huán)，并且釋放p1 p1 = NULL; //特別不要忘記把釋放的變量清空置為NULL,否則就變成"野指針"，即地址不確定的指針 return head; //返回創(chuàng)建鏈表的頭指針 } /* =========================== 功能：輸出節(jié)點(diǎn) 返回： void =========================== */ void Print(struct student *head) { struct student *p; printf ("\nNow , These %d records are:\n", n); p = head; if(head != NULL) //只要不是空鏈表，就輸出鏈表中所有節(jié)點(diǎn) { printf("head is %o\n", head); //輸出頭指針指向的地址 do { /* 輸出相應(yīng)的值：當(dāng)前節(jié)點(diǎn)地址、各字段值、當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)地址。 這樣輸出便于讀者形象看到一個(gè)單向鏈表在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)，和我們 設(shè)計(jì)的圖示是一模一樣的。 */ printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next); p = p->next; //移到下一個(gè)節(jié)點(diǎn) } while (p != NULL); } } /* ========================== 功能：刪除指定節(jié)點(diǎn) (此例中是刪除指定學(xué)號(hào)的節(jié)點(diǎn)) 返回：指向鏈表表頭的指針 ========================== */ struct student *Del (struct student *head, int num) { struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址 struct student *p2; //p2保存當(dāng)前檢查過的節(jié)點(diǎn)的地址 if (head == NULL) //是空鏈表(結(jié)合圖3理解) { printf ("\nList is null!\n"); return head; } //定位要?jiǎng)h除的節(jié)點(diǎn) p1 = head; while (p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，就繼續(xù)往下找 { p2 = p1; //保存當(dāng)前節(jié)點(diǎn)的地址 p1 = p1->next; //后移一個(gè)節(jié)點(diǎn) } if(p1->num==num) //找到了。(結(jié)合圖4、5理解) { if (p1 == head) //如果要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn) { head = p1->next; //頭指針指向第一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)，也就是第二個(gè)節(jié)點(diǎn)。這樣第一個(gè)節(jié)點(diǎn)就不在鏈表中，即刪除 } else //如果是其它節(jié)點(diǎn)，則讓原來指向當(dāng)前節(jié)點(diǎn)的指針，指向它的下一個(gè)節(jié)點(diǎn)，完成刪除 { p2->next = p1->next; } free (p1); //釋放當(dāng)前節(jié)點(diǎn) p1 = NULL; printf ("\ndelete %ld success!\n", num); n -= 1; //節(jié)點(diǎn)總數(shù)減1個(gè) } else //沒有找到 { printf ("\n%ld not been found!\n", num); } return head; } //銷毀鏈表 void DestroyList(struct student *head) { struct student *p; if(head==NULL) return 0; while(head) { p=head->next; free(head); head=p; } return 1; } /* ========================== 功能：插入指定節(jié)點(diǎn)的后面 (此例中是指定學(xué)號(hào)的節(jié)點(diǎn)) 返回：指向鏈表表頭的指針 ========================== */ struct student *Insert (struct student *head, int num, struct student *node) { struct student *p1; //p1保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址 if (head == NULL) //(結(jié)合圖示7理解) { head = node; node->next = NULL; n += 1; return head; } p1 = head; while(p1->num != num && p1->next != NULL) //p1指向的節(jié)點(diǎn)不是所要查找的，并且它不是最后一個(gè)節(jié)點(diǎn)，繼續(xù)往下找 { p1 = p1->next; //后移一個(gè)節(jié)點(diǎn) } if (p1->num==num) //找到了(結(jié)合圖示8理解) { node->next = p1->next; //顯然node的下一節(jié)點(diǎn)是原p1的next p1->next = node; //插入后，原p1的下一節(jié)點(diǎn)就是要插入的node n += 1; //節(jié)點(diǎn)總數(shù)增加1個(gè) } else { printf ("\n%ld not been found!\n", num); } return head; } /* ========================== 功能：反序節(jié)點(diǎn) (鏈表的頭變成鏈表的尾，鏈表的尾變成頭) 返回：指向鏈表表頭的指針 ========================== */ struct student *Reverse (struct student *head) { struct student *p; //臨時(shí)存儲(chǔ) struct student *p1; //存儲(chǔ)返回結(jié)果 struct student *p2; //源結(jié)果節(jié)點(diǎn)一個(gè)一個(gè)取 p1 = NULL; //開始顛倒時(shí)，已顛倒的部分為空 p2 = head; //p2指向鏈表的頭節(jié)點(diǎn) while(p2 != NULL) { p = p2->next; p2->next = p1; p1 = p2; p2 = p; } head = p1; return head; } /* ========================== 功能：選擇排序(由小到大) 返回：指向鏈表表頭的指針 ========================== */ struct student *SelectSort (struct student *head) { struct student *first; //排列后有序鏈的表頭指針 struct student *tail; //排列后有序鏈的表尾指針 struct student *p_min; //保留鍵值更小的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的指針 struct student *min; //存儲(chǔ)最小節(jié)點(diǎn) struct student *p; //當(dāng)前比較的節(jié)點(diǎn) first = NULL; while(head != NULL) //在鏈表中找鍵值最小的節(jié)點(diǎn) { //注意：這里for語(yǔ)句就是體現(xiàn)選擇排序思想的地方 for (p = head, min = head; p->next != NULL; p = p->next) //循環(huán)遍歷鏈表中的節(jié)點(diǎn)，找出此時(shí)最小的節(jié)點(diǎn) { if (p->next->num < min->num) //找到一個(gè)比當(dāng)前min小的節(jié)點(diǎn) { p_min = p; //保存找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：顯然p->next的前驅(qū)節(jié)點(diǎn)是p min = p->next; //保存鍵值更小的節(jié)點(diǎn) } } //上面for語(yǔ)句結(jié)束后，就要做兩件事;一是把它放入有序鏈表中;二是根據(jù)相應(yīng)的條件判斷，安排它離開原來的鏈表 //第一件事 if (first == NULL) //如果有序鏈表目前還是一個(gè)空鏈表 { first = min; //第一次找到鍵值最小的節(jié)點(diǎn) tail = min; //注意：尾指針讓它指向最后的一個(gè)節(jié)點(diǎn) } else //有序鏈表中已經(jīng)有節(jié)點(diǎn) { tail->next = min; //把剛找到的最小節(jié)點(diǎn)放到最后，即讓尾指針的next指向它 tail = min; //尾指針也要指向它 } //第二件事 if (min == head) //如果找到的最小節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn) { head = head->next; //顯然讓head指向原h(huán)ead->next,即第二個(gè)節(jié)點(diǎn)，就OK } else //如果不是第一個(gè)節(jié)點(diǎn) { p_min->next = min->next; //前次最小節(jié)點(diǎn)的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表 } } if (first != NULL) //循環(huán)結(jié)束得到有序鏈表first { tail->next = NULL; //單向鏈表的最后一個(gè)節(jié)點(diǎn)的next應(yīng)該指向NULL } head = first; return head; } /* ========================== 功能：直接插入排序(由小到大) 返回：指向鏈表表頭的指針 ========================== */ struct student *InsertSort (struct student *head) { struct student *first; //為原鏈表剩下用于直接插入排序的節(jié)點(diǎn)頭指針 struct student *t; //臨時(shí)指針變量：插入節(jié)點(diǎn) struct student *p,*q; //臨時(shí)指針變量 first = head->next; //原鏈表剩下用于直接插入排序的節(jié)點(diǎn)鏈表：可根據(jù)圖12來理解 head->next = NULL; //只含有一個(gè)節(jié)點(diǎn)的鏈表的有序鏈表：可根據(jù)圖11來理解 while(first != NULL) //遍歷剩下無(wú)序的鏈表 { //注意：這里for語(yǔ)句就是體現(xiàn)直接插入排序思想的地方 for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //無(wú)序節(jié)點(diǎn)在有序鏈表中找插入的位置 //退出for循環(huán)，就是找到了插入的位置，應(yīng)該將t節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，q節(jié)點(diǎn)之前 //注意：按道理來說，這句話可以放到下面注釋了的那個(gè)位置也應(yīng)該對(duì)的，但是就是不能。原因：你若理解了上面的第3條，就知道了 //下面的插入就是將t節(jié)點(diǎn)即是first節(jié)點(diǎn)插入到p節(jié)點(diǎn)之后，已經(jīng)改變了first節(jié)點(diǎn)，所以first節(jié)點(diǎn)應(yīng)該在被修改之前往后移動(dòng)，不能放到下面注釋的位置上去 first = first->next; //無(wú)序鏈表中的節(jié)點(diǎn)離開，以便它插入到有序鏈表中 if (q == head) //插在第一個(gè)節(jié)點(diǎn)之前 { head = t; } else //p是q的前驅(qū) { p->next = t; } t->next = q; //完成插入動(dòng)作 //first = first->next; } return head; } /* ========================== 功能：冒泡排序(由小到大) 返回：指向鏈表表頭的指針 ========================== */ struct student *BubbleSort (struct student *head) { struct student *endpt; //控制循環(huán)比較 struct student *p; //臨時(shí)指針變量 struct student *p1,*p2; p1 = (struct student *) malloc (LEN); p1->next = head; //注意理解：我們?cè)黾右粋€(gè)節(jié)點(diǎn)，放在第一個(gè)節(jié)點(diǎn)的前面，主要是為了便于比較。因?yàn)榈谝粋€(gè)節(jié)點(diǎn)沒有前驅(qū)，我們不能交換地址 head = p1; //讓head指向p1節(jié)點(diǎn)，排序完成后，我們?cè)侔裵1節(jié)點(diǎn)釋放掉 for (endpt = NULL; endpt != head; endpt = p) //結(jié)合第6點(diǎn)理解 { for (p = p1 = head; p1->next->next != endpt; p1 = p1->next) { if (p1->next->num > p1->next->next->num) //如果前面的節(jié)點(diǎn)鍵值比后面節(jié)點(diǎn)的鍵值大，則交換 { p2 = p1->next->next; //結(jié)合第1點(diǎn)理解 p1->next->next = p2->next; //結(jié)合第2點(diǎn)理解 p2->next = p1->next; //結(jié)合第3點(diǎn)理解 p1->next = p2; //結(jié)合第4點(diǎn)理解 p = p1->next->next; //結(jié)合第6點(diǎn)理解 } } } p1 = head; //把p1的信息去掉 head = head->next; //讓head指向排序后的第一個(gè)節(jié)點(diǎn) free (p1); //釋放p1 p1 = NULL; //p1置為NULL，保證不產(chǎn)生“野指針”，即地址不確定的指針變量 return head; } /* ========================== 功能：插入有序鏈表的某個(gè)節(jié)點(diǎn)的后面(從小到大) 返回：指向鏈表表頭的指針 ========================== */ struct student *SortInsert (struct student *head, struct student *node) { struct student *p; //p保存當(dāng)前需要檢查的節(jié)點(diǎn)的地址 struct student *t; //臨時(shí)指針變量 if (head == NULL) //處理空的有序鏈表 { head = node; node->next = NULL; n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加 return head; } p = head; //有序鏈表不為空 while(p->num < node->num && p != NULL) //p指向的節(jié)點(diǎn)的學(xué)號(hào)比插入節(jié)點(diǎn)的學(xué)號(hào)小，并且它不等于NULL { t = p; //保存當(dāng)前節(jié)點(diǎn)的前驅(qū)，以便后面判斷后處理 p = p->next; //后移一個(gè)節(jié)點(diǎn) } if (p == head) //剛好插入第一個(gè)節(jié)點(diǎn)之前 { node->next = p; head = node; } else //插入其它節(jié)點(diǎn)之后 { t->next = node; //把node節(jié)點(diǎn)加進(jìn)去 node->next = p; } n += 1; //插入完畢，節(jié)點(diǎn)總數(shù)加1 return head; } /* 以上函數(shù)的測(cè)試程序： 提示：根據(jù)測(cè)試函數(shù)的不同注釋相應(yīng)的程序段，這也是一種測(cè)試方法。 */ int main(void) { struct student *head; struct student *stu; int thenumber; // 測(cè)試Create()、Print() head = Create(); Print(head); //測(cè)試Del() printf("\nWhich one delete: "); scanf("%d",&thenumber); head = Del(head,thenumber); Print(head); //測(cè)試Insert() stu = (struct student *)malloc(LEN); printf("\nPlease input insert node -- num,score: "); scanf("%d %f",&stu->num,&stu->score); printf("\nInsert behind num: "); scanf("%d",&thenumber); head = Insert(head,thenumber,stu); Print(head); //測(cè)試Reverse() printf("\nReverse the LinkList: \n"); head = Reverse(head); Print(head); //測(cè)試SelectSort() printf("\nSelectSort the LinkList: \n"); head = SelectSort(head); Print(head); //測(cè)試InsertSort() printf("\nInsertSort the LinkList: \n"); head = InsertSort(head); Print(head); //測(cè)試BubbleSort() printf("\nBubbleSort the LinkList: \n"); head = BubbleSort(head); Print(head); printf("\nSortInsert the LinkList: \n"); //測(cè)試SortInsert():上面創(chuàng)建鏈表，輸入節(jié)點(diǎn)時(shí)請(qǐng)注意學(xué)號(hào)num從小到大的順序 stu = (struct student *)malloc(LEN); printf("\nPlease input insert node -- num,score: "); scanf("%d %f",&stu->num,&stu->score); head = SortInsert(head,stu); Print(head); //銷毀鏈表 DestroyList(head); printf ("\n"); system ("pause"); } 最后也為大家提供一些鏈表的參考資料供學(xué)習(xí)參考 |
|
|
