軟件技術(shù)基礎(chǔ)實驗報告-2

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

【實驗報告】實驗時間：實驗地點：實驗機號：具體實驗內(nèi)容

程序調(diào)試過程實習(xí)小結(jié)=1\*ROMANI實驗要求1．每次實驗中有若干習(xí)題，每個學(xué)生至少應(yīng)該完成其中的兩道習(xí)題。2．上機之前應(yīng)作好充分的準備工作，預(yù)先編好程序，經(jīng)過人工檢查無誤后，才能上機，以提高上機效率。3．獨立上機輸入和調(diào)試自己所編的程序，切忌抄襲、拷貝他人程序。4．上機結(jié)束后，應(yīng)整理出實驗報告。書寫實驗報告時，重點放在調(diào)試過程和小節(jié)部分，總結(jié)出本次實驗中的得與失，以達到鞏固課堂學(xué)習(xí)、提高動手能力的目的。實驗一線性表【實驗?zāi)康摹?．熟悉VC環(huán)境，學(xué)習(xí)如何使用C語言實現(xiàn)線性表的兩種存儲結(jié)構(gòu)。2．通過編程、上機調(diào)試，進一步理解線性表的基本概念,熟練運用C語言實現(xiàn)線性表基本操作。3．熟練掌握線性表的綜合應(yīng)用問題。【實驗內(nèi)容】必做：1．一個線性表有n個元素（n<MAXSIZE,MAXSIZE指線性表的最大長度），且遞增有序。（1）現(xiàn)有一元素x要插入到線性表的適當(dāng)位置上，并保持線性表原有的順序不變。采用鏈式存儲表示方法實現(xiàn)，設(shè)計程序?qū)崿F(xiàn)（2）從單鏈表中刪除指定的元素x，若x在單鏈表中不存在，給出提示信息。要求：=1\*GB3①指定的值x由鍵盤輸入；=2\*GB3②程序能處理空鏈表的情況。選做：3．設(shè)有頭結(jié)點的單鏈表，編程對表中的作一值只保留一個結(jié)點，刪除其余值相同的結(jié)點。要求：=1\*GB3①該算法用函數(shù)（非主函數(shù)）實現(xiàn)；=2\*GB3②在主函數(shù)中調(diào)用創(chuàng)建鏈表的函數(shù)創(chuàng)建一個單鏈表，并調(diào)用該函數(shù)，驗證算法的正確性。4．已知非空單鏈表第一個結(jié)點由head指出，請寫一算法，交換p所指結(jié)點與其下一個結(jié)點在鏈表中的位置。要求：=1\*GB3①該算法用函數(shù)Reverse(head,p)實現(xiàn)，其中head為表頭指針，p指向要交換的結(jié)點；=2\*GB3②在主函數(shù)中調(diào)用創(chuàng)建鏈表的函數(shù)創(chuàng)建一個單鏈表，并調(diào)用該函數(shù)，驗證算法的正確性。要求：=1\*GB3①建立一個結(jié)點中含有三個域的單鏈表；=2\*GB3②在主函數(shù)中調(diào)用此算法，構(gòu)成雙向循環(huán)鏈表；=3\*GB3③在主函數(shù)中利用正向和逆向兩種方式輸出鏈表中的數(shù)據(jù)，驗證算法的正確性。實驗二棧與隊列【實驗?zāi)康摹?．學(xué)習(xí)如何使用C語言實現(xiàn)堆棧與隊列。2．熟悉堆棧與隊列的基本操作及應(yīng)用?！緦嶒瀮?nèi)容】現(xiàn)有一循環(huán)順序隊列，其結(jié)構(gòu)描述為：#definemaxsize10structsequeue{datatypedata[maxsize];intfront，rear;}; /*循環(huán)順序隊列的類型*/sequeue*sq要求：=1\*GB3①設(shè)計隊列的幾種幾種操作：初始化、進隊、出隊、取隊頭元素和判斷隊列是否非空。=2\*GB3②編寫一個主函數(shù)進行測試。2．順序堆棧實驗要求：=1\*GB3①設(shè)計堆棧的幾種幾種操作：初始化、入棧、出棧、取棧頂元素和判斷堆棧是否非空。=2\*GB3②編寫一個主函數(shù)進行測試。實驗三隊列與棧的應(yīng)用必做：1、設(shè)一個算術(shù)表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個算法判斷其中的括號是否匹配。提示：本題使用一個運算符棧st，當(dāng)遇到的‘（’、‘[’、或‘{’時進棧，當(dāng)遇到‘}’、‘]’、‘）’時判斷棧頂是否為相應(yīng)的括號，若是退棧繼續(xù)執(zhí)行；否則算法結(jié)束。選做：2、假設(shè)以數(shù)組sequ[0..MaxSize-1]存放環(huán)形隊列的元素，同時設(shè)變量rear和len分別指示環(huán)形隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試寫出此環(huán)形隊列隊滿的條件，并設(shè)計相應(yīng)入隊和出隊的算法。（根據(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(chǎn)’)；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”）；}輸出：.入隊.入隊出隊一次：.入隊.入隊出隊一次：.入隊.入隊出隊一次：余下元素出列：實驗四樹實驗?zāi)康?.掌握二叉樹，二叉樹排序數(shù)的概念及存儲方法。2.掌握二叉樹的遍歷算法。3.熟練掌握編寫實現(xiàn)樹的各種運算的算法。實驗內(nèi)容樹的基本運算：創(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、求二叉樹的結(jié)點數(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###輸出：實驗五查找與排序【實驗?zāi)康摹渴煜じ鞣N查找與排序的算法，并對各種算法的效率進行比較和測試?！緦嶒瀮?nèi)容】排序算法比較。要求：=1\*GB3①調(diào)用函數(shù)intrand(void)產(chǎn)生100000個待排序的數(shù)據(jù)；=2\*GB3②測試下列各排序函數(shù)的機器實際執(zhí)行時間：a.直接插入排序；b.希爾排序c.選擇排序d.冒泡排序e.快速排序f.歸并排序?qū)嶒灹C合練習(xí)【實驗?zāi)康摹?．在掌握基本