資料結構與演演算法——單連結串列及第三次實驗題解
資料結構與演演算法——單連結串列及第三次實驗題解
學習思路
這塊涉及很多指標，所以對很多同學來說都會有難度。我覺的應該先抓一些基本操作，然後再去看大的演演算法設計是由哪些基本操作構成的。基本操作大概包括：
- 建立單連結串列；
- 插入元素；
- 刪除元素；
- 遍歷單連結串列；
書上的結構體、動態記憶體分配都是用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
}