資料結構與演算法——單鏈表及第三次實驗題解

學習思路

這塊涉及很多指標，所以對很多同學來說都會有難度，我覺的應該先抓一些基本操作，然后再去看大的演算法設計是由哪些基本操作構成的，基本操作大概包括：

• 創建單鏈表；
• 插入元素；
• 洗掉元素；
• 遍歷單鏈表；

書上的結構體、動態記憶體分配都是用C語言的結構體實作的，但我覺得大家可能對C++的new和delete更熟悉一點，而且C++的結構體形式也更加簡單，所以后續的代碼都將用C++給出

單鏈表的基本結構

單鏈表是由一個個的結點組成，每個節點都是指標型別的變數，都包含資料域和指標域，其中資料域用來存盤資料，指標域用來連接下一個結點：

我們用來存盤資料的單鏈表是由一個個上面這樣的結點組成的，對于每個節點，你可以通過它找到它下一個結點，但你不可以通過它找到它上一個結點，這就決定了要對單鏈表進行操作，必須找到目標結點的上一個結點

為了便于操作，我們經常給單鏈表添加頭指標和尾指標，分別指向首結點和尾結點

單鏈表的基本操作

定義單鏈表——C++版

struct node{
    int data; //資料域
    node *next; //指標域
};

創建單鏈表

與創建陣列不同，最初創建單鏈表，其實就是創建頭指標，后續的“擴大單鏈表”，其實就是給頭指標上掛上其他的鏈條，

所以我建議大家直接將“創建單鏈表”理解為“創建頭指標”，然后將其他的賦值、完善等操作理解為“給頭指標掛上新的鏈條”，

創建頭指標用到如下代碼

node *head;
head=new node();
head->next=NULL;

方便起見，我們把后兩句存放在一個初始化函式里：

void initList(node *&head){ //初始化函式
    head=new node();
    head->next=NULL;
}

這樣以后創建頭指標的時候，只要寫：

node *head;
initList(head);

就可以創建好了，

插入元素

插入元素可以很形象地理解為在一條鏈子上插入新的一環，比如將結點p插入到兩個結點之間，也就是插入到結點before之后，其實是這樣的程序：

p->next=before->next; //p的指標域連接last后面的環
before->next=p; //last的指標域連接p

在頭部插入元素

如果我要在最頭上插入一個新結點，那我找不到before，怎么辦？

這就體現出頭指標head的作用了，頭指標head的存在保證了就算你想在最開始的位置插入結點，你還是能找到一個before，來完成你的操作，

p->next=head->next; //p的指標域指向原來的首結點
head->next=p; //頭指標指向p，p成為新的首結點

在尾部插入元素

在尾部插入元素時，最后的元素相當于before，但沒有before->next，我們在最后加一個尾指標tail，這樣插入元素時，情況又變成了在兩個“結點”之間插入一個新的結點，

但值得注意的是，尾指標指向最后一個元素，而不是最后一個元素指向尾指標，所以插入操作與前面略有不同：

tail->next=p; //tail->next表示尾結點的指標域
tail=p; //尾指標指向新的尾結點p

頭指標與尾指標的區別

需要注意的是，頭指標其實是頭結點的指標域，也就是說，頭指標本身是一個結點，但尾指標并不是結點，它只是一個單純的指標，

頭指標通過指標域來發揮“指標”的作用，也就是說，首結點是head->next，在實際應用中，我們要輸出首結點的資料，其實是這樣輸出的：

cout<<head->next->data;

而尾指標就是一個純粹的指標，尾結點就是tail，所以如果要輸出尾結點的資料，是這樣的：

cout<<tail->data;

在初始化單鏈表，也就是創建頭指標的程序中，如果需要添加尾指標，應該是這樣的：

void initList_tail(node *&head){
    head=new node();
    head->next=NULL;
    node *tail=head;
}

因為剛創建頭指標的程序中，頭指標本身就是最后一個元素，所以按照尾指標的定義，應該讓尾指標指向最后一個元素，也就是指向頭指標，

洗掉元素

洗掉元素也可以類比取下鏈條中的某一環，并把這一環銷毀，思路應該是創建一個臨時指標，用來代表這個即將被銷毀的結點，然后重新連接鏈條，并銷毀待洗掉的結點，

node *q=before->next;
before->next=q->next;
delete q;

遍歷元素

單鏈表的遍歷特別有順藤摸瓜搗毀黑幫的感覺，就像你手里掌握著黑幫老大——頭指標，然后通過他，你能找到他的小弟，然后找到小弟的小弟…最后找到的那個人，他是黑幫最底層的人，他沒有小弟——NULL，
需要注意的有兩點：

• 黑幫成員之間有鮮明的等級觀念，只有上級能聯系下屬，下屬無法聯系上級，也就是說單鏈表的遍歷是單向的
• 黑幫老大是個重要人物，不能出事，因為我們一旦失去了黑幫老大，就再也控制不住整個黑幫了，所以每次遍歷的時候，我們需要額外找個跑腿的——作業指標p，用它來聯系小弟們，以保證老大head不被改變，

綜上，遍歷的操作應該是：

void findBro(node *head){
    node *p=head; //作業指標
    //或：node *p=head->next;
    while(p!=NULL){ //判斷當前的人是不是最底層小弟
        //操作
        p=p->next; //找他的小弟
    }
}

求單鏈表的長度

掌握了遍歷的方法后，我們可以在遍歷程序中夾帶一點私貨，比如記錄一下這個黑幫一共有多少人——求單鏈表長度：

int getLength(node *head){ //求長度
    int count=0;
    node *p=head->next; //作業指標
    while(p!=NULL){
        p=p->next;
        count++;
    }
    return count;
}

有了count的引入，就為我們的操作帶來了更多的可能，比如判斷if(count==i)，以實作找到第i個元素等，在后面的部分會給出相應的代碼

單鏈表的進階操作

輸出單鏈表

void output(node *head){ //其實就是在遍歷程序中加一個輸出
    node *p=head->next;
    while(p!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

銷毀單鏈表

拆分為基本操作：遍歷+單個元素洗掉

void destoryList(node *&head){ //銷毀
    node *pre=head,*p=head->next; //從頭結點開始洗掉
    while(p!=NULL){
        delete pre;
        pre=p;
        p=p->next;
    }
}

以已有陣列為基礎創建單鏈表

倒序創建——頭插法

拆分為基本操作：不斷地往表頭插入新結點

void createList(node *&head,int a[],int len){ //已有陣列a，陣列長度len
    for(int i=0;i<len;i++){
        node *s=new node(); //創建一個游離的新結點
        s->data=a[i]; //給新結點賦值
        s->next=head->next; //把新結點插入鏈表的前端
        head->next=s;
    }
}

正序創建——尾插法

拆分為基本操作：不斷地往表尾插入新的結點

void createList_tail(node *head,int a[],int len){
    node *tail=head;
    for(int i=0;i<len;i++){
        node *s=new node(); //創建一個游離的新結點
        s->data=a[i]; //給新結點賦值
        tail->next=s; //把新結點插入鏈表的尾端
        tail=s;
    }
}

洗掉第i個元素

拆分為基本操作：遍歷到第i-1個元素的位置，洗掉它后面的元素

void deleElem(node *&head,int i){ //洗掉第i個元素
    node *p=head; //作業指標
    int count=1;
    while(p!=NULL&&count!=i){
        p=p->next;
        count++;
    }
    node *q=p->next; //基本操作——洗掉
    p->next=q->next;
    delete q;
}

在第i個元素后插入值為value的結點

拆分為基本操作：遍歷到第i個元素的位置，在它后面插入新的元素

void insElem(node *&head,int value,int i){ //在第i個元素后插入值為value的結點
    node *p=head->next; //作業指標
    int count=1;
    while(p!=NULL&&count!=i){
        p=p->next;
        count++;
    }
    node *q=new node(); //創建
    q->data=value;
    q->next=p->next;
    p->next=q;
}

ps. i=0時在頭結點后直接插入結點

找到值為value的元素，并回傳它的位置

拆分為基本操作：遍歷單鏈表直到找到value，然后輸出此時的count

int findValue(node *head,int value){
    node *p=head->next;
    int count=1;
    while(p!=NULL&&p->data!=value)
    {
        p=p->next;
        count++;
    }
    return count;
}

題解

1:整數單鏈表的基本運算-1

題目鏈接：傳送門

描述

設計整數單鏈表的基本運算程式，并用相關資料進行測驗

輸入

順序輸入單鏈表A的各個元素

輸出

第一行：創建單鏈表A后，輸出所有元素
第二行：洗掉第一個元素，輸出洗掉后的所有元素
第三行：輸出洗掉元素后表的長度
第四行：在第二元素處插入一個新的元素100
第五行：輸出第一個元素100所在位置

樣例輸入

1 2 3 4 0 9

樣例輸出

1 2 3 4 0 9
2 3 4 0 9
5
2 100 3 4 0 9
2

題解1

#include <iostream>
using namespace std;
struct node{ //定義鏈表
    int data;
    node *next;
};

//頭結點用head表示

void initList(node *&head){ //初始化函式
    head=new node();
    head->next=NULL;
}

void destoryList(node *&head){ //銷毀鏈表
    node *pre=head,*p=head->next; //從頭結點開始洗掉
    while(p!=NULL){
        delete pre;
        pre=p;
        p=p->next;
    }
}

int getLength(node *head){ //求長度
    int count=0;
    node *p=head->next;
    while(p!=NULL){
        p=p->next;
        count++;
    }
    return count;
}

int findValue(node *head,int value){ //找到值為value的結點
    node *p=head->next;
    int count=1;
    while(p!=NULL&&p->data!=value)
    {
        p=p->next;
        count++;
    }
    return count;
}

void insElem(node *&head,int value,int i){ //在第i個元素后插入值為value的結點
    node *p=head->next;
    int count=1;
    while(p!=NULL&&count!=i){
        p=p->next;
        count++;
    }
    node *q=new node();
    q->data=value;
    q->next=p->next;
    p->next=q;
}

void deleElem(node *&head,int i){ //洗掉第i個元素
    node *p=head;
    int count=1;
    while(p!=NULL&&count!=i){
        p=p->next;
        count++;
    }
    node *q=p->next;
    p->next=q->next;
    delete q;
}

void output(node *head){ //輸出
    node *p=head->next;
    while(p!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

void createList_tail(node *head,int a[],int len){  //尾插法創建鏈表
    node *tc=head;
    for(int i=0;i<len;i++){
        node *s=new node();
        s->data=a[i];
        tc->next=s;
        tc=s;
    }
}

int main()
{
    node *head;
    initList(head);
    int a[10000];
    for(int i=0;i<6;i++)cin>>a[i];
    createList_tail(head,a,6);
    output(head);
    deleElem(head,1);
    output(head);
    cout<<getLength(head)<<endl;
    insElem(head,100,1);
    output(head);
    cout<<findValue(head,100)<<endl;
    destoryList(head);
    return 0;
}

2:整數單鏈表的基本運算-2

題目鏈接：傳送門

描述

設計有序整數單鏈表的插入運算程式，并用相關資料進行測驗

輸入

按升序順序輸入單鏈表A的各個元素和待插入元素

輸出

第一行：創建單鏈表A后，輸出所有元素
第二行：輸出按照升序插入后的所有元素

樣例輸入

0 1 2 3 4 9
7

樣例輸出

0 1 2 3 4 9
0 1 2 3 4 7 9

題解2

這個題需要稍微拐一個彎，就是需要找到插入位之前的元素，所以在比較大小的程序中，需要把手伸的長一點，即如果下一個元素的數值大于待插入元素，那么作業指標p停留在當前元素：

#include <iostream>
using namespace std;
struct node{
    int data;
    node *next;
};
//頭結點用head表示

void initList(node *&head){ //無值初始化
    head=new node();
    head->next=NULL;
}


void destoryList(node *&head){ //銷毀
    node *pre=head,*p=head->next; //從頭結點開始洗掉
    while(p!=NULL){
        delete pre;
        pre=p;
        p=p->next;
    }
}

void output(node *head){
    node *p=head->next;
    while(p!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

void createList_tail(node *head,int a[],int len){
    node *tc=head;
    for(int i=0;i<len;i++){
        node *s=new node();
        s->data=a[i];
        tc->next=s;
        tc=s;
    }
}

int main()
{
    node *head;
    initList(head);
    int a[1000],value;
    for(int i=0;i<6;i++)cin>>a[i];
    cin>>value;
    createList_tail(head,a,6);
    output(head);
    node *p=head->next;
    while(p!=NULL&&p->next->data<=value) 
        p=p->next;
    node *s=new node();
    s->data=value;
    s->next=p->next;
    p->next=s;
    output(head);
    destoryList(head);
    return 0;
}

3:單鏈表的插入和顯示操作

題目鏈接：傳送門

描述

使用尾插法創建鏈表，查找鏈表值最大結點（假定當前鏈表最大值唯一），在最大值結點后插入一個比最大值大10的結點，

#include <malloc.h>
#include <iostream>
using namespace std;

typedef int ElemType;
#define MAX_SIZE 100

typedef struct node
{
	ElemType data;					//資料域
	struct node *next;				//指標域
} SLinkNode;						//單鏈表結點型別

void CreateListR(SLinkNode *&L, ElemType a[], int n)	//尾插法建表
{
	SLinkNode *s, *tc;  int i;
	L = (SLinkNode *)malloc(sizeof(SLinkNode));		//創建頭結點
	tc = L;											//tc為L的尾結點指標
	for (i = 0; i < n; i++)
	{
		s = (SLinkNode *)malloc(sizeof(SLinkNode));
		s->data = a[i];								//創建存放a[i]元素的新結點s
		tc->next = s;									//將s結點插入tc結點之后
		tc = s;
	}
	tc->next = NULL;									//尾結點next域置為NULL
}

int InsElemSpe(SLinkNode *&L)	//插入結點
{

// 在此處補充你的代碼

return 1;					//插入運算成功,回傳1
	
}

void DispList(SLinkNode *L)			//輸出單鏈表
{
	SLinkNode *p = L->next;
	while (p != NULL)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	cout<<endl;
}
void DestroyList(SLinkNode *&L)		//銷毀單鏈表L
{
	SLinkNode *pre = L, *p = pre->next;
	while (p != NULL)
	{
		free(pre);
		pre = p; p = p->next;			//pre、p同步后移
	}
	free(pre);
}
int main()
{

	
	ElemType a[MAX_SIZE];
	
	SLinkNode *L;
	int nlength;
	cin >> nlength;
	for (int i = 0; i < nlength; i++) 
		cin >> a[i];

	
	CreateListR(L, a, nlength);
	InsElemSpe(L);
	DispList(L);
	DestroyList(L);
	return 0;
	
}

輸入

輸入分兩行資料，第一行是尾插法需要插入的資料的個數，第二行是具體插入的數值，

輸出

按程式要求輸出

樣例輸入

4
40 50 70 65

樣例輸出

40 50 70 80 65

題解3

只給出自己寫的那部分函式：

int InsElemSpe(SLinkNode *&L)
{
// 在此處補充你的代碼

    SLinkNode *p=L->next;
    int max_value=0;
    while (p!=NULL){
        max_value=max(max_value,p->data);
        p=p->next;
    }
    SLinkNode *pp=L->next;
    while(pp!=NULL&&pp->data!=max_value)
        pp=pp->next;
    SLinkNode *q=(SLinkNode*)malloc(sizeof(SLinkNode));
    q->data=max_value+10;
    q->next=pp->next;
    pp->next=q;
    
    return 1;					//插入運算成功,回傳1

}