資料結構與算法——雙連結清單題解
由于作業隻要求前四個題，且最後一道題的測試樣例可能有點問題，是以我先寫一下前四道題的題解
btw. 我做題解的時候，除了給出題目連結外，還會把題抄一遍，主要目的當然是湊字數 是csdn的代碼塊可以直接複制，這樣便于你在自己電腦上寫代碼的時候複制樣例進行測試。再加上為了確定題解能Accepted，我都會自己送出一遍，是以大家：
- 千萬千萬不要直接複制粘貼送出一套帶走，因為這樣不僅沒什麼收獲，還會被老師帶走。
- 不要生看，建議在電腦上看，一邊看一邊抄一遍，哪裡不懂自己運作一下就懂啦！
- 題解非官方，僅供參考，特别是有些題主要是想給大家提供一種不一樣的思路。一定要以老師講的為準！
1:雙連結清單的基本運算
題目連結：傳送門
描述
實作雙連結清單的基本運算：初始化、插入、删除、求表的長度、判空、釋放。
（1）初始化雙連結清單h；
（2）依次采用尾插法插入元素：輸入分兩行資料，第一行是尾插法需要插入的字元資料的個數，第二行是具體插入的字元資料。
（3）輸出雙連結清單h；
（4）輸出雙連結清單h的長度；
（5）判斷雙連結清單h是否為空；
（6）輸出雙連結清單h的第3個元素；
（7）輸出元素a的位置；
（8）在第4個元素位置上插入‘f’元素；
（9）輸出雙連結清單h；
（10）删除L的第5個元素；
（11）輸出雙連結清單h；
（12）釋放雙連結清單h。
輸入
兩行資料，第一行是尾插法需要插入的字元資料的個數，第二行是具體插入的字元資料。
輸出
按照程式要求輸出
樣例輸入
5
a b c d e
樣例輸出
a b c d e
5
no
c
1
a b c f d e
a b c f e
題解
#include <iostream>
#define Element char
using namespace std;
struct node{
Element data;
node *next;
node *prior;
};
void initList(node *&head){ //初始化雙連結清單
head=new node();
head->next=NULL;
head->prior=NULL;
}
void create_Tail(node *&head,Element a[],int len){ //尾插法建表
node *tc=head;
for(int i=0;i<len;i++){
node *s=new node();
s->data=a[i];
tc->next=s;
s->prior=tc;
tc=s;
}
tc->next=NULL;
}
void output(node *head){ //輸出
node *p=head->next;
while (p!=NULL)
cout<<p->data<<" ",p=p->next;
cout<<endl;
}
int getLength(node *head){ //求長度
int count=0;
node *p=head->next;
while (p!=NULL)
count++,p=p->next;
return count;
}
bool isEmpty(node *head){ //判斷是否為空
return head->next==NULL; //1為空
}
Element findTh(node *head,int th){ //找到第th個結點
node *p=head->next;
int count=1;
while (p!=NULL&&count!=th)
count++,p=p->next;
return p->data;
}
int findValue(node *head,Element value){ //找到值為value的結點
int count=1;
node *p=head->next;
while (p!=NULL&&p->data!=value)
count++,p=p->next;
return count;
}
void insElem(node *&head,Element e,int th){ //在第th個結點後插入值為e的結點
node *p=head;
int count=0;
while (p!=NULL&&count!=th)
count++,p=p->next;
node *s=new node();
s->data=e;
s->next=p->next;
if(p->next!=NULL)
p->next->prior=s;
s->prior=p;
p->next=s;
}
void delElem(node *&head,int th){ //删除第th個結點
node *p=head->next;
int count=1;
while (p!=NULL&&count!=th)
count++,p=p->next;
p->next->prior=p->prior;
p->prior->next=p->next;
delete p;
}
void destoryList(node *&head){ //釋放雙連結清單
node *pre=head,*p=pre->next;
while (p!=NULL){
delete pre;
pre=p;
p=p->next;
}
delete pre;
}
int main()
{
node *head;
initList(head);
int n;
char a[1000];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
create_Tail(head,a,n);
output(head);
cout<<getLength(head)<<endl;
if(isEmpty(head))cout<<"yes"<<endl;
else cout<<"no"<<endl;
cout<<findTh(head,3)<<endl;
cout<<findValue(head,'a')<<endl;
insElem(head,'f',3);
output(head);
delElem(head,5);
output(head);
destoryList(head);
return 0;
}
2:整數雙連結清單的基本運算-3
題目連結：傳送門
描述
設計整數雙連結清單的基本通路程式，并用相關資料進行測試
輸入
順序輸入雙連結清單A的各個元素
輸出
第一行：建立雙連結清單A後，按輸入順序輸出所有元素
第二行：按輸入反順序輸出雙連結清單A的所有元素
樣例輸入
樣例輸出
1 2 3 4 0 9
9 0 4 3 2 1
題解
反向輸出的核心思路是先正向找到最後的結點，再從最後借助
prior
往前輸出。
void PDDoutput(node *head){ //反向輸出
node *p=head->next;
while (p->next!=NULL) //找到最後一個結點
p=p->next;
while (p!=head)
cout<<p->data<<" ",p=p->prior; //借助prior往前
cout<<endl;
}
3:整數雙連結清單的基本運算-4
題目連結：傳送門
描述
設計整數雙連結清單的基本通路程式，删除整數雙連結清單中的重複元素，多個值相同的元素隻保留第一個，并用相關資料進行測試
輸入
順序輸入雙連結清單A的各個元素
輸出
第一行：建立雙連結清單A後，輸出所有元素
第二行：删除整數雙連結清單中的重複元素，多個值相同的元素隻保留第一個，然後輸出去重後的雙連結清單A的所有元素
樣例輸入
樣例輸出
0 1 2 4 3 2 4 4 0 9 9
0 1 2 4 3 9
題解
借助一個計數數組來記錄各數字出現的次數，然後将出現次數恰好為1的數字連接配接到頭結點後
int num[1000]={}; //計數數組
void simplify(node *&head){
node *p=head->next;
while (p->next!=NULL){ //保證停止的時候p指向最後一個結點
num[p->data]++; //記錄p->data出現了一次
p=p->next;
}
num[p->data]++; //記錄最後一個結點的資料
while(p!=head){ //逆向删除，以保證被删掉的是“後面的”資料
num[p->data]--; //次數減小
if(num[p->data]!=0){ //如果不為0，說明前面還有一樣的數，那麼删除現在這個結點
if(p->next!=NULL) //删除時候注意判斷邊界
p->next->prior=p->prior;
if(p->prior!=NULL)
p->prior->next=p->next;
delete p;
}
p=p->prior; //逆向查找
}
}
4:循環雙連結清單的基本運算
題目連結：傳送門
描述
實作循環雙連結清單的基本運算：初始化、插入、删除、求表的長度、判空、釋放。
（1）初始化循環雙連結清單h；
（2）依次采用尾插法插入元素：輸入分兩行資料，第一行是尾插法需要插入的字元資料的個數，第二行是具體插入的字元資料。
（3）輸出循環雙連結清單h；
（4）輸出循環雙連結清單h的長度；
（5）判斷循環雙連結清單是否為空；
（6）輸出循環雙連結清單h的第3個元素；
（7）輸出元素a的位置；
（8）在第4個元素位置上插入‘f’元素；
（9）輸出循環雙連結清單h；
（10）删除L的第5個元素；
（11）輸出循環雙連結清單h；
（12）釋放循環雙連結清單h。
輸入
兩行資料，第一行是尾插法需要插入的字元資料的個數，第二行是具體插入的字元資料。
輸出
按照程式要求輸出
樣例輸入
5
a b c d e
樣例輸出
a b c d e
5
no
c
1
a b c f d e
a b c f e
題解
循環雙連結清單隻要把雙連結清單中的
NULL
改為
head
即可
#include <iostream>
#define Element char
using namespace std;
struct node{
Element data;
node *next;
node *prior;
};
void initList(node *&head){ //初始化雙連結清單
head=new node();
head->next=head;
head->prior=head;
}
void create_Tail(node *&head,Element a[],int len){ //尾插法建表
node *tc=head;
for(int i=0;i<len;i++){
node *s=new node();
s->data=a[i];
tc->next=s;
s->prior=tc;
tc=s;
}
tc->next=head; //最後一個結點的prior應該指向head
}
void output(node *head){ //輸出
node *p=head->next;
while (p!=head)
cout<<p->data<<" ",p=p->next;
cout<<endl;
}
int getLength(node *head){ //求長度
int count=0;
node *p=head->next;
while (p!=head)
count++,p=p->next;
return count;
}
bool isEmpty(node *head){ //判斷是否為空
return head->next==head; //1為空
}
Element findTh(node *head,int th){ //找到第th個結點
node *p=head->next;
int count=1;
while (p!=head&&count!=th)
count++,p=p->next;
return p->data;
}
int findValue(node *head,Element value){ //找到值為value的結點
int count=1;
node *p=head->next;
while (p!=head&&p->data!=value)
count++,p=p->next;
return count;
}
void insElem(node *&head,Element e,int th){ //在第th個結點後插入值為e的結點
node *p=head->next;
int count=1;
while (p!=head&&count<th)
count++,p=p->next;
node *s=new node();
s->data=e;
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
}
void delElem(node *&head,int th){ //删除第th個結點
node *p=head->next;
int count=1;
while (p!=head&&count!=th)
count++,p=p->next;
p->next->prior=p->prior;
p->prior->next=p->next;
delete p;
}
void destoryList(node *&head){ //釋放雙連結清單
node *pre=head,*p=pre->next;
while (p!=head){
delete pre;
pre=p;
p=p->next;
}
delete pre;
}
int main()
{
node *head;
initList(head);
int n;
char a[1000];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
create_Tail(head,a,n);
output(head);
cout<<getLength(head)<<endl;
if(isEmpty(head))cout<<"yes"<<endl;
else cout<<"no"<<endl;
cout<<findTh(head,3)<<endl;
cout<<findValue(head,'a')<<endl;
insElem(head,'f',3);
output(head);
delElem(head,5);
output(head);
destoryList(head);
return 0;
}
![Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)