數(shù)據(jù)結構實驗-實驗3：線性表的查找、插入及刪除

《數(shù)據(jù)結構》實驗報告3

學號：姓名j班級：成績：

實驗名稱：線性表的查找、插入及刪除|實驗地點：理學院機房一

所使用的工具軟件及環(huán)境：VC++

一、實驗目的：

1、掌握線性表的兩類存儲結構（順序存儲結構和鏈式存儲結構）的描述方法。

2、掌握在順序結構中實現(xiàn)查找、插入、刪除操作的基本方法。

3、掌握在各種鏈表結構中實現(xiàn)查找、插入、刪除操作的基本方法。

二、評分標準：

1、評分成績?yōu)锳,B,C,D,E五檔，滿分為A

1）簡答題：每小題回答不完整和錯誤處超過2條（含2條），總分降一檔）

2）算法操作：每回答錯誤或不完整兩小處，總分降一檔。

3）補交作業(yè)成績降一檔

4）抄襲成績?yōu)榱?，且不準補交

一、上機實驗前完成下述問題：

1、線性結構的4個基本特征是什么？

2、線性表的順序表示指的是什么？

答：

3、線性表的鏈式存儲結構的特點是什么？

答:

4、線性表的順序存儲和鏈式存儲的優(yōu)缺點是什么？

答：

5、單鏈表的優(yōu)缺點是什么？

答：

6、循環(huán)鏈表的特點是什么？

答:

7、雙向鏈表的操作特點是什么？

答：

二、算法操作

所要實現(xiàn)的程序：設有n個人圍坐在一圈，現(xiàn)從指定的第1個人開始報數(shù)，

數(shù)到第m個人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m個人又出

列，如此重復，直到所有的人全部出列為止。

算法的參考思想

通過我們對約瑟夫問題的分析，我們認為單循環(huán)鏈表能較好的解決問題。

在建立循環(huán)鏈表時，因為約瑟夫環(huán)的大小有輸入決定。因此與匹配的結點數(shù)

也是變化的，所以要進行動態(tài)內(nèi)存分配。輸出數(shù)據(jù)的存儲單元也就需要動態(tài)

分配了，為方便操作，我們將每個結點數(shù)據(jù)域的值定為生成該結點時的順序

號。

進行操作時,我們用一個變量j來記住掃描過的結點，當掃描到需輸出的結

點的前一個結點時，我們將其直接后繼結點的數(shù)據(jù)域值輸出，并釋放已輸出數(shù)據(jù)

域值的那個結點,然后將j置0,讓j從被刪除結點的下一個結點重新記數(shù),這樣

不斷重復這一系列動作,就可以輕松解決約瑟夫環(huán)問題.

參考源程序(需要修改其中的錯誤，請標注出來并改正，同時需要給出代碼后面標志

為"http://**”符號后進行解釋說明本行代碼實現(xiàn)的功能)

#include<stdio.h>

typedefstructnode{〃*定義單循環(huán)鏈表的結構*(以下按這樣的結構描述)

intdata;

structnode*next;}Lnode;

Lnode*create(intn)

{inti;

Lnode*h,*p,*i-(Lnode*)malloc(sizeof(Lnode));〃**

r->data=n;h=r;〃**

for(i=n-l;i>0;i-)

{p=(Lnode*)malloc(sizeof(Lnode));*

p=->data=I;

p->next=h;

h=p；

)

r->next=h;returnh;

)

voidjeseph(Lnode*p,intm)

{Lnode*q;intj=0;

printf(€6outqueueorder:^^);

do{

j++;

if(j==m-l)

{q=p->next;〃**

p->next=q->next;//**

printf(“％d,,,q->data);

j=O;free(q);}〃**

p=p->next;

}while(p->next!=p)

printfT%d\n"p>data);

free(p);

)

Voidmain()

{Lnode*h;Intm,n;

printff\ninputn,m-u);

scanf("%d,%d”,&n,&m);