鏈表的操作實驗
一、實驗名稱和性質
二、實驗目的
1．掌握線性表的鏈式存盤結構的表示和實作方法，
2．掌握鏈表基本操作的演算法實作，
三、實驗內容
1．建立單鏈表，并在單鏈表上實作插入、洗掉和查找操作（驗證性內容），
2．建立雙向鏈表，并在雙向鏈表上實作插入、洗掉和查找操作（設計性內容），
3．計算已知一個單鏈表中資料域值為一個指定值x的結點個數（應用性設計內容），
四、實驗的軟硬體環境要求
硬體環境要求：PC機（單機）
使用的軟體名稱、版本號以及模塊：
Windows環境下的TurboC2.0以上或VC++ 等，
五、知識準備
前期要求熟練掌握了C語言的編程規則、方法和單鏈表和雙向鏈表的基本操作演算法，
六、驗證性實驗
1．實驗要求
編程實作如下功能
(1）根據輸入的一系列整數，以0標志結束，用頭插法建立單鏈表，并輸出單鏈表中各元素值，觀察輸入的內容與輸出的內容是否一致，
（2）在單鏈表的第i個元素之前插入一個值為x的元素，并輸出插入后的單鏈表中各元素值，
（3）洗掉單鏈表中第i個元素，并輸出洗掉后的單鏈表中各元素值，
（4）在單鏈表中查找第i個元素，如果查找成功，則顯示該元素的值，否則顯示該元素不存在，
2. 實驗相關原理：
線性表的鏈式儲結構是用一組任意的存盤單元依次存放線性表中的元素，這組存盤單元 可以是連續的，也可以是不連續的，為反映出各元素在線性表中的前后邏輯關系，對每個 資料元素來說，除了存盤其本身資料值之外，還需增加一個或多個指標域，每個指標域的值稱為指標，又稱作鏈，它用來指示它在線性表中的前驅或后繼的存盤地址，這兩個部分的的一起組成一個資料元素的存盤映像，稱為結點，若干個結點鏈接成鏈表，如果一個結點中只含一個指標的鏈表，則稱單鏈表，單鏈表的存盤結構描述如下：
typedef struct Lnode {
Elemtype data;/*資料域*/
struct Lnode *next;/*指標域*/
}LNODE,*Linklist; /*其中LNODE為結點型別名，Linklist為指向結點的指標型別名*/
【核心演算法提示】
1．鏈表建立操作的基本步驟：鏈表是一個動態的結構，它不需要予分配空間，因此建立鏈表的程序是一個結點“逐個插入” 的程序，先建立一個只含頭結點的空單鏈表，然后依次生成新結點，再不斷地將其插入到鏈表的頭部或尾部，分別稱其為“頭插法”和“尾插法”，
2．鏈表查找操作的基本步驟：因鏈表是一種"順序存取"的結構，則要在帶頭結點的鏈表中查找到第 i個 元素，必須從頭結點開始沿著后繼指標依次"點數"，直到點到第 i 個結點為止,如果查找成功，則用e回傳第i個元素值，頭結點可看成是第0個結點，
3．鏈表插入操作的基本步驟：先確定要插入的位置，如果插入位置合法，則再生成新的結點，最后通過修改鏈將新結點插入到指定的位置上，
4．鏈表洗掉操作的基本步驟：先確定要洗掉的結點位置，如果位置合法，則再通過修改鏈使被刪結點從鏈表中“卸下”，最后釋放被刪結點的空間，
【核心演算法描述】
void creat1(Linklist &L) /*輸入一系列整數，以0標志結束，將這些整數作為data域并用頭插法建立一個帶頭結點的單鏈表的函式*/
{ L=(Linklist)malloc(sizeof(LNODE));/*生成頭結點*/
L->next=NULL;/*頭結點的指標域初始為空*/
scanf("%d",&node);
while(node!=0)
{ p=(Linklist)malloc(sizeof(LNODE));/*為一個新結點的分配空間*/
p->data=node; /*為新結點資料域賦值*/
p->next=L->next;/*新結點指標域指向開始結點*/
L->next=p; /*頭結點指標域指向新結點，即新結點成為開始結點*/
scanf("%d",&node);
}
}
void creat2(Linklist &L) /*輸入一系列整數，以0標志結束，將這些整數作為data域并用尾插法建立一個帶頭結點的單鏈表的函式*/
{ L=(Linklist)malloc(sizeof(LNODE));/*為頭結點分配空間*/
L->next=NULL; /*頭結點的指標域初始為空*/
r=L; /*尾指標初始指向頭結點*/
scanf("%d",&node);
while(node!=0)
{ p=(Linklist)malloc(sizeof(LNODE));/*為一個新結點分配空間*/
p->data=node; /*新結點資料域賦值*/
p->next=NULL; /*新結點指標域為空*/
r->next=p;/*尾結點指標域指向新結點*/
r=p; /*尾指標指向新結點，即新結點成為尾結點*/
scanf("%d",&node);
}
}
status list_search(Linklist L, int i;Elemtype &e)
/*在帶頭結點的單鏈表L中查找第i個元素，如果查找成功則用e回傳其值*/
{ p=L->next; /*使指標p指向第1個元素結點*/
j=1; /*計數器賦初值為1*/
while (p&& j<i) /*順著后繼指標查找第i個元素結點*/
{ p=p->next;
j++;
}
if (!p&& j>i)
return ERROR; /*如果i值不合法，即i值小于1或大于表長，則出錯*/
e=p->data; /*如果第i個元素存在，則將該元素值賦給e*/
return OK;
}
status list_insert(Linklist &L,int i;Elemtype x)
/*在帶頭結點的單鏈表L中第i個位置之前插入新元素x*/
{ p=L; j=0;
while(p!=NULL&&j<i-1) /*尋找插入位置，并使p指向插入位置的前驅結點，即L中的第i-1個位置*/
{ p=p->next;
++j;
}
if(p==NULL||j>i-1)
return ERROR; /*若位置不正確,即i小于1或大于表的長度加1，則出錯*/
s=(Linklist)malloc(sizeof(LNODE)); /*分配一個新結點的空間*/
s->data=x; /*為新結點資料域賦值*/
/*下面兩條陳述句就是完成修改鏈，將新結點s插入到p結點之后*/
s->next=p->next; /*新結點指標域指向p的后繼結點*/
p->next=s; /*新結點成為p的后繼結點*/
return OK;
}
status list_delete(Linklist &L,int i,Elemtype &x)
/*在帶頭結點的單鏈表L中，洗掉第i個元素結點,并用x回傳其值*/
{ p=L;j=0;
while(p->next!=NULL&&j<i-1) /*尋找被刪結點，并使p指向被刪結點的前驅*/
{ p=p->next;
++j;
}
if (p->next==NULL||j>i-1)
return ERROR; /*若位置不正確，即i小于1或大于表長，則出錯*/
q=p->next; /* q指向p的后繼結點*/
p->next=q->next; /*q的后繼結點成為p的后繼結點*/
x=q->data; /*用x回傳第i個位置的元素*/
free(q); /*釋放q所指的被刪結點的空間*/
return OK;
}
3．源程式代碼參考
#include <stdio.h>
#include <malloc.h>
typedef struct Lnode
{ int data;
struct Lnode *next;
} LNODE,*Linklist;
Linklist creat(Linklist L) /*單鏈表建立函式 */
{int node; Linklist p;
L=(Linklist)malloc(sizeof(LNODE));
L->next=NULL;
printf("\nplease input the node(end with 0):\n ");
/*請求輸入線性表中各個元素，以0結束*/
scanf("%d",&node);
while(node!=0)
{p=(Linklist)malloc(sizeof(LNODE));
if (!p) exit();
p->data=node;
p->next=L->next;
L->next=p;
scanf("%d",&node);
}
return L;
}
Linklist insert(Linklist L,int i,int x) /*單鏈表插入函式*/
{ int j;Linklist p,s;
p=L; j=0;
while (p!=NULL&&j<i-1)
{ p=p->next;
++j;
}
if (p==NULL||j>i-1)
printf("\n ERROR position!\n");
else
{ s=(Linklist)malloc(sizeof(LNODE));
s->data=x;
s->next=p->next;
p->next=s;
}
return L;
}
Linklist delete(Linklist L,int i) /*單鏈表洗掉函式*/
{ int j,x; Linklist p,q;
p=L; j=0;
while(p->next!=NULL&&j<i-1)
{p=p->next;
++j;
}
if(p->next==NULL||j>i-1)
printf("\n ERROE position!\n");
else
{ q=p->next;
p->next=q->next;
x=q->data;
printf("the delete data is:%d\n",x);
free(q);
}
return L;
}
int search(Linklist L, int i) /*單鏈上的查找函式*/
{ Linklist p; int j;
p=L->next;
j=1;
while (p&& j<i)
{ p=p->next;
j++;
}
if (!p&& j>i)
return 0; /*如果i值不合法，即i值小于1或大于表長，則函式回傳0值*/
else
return(p->data); /*否則函式回傳第i個元素的值*/
}
void display(Linklist L) /*單鏈表元素輸出函式*/
{ Linklist p;
p=L->next;
while(p!=NULL)
{ printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
main()/*主函式*/
{Linklist L=NULL; int i,x;
L=creat(L);/*呼叫單鏈表建立函式*/
printf("the Linklist is:\n");
display(L); /*呼叫單鏈表元素輸出(遍歷)函式*/
printf("please input the position you want to insert:");/*請求輸入插入操作位置*/
scanf("%d",&i);
printf("please input the node you want to insert:");/*請求輸入需要插入的元素*/
scanf("%d",&x);
L=insert(L,i,x);/*呼叫單鏈表插入函式*/
printf("the Linklist after inserted is:\n");
display(L);/*呼叫單鏈表元素輸出(遍歷)函式*/
printf("please input the node position you want to delete:"); /*請求輸入洗掉操作位置*/
scanf("%d",&i);
L=delete(L,i); /*呼叫單鏈表洗掉函式*/
printf("the Linklist after deleted is:\n");
display(L); /*呼叫單鏈表元素輸出(遍歷)函式*/
printf("please input the position you want to search:"); /*請求輸入待查找元素的位置*/
scanf("%d",&i);
x=search(L,i); /*呼叫單鏈表查找函式*/
if (x) /*如果查找成功，則顯示第i個元素的值，否則顯示第i個元素不存在*/
printf(" the %dth elem is %d\n",i,x);
else
printf(" the %dth elem is not exsit\n");
}
4．運行結果參考如圖2-1所示：
七、設計性實驗
1.實驗要求
（1）輸入鏈表的長度和各元素的值，用尾插法建立雙向回圈鏈表，并輸出鏈表中各元素值，觀察輸入的內容與輸出的內容是否一致，
（2）在雙向回圈鏈表的第i個元素之前插入一個值為x的元素，并輸出插入后的鏈表中各元素值，
（3）洗掉雙向回圈鏈表中第i個元素，并輸出洗掉后的鏈表中各元素值，
（4）在雙向回圈鏈表中查找值為x元素，如果查找成功，則顯示該元素在鏈表中的位置，否則顯示該元素不存在，
2, 核心演算法提示
雙向回圈鏈表采用的存盤結構描述如下：
typedef struct DULNODE
{ Elemtype data; /*資料域*/
struct DULNODE *prior; /*指向前驅結點的指標域*/
struct DULNODE *next;/*指向后繼結點的指標域*/
}DULNODE,*DuLinklist;
typedef int Elemtype;
不論是建立雙向回圈鏈表還是在雙向回圈鏈表中進行插入、洗掉和查找操作，其操作方法和步驟都跟單鏈表類似，只不過要注意兩點：
（1）凡是在操作中遇到有修改鏈的地方，都要進行前驅和后繼兩個指標的修改，
（2）單鏈表操作演算法中的判斷條件：p= =NULL 或p!=NULL ,在回圈鏈表的操作演算法中則需改為：p!= L,其中L為鏈表的頭指標，
⑶ 核心演算法描述
void DuList_creat (DuLinklist &L,int n) /*輸入n個整數（其中n為表長），將這些整數作為data域并用尾插法建立一個帶頭結點的雙向回圈鏈表的函式*/
{ L=( DuLinklist)malloc(sizeof(DULNODE));/*為頭結點分配空間*/
L->next=L->prior=L;
/*使頭結點的后繼指標和前驅指標都指向自身，形成空的雙向回圈鏈表*/
r=L; /*尾指標初始指向頭結點*/
for (i=0;i<n;i++)
{ p=(DuLinklist)malloc(sizeof(DULNODE));/*為一個新結點分配空間*/
scanf("%d",&p->data); /*從鍵盤輸入值，并保存在新結點資料域中*/
p->next=r->next; /*新結點后繼指標指向尾結點r的后繼結點*/
p->prior=r; /*新結點的前驅指標指向尾結點r*/
r->next=p; /*尾結點的后繼指標指向新結點*/
r=p; /*尾指標指向新結點，即新結點成為尾結點*/
}
L->prior=r; /*使尾結點成為頭結點的前驅結點*/
}
status DuList_search(DuLinklist L, int i;Elemtype &e)
/*在帶頭結點的雙向回圈鏈表L中查找第i個元素，如果查找成功則用e回傳其值*/
{ p=L->next; /*使指標p指向第1個元素結點*/
j=1; /*計數器賦初值為1*/
while (p!=L && j<i) /*順著后繼指標查找第i個元素結點*/
{ p=p->next;
j++;
}
if (j!=i)
return ERROR; /*如果i值不合法，即i值小于1或大于表長，則出錯*/
e=p->data; /*如果第i個元素存在，則將該元素值賦給e*/
return OK;
}
status DuList_insert(DuLinklist &L,int i;Elemtype x)
/*在帶頭結點的雙向回圈鏈表L中第i個位置之前插入新元素x*/
{ p=L->next; j=1;
while(p!=L &&j<i) /*尋找插入位置，并使p指向插入位置的結點，即L中的第i個結點*/
{ p=p->next;
++j;
}
if(j!=i)
return ERROR; /*若位置不正確,即i小于1或大于表的長度加1，則出錯*/
s=(DuLinklist)malloc(sizeof(DULNODE)); /*為一個新結點s分配空間*/
s->data=x; /*為新結點資料域賦值*/
/*下面四條陳述句就是完成修改鏈，將新結點s插入到p結點之前*/
s->next=p;
p->prior->next=s;
s->prior=p->prior;
p->prior=s;
return OK;
}
status DuList_delete(DuLinklist &L,int i,Elemtype &x)
/*在帶頭結點的雙向回圈鏈表L中，洗掉第i個元素結點，并用x回傳其值*/
{ p=L->next;j=1;
while(p!=L&&j<i) /*尋找被刪結點，并使p指向被刪結點的前驅*/
{ p=p->next;
++j;
}
if (j!=i)
return ERROR; /*若位置不正確，即i小于1或大于表長，則出錯*/
q=p; /*記下被刪結點*/
p->prior->next=p->next; /*修改鏈使得p結點從鏈中脫離*/
p->next->prior=p->prior;
x=q->data;
printf("the delete data is:%d\n",x);
free(q); //釋放被刪結點空間
return OK;
}
提醒: 請將上述演算法與單鏈表上相應操作的演算法對照學習，特別注意它們不相同的地方，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/264862.html
標籤：其他
下一篇：IO流實作文章的復制