基本介紹
- 中文名：單向鍊表
- 外文名：One-way LinkedList
- 定義：鍊表的一種
- 特點：鍊表的連結方向是單向的
- 目的：學習單向鍊表
鍊表的優點,語言實例,
鍊表的優點
相比較普通的線性結構，鍊表結構的可以總結一下：
（1）單個結點創建非常方便，普通的線性記憶體通常在創建的時候就需要設定數據的大小
（2）結點的刪除非常方便，不需要像線性結構那樣移動剩下的數據
（3）結點的訪問方便，可以通過循環或者遞歸的方法訪問到任意數據，但是平均的訪問效率低於線性表
語言實例
/*
===============================================
目的：學習單向鍊表的創建、刪除、
插入（無序、有序）、輸出、
排序（選擇、插入、冒泡）、反序
排序（選擇、插入、冒泡）
插入（有序）
================================================
*/
/*
單向鍊表的圖示：
---->[NULL]
head
圖1：空鍊表
---->[p1]---->[p2]...---->[pn]---->[NULL]
head p1->next p2->next pn->next
圖2：有N個結點的鍊表
*/
#include <stdlib.h>
#include <stdio.h>
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
long num; /*學號 */
float score; /*分數，其他信息可以繼續在下面增加欄位 */
struct student *next; /*指向下一結點的指針 */
};
int n; /*結點總數 */
/*
==========================
功能：創建結點
返回：指向鍊表表頭的指針
==========================
*/
struct student *
Create ()
{
struct student *head; /*頭結點 */
struct student *p1 = NULL; /*p1保存創建的新結點的地址 */
struct student *p2 = NULL; /*p2保存原鍊表最後一個結點的地址 */
n = 0; /*創建前鍊表的結點總數為0：空鍊表 */
p1 = (struct student *) malloc (LEN); /*開闢一個新結點 */
p2 = p1; /*如果結點開闢成功，則p2先把它的指針保存下來以備後用 */
if (p1 == NULL) /*結點開闢不成功 */
{
printf ("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else /*結點開闢成功 */
{
head = NULL; /*開始head指向NULL */
printf ("Please input %d node -- num,score: ", n + 1);
scanf ("%ld,%f", &(p1->num), &(p1->score)); /*錄入數據 */
}
while (p1->num != 0) /*只要學號不為0，就繼續錄入下一個結點 */
{
n += 1; /*結點總數增加1個 */
if (n == 1) /*如果結點總數是1，則head指向剛創建的結點p1 */
{
head = p1;
/*
注意：
此時的p2就是p1,也就是p1->next指向NULL。
這樣寫目的是與下面else保持一致。
*/
p2->next = NULL;
}
else
{
p2->next = p1; /*指向上次下面剛開闢的結點 */
}
p2 = p1; /*把p1的地址給p2保留，然後p1去產生新結點 */
p1 = (struct student *) malloc (LEN);
printf ("Please input %d node -- num,score: ", n + 1);
scanf ("%ld,%f", &(p1->num), &(p1->score));
}
p2->next = NULL; /*此句就是根據單向鍊表的最後一個結點要指向NULL */
free (p1); /*釋放p1。用malloc()、calloc()的變數都要free() */
p1 = NULL; /*特別不要忘記把釋放的變數清空置為NULL,否則就變成"野指針"，即地址不確定的指針。 */
}
/*
===========================
功能：輸出結點
返回： void
===========================
*/
void
Print (struct student *head)
{
struct student *p;
printf ("\nNow , These %d records are:\n", n);
p = head;
if (head != NULL) /*只要不是空鍊表，就輸出鍊表中所有結點 */
{
printf ("head is %o\n", head); /*輸出頭指針指向的地址 */
do
{
/*
輸出相應的值：當前結點地址、各欄位值、當前結點的下一結點地址。
這樣輸出便於讀者形象看到一個單向鍊表在計算機中的存儲結構，和我們
設計的圖示是一模一樣的。
*/
printf ("%o %ld %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next; /*移到下一個結點 */
}
while (p != NULL);
}
}
/*
==========================
功能：刪除指定結點
(此例中是刪除指定學號的結點)
返回：指向鍊表表頭的指針
==========================
*/
/*
單向鍊表的刪除圖示：
---->[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個結點的鍊表，刪除第一個結點
結合原鍊表和刪除後的鍊表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白head就是第1個結點，head->next就是第2個結點；
2、刪除後head指向第2個結點，就是讓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個結點的鍊表，刪除中間一個（這裡圖示刪除第2個）
結合原鍊表和刪除後的鍊表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白head就是第1個結點，1->next就是第2個結點，2->next就是第3個結點；
2、刪除後2，1指向第3個結點，就是讓1->next=2->next。
*/
struct student *
Del (struct student *head, long num)
{
struct student *p1; /*p1保存當前需要檢查的結點的地址 */
struct student *p2; /*p2保存當前檢查過的結點的地址 */
if (head == NULL) /*是空鍊表（結合圖3理解） */
{
printf ("\nList is null!\n");
return head;
}
/*定位要刪除的結點 */
p1 = head;
while (p1->num != num && p1->next != NULL) /*p1指向的結點不是所要查找的，並且它不是最後一個結點，就繼續往下找 */
{
p2 = p1; /*保存當前結點的地址 */
p1 = p1->next; /*後移一個結點 */
}
if (num == p1->num) /*找到了。（結合圖4、5理解） */
{
if (p1 == head) /*如果要刪除的結點是第一個結點 */
{
}
else /*如果是其它結點，則讓原來指向當前結點的指針，指向它的下一個結點，完成刪除 */
{
p2->next = p1->next;
}
free (p1); /*釋放當前結點 */
p1 = NULL;
printf ("\ndelete %ld success!\n", num);
n -= 1; /*結點總數減1個 */
}
else /*沒有找到 */
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
/*
==========================
功能：插入指定結點的後面
(此例中是指定學號的結點)
返回：指向鍊表表頭的指針
==========================
*/
/*
單向鍊表的插入圖示：
---->[NULL]（原鍊表）
head
---->[1]---->[NULL]（插入後的鍊表）
head 1->next
圖7 空鍊表插入一個結點
結合原鍊表和插入後的鍊表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白空鍊表head指向NULL就是head=NULL；
2、插入後head指向第1個結點，就是讓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個結點的鍊表，插入一個結點（這裡圖示插入第2個後面）
結合原鍊表和插入後的鍊表，就很容易寫出相應的代碼。操作方法如下：
1、你要明白原1->next就是結點2，2->next就是結點3；
2、插入後x指向第3個結點,2指向x，就是讓x->next=2->next,1->next=x。
*/
struct student *
Insert (struct student *head, long num, struct student *node)
{
struct student *p1; /*p1保存當前需要檢查的結點的地址 */
if (head == NULL) /*（結合圖示7理解） */
{
head = node;
node->next = NULL;
n += 1;
return head;
}
p1 = head;
while (p1->num != num && p1->next != NULL) /*p1指向的結點不是所要查找的，並且它不是最後一個結點，繼續往下找 */
{
p1 = p1->next; /*後移一個結點 */
}
if (num == p1->num) /*找到了（結合圖示8理解） */
{
node->next = p1->next; /*顯然node的下一結點是原p1的next */
p1->next = node; /*插入後，原p1的下一結點就是要插入的node */
n += 1; /*結點總數增加1個 */
}
else
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
/*
==========================
功能：反序結點
(鍊表的頭變成鍊表的尾，鍊表的尾變成頭)
返回：指向鍊表表頭的指針
==========================
*/
/*
單向鍊表的反序圖示：
---->[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個結點的鍊表反序
結合原鍊表和插入後的鍊表，就很容易寫出相應的代碼。操作方法如下：
1、我們需要一個讀原鍊表的指針p2,存反序鍊表的p1=NULL（剛好最後一個結點的next為NULL）,還有一個臨時存儲變數p；
2、p2在原鍊表中讀出一個結點，我們就把它放到p1中，p就是用來處理結點放置順序的問題；
3、比如，現在我們取得一個2,為了我們繼續往下取結點，我們必須保存它的next值，由原鍊表可知p=2->next;
4、然後由反序後的鍊表可知，反序後2->next要指向1，則2->next=1;
5、好了，現在已經反序一個結點，接著處理下一個結點就需要保存此時的信息：
p1變成剛剛加入的2，即p1=2;p2要變成它的下一結點，就是上面我們保存的p,即p2=p。
*/
struct student *
Reverse (struct student *head)
{
struct student *p; /*臨時存儲 */
struct student *p1; /*存儲返回結果 */
struct student *p2; /*源結果結點一個一個取 */
p1 = NULL; /*開始顛倒時，已顛倒的部分為空 */
while (p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}
/*
==========================
功能：選擇排序(由小到大)
返回：指向鍊表表頭的指針
==========================
*/
/*
選擇排序的基本思想就是反覆從還未排好序的那些結點中，
選出鍵值（就是用它排序的欄位，我們取學號num為鍵值）最小的結點，
依次重新組合成一個鍊表。
我認為寫鍊表這類程式，關鍵是理解：
head存儲的是第一個結點的地址，head->next存儲的是第二個結點的地址；
任意一個結點p的地址，只能通過它前一個結點的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個結點的鍊表選擇排序
1、先在原鍊表中找最小的，找到一個後就把它放到另一個空的鍊表中；
2、空鍊表中安放第一個進來的結點，產生一個有序鍊表,並且讓它在原鍊表中分離出來（此時要注意原鍊表中出來的是第一個結點還是中間其它結點）；
3、繼續在原鍊表中找下一個最小的，找到後把它放入有序鍊表的尾指針的next,然後它變成其尾指針；
*/
struct student *
SelectSort (struct student *head)
{
struct student *first; /*排列後有序鏈的表頭指針 */
struct student *tail; /*排列後有序鏈的表尾指針 */
struct student *p_min; /*保留鍵值更小的結點的前驅結點的指針 */
struct student *min; /*存儲最小結點 */
struct student *p; /*當前比較的結點 */
first = NULL;
while (head != NULL) /*在鍊表中找鍵值最小的結點。 */
{
/*注意：這裡for語句就是體現選擇排序思想的地方 */
for (p = head, min = head; p->next != NULL; p = p->next) /*循環遍歷鍊表中的結點，找出此時最小的結點。 */
{
if (p->next->num < min->num) /*找到一個比當前min小的結點。 */
{
p_min = p; /*保存找到結點的前驅結點：顯然p->next的前驅結點是p。 */
min = p->next; /*保存鍵值更小的結點。 */
}
}
/*上面for語句結束後，就要做兩件事；一是把它放入有序鍊表中；二是根據相應的條件判斷，安排它離開原來的鍊表。 */
/*第一件事 */
if (first == NULL) /*如果有序鍊表目前還是一個空鍊表 */
{
first = min; /*第一次找到鍵值最小的結點。 */
tail = min; /*注意：尾指針讓它指向最後的一個結點。 */
}
else /*有序鍊表中已經有結點 */
{
tail->next = min; /*把剛找到的最小結點放到最後，即讓尾指針的next指向它。 */
tail = min; /*尾指針也要指向它。 */
}
/*第二件事 */
if (min == head) /*如果找到的最小結點就是第一個結點 */
{
head = head->next; /*顯然讓head指向原head->next,即第二個結點，就OK */
}
else /*如果不是第一個結點 */
{
p_min->next = min->next; /*前次最小結點的next指向當前min的next,這樣就讓min離開了原鍊表。 */
}
}
if (first != NULL) /*循環結束得到有序鍊表first */
{
tail->next = NULL; /*單向鍊表的最後一個結點的next應該指向NULL */
}
head = first;
return head;
}
/*
==========================
功能：直接插入排序(由小到大)
返回：指向鍊表表頭的指針
==========================
*/
/*
直接插入排序的基本思想就是假設鍊表的前面n-1個結點是已經按鍵值
（就是用它排序的欄位，我們取學號num為鍵值）排好序的，對於結點n在
這個序列中找插入位置，使得n插入後新序列仍然有序。按照這種思想，依次
對鍊表從頭到尾執行一遍，就可以使無序鍊表變為有序鍊表。
單向鍊表的直接插入排序圖示：
---->[1]---->[3]---->[2]...---->[n]---->[NULL]（原鍊表）
head 1->next 3->next 2->next n->next
---->[1]---->[NULL]（從原鍊表中取第1個結點作為只有一個結點的有序鍊表）
head
圖11
---->[3]---->[2]...---->[n]---->[NULL]（原鍊表剩下用於直接插入排序的結點）
first 3->next 2->next n->next
圖12
---->[1]---->[2]---->[3]...---->[n]---->[NULL]（排序後鍊表）
head 1->next 2->next 3->next n->next
圖13：有N個結點的鍊表直接插入排序
1、先在原鍊表中以第一個結點為一個有序鍊表，其餘結點為待定結點。
2、從圖12鍊表中取結點，到圖11鍊表中定位插入。
3、上面圖示雖說畫了兩條鍊表，其實只有一條鍊表。在排序中，實質只增加了一個用於指向剩下需要排序結點的頭指針first罷了。
這一點請讀者務必搞清楚，要不然就可能認為它和上面的選擇排序法一樣了。
*/
struct student *
InsertSort (struct student *head)
{
struct student *firs
