PAGEPAGE4 《計算機軟件技術基礎》實驗報告專業(yè)_____________年級_____________學號_____________學生姓名_____________指導老師_____________南華大學計算機學院編

【實驗報告】實驗時間：實驗地點：實驗機號：具體實驗內容

程序調試過程實習小結=1\*ROMANI實驗要求1．每次實驗中有若干習題，每個學生至少應該完成其中的兩道習題。2．上機之前應作好充分的準備工作，預先編好程序，經過人工檢查無誤后，才能上機，以提高上機效率。3．獨立上機輸入和調試自己所編的程序，切忌抄襲、拷貝他人程序。4．上機結束后，應整理出實驗報告。書寫實驗報告時，重點放在調試過程和小節(jié)部分，總結出本次實驗中的得與失，以達到鞏固課堂學習、提高動手能力的目的。實驗一線性表【實驗目的】1．熟悉VC環(huán)境，學習如何使用C語言實現(xiàn)線性表的兩種存儲結構。2．通過編程、上機調試，進一步理解線性表的基本概念,熟練運用C語言實現(xiàn)線性表基本操作。3．熟練掌握線性表的綜合應用問題?！緦嶒瀮热荨勘刈觯?．一個線性表有n個元素（n<MAXSIZE,MAXSIZE指線性表的最大長度），且遞增有序。（1）現(xiàn)有一元素x要插入到線性表的適當位置上，并保持線性表原有的順序不變。采用鏈式存儲表示方法實現(xiàn)，設計程序實現(xiàn)（2）從單鏈表中刪除指定的元素x，若x在單鏈表中不存在，給出提示信息。要求：=1\*GB3①指定的值x由鍵盤輸入；=2\*GB3②程序能處理空鏈表的情況。選做：3．設有頭結點的單鏈表，編程對表中的作一值只保留一個結點，刪除其余值相同的結點。要求：=1\*GB3①該算法用函數(shù)（非主函數(shù)）實現(xiàn)；=2\*GB3②在主函數(shù)中調用創(chuàng)建鏈表的函數(shù)創(chuàng)建一個單鏈表，并調用該函數(shù)，驗證算法的正確性。4．已知非空單鏈表第一個結點由head指出，請寫一算法，交換p所指結點與其下一個結點在鏈表中的位置。要求：=1\*GB3①該算法用函數(shù)Reverse(head,p)實現(xiàn)，其中head為表頭指針，p指向要交換的結點；=2\*GB3②在主函數(shù)中調用創(chuàng)建鏈表的函數(shù)創(chuàng)建一個單鏈表，并調用該函數(shù)，驗證算法的正確性。要求：=1\*GB3①建立一個結點中含有三個域的單鏈表；=2\*GB3②在主函數(shù)中調用此算法，構成雙向循環(huán)鏈表；=3\*GB3③在主函數(shù)中利用正向和逆向兩種方式輸出鏈表中的數(shù)據(jù)，驗證算法的正確性。實驗二棧與隊列【實驗目的】1．學習如何使用C語言實現(xiàn)堆棧與隊列。2．熟悉堆棧與隊列的基本操作及應用?！緦嶒瀮热荨楷F(xiàn)有一循環(huán)順序隊列，其結構描述為：#definemaxsize10structsequeue{datatypedata[maxsize];intfront，rear;}; /*循環(huán)順序隊列的類型*/sequeue*sq要求：=1\*GB3①設計隊列的幾種幾種操作：初始化、進隊、出隊、取隊頭元素和判斷隊列是否非空。=2\*GB3②編寫一個主函數(shù)進行測試。2．順序堆棧實驗要求：=1\*GB3①設計堆棧的幾種幾種操作：初始化、入棧、出棧、取棧頂元素和判斷堆棧是否非空。=2\*GB3②編寫一個主函數(shù)進行測試。實驗三隊列與棧的應用必做：1、設一個算術表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個算法判斷其中的括號是否匹配。提示：本題使用一個運算符棧st，當遇到的‘（’、‘[’、或‘{’時進棧，當遇到‘}’、‘]’、‘）’時判斷棧頂是否為相應的括號，若是退棧繼續(xù)執(zhí)行；否則算法結束。選做：2、假設以數(shù)組sequ[0..MaxSize-1]存放環(huán)形隊列的元素，同時設變量rear和len分別指示環(huán)形隊列中隊尾元素的位置和內含元素的個數(shù)。試寫出此環(huán)形隊列隊滿的條件，并設計相應入隊和出隊的算法。（根據(jù)題目填空完善程序）提示：該環(huán)形隊列對滿的條件為：len==MaxSize，隊空的條件為：len==0。由rear,len求隊列頭指針front的過程為：front=rear-len+1；if(front<0)front=front+MaxSize；即front=(rear-len+1+MaxSize)%MaxSize#include<stdio.h>#definemaxsize6typedefcharqueue[maxsize]；intrear=0,len=0；intenqueue(queuequ,charx){if(len==maxsize)return0；else{rear=(rear+1)%maxsize；qu[rear]=x；len++；return1；}}intdequeue(queuequ,char*x){intfront；if(len==0)return0；else{front=(rear-len+1+maxsize)%maxsize；*x=qu[front]；len--；return1；}}voidmain(){charx；queuequ；printf(“a入隊\n”）；enqueue(qu,‘a’)；printf(“b入隊\n”）；enqueue(qu,‘b’)；printf(“c入隊\n”）；enqueue(qu,‘c’)；printf(“出隊一次：”）；dequeue(qu,&x)；printf(“%c\n”,x)；printf(“d入隊\n”）；enqueue(qu,‘d’)；printf(“e入隊\n”）；enqueue(qu,‘e’)；printf(“出隊一次：”）；dequeue(qu,&x)；printf（“%c\n”,x)；printf(“f入隊\n”）；enqueue(qu,‘f’)；printf(“g入隊\n”）；enqueue(qu,‘g’)；printf(“出隊一次：”）；dequeue(qu,&x)；printf（“%c\n”,x)；printf（“余下元素出列：”）；while(len>0){dequeue(qu,&x)；printf（“%c\n”,x)；}printf（“\n”）；}輸出：.入隊.入隊出隊一次：.入隊.入隊出隊一次：.入隊.入隊出隊一次：余下元素出列：實驗四樹實驗目的1.掌握二叉樹，二叉樹排序數(shù)的概念及存儲方法。2.掌握二叉樹的遍歷算法。3.熟練掌握編寫實現(xiàn)樹的各種運算的算法。實驗內容樹的基本運算：創(chuàng)建樹；輸出樹；遍歷樹；求二叉樹的深度；創(chuàng)建二叉排序樹；二叉排序樹的查找；二叉排序樹的刪除；創(chuàng)造哈夫曼樹；輸出哈夫曼樹；1、建立一棵二叉樹并中序遍歷。（填空）#include“stdio.h”#include“malloc.h”structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；blinkadd(blinkbt,charch){if(bt==NULL){bt=nalloc(sizeof(bnode))；bt->data=ch；bt->lchild=bt->rchild=NULL；}elseif(ch<bt->data)bt->lchild=add(bt->lchid,ch)；elsebt->rchild=add(bt->rchild,ch)；returnbt；}voidinorder(blinkbt){if(bt){inorder(bt->)；printf（“%c”,）；inorder(bt->)；}}main(){blinkroot=null；inti,n；charx；scanf（“%c”,&n)；for(i=1；i<=n；i++){x=getchar()；root=add(root,x)；}inorder(root)；printf（“\n”）；}輸入：ephqsbma輸出：2、求二叉樹的結點數(shù)和葉子數(shù)(填空)#include“stdio.h”#include“alloc.h”structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；intn=0,no=0；voidpreorder(blinkbt){if(bt){n++；if(bt->lchild==NULL&&bt->rchild==NULL)no++；preorder(bt->；)preorder(bt->；)}}blinkcreat(){blinkbt；charch；ch=getchar()；if(ch!=’#’){bt=nalloc(sizeof(bnode))；bt->data=ch；bt->lchild=()；bt->rchild=()；}elsebt=NULL；returnbt；}main(){blinkroot；root=creat()；preorder(root)；printf（“numberofnode：%dnumberofleaf：%d\n”,n,no)；}輸入：ab##cd###輸出：實驗五查找與排序【實驗目的】熟悉各種查找與排序的算法，并對各種算法的效率進行比較和測試。【實驗內容】排序算法比較。要求：=1\*GB3①調用函數(shù)intrand(void)產生100000個待排序的數(shù)據(jù)；=2\*GB3②測試下列各排序函數(shù)的機器實際執(zhí)行時間：a.直接插入排序；b.希爾排序c.選擇排序d.冒泡排序e.快速排序f.歸并排序實驗六綜合練習【實驗目的】1．在掌握基本