第一篇：數(shù)據(jù)結(jié)構(gòu)參考材料
數(shù)據(jù)結(jié)構(gòu)參考題目
一、選擇
1.如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是（）
A.棧 B.隊(duì)列 C.樹 D.圖 2.下面程序段的時(shí)間復(fù)雜度為（）for(i=0;i
A.串的長(zhǎng)度相等 B.含有相同的字符集
C.都是非空串 D.串的長(zhǎng)度相等且對(duì)應(yīng)的字符相同 5．若以S和X分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（）
A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50個(gè)結(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn)，則該樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為（）A.0 B.1 C.48 D.49 7.已知用某種排序方法對(duì)關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進(jìn)行排序時(shí)，前兩趟排序的結(jié)果為
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）
A.插入排序 B.冒泡排序 C.快速排序 D.歸并排序
8.已知散列表的存儲(chǔ)空間為T[0..16]，散列函數(shù)H（key）=key%17,并用二次探測(cè)法處理沖突。散列表中已插入下列關(guān)鍵字：T[5]=39，T[6]=57和T[7]=7，則下一個(gè)關(guān)鍵字23插入的位置是（）
A.T[2] B.T[4] C.T[8] D.T[10] 9.如果將矩陣An×n的每一列看成一個(gè)子表，整個(gè)矩陣看成是一個(gè)廣義表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運(yùn)算求取矩陣中的每一個(gè)元素，則求得a21的運(yùn)算是（）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))10.在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，所有頂點(diǎn)的出度之和為Dout，則所有頂點(diǎn)的入度之和為（）
A.Dout B.Dout-1 C.Dout+1 D.n 11．從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是（）A線性結(jié)構(gòu) B.樹形結(jié)構(gòu) C.線性結(jié)構(gòu)和樹型結(jié)構(gòu) D.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)
12．棧的插入和刪除操作在()進(jìn)行。
A．棧頂 B.棧底 C.任意位置 D指定位置 13．由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）A.24 B.71 C.48 D.53 14．一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是()A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 15．關(guān)于棧和隊(duì)列的說法中正確的是（）
A．棧和隊(duì)列都是線性結(jié)構(gòu) B.棧是線性結(jié)構(gòu)，隊(duì)列不是線性結(jié)構(gòu) C.棧不是線性結(jié)構(gòu)，隊(duì)列是線性結(jié)構(gòu) D.棧和隊(duì)列都不是線性結(jié)構(gòu) 16．關(guān)于存儲(chǔ)相同數(shù)據(jù)元素的說法中正確的是（）A．順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)少占空間 B.順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)多占空間
C.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)都要求占用整塊存儲(chǔ)空間 D.鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)難于擴(kuò)充空間
17．已知一個(gè)單鏈表中，指針q指向指針p的前趨結(jié)點(diǎn)，若在指針q所指結(jié)點(diǎn)和指針p所指結(jié)點(diǎn)之間插入指針s所指結(jié)點(diǎn)，則需執(zhí)行（）A.q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q；
18．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數(shù)為H(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（）A.1 B.2 C.3 D.4 19．執(zhí)行下面程序段時(shí)，S語句被執(zhí)行的次數(shù)為：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)S;A.n*n B.n*n/2 C.n(n+1)D.n(n+1)/2 20．在長(zhǎng)度為n的線性表中刪除一個(gè)指針p所指結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．設(shè)一個(gè)棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（）
A.a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 22．關(guān)于串的敘述中，正確的是（）A．空串是只含有零個(gè)字符的串 B.空串是只含有空格字符的串
C.空串是含有零個(gè)字符或含有空格字符的串
D.串是含有一個(gè)或多個(gè)字符的有窮序列
23．在具有m個(gè)單元的循環(huán)隊(duì)列中，隊(duì)頭指針為front，隊(duì)尾指針為rear，則隊(duì)滿的條件是（）
A．front==rear
B.(front+1)%m==rear
C.rear+1==front
D.(rear+1)%m==front 24．設(shè)有二維數(shù)組
?1????A［n］［n］表示如下：?23456??????????，則A［i］［i］（0≤i≤n-1）的D.i2/2 值為（）
A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 25．高度為h的完全二叉樹中，結(jié)點(diǎn)數(shù)最多為（）
hA．2h-1 B.2h+1 C.2-1 D.2h 26．由m棵結(jié)點(diǎn)數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點(diǎn)的右子樹上具有的結(jié)點(diǎn)個(gè)數(shù)是（）
A.mn B.mn-1 C.n(m-1)D.m(n-1)27．在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，每個(gè)頂點(diǎn)度的最大值為（）A.n B.n-1 C.n+1 D.2(n-1)28．關(guān)于無向圖的鄰接矩陣的說法中正確的是（）A.矩陣中非全零元素的行數(shù)等于圖中的頂點(diǎn)數(shù)
B.第i行上與第i列上非零元素總和等于頂點(diǎn)Vi的度數(shù) C.矩陣中的非零元素個(gè)數(shù)等于圖的邊數(shù)
D.第i行上非零元素個(gè)數(shù)和第i列上非零元素個(gè)數(shù)一定相等
29．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（）A.1 B.2 C.3 D.4 30．設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個(gè)關(guān)鍵字值為基準(zhǔn)得到的一次劃分為（）
A.36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81
二、填空題
1.數(shù)據(jù)是計(jì)算機(jī)加工處理的對(duì)象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面()。
3.線性表是由n≥0個(gè)相同類型組成的有限序列（）。4.棧是一種后進(jìn)先出的線性表（）。
5.從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，只能找到它的后繼結(jié)點(diǎn)，不能找到它的前驅(qū)結(jié)點(diǎn)（）。6.單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了簡(jiǎn)化運(yùn)算（）。7.樹的最大特點(diǎn)是一對(duì)多的層次結(jié)構(gòu)（）。8.組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素（）。
9.從非循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，既能找到它的后繼結(jié)點(diǎn)，又能找到它的前驅(qū)結(jié)點(diǎn)（）。
10.單鏈表結(jié)點(diǎn)的指針域是用來存放其直接后繼結(jié)點(diǎn)的首地址的（）
11.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映象（）。
12.用順序表來存儲(chǔ)線性表時(shí)，不需要另外開辟空間來保存數(shù)據(jù)元素之間的相互關(guān)系（）。
13.在非線性結(jié)構(gòu)中，至少存在一個(gè)元素不止一個(gè)直接前驅(qū)或不止一個(gè)直接后驅(qū)（）。14.樹的最大特點(diǎn)是一對(duì)多的層次結(jié)構(gòu)（）。15.隊(duì)列的特點(diǎn)是先進(jìn)先出（）。
16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)（）。18.線性表簡(jiǎn)稱為”順序表”。（）
19.對(duì)數(shù)據(jù)的任何運(yùn)算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）。20.從循環(huán)單鏈表的任一結(jié)點(diǎn)出發(fā)，可以找到表中的所有結(jié)點(diǎn)（）。21.棧是一種先進(jìn)先出的線性表（）。22.鏈表的主要缺點(diǎn)是不能隨機(jī)訪問（）。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩(wěn)定的排序（）。25.算法是對(duì)解題方法和步驟的描述（）。26.算法可以用任意的符號(hào)來描述（）。
27.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型（）。
28.線性表的順序存儲(chǔ)方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）。29.棧是一種先進(jìn)后出的線性表（）。
30.將插入和刪除限定在表的同一端進(jìn)行的線性表是隊(duì)列（）。
三、畫圖題
1.請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
K={15,11,20,8,14,13 } R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
K={A,B,C,D,E,F,G,H,I,J} R={
K={1,2,3,4,5} R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) K={0,1,2,3,4,5,6,7} R={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
K={1,2,3,4,5,6,7} R={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}
四、運(yùn)算題
1．已知一個(gè)圖的頂點(diǎn)集V和邊集H分別為：
V＝{0，1，2，3，4，5，6，7}
E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照克魯斯卡爾算法得到最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。______，______，______，______，______，______，______。
2.一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。
平均查找長(zhǎng)度：（寫出計(jì)算過程）
3．已知一個(gè)圖的頂點(diǎn)集V和邊集H分別為：
V＝{0，1，2，3，4，5，6，7}
E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照普里姆算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（從頂點(diǎn)2出發(fā)）
____
__，___
_，___
___，__
____，___ ___，__ ____，___ ___。4.寫出下圖所示的二叉樹的前中后序遍歷結(jié)果：
前序： 中序： 后序：
5.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。
五、編程題
1.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)十進(jìn)制整數(shù)與二進(jìn)制數(shù)的轉(zhuǎn)換。Void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：
Int search_bin(Keytype k,sstable st){ 3.請(qǐng)編寫一個(gè)算法，實(shí)現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點(diǎn)）。LINKLIST *INVERTLINK(LINKLIST *H){
第二篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
數(shù) 據(jù) 結(jié) 構(gòu)
課程設(shè)計(jì)報(bào)告
題 目： 一元多項(xiàng)式計(jì)算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級(jí)： 2012級(jí)普本班 學(xué) 號(hào)： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時(shí) 間：
一、課程設(shè)計(jì)題目分析
本課程設(shè)計(jì)要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。
二、設(shè)計(jì)思路
本程序采用C語言來完成課程設(shè)計(jì)。
1、首先，利用順序存儲(chǔ)結(jié)構(gòu)來構(gòu)造兩個(gè)存儲(chǔ)多項(xiàng)式A(x)和 B(x)的結(jié)構(gòu)。
2、然后把輸入，加，減，乘，除運(yùn)算分成五個(gè)主要的模塊：實(shí)現(xiàn)多項(xiàng)式輸入模塊、實(shí)現(xiàn)加法的模塊、實(shí)現(xiàn)減法的模塊、實(shí)現(xiàn)乘法的模塊、實(shí)現(xiàn)除法的模塊。
3、然后各個(gè)模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時(shí)錯(cuò)誤的出現(xiàn)。
4、最后編寫main()主函數(shù)以實(shí)現(xiàn)對(duì)多項(xiàng)式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。
三、設(shè)計(jì)算法分析
1、相關(guān)函數(shù)說明：
(1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型變量
typedef struct Polynomial{}
(2)其他功能函數(shù)
插入函數(shù)void Insert(Polyn p,Polyn h)
比較函數(shù)int compare(Polyn a,Polyn b)
建立一元多項(xiàng)式函數(shù)Polyn Create(Polyn head,int m)
求解并建立多項(xiàng)式a+b，Polyn Add(Polyn pa,Polyn pb)
求解并建立多項(xiàng)式a-b，Polyn Subtract(Polyn pa,Polyn pb)2
求解并建立多項(xiàng)式a*b，Polyn Multiply(Polyn pa,Polyn pb)
求解并建立多項(xiàng)式a/b，void Device(Polyn pa,Polyn pb)
輸出函數(shù)輸出多項(xiàng)式，void Print(Polyn P)
銷毀多項(xiàng)式函數(shù)釋放內(nèi)存，void Destroy(Polyn p)
主函數(shù)，void main（）
2、主程序的流程基函數(shù)調(diào)用說明(1)typedef struct Polynomial {
float coef;
int expn;
struct Polynomial *next;} *Polyn,Polynomial;
在這個(gè)結(jié)構(gòu)體變量中coef表示每一項(xiàng)前的系數(shù)，expn表示每一項(xiàng)的指數(shù)，polyn為結(jié)點(diǎn)指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對(duì)象名。
(2)當(dāng)用戶輸入兩個(gè)一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲(chǔ)這兩個(gè)多項(xiàng)式，主要說明如下：
Polyn CreatePolyn(Polyn head,int m)建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式
p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項(xiàng)式申請(qǐng)足夠的存儲(chǔ)空間
p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點(diǎn)以接收數(shù)據(jù)
Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點(diǎn)
這就建立一元多項(xiàng)式的關(guān)鍵步驟
(3)由于多項(xiàng)式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對(duì)多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個(gè)程序模塊中，使用鏈表，根據(jù)對(duì)指數(shù)大小的比較，對(duì)各種情況進(jìn)行處理，此處由于反復(fù)使用指針對(duì)各個(gè)結(jié)點(diǎn)進(jìn)行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實(shí)現(xiàn)：
在該程序中，最關(guān)鍵的一步是實(shí)現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負(fù)的加法實(shí)現(xiàn)；對(duì)于乘除算法的大致流程都是：首先建立多項(xiàng)式a*b，a/b，然后使用鏈表存儲(chǔ)所求出的乘積，商和余數(shù)。這就實(shí)現(xiàn)了多項(xiàng)式計(jì)算模塊的主要功能。
(5)另一個(gè)子函數(shù)是輸出函數(shù) PrintPolyn（）；
輸出最終的結(jié)果，算法是將最后計(jì)算合并的鏈表逐個(gè)結(jié)點(diǎn)依次輸出，便得到整鏈表，也就是最后的計(jì)算式計(jì)算結(jié)果。由于考慮各個(gè)結(jié)點(diǎn)的指數(shù)情況不同，分別進(jìn)行了判斷處理。
四、程序新點(diǎn)
通過多次寫程序，發(fā)現(xiàn)在程序在控制臺(tái)運(yùn)行時(shí)總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺(tái)背景顏色，0是控制臺(tái)輸出字體顏色。
五、設(shè)計(jì)中遇到的問題及解決辦法
首先是，由于此次課程設(shè)計(jì)里使用指針使用比較多，自己在指針多的時(shí)候易腦子混亂出錯(cuò)，對(duì)于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4
代碼編寫。
其次是，在寫除法模塊時(shí)比較復(fù)雜，自己通過查資料最后成功寫出除法模塊功能。
最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計(jì)時(shí)的一個(gè)經(jīng)驗(yàn)吧。
六、測(cè)試（程序截圖）
1.數(shù)據(jù)輸入及主菜單
2.加法和減法模塊
3.乘法和除法模塊
七、總結(jié)
通過本次應(yīng)用C語言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語言程序設(shè)計(jì)的知識(shí)，以前對(duì)指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過此次課程設(shè)計(jì)對(duì)指針理解的比較深刻了。而且對(duì)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識(shí)的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計(jì)開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對(duì)自己以后學(xué)習(xí)其他語言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。
八、指導(dǎo)老師評(píng)語及成績(jī)
附錄：（課程設(shè)計(jì)代碼）
#include
float coef;6
int expn;
struct Polynomial *next;} *Polyn,Polynomial;
//Polyn為結(jié)點(diǎn)指針類型 void Insert(Polyn p,Polyn h){
if(p->coef==0)free(p);
//系數(shù)為0的話釋放結(jié)點(diǎn)
else
{
Polyn q1,q2;
q1=h;q2=h->next;
while(q2&&p->expn
{
q1=q2;q2=q2->next;}
if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 {
q2->coef+=p->coef;
free(p);
if(!q2->coef)//系數(shù)為0的話釋放結(jié)點(diǎn)
{ q1->next=q2->next;free(q2);}
}
else { p->next=q2;q1->next=p;
}//指數(shù)為新時(shí)將結(jié)點(diǎn)插入
} 7
} //建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 Polyn Create(Polyn head,int m){
int i;
Polyn p;
p=head=(Polyn)malloc(sizeof(struct Polynomial));
head->next=NULL;
for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf(“請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn) } return head;} //銷毀多項(xiàng)式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項(xiàng)式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器 if(!q)//若多項(xiàng)式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng) 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空 } //求解并建立多項(xiàng)式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) } return headc;} //求解并建立多項(xiàng)式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項(xiàng)式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng) } } return hf;} //求解并建立多項(xiàng)式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn),存儲(chǔ)商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)，存儲(chǔ)余數(shù) pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數(shù)是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL printf(“請(qǐng)輸入A(x)的項(xiàng)數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項(xiàng)式A printf(“n”);printf(“請(qǐng)輸入B(x)的項(xiàng)數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項(xiàng)式B printf(“n”);printf(“**********************************************n”);printf(“* 多項(xiàng)式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項(xiàng)式A(x):“);Print(pa);*n”); printf(“多項(xiàng)式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項(xiàng)式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項(xiàng)式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項(xiàng)式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 1.赫夫曼編碼器 設(shè)計(jì)一個(gè)利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。要求： 1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個(gè)字符和26個(gè)權(quán)值（統(tǒng)計(jì)一篇英文文章中26個(gè)字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實(shí)現(xiàn)屏幕輸出，然后實(shí)現(xiàn)文件輸出）； 5)界面優(yōu)化設(shè)計(jì)。 代碼如下： #include typedef struct HTNode //結(jié)構(gòu)體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權(quán)值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹，進(jìn)行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請(qǐng)輸入權(quán)值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功！”);} void Coding_H(int n,HTNode *HT) //對(duì)結(jié)點(diǎn)進(jìn)行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)