《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)教案

數(shù)據(jù)結(jié)構(gòu)

實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)課程：數(shù)據(jù)結(jié)構(gòu)

學(xué)號(hào)：2016031124

學(xué)生姓名：

班級(jí)：16軟件

2017年月日

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)一函數(shù)與結(jié)構(gòu)體（復(fù)習(xí)）

一、實(shí)驗(yàn)?zāi)康模?/p>

鞏固復(fù)習(xí)前期所學(xué)C語言的函數(shù)參數(shù)傳遞、指針和結(jié)構(gòu)體等知識(shí)點(diǎn)，加強(qiáng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)語言基礎(chǔ)。

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容：

1.用數(shù)組處理Fibonacci數(shù)列問題。

已知Fibonacci數(shù)列：

112358132134??輸出數(shù)列的前20項(xiàng)。

#include<stdio.h>

intmain()

{

inta[22],i,n;

a[0]=a[1]=1;

for(i=2;i<21;i++)

a[i]=a[i-1]+a[i-2];

printf("%d",a[0]);

for(i=1;i<21;i++)

printf("%d",a[i]);

printf("\n");

return0;}

2.下面的程序的功能是：輸入三個(gè)整數(shù)，輸出其中最大的數(shù)，補(bǔ)足所缺語句。

2

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

#include<stdio.h>

intmax(intx,inty);/*函數(shù)max的聲明*/

intmax3(intx,inty,intz);/*函數(shù)max3的聲明*/

voidmain()

{

inta,b,c,m;

printf("請(qǐng)輸入三個(gè)整數(shù)，用逗號(hào)隔開：\n");

scanf("%d,%d,%d",&a,&b,&c);/*從鍵盤接收3個(gè)整數(shù)*/

m=max3(a,b,c);

printf("Maxis%d\n",m);

getch();

}

intmax(intx,inty)/*函數(shù)功能：返回x、y的最大值*/

{

return(x>y?x:y);

}

intmax3(intx,inty,intz)/*函數(shù)功能：返回x、y、z的最大值*/

{

intm;

m=max(max(x,y),z);

returnm;

}

3.學(xué)生信息的顯示，具體要求如下：

1）定義一個(gè)結(jié)構(gòu)體描述學(xué)生信息(學(xué)號(hào),姓名,性別,年齡,住址)；

2）設(shè)計(jì)一個(gè)函數(shù)，用于顯示單個(gè)學(xué)生信息，函數(shù)的參數(shù)為前面定義的結(jié)構(gòu)體類型；

3）設(shè)計(jì)一個(gè)主函數(shù)，在主函數(shù)中輸入學(xué)生的信息，并調(diào)用前面定義的函數(shù)進(jìn)行顯示（學(xué)生人數(shù)不

少于5人）。

3

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

提示：可用結(jié)構(gòu)體數(shù)組保存學(xué)生信息。

4.輸入若干個(gè)整數(shù)作為數(shù)組元素值，然后按輸入時(shí)順序的就地逆置排序，最后打印出逆置后的元

素值。例如輸入：1023045，逆置后顯示為：5430210。

四、程序運(yùn)行結(jié)果和源代碼為：

此處寫程序源代碼，請(qǐng)?jiān)诔绦蛑羞m當(dāng)注釋，便于老師更快地看懂你的程序。

此處寫出程序運(yùn)行的結(jié)果，即輸入數(shù)據(jù)是什么，輸出數(shù)據(jù)是什么，分析結(jié)果是否正確，如果

不正確是什么原因。

五、實(shí)驗(yàn)總結(jié)

1、收獲

2、存在的問題

4

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)二線性表的算法實(shí)現(xiàn)

一、實(shí)驗(yàn)?zāi)康模?/p>

1、掌握線性表的定義方法；

2、.掌握線性表基本操作的實(shí)現(xiàn)方法；

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容及思路：

要求：將調(diào)試好的代碼存放到各算法的空白處。

1、線性表的定義：

#defineMAX最大長(zhǎng)度值

typedefstruct

{datatypedata[MAX];

intlast;

}list;

2、線性表的初始化

思路：順序表的初始化就是構(gòu)造一個(gè)空表，或者說是為了給線性表l分配存儲(chǔ)空間。由于采用的是

靜態(tài)存儲(chǔ)結(jié)構(gòu)（數(shù)組），線性表的存儲(chǔ)空間是由編譯系統(tǒng)分配的，因此，只要對(duì)線性表的長(zhǎng)度進(jìn)行

初始化即可。

3、求線性表的長(zhǎng)度

4、插入運(yùn)算

思路：在保證所給插入位置i合理的前提下，必須先將第i個(gè)及其以后的數(shù)據(jù)元素，向后移動(dòng)一個(gè)

元素的位置，然后才能將新的元素x存入留出的空位置上，插入后使原表長(zhǎng)last的長(zhǎng)度值加1。

5、刪除運(yùn)算

思路：在此討論線性表的刪除運(yùn)算是指將表中第i個(gè)元素從線性表中去掉，因?yàn)槭琼樞虼鎯?chǔ)結(jié)構(gòu)，

在保證所給刪除位置i合理的前提下，刪除后必須將第i+1個(gè)及其以后的元素前移一個(gè)位置，最后

表的長(zhǎng)度減1。

5

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

6、查找

思路：在此討論線性表的查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。從線性表的第一個(gè)

元素l->data[1]起依次和x比較，直到找到一個(gè)與x相等的數(shù)據(jù)元素，則返回它在線性表中

的存儲(chǔ)下標(biāo)；或者查遍整個(gè)表都沒有找到與x相等的元素，返回0。

7、線性表元素的輸出

8、主函數(shù)main()

程序結(jié)構(gòu)：

（1）聲明變量及線性表；

（2）初始化線性表；

（3）輸入線性表的元素（提示：用插入算法來實(shí)現(xiàn)）；

（4）輸出線性表中的元素；

（5）顯示線性表的長(zhǎng)度；

（6）在線性表中進(jìn)行元素查找（可提供元素值，也可以提供元素位置）；

（7）往線性表中插入數(shù)據(jù)元素（提供元素值及位置）；

（8）刪除線性表中的數(shù)據(jù)元素（提供元素值或位置）；

（9）輸出線性表中最后的結(jié)果。

四、程序運(yùn)行結(jié)果和源代碼為：

五、實(shí)驗(yàn)總結(jié)：

1、收獲

2、存在的問題

6

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)三線性表的應(yīng)用

一、實(shí)驗(yàn)?zāi)康模?/p>

1、進(jìn)一步掌握線性表的定義方法；

2、進(jìn)一步掌握線性表基本操作的實(shí)現(xiàn)方法；

3、掌握線性表的應(yīng)用。

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容及思路：

要求：將調(diào)試好的代碼存放到各算法的空白處。

1、有兩個(gè)線性表la和lb，類型為list。編寫一個(gè)算法將它們合并成一個(gè)線性表la，要求將lb接到

la的后面，并且要求lb中的元素在la中已存在，則不把該元素合進(jìn)去。

算法思路：把線性表la和lb的長(zhǎng)度分別賦給n和m；從lb中的第一個(gè)元素起，對(duì)每一個(gè)元素與la

中的每一個(gè)元素進(jìn)行查找比較，若未找到則將這個(gè)lb元素插入到la表尾，否則繼續(xù)比較下一個(gè)，

直到lb中所有元素比較完，則合并完成；并應(yīng)保證la表足夠長(zhǎng)。

2、已知一個(gè)線性表la中的元素已按升序排列，其類型為list。編寫一個(gè)算法將該線性表中的重復(fù)

元素刪除（即在表中不能有相同的元素）。

算法思路：由于線性表la中的元素已按升序排列，所以值相同的元素必為相鄰的元素，因此依次

比較相鄰的兩個(gè)元素，若值相等，則刪除其中的一個(gè)，否則繼續(xù)向后比較，直到表尾。

3、有順序表A和B，其元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)順序表C，

要求C的元素也是從小到大的升序排列。

算法思路：依次掃描通過A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此址

到一個(gè)線性表掃描完畢，然后將未完的那個(gè)順序表中余下部分賦給C即可。C的容量要能夠容納A、

B兩個(gè)線性表相加的長(zhǎng)度。

7

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

4、主函數(shù)main()

程序結(jié)構(gòu)：

（1）聲明變量及線性表；

（2）初始化線性表；

（3）輸入線性表的元素（提示：用插入算法來實(shí)現(xiàn)）；

（4）輸出線性表中的元素；

（5）對(duì)兩個(gè)線性表進(jìn)行按升序合并

（6）輸出合并后線性表中元素。

四、程序運(yùn)行結(jié)果和源代碼為：

五、實(shí)驗(yàn)總結(jié)：

1、收獲

2、存在的問題

8

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)四棧的實(shí)現(xiàn)

一、實(shí)驗(yàn)?zāi)康模?/p>

1、理解棧的線性結(jié)構(gòu)的特點(diǎn)；

2、掌握棧的順序表示；

2、掌握棧基本操作的實(shí)現(xiàn)方法；

3、能夠應(yīng)用棧設(shè)計(jì)算法解決實(shí)際問題。

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容及思路：

要求：將調(diào)試好的代碼存放到各算法的空白處。

1、棧的定義：

#defineMAX棧中允許存放元素的最大個(gè)數(shù)

typedefstruct

{datatypedata[MAX];

inttop;

}stack;

2、棧的基本算法的實(shí)現(xiàn)

⑴棧初始化：init(s)構(gòu)造了一個(gè)空棧；

⑵判棧空：empty(s)若棧s為空棧返回為1，否則返回為0；

⑶入棧：push(s,x)在棧s的頂部插入一個(gè)新元素x，使x成為新的棧頂元素；

⑷出棧：pop(s)棧s的頂部元素從棧中刪除；

⑸讀棧頂元素：get(s)取棧頂元素作為結(jié)果返回；

⑹置棧空：clear(s)清除棧s中的所有元素，使之成為空棧。

利用主函數(shù)main()調(diào)用上述函數(shù)。

3、利用棧結(jié)構(gòu)實(shí)現(xiàn)“數(shù)制轉(zhuǎn)換”問題

要求：輸入的一個(gè)十進(jìn)制數(shù)，能夠轉(zhuǎn)換成相應(yīng)的八進(jìn)制數(shù)，并輸出。

思路：把十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)采用的方法是“除8取余”，直到商為0。依次得到的余數(shù)是

k1,k2,k3,??,km,而轉(zhuǎn)換后的八進(jìn)制數(shù)是kmkm-1?k3k2k1，從結(jié)果看恰好與計(jì)算過程相反，因此

9

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

轉(zhuǎn)換過程中每得到一位八進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。此種方法同

樣適用于將十進(jìn)制數(shù)轉(zhuǎn)換為r進(jìn)制的數(shù)。把十進(jìn)制整數(shù)11轉(zhuǎn)換為八進(jìn)制的過程如下：

（1）定義“棧”的結(jié)構(gòu)

（2）實(shí)現(xiàn)“?！钡幕静僮?/p>

①棧初始化操作InitStack

②進(jìn)棧操作Push

③出棧操作Pop

④判斷棧是否為空操作Empty

（3）實(shí)現(xiàn)主程序main()

主程序主要是用來控制程序的執(zhí)行過程，實(shí)現(xiàn)數(shù)制的轉(zhuǎn)換操作，以及輸入、輸出。

程序結(jié)構(gòu)：

①聲明變量及棧；

②初始化棧；

③輸入要轉(zhuǎn)換的十進(jìn)制數(shù)；

④進(jìn)行進(jìn)制轉(zhuǎn)換，余數(shù)入棧，商作為被除數(shù)繼續(xù)運(yùn)算；

⑤顯示轉(zhuǎn)換后的八進(jìn)制數(shù)（利用出棧）。

（4）程序的編譯、鏈接

（5）程序的調(diào)試

4、雙棧操作

設(shè)有兩個(gè)棧s1和s2共享一個(gè)連續(xù)的存儲(chǔ)空間ds[1]~ds[m]，它們對(duì)應(yīng)的棧頂指針分別是top1和

top2，s1的棧底設(shè)在ds[1]處，s2的棧底設(shè)在ds[m]處，分別編寫s1和s2的進(jìn)棧函數(shù)push(ds,x,k)

和出棧函數(shù)pop(ds,k)。提示：利用一個(gè)變量判斷應(yīng)對(duì)s1還是s2進(jìn)行操作。

算法思路：按提示設(shè)當(dāng)K=1時(shí)對(duì)s1進(jìn)行操作，否則對(duì)s2進(jìn)行操作。當(dāng)top2=top1+1表示棧滿，

都不能進(jìn)棧，當(dāng)top1=0時(shí)s1不能出棧，而top2=m+1時(shí)s2不能出棧。

四、程序運(yùn)行結(jié)果和源代碼為：

五、、實(shí)驗(yàn)總結(jié)：

1、收獲

2、存在的問題

10

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)五棧的應(yīng)用和隊(duì)列的實(shí)現(xiàn)

一、實(shí)驗(yàn)?zāi)康模?/p>

1、理解棧和隊(duì)列的定義及線性存儲(chǔ)；

2、掌握棧和隊(duì)列的運(yùn)算方法；

3、了解循環(huán)隊(duì)列的定義及相關(guān)算法；

3、能夠應(yīng)用棧和隊(duì)列設(shè)計(jì)算法，解決實(shí)際問題。

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容及思路：

要求：將調(diào)試好的代碼存放到各算法的空白處。

1、隊(duì)列的定義：

#defineMAX隊(duì)列的最大容量

typedefstruct

{datatypedata[MAX];

intf,r;

}queue;

2、隊(duì)列的基本算法的實(shí)現(xiàn)

（1）隊(duì)列初始化：init(q)

（2）入隊(duì)操作：insert(q,x)

思路：入隊(duì)時(shí)，首先判隊(duì)是否滿了，隊(duì)滿的條件為：q->r==MAX-1，隊(duì)滿時(shí)，不能入隊(duì)，可以進(jìn)

行溢出錯(cuò)誤處理，若可以入隊(duì)則先將隊(duì)尾指針后移(q->r++)，再將元素賦給隊(duì)尾單元。

（3）出隊(duì)操作：delete(q,x)

思路：先判隊(duì)列是否為空，為空時(shí)不能出隊(duì)，若可以出隊(duì)，則可先將隊(duì)首元素賦給指定變量（若不

需要保留，可以省去這一步），隊(duì)首指針后移（q->f--）。

（4）讀隊(duì)頭元素：get(q,x)

思路：先判隊(duì)列是否為空，為空時(shí)不能取元素，否則取出隊(duì)首元素，但隊(duì)首指針保持不變。

（5）判隊(duì)空操作：empty(q)

（6）置隊(duì)空：clear(q)

11

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

3、利用棧結(jié)構(gòu)實(shí)現(xiàn)“算術(shù)表達(dá)式”問題

要求：輸入的一個(gè)十進(jìn)制數(shù)，能夠轉(zhuǎn)換成相應(yīng)的八進(jìn)制數(shù)，并輸出。

思路：1、先將輸入的中綴表達(dá)式，存入字符數(shù)組a中，取出a數(shù)組中的每一個(gè)字符存于c變量中，

對(duì)于每一個(gè)c變量的值做如下處理：

①若c為數(shù)字，則存于數(shù)組b中；

②若c為左括號(hào)'('，則將其壓入棧s;

③若c為右括號(hào)')'，則將棧s中左括號(hào)'('以后的運(yùn)算符依次出棧，存于數(shù)組b中，然后將

左括號(hào)'('出棧；

④若c為'+'或'-'，則將棧s中左括號(hào)'('以后的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將

c壓入棧s中；

⑤若c為'*'或'/'，則將棧s中的棧頂端連續(xù)的'*'或'/'出棧，存于數(shù)組b中，然后將c壓入

棧s中

⑥若c為'='，則將棧S中的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將c存于數(shù)組b

中，最后得到的后綴表達(dá)式存儲(chǔ)在字符數(shù)組b中。

2、后綴表達(dá)式求值

具體思路：需要一個(gè)存放數(shù)值的棧s1，當(dāng)從左向右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入棧中

保存，每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果再入棧，直到整個(gè)

表達(dá)式結(jié)束，這時(shí)棧頂存放的值就是后綴表達(dá)式的結(jié)果。

4、主程序主要是用來控制程序的執(zhí)行過程。

四、程序運(yùn)行結(jié)果和源代碼為：

五、、實(shí)驗(yàn)總結(jié)：

1、收獲

2、存在的問題

12

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)六——八鏈表的建立及應(yīng)用、鏈棧及鏈隊(duì)列

一、實(shí)驗(yàn)?zāi)康模?/p>

1、理解單鏈表的定義及存儲(chǔ)結(jié)構(gòu)；

2、掌握單鏈表的基本運(yùn)算方法；

3、了解鏈棧和鏈隊(duì)列的應(yīng)用方法；

4、能夠應(yīng)用單鏈表設(shè)計(jì)算法，解決實(shí)際問題。

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容及思路：

要求：將調(diào)試好的代碼存放到各算法的空白處。

單鏈表的定義：

typedefstructnode

{datatypedata;

structnode*next;

}linklist;

1、利用首插法和尾插法實(shí)現(xiàn)單鏈表的創(chuàng)建。

2、單鏈表的插入運(yùn)算。

要求：

在單鏈表的第i個(gè)元素之前插入一個(gè)元素x。

實(shí)現(xiàn)思想：

（1）找到第i-1個(gè)元素

（2）在i-1個(gè)元素之后插入x

3、在單鏈表中按值查找。

算法思路：從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)其值是否等于x，若是，返回該結(jié)點(diǎn)的地址，

否則繼續(xù)向后查找，直到鏈表結(jié)束為止。找不到時(shí)返回空。

13

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

4、單鏈表的刪除運(yùn)算。

（1）在指定位置刪除。

要求：刪除單鏈表的第i個(gè)元素

實(shí)現(xiàn)思想：1、找到第i-1個(gè)元素；2、刪除第i個(gè)元素。

（2）根據(jù)所給條件找到位置再進(jìn)行刪除。

5、試寫一算法求帶頭結(jié)點(diǎn)的單鏈表L的長(zhǎng)度。

思路：?jiǎn)捂湵淼拈L(zhǎng)度是指單鏈表中結(jié)點(diǎn)的個(gè)數(shù)。求單鏈表表長(zhǎng)的基本操作是移動(dòng)指針，將指針從表

頭移動(dòng)到表尾。在指針移動(dòng)過程中，累計(jì)掃描過的結(jié)點(diǎn)數(shù)即為表長(zhǎng)。由此需要設(shè)一個(gè)指針p，順鏈

向后移動(dòng)；還要設(shè)一個(gè)整型變量j，作為計(jì)數(shù)器。指針p的初始值指向頭結(jié)點(diǎn)，計(jì)數(shù)器j的初始值

為0。

程序參考：

intLength_LinkList1(LinkListL)

{Lnode*p=L;/*p指向頭結(jié)點(diǎn)*/

intj=0;

while(p->next)

{p=p->next;j++}/*p所指的是第j個(gè)結(jié)點(diǎn)*/

returnj;

}

6、已知帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫一算法將值為x的結(jié)點(diǎn)插

人表中，使L仍然有序。

7、試寫一算法對(duì)帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置。

算法描述：

（1）空表或長(zhǎng)度為1的表不做任何處理

（2）長(zhǎng)度大于等于2時(shí)，做如下處理：從表中第二個(gè)結(jié)點(diǎn)開始，依次取原鏈表中的結(jié)點(diǎn)，將其作

為第一個(gè)結(jié)點(diǎn)插入到新鏈表中去。

8、編程序判斷一個(gè)字符序列是否是回文，要求采用鏈?zhǔn)疥?duì)列和鏈?zhǔn)蕉褩！?/p>

算法提示：設(shè)字符數(shù)組str中存放了要判斷的字符串。把字符數(shù)組中的字符逐個(gè)分別存入隊(duì)列和堆

棧，然后逐個(gè)出隊(duì)列和退棧并比較出隊(duì)列的字符和退棧的字符是否相等，若全部相等則該字符序列

14

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

是回文，否則就不是回文。

四、程序運(yùn)行結(jié)果和源代碼為：

五、、實(shí)驗(yàn)總結(jié)：

1、收獲

2、存在的問題

15

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)九——十二叉樹的建立及遍歷

一、實(shí)驗(yàn)?zāi)康模?/p>

1、熟悉二叉鏈表表示的二叉樹結(jié)構(gòu)及其遞歸遍歷；

2、掌握建立二叉鏈表要領(lǐng)；

3、理解遞歸遍歷二叉鏈表的執(zhí)行路徑；

4、掌握二叉樹的中序遍歷的非遞歸思路；了解二叉樹的后序遍歷的非遞歸思路

5、能利用二叉樹的遍歷策略解決實(shí)際問題；

6、了解哈夫曼編碼的思路及方法。

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容及思路：

要求：將調(diào)試好的代碼存放到各算法的空白處。

二叉樹的二叉鏈表存儲(chǔ)表示可描述為：

typedefstructbitnode

{elemtypedata;

structbitnode*lchild,*rchild;

/*左、右孩子指針*/

}bintree;

1、建立一顆二叉鏈表表示的二叉樹。

思路：

先將二叉樹通過加入虛節(jié)點(diǎn)的方式使其完全化，然后按層將其輸入?？梢杂枚鏄渲胁粫?huì)出現(xiàn)

字符表示虛節(jié)點(diǎn)例如#，用例二叉樹如圖1所示。

圖1

輸入該二叉鏈表時(shí)，應(yīng)按如下順序：AB#DE###C##。

16

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

2、對(duì)其進(jìn)行先序，中序，后序輸出。（用遞歸方法實(shí)現(xiàn)）

（1）先序遍歷

（2）中序遍歷

（3）后序遍歷

3、實(shí)現(xiàn)二叉樹的中序遍歷的非遞歸算法。

提示：二叉樹以二叉鏈表存放，一維數(shù)組stack[MAX]用以實(shí)現(xiàn)棧，變量top用來表示當(dāng)前棧頂?shù)?/p>

位置。

4、統(tǒng)計(jì)二叉樹中葉結(jié)點(diǎn)的數(shù)目

算法思想：

（1）若二叉樹為空，則它的葉結(jié)點(diǎn)的數(shù)目為0

（2）若二叉樹只有一個(gè)結(jié)點(diǎn)，則它的葉結(jié)點(diǎn)的數(shù)目為1

（3）否則，它的葉結(jié)點(diǎn)的數(shù)目等于左子樹的葉結(jié)點(diǎn)的數(shù)目和右子樹葉結(jié)點(diǎn)的數(shù)目之和。

5、求二叉樹的深度

算法思想：

（1）若二叉樹為空，則它的深度等于0

（2）否則，它的深度等于左子樹和右子樹中的最大深度加1。

6、在二叉樹中查找數(shù)據(jù)元素

算法思想：

在二叉樹中查找數(shù)據(jù)元素x。查找成功時(shí)返回該結(jié)點(diǎn)的指針；查找失敗時(shí)返回空指針。

17

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

7、實(shí)現(xiàn)哈夫曼編碼

實(shí)現(xiàn)哈夫曼編碼的算法可分為兩大部分：

（1）構(gòu)造哈夫曼樹；

（2）在哈夫曼樹上求葉子結(jié)點(diǎn)的編碼。

求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉子結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回

退到根結(jié)點(diǎn)，每回退一步，就走過了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字

符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得

到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼?？梢栽O(shè)置一結(jié)構(gòu)數(shù)組

huffcode用來存放各字符的哈夫曼編碼信息，數(shù)組元素的結(jié)構(gòu)如下：

bitstart

其中，分量bit為一維數(shù)組，用來保存字符的哈夫曼編碼，start表示該編碼在數(shù)組bit中的開始位

置。所以，對(duì)于第i個(gè)字符，它的哈夫曼編碼存放在huffcode[i].bit中的從huffcode[i].start到n的分

量上。

8、完成知識(shí)實(shí)踐九。

四、程序運(yùn)行結(jié)果和源代碼為：

五、、實(shí)驗(yàn)總結(jié)：

1、收獲

2、存在的問題

18

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)十一靜態(tài)查找

一、實(shí)驗(yàn)?zāi)康模?/p>

1、加深對(duì)查找的理解；

2、掌握靜態(tài)查找表的存儲(chǔ)結(jié)構(gòu)；

3、掌握順序查找、二分查找及其查找的算法。

4、了解分塊查找的思路。

二、實(shí)驗(yàn)要求

1、學(xué)生提前準(zhǔn)備好實(shí)驗(yàn)報(bào)告，預(yù)習(xí)并熟悉實(shí)驗(yàn)步驟；

2、遵守實(shí)驗(yàn)室紀(jì)律，在規(guī)定的時(shí)間內(nèi)完成要求的內(nèi)容；

3、1~2人為1小組，實(shí)驗(yàn)過程中獨(dú)立操作、相互學(xué)習(xí)。

三、實(shí)驗(yàn)內(nèi)容及思路：

要求：將調(diào)試好的代碼存放到各算法的空白處。

靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)

typedefstruct

{elemtypeelem[MAX];/*數(shù)組基址*/

intlength;/*表長(zhǎng)度*/

}s_tbl;

靜態(tài)查找表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

typedefstructnode

{elemtypeelem;/*結(jié)點(diǎn)的值域*/

structnode*next;/*下一個(gè)結(jié)點(diǎn)指針域*/

}nodetype;

（一）順序查找算法的實(shí)現(xiàn)

1、正確設(shè)計(jì)程序，并編譯、鏈接成可執(zhí)行文件

（1）首先正確寫出查找表的結(jié)構(gòu)體typedefstructSSTable

（2）正確寫出順序查找算法Search_Seq

（3）寫出主程序main，提供輸入與輸出操作

本程序的特點(diǎn)是對(duì)于用戶給定的一組關(guān)鍵字序列（64，80，13，56，37，92，19，05，88，21，

75），采用順序查找算法找到給定的關(guān)鍵字，并返回其在查找表中的下標(biāo)。

2、進(jìn)行程序測(cè)試

直接運(yùn)行可執(zhí)行文件，通過不同的值來觀察輸出結(jié)果。

19

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

（二）折半查找算法的實(shí)現(xiàn)

1、正確設(shè)計(jì)程序，并編譯、鏈接成可執(zhí)行文件

（1）首先正確寫出查找表的結(jié)構(gòu)體typedefstructSSTable

（2）正確寫出折半查找算法Search_Bin

（3）寫出主程序main，提供輸入與輸出操作

本程序的特點(diǎn)是對(duì)于用戶給定的一組有序的關(guān)鍵字序列（05，13，19，21，37，56，64，75，

80，88，92），采用折半查找算法找到給定的關(guān)鍵字，并返回其在查找表中的下標(biāo)。

2、進(jìn)行程序測(cè)試

直接運(yùn)行可執(zhí)行文件，通過不同的值來觀察輸出結(jié)果。

四、程序運(yùn)行結(jié)果和源代碼為：

五、、實(shí)驗(yàn)總結(jié)：

1、收獲

2、存在的問題

20

山東信息職業(yè)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告

學(xué)號(hào)：2016031124姓名：鄭世林班級(jí)：16軟件同組者：

課程名稱：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)老師：武洪萍實(shí)驗(yàn)成績(jī)：

實(shí)驗(yàn)十二——十三排序

一、實(shí)驗(yàn)?zāi)康模?/p>

1理解排序的定義和各