軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告-2

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

【實(shí)驗(yàn)報(bào)告】實(shí)驗(yàn)時(shí)間：實(shí)驗(yàn)地點(diǎn)：實(shí)驗(yàn)機(jī)號：具體實(shí)驗(yàn)內(nèi)容

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