資料結構–雙鏈表的c/c++實作（超詳細注釋/實驗報告）
知識小回顧
如果希望從表中快速確定某一個結點的前去，其中一個解決方法就是在單鏈表的每個結點再增加一個指向其前去的指標域prior，這樣形成的鏈表中就有兩條方向不同的鏈，稱之為雙向鏈表(Double Linked List)，
實驗題目
實作雙鏈表各種基本運算
實驗目的
- 熟悉將演算法轉換為程式代碼的程序；
- 了解雙鏈表的邏輯結構特性，熟練掌握雙鏈表存盤結構的C語言描述方法；
- 熟練掌握順序表的基本運算：查找、插入、洗掉等，掌握順序表的前驅結點的特性，
實驗要求
- 以雙鏈表作為存盤結構；
- 實作雙鏈表上的資料元素的插入運算；
- 實作雙鏈表上的資料元素的洗掉運算；
- 實作雙鏈表上的資料元素的查找運算，
實驗內容和實驗步驟
1.需求分析
以選單的形式作為用戶與程式的介面，用戶輸入選單號來實行相應的操作，
2. 概要設計
設計幾個函式來實作初始化、插入、洗掉和查找的功能，然后再主函式中呼叫函式來實作操作，
3. 詳細設計
匯入一些庫，并定義表中元素的型別，
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
定義線性表鏈式存盤結構
//定義線性表鏈式存盤結構
typedef struct DLnode
{
ElemType data;//定義資料型別
struct DLnode *prior;//指向前驅的結點
struct DLnode *next;//指向后繼的結點
}DLnode,*DLinkList;
初始化雙鏈表
//初始化雙鏈表
void Init_DLinkList(DLinkList &L)
{
L=(DLnode *)malloc(sizeof(DLnode));//生成頭結點
L->prior=L->next=NULL;//初始化頭、尾指標，使它們都為NULL
}
頭插法創建雙鏈表
//頭插法創建雙鏈表
void Create_DLinkList(DLinkList &L,int n)
{
int i;
DLinkList p;//新開一個結點
Init_DLinkList(L);//初始化一下
for(i=n;i>0;--i)
{
p=(DLinkList)malloc(sizeof(DLnode));//下面是頭插法演算法
p->data=i;
p->next=L->next;
L->next=p;
if(p->next!=NULL)
p->next->prior=p;//因為是雙鏈表，所以還要把前指標給設定好
p->prior=L;//由于是頭插法，所以p永遠是頭結點的下一個結點
}
}
在雙鏈表中查找某個資料元素
//在雙鏈表中查找某個資料元素
int Locate_DLinkList(DLinkList L,ElemType e)
{
int i=1;//i為計數器
DLinkList p=L->next;
while (p!=NULL&&p->data!=e)
{
i++;
p=p->next;
}
if(p==NULL)
{
printf("雙鏈表中不存在該元素！\n");
return 0;
}
else
return i;
}
在雙鏈表的第i個元素之前插入新元素
//在雙鏈表的第i個元素之前插入新元素
int Insert_DLinkList(DLinkList &L,int i,ElemType e)
{
int j=0;
DLinkList p=L,s;
while (p!=NULL&&j<i)//注意回圈體的撰寫，每回圈一次j++，p往后挪一位，j一開始是0，p是頭結點，一次回圈之后j是1，p到了第一個結點
{
j++;
p=p->next;
}
if(p==NULL)
{
printf("插入位置不正確！\n");
return 0;
}
else
{//注意下面賦值陳述句的順序，先把新的線搭好，再把舊的線拆掉
s=(DLnode *)malloc(sizeof(DLnode));//新開一個結點
s->data=e;
s->prior=p->prior;//s的前面是p的前面
s->next=p;
p->prior->next=s;//沒放s之前的時候p的前面的后面應該為s
p->prior=s;//p的前面是s
return 1;
}
}
洗掉雙鏈表中第i個資料元素
//洗掉雙鏈表中第i個資料元素
int Delete_DLinkList(DLinkList &L,int i)
{
int j=0;
DLinkList p=L;
while (j<i&&p!=NULL)//這個回圈體和上面插入是一樣的
{
j++;
p=p->next;
}
if(p==NULL)
{
printf("洗掉位置不正確！\n");
return 0;
}
else
{
p->prior->next=p->next;//p前面的后面等于p的后面，相當于把p給忽略了
if(p->next!=NULL)//如果p不是最后一個的話
{
p->next->prior=p->prior;//p后面的前面等于p的前面，這句和上句一起把p前后兩個結點的指標給設定好了
}
free(p);//釋放p
return 1;
}
}
雙鏈表的顯示
//雙鏈表的顯示
void Display_DLinkList(DLinkList L)
{//沒什么可說的，一個接著一個列印
DLinkList p;
p=L->next;
while (p)
{
printf("%d ",p->data);
p=p->next;
}
}
主函式部分，用一種“選單”的形式使線性表的操作更加地清晰地展示出來，
int main()
{
DLinkList L;
int i=0,j,e,x,t;
char ch;
//Init_DLinkList(L);
Create_DLinkList(L,5);
printf("初始化\n建立雙鏈表如下：\n");
//Display_DLinkList(L);
while(i<5)
{
Display_DLinkList(L);
printf("\n------------------------------------\n");
printf("\n 主選單 \n");
printf(" 1 查找指定元素 \n");
printf(" 2 插入元素到指定位置 \n");
printf(" 3 洗掉某一指定位置元素 \n");
printf(" 4 清屏 \n");
printf(" 0 退出 \n");
printf("------------------------------------\n");
printf("請輸入你選擇的選單號<1, 2, 3, 4, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("請輸入查找元素：");
scanf("%d",&x);
j=Locate_DLinkList(L,x);
if(j!=0)
{
printf("指定元素位置是 %d",j);
}
printf("\n\n");
break;
case 2:
printf("請輸入插入元素位置：");
scanf("%d",&t);
printf("請輸入插入元素值：");
scanf("%d",&x);
j=Insert_DLinkList(L,t,x);
if(j!=0)
{
printf("插入后順序表如下顯示：\n");
Display_DLinkList(L);
printf("\n");
}
printf("\n\n");
break;
case 3:
printf("請輸入洗掉元素位置：");
scanf("%d",&t);
//j=Delete_DLinkList(L,t,x);
j=Delete_DLinkList(L,t);
if(j!=0)
{
printf("洗掉后順序表如下顯示：\n");
Display_DLinkList(L);
printf("\n");
}
printf("\n\n");
break;
case 4:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("輸入有誤~");
}
}
}
4. 除錯分析
遇到的問題及解決方法
-雙鏈表這一個程式主要是依托實驗指導書，但是實驗指導書上有一些代碼設計的不合理，有一些無用的代碼，占用了不必要的空間，然后我就改了一下，
演算法的時空分析
- 都是比較基礎的操作，沒有涉及很復雜的演算法，故時空復雜度也還不算很大，
實驗結果
實驗結果很不錯，所有操作都能正常執行，并且自己加入了“清屏”選項，使得界面更加的整潔，
實驗總結
這是第三個資料結構的代碼實作，主要還是跟著實驗指導書上寫，原創性不足，不過也學到了很多知識，也為之后的程式撰寫搭建了一個不錯的框架！多多重復，百煉成鋼！
最后附上完整的代碼
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int ElemType;
//定義線性表鏈式存盤結構
typedef struct DLnode
{
ElemType data;//定義資料型別
struct DLnode *prior;//指向前驅的結點
struct DLnode *next;//指向后繼的結點
}DLnode,*DLinkList;
//初始化雙鏈表
void Init_DLinkList(DLinkList &L)
{
L=(DLnode *)malloc(sizeof(DLnode));//生成頭結點
L->prior=L->next=NULL;//初始化頭、尾指標，使它們都為NULL
}
//頭插法創建雙鏈表
void Create_DLinkList(DLinkList &L,int n)
{
int i;
DLinkList p;//新開一個結點
Init_DLinkList(L);//初始化一下
for(i=n;i>0;--i)
{
p=(DLinkList)malloc(sizeof(DLnode));//下面是頭插法演算法
p->data=i;
p->next=L->next;
L->next=p;
if(p->next!=NULL)
p->next->prior=p;//因為是雙鏈表，所以還要把前指標給設定好
p->prior=L;//由于是頭插法，所以p永遠是頭結點的下一個結點
}
}
//在雙鏈表中查找某個資料元素
int Locate_DLinkList(DLinkList L,ElemType e)
{
int i=1;//i為計數器
DLinkList p=L->next;
while (p!=NULL&&p->data!=e)
{
i++;
p=p->next;
}
if(p==NULL)
{
printf("雙鏈表中不存在該元素！\n");
return 0;
}
else
return i;
}
//在雙鏈表的第i個元素之前插入新元素
int Insert_DLinkList(DLinkList &L,int i,ElemType e)
{
int j=0;
DLinkList p=L,s;
while (p!=NULL&&j<i)//注意回圈體的撰寫，每回圈一次j++，p往后挪一位，j一開始是0，p是頭結點，一次回圈之后j是1，p到了第一個結點
{
j++;
p=p->next;
}
if(p==NULL)
{
printf("插入位置不正確！\n");
return 0;
}
else
{//注意下面賦值陳述句的順序，先把新的線搭好，再把舊的線拆掉
s=(DLnode *)malloc(sizeof(DLnode));//新開一個結點
s->data=e;
s->prior=p->prior;//s的前面是p的前面
s->next=p;
p->prior->next=s;//沒放s之前的時候p的前面的后面應該為s
p->prior=s;//p的前面是s
return 1;
}
}
//洗掉雙鏈表中第i個資料元素
int Delete_DLinkList(DLinkList &L,int i)
{
int j=0;
DLinkList p=L;
while (j<i&&p!=NULL)//這個回圈體和上面插入是一樣的
{
j++;
p=p->next;
}
if(p==NULL)
{
printf("洗掉位置不正確！\n");
return 0;
}
else
{
p->prior->next=p->next;//p前面的后面等于p的后面，相當于把p給忽略了
if(p->next!=NULL)//如果p不是最后一個的話
{
p->next->prior=p->prior;//p后面的前面等于p的前面，這句和上句一起把p前后兩個結點的指標給設定好了
}
free(p);//釋放p
return 1;
}
}
//雙鏈表的顯示
void Display_DLinkList(DLinkList L)
{//沒什么可說的，一個接著一個列印
DLinkList p;
p=L->next;
while (p)
{
printf("%d ",p->data);
p=p->next;
}
}
int main()
{
DLinkList L;
int i=0,j,e,x,t;
char ch;
//Init_DLinkList(L);
Create_DLinkList(L,5);
printf("初始化\n建立雙鏈表如下：\n");
//Display_DLinkList(L);
while(i<5)
{
Display_DLinkList(L);
printf("\n------------------------------------\n");
printf("\n 主選單 \n");
printf(" 1 查找指定元素 \n");
printf(" 2 插入元素到指定位置 \n");
printf(" 3 洗掉某一指定位置元素 \n");
printf(" 4 清屏 \n");
printf(" 0 退出 \n");
printf("------------------------------------\n");
printf("請輸入你選擇的選單號<1, 2, 3, 4, 0>:\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("請輸入查找元素：");
scanf("%d",&x);
j=Locate_DLinkList(L,x);
if(j!=0)
{
printf("指定元素位置是 %d",j);
}
printf("\n\n");
break;
case 2:
printf("請輸入插入元素位置：");
scanf("%d",&t);
printf("請輸入插入元素值：");
scanf("%d",&x);
j=Insert_DLinkList(L,t,x);
if(j!=0)
{
printf("插入后順序表如下顯示：\n");
Display_DLinkList(L);
printf("\n");
}
printf("\n\n");
break;
case 3:
printf("請輸入洗掉元素位置：");
scanf("%d",&t);
//j=Delete_DLinkList(L,t,x);
j=Delete_DLinkList(L,t);
if(j!=0)
{
printf("洗掉后順序表如下顯示：\n");
Display_DLinkList(L);
printf("\n");
}
printf("\n\n");
break;
case 4:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("輸入有誤~");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303992.html
標籤：python
上一篇：2021ICPC網路賽（第二場）