數據結構實驗報告剖析

1、數據結構實驗報告(一)提交日期:班級姓名學號上機號67實驗線性表名稱線性表是最簡單的線性結構。線性表的主要操作特點是可以在任意位置插入和刪除一個數據元素。一、線性表的順序存儲結構線性表的順序存儲結構的本質是：在邏輯上相鄰的兩個數據元素ai-1, ai，在存儲地址中也是相鄰的，既地址連續(xù)。我們采用的是含靜態(tài)一維數組和線性表長的結構體。測試數據與運行記錄如下：步驟一，建立線性表。輸入“ 1”?；剀囨I入，得到“n=?”輸入的n即為線性表所要存儲的元素長度，由于建立線性表時已規(guī)定 MAXSIZE=20，因此所輸入的n應該小于等于20。此處實驗輸入n=6。 然后，將想要插入的數據元素分別輸入數據域dat

2、a 0到data5?；剀囨I入，程序得出一段由6個數據元素組成的如下圖所示的線性鏈表。測試 數據 與運 行記 錄鏈表數據為：1, 2，3，4，5, 6。 C:Ll s e rsl en o voD es kto p5S5sHt5D e b og1 ,exe1. 建立線，性表2在i位置插入元素e3. 刪除第i個元素，返回苴值4*查找值為e的元素6.結束程序運行請輸入您的選擇(1, 2, 3, 4, 6) 1n=?6data 0=?1data 1=?2data 2=?3data 3=?4data 4=?5data 5二？6123456打回車鍵，繼續(xù)。測 數 與 行 錄試 據 運 記步驟二，插入數據元

3、素選擇“2”?；剀囨I入，得到“ i，e=？ ”即輸入想在位置i插入的數據元素 e。本次測試中分別輸入3和6?；剀?，程序運行得到如下圖所展示的一個插入新元素的新鏈表，即在原數據鏈表中第 個數據元素所在位置插入新的數據元素 號+1,同時，新鏈表的長度 +1。因此本實驗中新的到的數據鏈表長度為6。LN3.4.6.建立線性表在i位晝皤人元素日刪除第i個元素，返回其值 查找值為e的元素 結束程序運行3“6”，原數據表中的第3個元素及以后的元素序6+1=7，新鏈表中數據為：1, 2, 6, 3, 4, 5,請輸入您的選擇(1，2, 3, 4, 6) 2I, e=?3, e步驟三，刪除數據元素選擇“ 3”。

4、回車鍵入，得到“ i= ? ”，即鍵入想刪除的第i個元素，返回該元素的值, 使i+1及以后的數據元素的序號 -1，同時，數據鏈表的長度 -1。因此本實驗中將步驟二中建立的數據鏈表第3個元素刪除，刪除后數據鏈表長度為7-1=6，得到的數據鏈表中的數據為：1, 2, 3, 4, 5, 6。1.2.3.生6.建立線性表在i位置插入元素e 刪除第i個元素，理回其值 查找值為b的元素 結束程序運行請輸入您的選擇(1. 2, 3, 4, 6) 31=?3步驟四，查找元素選擇 “ 4”。回車鍵入， 元素在鏈表所處的位置。 因此本實驗中輸入e=得到“ e=? ”即在步驟三中新生成的數據鏈表中查找值為另外輸入數

5、據鏈表中未存儲的數據“ 行無誤?！?”，程序運行結果為“已找到，元素位置是4”。10”，程序運行結果為“未找到-1 ”，說明程序運4. 查找值為e的元素6.結束程序運行請輸入您的選擇(1, 2i 3, 4, 6)4 e=?40=?1O未找到-1最后，程序運行完畢，回車退出。二、線性表的鏈式存儲結構線性表鏈式存儲的操作同樣包括幾個方面： 線性表的建立、元素的插入、刪除、查詢等。 其本質是：在邏輯上相鄰的兩個數據元素 ai-1, ai,在存儲地址中可以不相鄰 ，既地址不 連續(xù)。根據指針域的不同和結點的構造鏈的方式不同，鏈表主要有單鏈表、單循環(huán)鏈表和雙向循環(huán)鏈表。其中，單鏈表是最經常使用的鏈表。試據

6、運記 測數與行錄步驟一，建線性鏈表選擇 “ 1”。輸入元素組成一個鏈表。鏈表的建立與順序表不同，它是一種動態(tài)結構。建立線性表的鏈式存儲結構的過程就是一個動態(tài)生成鏈表的過程。因此每輸入一個元素即重新分配新的結點，本次實驗輸入元素為：5，1，2，3，4，5，6，7。步驟二，插入元素鏈表和順序表的插入運算不同， 順序表在插入時要移動大量的結點， 而鏈表在插入時不 需要移動結點，但需要移動指針來進行位置的查找。先使p指向ai-1，然后生成一個數據域值為x的新結點*s，再進行插入操作。N在i位置插入元素日M刪除第i個元素，返回其值4. 查找值為e的元素結束程序運行請輸入您的選擇(1,2 3, 5)2ir

7、e=?5. 115123114567步驟三，刪除第i個元素選擇“3”，回車鍵入，輸入想要刪掉的第“i”個元素3-刪除第i個元素，返回其值也查找值為e的元素5. 結束程序運行請輸入您的選擇(1,2,乳4, 5)3513114567步驟四，查找元素4. 查找值為e的元素5. 結束程序運行請輸入您的選擇(1, 2, 3, 4, 5)4e=?4已找到，元素位置是5最后，程序運行完畢，回車退出。一、線性表的順序結構存儲 創(chuàng)建順序表 create_list L并輸出表 out_list L(注：本程序中未進行順序表的初始化InitList L ,其效果與create_list L的效果一樣，據部實總的序程

8、 根本分驗結程流對實驗無影響。)/*建立線性表 */void creat_list(SqList *L) int i;printf(n n=?”)； scanf(%d,&L-length); for(i=0;ivL-length;i+) printf(n data %d=?,i);scanf(%d, &(L-ai); /* creat_list */【說明】由于函數中要改變參數L的一維數組MAXSIZE的值，因此參數L應設計為輸出型參數，即 L設計為SqList的指針類型，否則，一維數組子域的修改值將不能帶 回去。(2)插入數據元素insert_sqvoid insert_sq(SqList

9、*L,int i,ElemType e) int j; if (L-length=MAXSIZE) printf(n overflow !);else if(iL-length+1) printf(n erroe i !);else for(j=L-length-1; ji-1; j-) L-aj+1=L-aj;/*向后移動數據元素 */L-ai-1=e;/* 插入元素*/L-length+;/* 線性表長加 1 */ /* insert_sq */【說明】數據元素個數 size比數組下標，即參數 i的值大1,所以插入位置參數i應大于等于0且小于等于宏定義的MAXSIZE 20.當參數i不在上

10、述區(qū)間內時，即可判定參數出錯。數組的存儲空間是有限的，若當前已存滿數組的MAXSIZE的存儲空間，則不能繼續(xù)插入。(注：本程序先把存儲單元i-1至存儲單元i中的數據元素依次后移，然后把數據元素 e插入到存儲單元i中，最后把數據元素+1.)刪除數據元素delete_sq ElemType delete_sq(SqList *L, int i) ElemType x; int j;據部實總的序程 根本分驗結程流if( L-length=0) printf(n 是空表。underflow !); else if(i L-length) printf(n error i !);x=-1;else x=

11、L-ai-1;for(j=i; jlength-1; j+) L-aj-1=L-aj; L-length-;return(x); /* delete_sq */【說明】若順序表中當前沒有一個數據元素，則無法進行刪除，判斷為函數調用出錯。 刪除位置參數i應大于等于0且小于等于i-1,當參數i不在上述區(qū)間，即為參數出錯。 刪除步驟總結如下：首先把存儲單元i中的數據元素，即ai存放到參數x中，然后從前向后依次前移從存儲位置i到存儲單元i-1中的數據元素，最后把數據元素個數-1。(4)查找數據元素 locat_sq(注：此處為按結點值查找方法，另有按結點序號查找get_sq)/*查找值為e的元素，返回

12、它的位置 */int locat_sq(SqList L, ElemType e) int i=0;while(iv=L.length-1 & L.ai!=e) i+; if(inext; j+; if(p=NULL | ji-1) printf(n i ERROR !); else s=(LNode *)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s; /* insert_L */【說明】要在帶頭結點的單鏈表第i (Ow i w siZe個結點前插入一個存放數據元素e的結點，首先在單鏈表中尋找到第i-1個結點并由p指示，然后動態(tài)申請一

13、個結點存儲空間并由s指示，并s-data=e，最后修改新結點指針域指向ai： s-next=p-next，并修改ai-1指針域使之指向 s,即p-next=s。(2) 刪除數據元素delete_L刪除運算就是將鏈表中的第i個結點從表中刪去。由于第i個結點的存儲位置存儲在第i-1個結點的指針域 next中，因此要先使p指向第i-1個結點，然后使得p-next指向第 i+1個結點，再將第i個結點釋放掉。(3) 查找數據元素locat_L在單鏈表中按值查找結點，就是從鏈表的開始結點出發(fā)，順鏈逐個將結點的值和給定的e進行比較，若相等，則返回結點的存儲位置，否則程序return (-1 )。1、 VC6

14、.0 自動檢測出的錯誤顯示為getch:undeclared identifier ”。實驗 中遇 到的 問題 及解 決情 況問題分析：“ undeclared identifier ”意為未聲明的標識符。未聲明的標識符有以下兩種 情況：一為沒有聲明的語句直接使用；二為沒有聲明語句，直接使用函數。因此此處 可以添加頭文件。頭文件的作用是避免多個代碼文件全局變量(函數)，防止定義沖突。因此可以在函數聲明處添加#include另外，getch ()函數在此程序中并未起實際作用，可以刪去。2、VC6.0 檢測錯誤顯示main : function should return a value; voi

15、d return type assumed。問題分析：main : function should return a value意為主函數沒有返回值，有三種改正方法：(1)改為空類型，即把 main ()改為void main();不加void的話主函數默認返回值是int，所以可以把 main(網為int main (),再在主函數末尾加入 return (0);直接只加入return (0)。3、在程序運行過程中因為輸入法問題導致程序運行錯誤，如下圖所示:2- 在i位置插入元素3- 刪除第i個元素，返回其值 組查找值為e的元素匕結束程序運行請輸入您的選擇2. 3. 4, 6） 2i, e=?

16、2, 61-858993460234打回車犍，繼續(xù)。 辣軟拼音半：問題分析：程序中只識別英文編輯狀態(tài)下的字符，不能識別中文輸入的字符，上圖中的逗號是中文方式輸入，程序無法識別，導致程序終止。將逗號輸入切換到英文狀態(tài)下即 可。實驗 完成 后的 體會通過本次實驗，我對線性表的順序存儲結構和鏈表存儲結構有了新的認識。線性表的順序存儲結構優(yōu)點是空間利用率高，可以隨機存取。缺點是插入元素和刪除元素存在元素移動，耗時較多，并且順序存儲結構有空間限制，當需要存取的元素個數可能多于順序表的元素個數時，會出現(xiàn)溢出問題.當元素個數遠少于預先分配的空間時 ，空間浪費大。 線性表在單鏈表存儲結構上的基本運算有建表、插

17、入、刪除和查找。鏈表存儲結構彌補 了順序存儲結構的缺憾，其插入元素和刪除元素速度快并且沒有空間限制，存儲元素的個數無上限，基本只與內存空間大小有關。缺點是占用額外的空間以存儲指針（浪費空間），存取某個元素速度慢。順序存儲結構和鏈表存儲結構對比如下：（1） 順序結構可以進行隨機存取順序存儲表中的第i個元素，鏈式存儲不能進行隨機 的存儲，每次訪問數據元素都需要從頭指針開始進行。（2）順序存儲不需要為表示表中元素之間的邏輯關系增加額外的存儲空間一個存儲單 位就存儲一個數據元素， 即存儲密度大。鏈式存儲數據元素之間的邏輯關系與物理關系 位置不對應，需要指示結點之間關系的指針域，因而在存儲空間要付出代價

18、。（3）順序存儲采用靜態(tài)分配的內存空間，存儲容量難以事先確定，分配過大或過小都 不好；鏈式存儲的存儲空間采用動態(tài)分配的方式，不會存在分配不夠用或浪費的情況。（4）在順序存儲表上進行大量的插入和刪除操作時，需要移動大量的元素，使操作運行時間長；鏈式存儲進行插入和刪除數據時，不需要移動大量的元素，只需要修改指針。另外，實驗過程中發(fā)現(xiàn)許多在課堂上忽視的問題，在實驗室中，從自己動手調試程序， 修改程序中錯誤，再到成功運行出程序，在此過程中有屢次調試失敗的灰心喪氣，也有 成功后的莫大喜悅，這應該就是學習數據結構的魅力所在了吧。與此同時，我更深刻認識到了自己的不足， 有時候一個小小的標點就能使一個大的程序

19、卡死或者停止運行。記得老師說過“細節(jié)決定成敗”，在調試程序的時候，我就是因為對輸入法的不在意，中 文狀態(tài)下的標點符號不被程序識別，結果耽誤了整整半堂實驗，到最后經過逐一排查， 終于找到了問題所在，最終成功運行出了程序。由此可以看出實踐不光是檢驗真理的唯一標準，還是發(fā)現(xiàn)自身錯誤的最好方法。通過這次實驗，我不僅對老師在課堂上講過的內容加深了理解，更深刻的體會到自己自身的缺點帶來的麻煩。在今后的學習過程中，我更要加倍努力改正自己的缺點，盡可能將粗心 帶來的實驗誤差降到最低。數據結構實驗報告（二）提交日期:姓名 上機號 67 棧的順序存儲結構及實現(xiàn)假設棧S= （a1,a2,，an），則稱al為棧底元素

20、，an為棧頂元素。棧中元素按 a1,a2, an的次序進棧，退棧的第一個元素為棧頂元素，即棧的修改是按后進先出（LIFO ）或先進后出（FILO ）的原則。程序運行如下：1、進棧1. 數據元素di棧2. 出棧一個元素，返回其值&結束程序運行試據運記 測數與行錄請輸入您的選擇（1, 2? 3）1 進棧e=?6data=6data5data=4data-3data=2data=l2、出棧最后，運行結束，回車退出程序。本次實驗內容為棧的順序存儲結構及實現(xiàn)。由于棧是運算受限的線性表，因此線性表的存儲結構對棧也適用。棧的順序存儲結構簡稱為順序棧。因為棧底位置是固定不變的， 所以可以講棧底位置設置在數組的

21、最低端(即下標為0)；棧頂位置是隨著進棧和退棧操作而變化的，故用一個整型量top來指示當前棧頂位置，則 top為棧頂指針。因此，順序棧的類型定義僅僅是將順序表類型定義中的長度length改為top，SqList改為SqStack。因此可定義順序棧如下:#include #include /*數組最大界限*/*數據元素類型*/* 一維數組子域*/*棧頂指針子域*/*棧的順序結構體類型*/#define MAXSIZE 20 typedef int ElemType; typedef struct ElemType aMAXSIZE; int top;據部實總的序程 根本分驗結程流SqStack;

22、SqStack s1;順序棧的操作實現(xiàn)如下：初始化空棧init_s步驟如下：(1) 分配空間并檢查空間是否分配失敗，若失敗則返回錯誤(2) 設置棧底和棧頂指針 S.top = S.base;(3) 設置棧大小2、進棧pushvoid push(SqStack *s,ElemType e) if(s-top=MAXSIZE-1)printf(n Sstack is Overflow!); else s-top+ ;s-as-top=e;/* push */【說明】先判斷是否棧滿，若滿則出錯；然后將元素e壓入棧頂，同時，棧頂指針加1。1、出棧popElemType pop(SqStack *s)

23、ElemType x;if(s-top=-1) printf(n Stack is Underflow!);x=-1; else x=s-as-top; s-top-; return(x); /* pop */【說明】首先判斷是否?？?，若空則出錯；接著獲取棧頂元素e,同時，棧頂指針減 1。另外，本實驗中程序沒有涉及到取順序棧棧頂元素，即GetTop，其運行思路為：首先，判斷是否空棧，若空則返回錯誤；否則通過棧頂指針獲取棧頂元素。實驗 中遇 到的 問題 及解 決情 況1、 VC6.0 測試出現(xiàn)錯誤error C2018: unknown character 0xa3 ; error C2018:

24、 unknown characterOxbb ”。問題分析：“ printf（nn2.出棧一個元素，返回其值 ）;”原程序段中的；”是在中文狀態(tài)下輸入的字符，程序無法識別導致出錯。應使用英文輸入法輸入程序語言。2、調試出現(xiàn)syntax error : missing ; before identifier push ”問題分析：“ case 1: printf（n 進棧 e=?）; scanf（%d,&e） ” 末尾缺少；”，應在句 末加上一個分號，并且是英文狀態(tài)下的字符形式。3、VC6.0測試出現(xiàn)錯誤如下：error C26Q1: outs : local function definiti

25、ons are illegal error C2601: * push : local function definitions are illegal error 026 91: 4 pop * : local function definitions are illegal問題分析：local function definitions are illegal ”意為函數定義出錯。調試錯誤原因是 主應用程序的函數少了一個“ ”。用“ Ctrl+ ”逐一排查函數（一般報錯位置并不是真正 的出錯位置，通常是報錯位置的上一個函數）。通過在課堂內外的學習和實踐， 我了解到棧是一種重要的線性結構。 從

26、數據結構角度看， 棧也是線性表，其特殊性在于棧的基本操作是線性表操作的子集，它是操作受限的線性表，因此，可稱為限定性的數據結構。與前面學的關于順序表的知識對比發(fā)現(xiàn)，順序棧和順序表的數據成員是相同的，不同的實驗 完成 后的 體會(19)(19)(21)(32)07)(37)(38)(46):error :error :error :error :error :errorC2018:C2618:C2146:C2U5：C2144：C2H5:unknoun character 0Ma3* 1 * * 4 5 unknown character Oxbbh sj/ntaK error : nissing

27、 b; beFqre identifier printf* dexitb : undeclared identifiersyntax 電rror : Hissing ;H before ideiitiFier *pr*intF getch : undeclared identifier:learningddin : function should return 3 value; void:error C2S19: type SqStack does not have an overLoadBd menberreturn ti/peoperator -叩p1.cpp(4) : see decla

28、ration oF SqStack(46) : error(47) : errorcpp1.cpp(4)(47) : error(iiB) : errorC2227: Left of -top nust paint to class/struct/union C2819: tj|pe b$qStack does not haut an ouerlnaded membersee declaration of 1SqStack1C2227: LeFt oF -top- nust point to cljss/struct/union C2819: tppe FSqStackF does not h

29、av an overloaded menberoperator -1 operator -是，順序棧的入棧和出棧操作只能對于當前棧頂元素進行。cppl.cpp(4) : See declardtion oF SqStack*(48) : error C2227: Left of -a must point to class/5truct/union個人體會：剛開始調試程序時，VC6.0檢測出上圖所示的長長的一串錯誤來，讓人看了都覺得十分發(fā)愁。后來通過老師的指導，我和身邊的同學分工合作，將困難化整為零， 認真考慮程序的可能存在錯誤點，最后我們終于把程序成功的運行了出來。經過這次實驗，我深深地體會

30、到耐心對于學好程序的重要性。隨著學習的不斷深入，我 們所學的問題深度越來越多， 所需要處理的程序也就越來越長，只有耐下心來分析問題,才能得到正確的結果。同時，在運行程序的時候一定不要害怕麻煩，靜下心來做，慢慢 把錯誤的一個大的程序慢慢分解成一個個小的問題，化繁為簡，認真細心地分析函數中的每一個語句和運算，隱藏在程序語句中的錯誤最終都會被糾正。數據結構實驗報告（三）提交日期:班級 學號 實驗名稱姓名 上機號 67 隊列隊列也是一種特殊的線性表，隊列的數據元素及數據元素間的邏輯關系和線性表的完全相同，其差別是：線性表允許在任意位置插入和刪除數據元素，而隊列只允許在其一端 進行插入操作（隊尾），另一

31、端進行刪除操作（隊頭）。隊列中，最先進入隊列的數據元素總是最先出隊列，所以隊列是一種先進先出表。和線 性表類似，隊列也有兩種存儲表示循環(huán)隊列（順序存儲）和鏈隊列。一、循環(huán)隊列（即隊列的順序存儲結構）實現(xiàn)用數組實現(xiàn)隊列時，隨著數據的不斷讀寫，會出現(xiàn)假滿隊列情況。即尾數組已滿而頭數是空的；循環(huán)隊列在邏輯上把數組的頭尾相連，能夠很好的利用有限的資源。i進隊測試 數據 與運 行記 錄L數據元素e進隊列2. 岀隊一個元素，返回其值3. 結束程序運行請輸入您的選擇 厲2勸1進隊e=?ld咼 t a=5data=4data=3data=2data=l2、出隊1.數據元素e進隊列岀隊一個元素，返回其值1結束程

32、序運行請輸入您的選擇（1,2 3）2隊請:4data=3data=2datal最后，程序運行結束，回車退出。二、隊列的鏈表存儲結構及實現(xiàn)鏈隊就是采用鏈式存儲結構存儲隊列，這里采用單鏈表來實現(xiàn)。鏈表的特點是不存在隊列溢滿的情況。鏈隊同循環(huán)隊列的程序運行步驟相同，都是進隊和出隊兩個步驟。、步驟如下：1、進隊1. 數據元素。進隊列2. 出隊一個元素，返回其值3. 結束程序運行請輸入您的選擇（1：Z3）1 進隊e=?6試據運記 測數與行錄3452、出隊6L數據元素E進隊列2.岀隊一個元素，返回其值比結束程序運行請輸入您的選擇（1,2, 3） 2出隊元素：3456最后，程序運行結束，回車退出。一、循環(huán)隊

33、列據部實總的序程 根本分驗結程流通過順序隊列的“假溢出”現(xiàn)象優(yōu)化得到循環(huán)隊列結構。 循環(huán)隊列結構存在兩種狀態(tài)和兩種操作，如下：1、兩種狀態(tài)（1）隊空狀態(tài)：Q-front=Q-rear。（2）隊滿狀態(tài)：（Q-rear+1）%MAXSIZE=Q-front）2、兩種操作（1）進隊 EnQueue : Q-rear=（Q-rear+1）% MAXSIZE ;Q-aQ-rear=e;（2）出隊 DeQueue: Q-front=（Q-front+1）% MAXSIZE ； x=Q-aQ-front; 程序流程為：1、初始化空隊列init_Q并輸出隊列out_Q2、進隊 EnQueue3、出隊 DeQu

34、eue根據 本部 分實 驗總 結的 程序 流程實驗 中遇 到的 問題 及解 決情 況二、鏈隊列1 入隊 EnQueue_void EnQueue(L_Queue *Q,ElemType e) QNode *s;s=(QNode *)malloc(sizeof(QNode);s-data=e; s-next=NULL;Q-rear-next=s; Q-rear=s; /* EnQueue */【說明】元素插入到隊列中只能在隊尾插入，隊頭指針始終指向頭結點，隊尾指針指向 隊列的最后一個元素。首先開辟一個新結點s,再在隊尾插入結點 Q-rear-next=s;最后修改隊尾指針：Q-rear=s;(2

35、)出隊操作 DeQueueElemType DeQueue(L_Queue *Q) ElemType x; QNode *p;if(Q-front=Q-rear) printf(n Queue is NULL!);x=-1;else p=Q-front-next;x=p-data;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;free(p);return(x); /* DeQueue */【說明】首先判斷此隊列是否為空，若為空，則返回-1，結束進程。否則，使p指向隊頭元素，再使隊頭元素p出隊。如果隊中只有一個元素，則p出隊后成為空隊。最后釋放存儲

36、空間。1、SqQueue : illegal use of this type as an expression原程序如圖所示：switch(k) case 1 ： printf(n 進隊 e=?); scanf(Ia%da,;EnQueue(SqQueue &Q1,e): out_Q(&Q1; break;問題分析：編譯不允許在用到函數的時候，再去聲明這個函數，即應把聲明函數放在函數體最前面。此處 SqQueue重復聲明，直接把聲明去掉即可。2、“ Free : undeclared identifier ”問題分析：void free( void *p )動態(tài)釋放函數內存空間的函數，這個函

37、數包含在頭文件 malloc.h中。在程序中，用 malloc ()函數申請的內存空間要用一個指針類型的變量指 示其首地址。此處 Free ( p)改為free( p)，在程序編譯中，需要區(qū)分大小寫。實驗 中遇 至U的 問題 及解 決情 況3、調試檢測到的錯誤如下(8) : see declaration of SqQueue1rror C2819:*SqQueue1 do色占 not hauE an ouerloaded member *oprdtor(6) : see declaration oF SqQueue*葉葉 C2227: left of -Frnntb must point t

38、o clss/struct/unionrroir C2819: type SqQueue does not have an ouerlcuaded nember operator - (6) : see declaration of SqQueuerror C2227: left of -rear must point to class/struct/unionrror C281I9: tyipe *SqQueue does not haue an ouerlcuaded menber operator - (6) : se(? declaration of SqQueue*rror C222

39、7: left of *-Front must point to class/struct/unionrror C2819: ti/pe * SqQueue does not have an ouerloaded nember 1 operator(6) : see declaration of SqQueue*冋題分析：must point to class/struct/union 意為左邊必須有 類/結構/聯(lián)合，疋義一個有指針變量的函數時，若有“一 ”指向一個變量時，所定義的指針變量前面必須加“*”，因此out_Q函數中定義的變量 Q應該為*Q，修改如下：void out_Q(SqQue

40、ue () char ch; int i;if (Q-Front=Q-rear) printF(n Queue is NULL.;else i=(Q-front+1) MAKS1ZE;uhile( i?=Q-rear) printf (ri data=d*. Q-ai):|L = (i+1)WXSIZE; printf(n data=d Q-ai);printf (fin 打回車鍵，繼續(xù)。)；ch=getch( ;實驗 完成 后的 體會通過上述的實驗使我對隊列有了一個更加深刻地理解。對于循環(huán)隊列與鏈隊列的比較， 可以從兩方面來考慮：從時間上，其實它們的基本操作都是常數時間，即都為0(1)的，不

41、過循環(huán)隊列是事先申請好空間，使用期間不釋放，而對于鏈隊列，每次申請和釋放結點也會存在一些時間開 銷，如果入隊出隊頻繁，則兩者還是有細微差異。對于空間上來說，循環(huán)隊列必須有一個固定的長度，所以就有了存儲兀素個數和空間浪費的問題。而鏈隊列不存在這個問題，盡管它需要一個指針域，會產生一些空間上的開 銷，但也可以接受。所以在空間上，鏈隊列更加靈活?？偟膩碚f，在可以確定隊列長度最大值的情況下，建議用循環(huán)隊列，如果你無法預估隊列的長度時，則用鏈隊列。在實驗的過程中，程序的運行出現(xiàn)了很多的錯誤，所以我必須了嚴格的檢查程序中的每個字符，不斷地進行調試。在調試的過程中，也發(fā)現(xiàn)了很多應該注意的問題，例如函數 的聲

42、明應該與函數的應用相一致、函數的名稱不能有重復、函數中的指針的引用等。通 過實驗使我對瑣碎的知識點有了一個更加清晰的認識，使很多的知識點聯(lián)系在一起，冋時也鍛煉了我的計算機操作的能力，所以我們應該增加這樣的實驗操作，提高我們的動手能力。在實踐操作的冋時，也要培養(yǎng)自己嚴謹的學習態(tài)度，在細節(jié)上更要注意一下。例如，函 數Free (p)和free (p)的區(qū)別，雖然兩個函數的意思是一樣的，但是在程序編寫中 意思截然不冋，“失之毫厘，差之千里”，平時只有多加注意小枝末節(jié)，不粗心大意，才 能將不必要的失誤盡量避免掉，并且能夠節(jié)省更多的練習時間。數據結構實驗報告(四)提交日期:姓名上機號67班級 學號 實驗

43、樹與二叉樹 名稱樹形結構是一類非線性數據結構。樹結構包括樹和二叉樹。 在樹結構中，每個結點都只允許有一個直接前驅結點，但允許有一個以上直接后繼結點。樹的存儲結構和本次實驗內容包括： 二叉操作實現(xiàn)都比較復雜， 但樹可以轉換為二叉樹進行處理。樹的建立、二叉樹的遍歷和哈夫曼編碼。一、二叉樹的建立和遍歷建立二叉樹有各種不同的方法。一種方法利用二叉樹的 性質5來建立二叉樹，輸入數據時將結點的序號和數據同 時給出：序號 數據元素。1、用二叉樹性質5建二叉樹輸入數據：11, 2 2，33, 44, 65，7 6，1315 9。測試 數據 與運 行記 錄2、中序遍歷3. 中序遞歸遍歷二叉樹4-計算樹中結點個數

44、5.結束程序運行請輸入您的選擇12,111 6)34215738693、計算樹中結點數4. 計算樹中結點個數5. 結束程序運行請輸入您的選擇(1,3, 4, 5, 6)4421573869二叉樹結點總數n=9二叉袖壬字結點藪n0=4度為1的結點數二2度為2的結點數n2=3二、哈夫曼編碼利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。哈夫曼樹中，從根到每個葉子都有一條路徑，對路徑上的各分支約定指向左子樹的分支表示“0”碼，指向右子樹的分支表示“ 1 ”碼，取每條路徑上的“ 0”和“ 1”的序列作為和各個 葉子對應的字符的編碼，就是哈夫曼編碼。1、輸入權植輸入 8 個權植 5, 29, 7,

45、 8, 14, 23, 3, 11.2、輸入字符，得出哈夫曼編碼請輸入字符asdfghjk第1個字符亂的編碼為0001 第2個字符3的編碼為10第3個字符d的編碼為1110 第4個字符f的編碼為1111 第5個字符曲編碼為11。 第&個字符h的編碼為01第7個字符j的編碼為0000 第呂個字符k的編碼為001一、二叉樹的建立和遍歷實驗中的非遞歸遍歷算法特點是，在所有未被訪問的結點中，最后訪問結點的左子樹的根結點將最先被訪問。實驗原理如下：根據如果有一顆有 n個節(jié)點的完全二叉樹的節(jié)點按層次序編號，對任一層的節(jié)點i(1v=iv=n )有：1. 如果i=1，則節(jié)點是二叉樹的根，無雙親，如果 i1，則

46、其雙親節(jié)點為i/2，向下 取整2. 如果2in那么節(jié)點i沒有左孩子，否則其左孩子為2i據部實總的序程 根本分驗結程流3. 如果2i+1n那么節(jié)點沒有右孩子，否則右孩子為2i+1 中序遍歷：若二叉樹非空，則依次執(zhí)行以下操作：(1) 中序遍歷左子樹(2) 訪問根結點(3) 中序遍歷右子樹void inorder(BiTNode *p) if (p) inorder(p-lch);printf(%3d,p-data);inorder(p-rch); /* inorder */二、哈夫曼編碼對于同一組結點，構造出的哈夫曼樹可能不是唯一的。但是對于同一組結點，雖然會產生多棵哈夫曼樹，但是它們的帶權路徑長

47、度(WPL )是相同的，即一組結點有唯一的WPL和它對應。算法如下：1、 輸入權植。首先將這n個權值分別看作是只有根的n棵二叉樹，這些二叉樹構 成一個集合2、篩選最小權值。選出兩棵根結點的權值最小的樹作為左、右子樹構造一棵新的 二叉樹，新二叉樹的根結點的權值為左、右子樹根結點權值之和。void selectmin(huffmantree ht, int i, int *p1, int *p2)/*在ht1.i中選兩個權值最小的根結點，其序號為*p1和*p2 , *p1中放權值最小的根結點的序號，*p2中放權值次小的根結點的序號*/int j,min1,min2;/* min1,min2分別是最

48、小權值和次小權值*/min1=min2=32767;*卩仁 *p2=0;for(j=1;jv=i;j+)if(htj.parent=O)/* j 為根結點 */if(htj.weightvmin1|min 仁=32767)if(min1!=32767) min2=min1; *p2=*p1;min1=htj.weight;*p1=j;elseif(htj.weightvmin2|min2=32767)min2=htj.weight;*p2=j;3、從集合中刪除左、右子樹，加入新構造的樹。實 中 到 問 及 決 況驗 遇 的 題 解 情重復步驟2和3，直到集合中剩下一棵樹為止，這棵樹就是哈夫曼樹

49、。4、程序語法沒有問題，調試不出錯誤，但是程序在運行期出錯導致程序運行終止。實驗 中遇 到的 問題 及解 決情 況請輸入8個權值 請鬲入第1個權值 請輸入第2個 請輸入第3個權值： 請輸入第4個權值： 請鬲入童5個權值； 請輸入第6個權值； 請輸入第7個權值： 請輪入束8個權值； 請輸入字符曰dsf gjk權值529781423311Cppkexe已停止工作出現(xiàn)了一個I可題r導匙融停止正宰工恨如JI購可用的驛決 方秦f Windows捋黃岡程序并通知你，渭試Q)問題分析：在哈夫曼樹初始化函數中， 缺少了十分重要的步驟： 指定雙親結點。結 果導致運算不能繼續(xù)， 程序終止。應該在選擇兩個權值最小的

50、根結點之后， 添加指實驗 完成 后的 體會定雙親結點的語句：“ htp1.parent=htp2.parent=i; ”數據結構實驗報告（五）提交日期:姓名 上機號 67班級 學號 實驗圖 名稱圖是一種非線性結構。在圖的結構中，數據元素之間的關系是多對多的，。之前在運籌學中從理論方面學習過圖，本次數據結構實驗中主要從圖的存儲結構 和操作實現(xiàn)方面學習圖。一、圖的鄰接矩陣存儲（數組表示）、簡單輸出圖有多種存儲方式， 主要應用的是鄰接表和鄰接矩陣。本次實驗中使用的存儲方式是鄰接矩陣。輸入頂點數n，邊數e,然后輸入一條邊連接的兩個頂點的編號i和j。本次實驗輸入的 n=6，e=10，i 和 j的數值分另

51、U為 6 5，6 1, 2 3，1 2, 5 4, 4 3，6 4, 1 4, 1 3, 6 3。0111011010001101011010110001011 1_Ja101110測試 數據 與運 行記 錄2、回車鍵入，得到 0-1鄰接矩陣。二、圖的鄰接鏈表存儲及遞歸深度優(yōu)先遍歷 圖的深度優(yōu)先遍歷類似于二叉樹的先序遍歷。1、輸入頂點數n,邊數e,然后輸入一條邊連接的兩個頂點的編號i和j。本次實驗輸入的 n=8 , e=9, i 和 j 分別為：1 2, 1 3, 2 4, 2 5, 5 8, 4 8, 3 6, 3 7, 6 7。2、回車鍵入得到每個頂點的鄰接鏈表1 = 132i=2541i=376 1i=482i=582i=673i=763i=845打回車鍵, 輸入繼練3、輸入V，從頂點Vi開始，對圖進行深度優(yōu)先遍歷輸入琴11 3 7 6 2 5 S 4據部實總的序程 根 本分驗 結程流一、鄰接矩陣鄰接矩陣是圖的順序存儲結構， 由鄰接矩陣的行數或列數可知圖中的頂點數。對于無向圖，鄰接矩陣是對稱的，矩陣中的“1”的個數為圖中總邊數的 2倍；對于有向圖，矩陣中的“ 1 ”的個數為圖的邊數。無向網鄰接矩陣的建立方法是：首先將矩