2011-軟件技術(shù)基礎(chǔ)實驗指導書.doc

軟件技術(shù)基礎(chǔ)課程實驗指導書實驗環(huán)境：C/C+語言編程 Turbo C3.0 / Visual C+6.0一、實驗內(nèi)容序號實驗內(nèi)容實驗類型學時要求1單鏈表的操作設(shè)計2必做2堆棧操作設(shè)計2必做3二叉樹操作設(shè)計2必做4數(shù)據(jù)的查找與排序設(shè)計2必做二、實驗指導實驗一 單鏈表的操作一、 實驗目的1.掌握線性表的鏈式存儲結(jié)構(gòu)(1)線性表的鏈式存儲原理(2)鏈式存儲結(jié)構(gòu)的優(yōu)缺點2.掌握結(jié)構(gòu)體的應用以及數(shù)據(jù)結(jié)點的生成(1)結(jié)構(gòu)體的定義(2)動態(tài)存儲分配函數(shù)的使用(3)強制類型轉(zhuǎn)換的方法3.掌握指針的應用(1)鞏固指針的含義和用法(2)結(jié)構(gòu)體指針的使用二、 預習要求1.復習C語言(1)鞏固C語言程序設(shè)計的基本方法(2)鞏固在TC或VC環(huán)境中編寫和調(diào)試C程序2.復習指針和結(jié)構(gòu)體兩部分的知識(1)鞏固指針的含義以及定義方式(2)理解結(jié)構(gòu)體的定義以及其成員的賦值和引用3.理解課本關(guān)于單鏈表部分的知識(1)掌握單鏈表的生成原理和過程(2)在草稿紙上畫出簡單程序流程圖三、 實驗內(nèi)容1.通過C語言編程，用函數(shù)實現(xiàn)不低于五個結(jié)點的單鏈表的建立：(1)要求編寫功能函數(shù)實現(xiàn)單鏈表的建立；(2)鏈表中結(jié)點的數(shù)據(jù)類型為任意原子類型，以下參考算法假設(shè)的是整型；(3)采用循環(huán)結(jié)構(gòu)建表，請同學自定義循環(huán)結(jié)束標志，以下是次數(shù)循環(huán)，同學們可設(shè)計為輸入某個鍵值結(jié)束，如數(shù)字-1結(jié)束；(4)編寫訪問各結(jié)點的算法，把建成的單鏈表順序輸出。2.實現(xiàn)單鏈表的插入和刪除算法。3.編寫主函數(shù)調(diào)用以上各算法函數(shù)，調(diào)試并運行整個程序，分析運行結(jié)果。四、 實驗原理1尾插法建立單鏈表(1)算法原理：從一個空表開始,循環(huán)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當前鏈表的表尾上,直到循環(huán)結(jié)束為止。12345L (2)算法示意圖如下，若要建立L=（1，2，3，4，5）的單鏈表，則鏈表結(jié)構(gòu)為：(3)算法描述：/結(jié)點結(jié)構(gòu)體定義struct node int data; struct node *next; ;/尾插法建立n個結(jié)點的單鏈表Lstruct node* CreateList(struct node *L,int n) int i; int x; struct node *p,*q; L=(struct node *) malloc(sizeof(struct node); L-data=n; L-next=NULL; q=L; for(i=n;i0;i-) p=(struct node *) malloc(sizeof(struct node); scanf(%d,&x); p-data=x; q-next=p; p-next=NULL; q=p; return L;2. 單鏈表的訪問從頭節(jié)點開始，依次輸出每個節(jié)點的值。void access(struct node *h) struct node *p; p=h; while(p-next!=NULL) p=p-next; printf(%d ,p-data); 3單鏈表的插入算法(1)算法原理：在以上算法的基礎(chǔ)上，在指定位置插入一個新結(jié)點。首先定義一個搜索指針p，從頭開始搜索(p=p-next)直到指定位置的前一個位置；然后建立新結(jié)點，修改指針使之插入。(2)算法示意圖：若要在3號位置插入一個數(shù)據(jù)域為6的結(jié)點t，則鏈表結(jié)構(gòu)變?yōu)椋?2345L 6(3)算法描述：/在第i個位置上插入一個新結(jié)點tstruct node * insert(struct node * L,int i) p=L; j=0; while(p-next!=NULL & jnext; j+; if(j!=i-1) printf(i is invalid!n); exit(0); t=(struct node *)malloc(sizeof(struct node); scanf(%d,&x); t-data=x; t-next=p-next; p-next=t; return L; 4.單鏈表的刪除算法請同學們參見課本P14的算法5，注意相關(guān)定義和語句的修改和完善。5.同學自行編寫主程序，完成整個實驗。五、 實驗報告要求1.按教務處印發(fā)的標準的計算機實驗報告格式填寫實驗報告(1)字跡工整，內(nèi)容屬實規(guī)范；(2)報告不得打印或復印，也不得抄襲或有雷同。2.本實驗為軟件設(shè)計，報告中應先畫程序流程圖，再闡述你的設(shè)計思路和過程；3.避免純粹的抄寫源程序，應適當?shù)靥顚懸恍┱{(diào)試情況以及問題的產(chǎn)生原因和處理辦法；4.設(shè)計感想可包括你對本次實驗的收獲、啟示以及不足和希望。六、 思考題1.如果結(jié)點指針P指向鏈表中某一中間結(jié)點，問：如何用P表示P之后的每一個結(jié)點？2.單鏈表可以按隨意順序輸出嗎？3.單鏈表和順序表所花的存儲空間相同嗎？七、 注意事項1.算法和程序是不同的，課本上的算法不能直接拿來調(diào)試和運行，必須將其改寫為程序；2.算法到程序的完善方法：(1)將變量類型具體化；(2)將每一個語句標準化；(3)補充主函數(shù)，實現(xiàn)變量定義、函數(shù)調(diào)用等功能。八、 實驗環(huán)境、條件1.P4、Windows操作系統(tǒng)、臺式計算機每人一套；2.Turbo C/VC+ 軟件編程環(huán)境；3.學生自備實驗報告紙一張，最好有U盤用以備份自己的程序。實驗二 堆棧的基本操作一、 實驗目的1.理解堆棧的特殊性質(zhì)FILO2.熟悉順序堆棧的結(jié)構(gòu)和定義方法3.掌握順序堆棧的進棧和出棧操作二、 預習要求1.熟悉結(jié)構(gòu)體和指針的用法。2.熟悉VC環(huán)境中的調(diào)試方法。三、 實驗內(nèi)容1.通過C語言編程，實現(xiàn)十進制到二進制的轉(zhuǎn)換。(1)要求編寫功能函數(shù)實現(xiàn)堆棧的定義；(2)編寫進棧函數(shù)push()；(3)編寫出棧函數(shù)pop()；(4)將轉(zhuǎn)換結(jié)果輸出。2.選做：實現(xiàn)十進制到十六進制的轉(zhuǎn)換。四、 實驗原理1.算法原理：由于十進制數(shù)轉(zhuǎn)換為二進制數(shù)的方法是依次將十進制數(shù)除以2取余，然后將余數(shù)倒排序。這樣剛好滿足“先進后出”的特性，即可以將除2取余的結(jié)果依次進棧，最后再依次出棧。2.算法示意圖：例如將十進制數(shù)13轉(zhuǎn)換為二進制，其方法如下：3.算法描述：/順序棧結(jié)構(gòu)體定義#define MAXNUM 20struct stacktype int stackMAXNUM; int top;(1)進棧函數(shù)定義int push(struct stacktype *s，int x) if(s-top = MAXNUM-1) return false; else s-top+; s-stacks-top=x; return true； (2)出棧函數(shù)定義int pop(struct stacktype *s) if(s-top top-; return(s-stacks-top+1); (3)進制轉(zhuǎn)換函數(shù)定義void dec_to_bin(int N,int B)int e;InitStack(S); /初始化堆棧，算法定義見課本while(N)push(S,N%B);N=N/B;while(!StackEmpty(S) /堆棧判空，算法定義見課本e=pop(S);printf(“%d”,e);（4）同學自行編寫主函數(shù)完成上述功能函數(shù)的調(diào)用，調(diào)試和運行該程序，并分析結(jié)果。五、 實驗報告要求如實驗一所述。六、 思考題1.能否編寫功能全面的任意進制之間的相互轉(zhuǎn)換的程序？要求程序有一定的交互性能。七、 注意事項1.以上轉(zhuǎn)換函數(shù)中的InitStack(S)和StackEmpty(S)兩個函數(shù)需要自己定義；2.如果涉及十六進制，注意AF的需要存儲其ASCII碼，然后用%c的格式輸出。八、 實驗環(huán)境、條件如實驗一所述。實驗三 二叉樹實驗一、 實驗目的1.了解二叉樹在存儲器中的表示；2.掌握二叉鏈表的實現(xiàn)方法；3.掌握用二叉鏈表遍歷二叉樹的過程；4.深入理解對二叉樹的遞歸遍歷過程。二、 預習要求1.二叉樹的相關(guān)定義和概念(1)預習二叉樹的層次概念和左右子樹的概念；(2)預習二叉樹的性質(zhì)。2.復習課本上二叉樹的兩種存儲方法(1)理解二叉鏈表的表示方法和結(jié)構(gòu)特點；(2)理解結(jié)構(gòu)體和指針在二叉樹的存儲結(jié)構(gòu)中的應用。3.理解課本上二叉樹的三種遍歷的原理和方法4.復習并掌握C語言中遞歸程序設(shè)計的方法三、 實驗內(nèi)容1.采用遞歸方法建立二叉樹；2.給出三種遍歷序列；3.理解遞歸中堆棧的用處。四、 實驗原理1.遞歸建樹(1)算法原理：從根開始，采用先序的方式依次建立含有n個結(jié)點的二叉樹。(2)算法示意圖：若要建立H=（1，2，3，4，5）的二叉樹,結(jié)構(gòu)可如下圖所示：12345(3)算法描述：/結(jié)點結(jié)構(gòu)體定義struct tree int data; struct tree *lchild; struct tree *rchild;/遞歸建立二叉樹struct tree *create(struct tree *BT,int k) struct tree *p,*h; int x; printf(Input an integer: ); scanf(%d,&x); if(x!=0) if(!(p=(struct tree *)malloc(sizeof(struct tree) /申請結(jié)點空間不成功 exit(0); p-data=x; p-lchild=NULL; p-rchild=NULL; if(k=0) /是根結(jié)點 h=p; if(k=1) /是左結(jié)點 BT-lchild=p; if(k=2) /是右結(jié)點 BT-rchild=p; create(p,1); /建立左結(jié)點 create(p,2); /建立右結(jié)點 return(h); 2遞歸遍歷將以上建立的二叉樹進行先序遍歷每一個結(jié)點。/遞歸先序遍歷二叉樹int visit(struct tree *BT) if(BT!=NULL) printf(%d ,BT-data); visit(BT-lchild); visit(BT-rchild); return 0;3.同學們模仿先序遍歷編寫中序和后序遍歷算法，再編寫主函數(shù)調(diào)用上述算法實現(xiàn)整個程序的調(diào)試和運行。五、 實驗報告要求如實驗一所述。六、 思考題1.遞歸的執(zhí)行過程是怎樣的？能否用堆棧畫圖描述？七、 注意事項1.注意在寫遞歸程序時不要進入死循環(huán)；2.二叉樹的三種遍歷方式的區(qū)別。八、 實驗環(huán)境、條件如實驗一所述。實驗四 數(shù)據(jù)的查找與排序一、 實驗目的1.了解數(shù)據(jù)查找的一系列方法(1)了解查找表的分類(2)掌握折半查找法的原理2.掌握各種排序（簡單插入，簡單選擇，冒泡排序，快速排序等）方法及適用場合，并能在解決實際問題時靈活應用。3.了解查找與排序在實際生活中的應用。二、 預習要求1.預習課本有關(guān)查找和排序的概念2.預習查找表的分類以及各類查找表的查找方法3.在草稿紙上畫出四種排序方法的簡單程序流程圖4.重點預習如下算法：(1)折半查找法的基本原理和過程(2)簡單排序和冒泡排序算法三、 實驗內(nèi)容現(xiàn)有給定序列(5，13，19，21，37，56，64，75，80，88)，寫出查找關(guān)鍵字K分別是21和85的完整程序。1.通過C語言編程，用函數(shù)實現(xiàn)折半查找(1)對于給定的記錄集可以是有序或無序的；(2)對于無序的記錄集，考慮先排序再查找。2.對關(guān)鍵字序列為（49 38 65 97 76 13 27 58）的線性表分別進行簡單排序和冒泡排序，并分析比較它們的性能。3.了解和學習其它查找與排序方法。四、 實驗原理1.順序查找(1)算法原理：從一個給定的表中的最后一個記錄開始，逐個進行記錄的關(guān)鍵字和給定值的比較，若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若直至第一個記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒有所查的記錄，查找不成功。(2)算法描述（注意：a數(shù)組應該比aMAX 有更大的容量）：int search_seq(int aMAX,int key) a0=key; for(i=MAX;i=1;i-) if(ai=key) return i; 2.折半查找(1)算法原理：在一個有序表中，先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直道找到或找不到該記錄為止。(2)算法描述：/升序排列的有序表查找算法int search_bin(int aMax,int key) low=1;high=MAX;while(low=high) mid=(low+high)/2; if(key=amid) return mid; else if(keyamid) high=mid-1; else low=mid+1;return 0;3.簡單插入排序(1)算法原理：把n個數(shù)據(jù)元素的序列分為兩部分，（R1,Ri-1）為已排好序的有序部分，（Ri,Ri+1,Rn）為未排好序的部分。這時，把未排序的部分的第1個元素Ri依次與R1,Ri-1比較，并插入到有序部分的合適位置上，使得（R1,Ri）變?yōu)樾碌挠行虿糠帧?2)算法描述：insertsort(int x,int n) int i,j,a; for(i=0;i-1 & a xj) xj+1=xj; j-; xj+1=a; 4.簡單選擇排序(1)算法原理：第一趟排序是在無序的（R1,R2,R3,Rn）按排序碼選出最小的元素，將它與R1交換；第二趟排序是在無序的（R2,R3,Rn）中選出最小的元素，將它與R2交換；如此經(jīng)過n-1趟后整個數(shù)據(jù)元素序列就是有序的。(2)算法描述：selectsort (int x,int n) int i,j,small,swap;for(i=0;in-1;i+) small=i; for(j=i+1;jn;j+) if(xjRi+1則交換Ri和Ri+1的位置。第一趟完畢時Rn是序列中最大的數(shù)據(jù)元素。再從R1開始，兩兩比較Ri和Ri+1（i=1,2,n-2）的大小，若RiRi+1則交換Ri和Ri+1的位置。第二趟完畢時Rn-1是序列中次大的數(shù)據(jù)元素。如此反復進行n-1趟排序后將全部有序。(2)算法描述：bubblesort (int x,int n) int i,j,flag,swap; flag=1;