資料結構與演算法——單鏈表及第三次實驗題解
文章目錄
- 資料結構與演算法——單鏈表及第三次實驗題解
- 學習思路
- 單鏈表的基本結構
- 單鏈表的基本操作
- 定義單鏈表——C++版
- 創建單鏈表
- 插入元素
- 在頭部插入元素
- 在尾部插入元素
- 頭指標與尾指標的區別
- 洗掉元素
- 遍歷元素
- 求單鏈表的長度
- 單鏈表的進階操作
- 輸出單鏈表
- 銷毀單鏈表
- 以已有陣列為基礎創建單鏈表
- 倒序創建——頭插法
- 正序創建——尾插法
- 洗掉第i個元素
- 在第i個元素后插入值為value的結點
- 找到值為value的元素,并回傳它的位置
- 題解
- 1:整數單鏈表的基本運算-1
- 描述
- 輸入
- 輸出
- 樣例輸入
- 樣例輸出
- 題解1
- 2:整數單鏈表的基本運算-2
- 描述
- 輸入
- 輸出
- 樣例輸入
- 樣例輸出
- 題解2
- 3:單鏈表的插入和顯示操作
- 描述
- 輸入
- 輸出
- 樣例輸入
- 樣例輸出
- 題解3
學習思路
這塊涉及很多指標,所以對很多同學來說都會有難度,我覺的應該先抓一些基本操作,然后再去看大的演算法設計是由哪些基本操作構成的,基本操作大概包括:
- 創建單鏈表;
- 插入元素;
- 洗掉元素;
- 遍歷單鏈表;
書上的結構體、動態記憶體分配都是用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
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/136328.html
標籤:其他
