個(gè)人資料整理 僅限學(xué)習(xí)使用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、引言數(shù)據(jù)結(jié)構(gòu)是一門理論性強(qiáng)、思維抽象、難度較大的課程，是基礎(chǔ)課和專業(yè)課之間的橋梁。該課程的先行課程是計(jì)算機(jī)基礎(chǔ)、程序設(shè)計(jì)語(yǔ)言、離散數(shù)學(xué)等，后續(xù)課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)原理、軟件工程等。通過(guò)本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力和解決實(shí)際問(wèn)題的能力。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在該專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問(wèn)題的能力。對(duì)于現(xiàn)實(shí)世界中的問(wèn)題，應(yīng)該能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最后獲得問(wèn)題的解答。實(shí)習(xí)課程是為了加強(qiáng)編程能力的培養(yǎng)，鼓勵(lì)學(xué)生使用新興的編程語(yǔ)言。相信通過(guò)數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐，無(wú)論是理論知識(shí)，還是實(shí)踐動(dòng)手能力，我們都會(huì)有不同程度上的提高。二、課程設(shè)計(jì)目的本課程是數(shù)據(jù)結(jié)構(gòu)課程的實(shí)踐環(huán)節(jié)。主要目的在于加強(qiáng)學(xué)生在課程中學(xué)習(xí)的相關(guān)算法和這些方法的具體應(yīng)用，使學(xué)生進(jìn)一步掌握在 C++或其他語(yǔ)言中應(yīng)用這些算法的能力。通過(guò)課程設(shè)計(jì)題目的練習(xí)，強(qiáng)化學(xué)生對(duì)所學(xué)知識(shí)的掌握及對(duì)問(wèn)題分析和任務(wù)定義的理解。個(gè)人資料整理 僅限學(xué)習(xí)使用三、內(nèi)容設(shè)計(jì)要求二叉排序樹(shù)的實(shí)現(xiàn)：用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)1）以回車<‘\n’）為輸入結(jié)束標(biāo)志，輸入數(shù)列 L,生成一棵二叉排序樹(shù)T。2>對(duì)二叉排序樹(shù)T作中序遍歷，輸出結(jié)果；3）輸入元素x，查找二叉排序樹(shù)T，若存在含x的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并作中序遍歷<執(zhí)行操作2）；否則輸出信息“無(wú)x”。<一）問(wèn)題分析和任務(wù)定義對(duì)問(wèn)題的描述應(yīng)避開(kāi)具體的算法和涉及的數(shù)據(jù)結(jié)構(gòu)，它是對(duì)要完成的任務(wù)作出明確的回答，強(qiáng)調(diào)的是做什么，而不是怎么做。<二）詳細(xì)的設(shè)計(jì)和編碼算法的具體描述和代碼的書(shū)寫(xiě)。<三）上機(jī)調(diào)試源程序的輸入和代碼的調(diào)試。要求：設(shè)計(jì)中要求綜合運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些與實(shí)際應(yīng)用結(jié)合緊密的、規(guī)模較大的問(wèn)題，通過(guò)分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，深刻理解、牢固的掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)技術(shù)，掌握分析、解決實(shí)際問(wèn)題的能力。四、源代碼1、用二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)#include<iostream>usingnamespacestd。typedefintKeyType。個(gè)人資料整理 僅限學(xué)習(xí)使用typedefstructNode{KeyTypekey。structNode*lchild,*rchild。}BSTNode,*BSTree。voidInsertBST(BSTree*bst,KeyTypekey>{BSTrees。if(*bst==NULL>/* 遞歸結(jié)束條件*/{s=newBSTNode。s->key=key。s->lchild=NULL。s->rchild=NULL。*bst=s。}elseif(key<(*bst>->key>InsertBST(&((*bst>->lchild>,key>。/*將s插入左子樹(shù)*/elseif(key>(*bst>->key>InsertBST(&((*bst>->rchild>,key>。/*將s插入右子樹(shù)*/}voidCreateBST(BSTree*bst>{個(gè)人資料整理 僅限學(xué)習(xí)使用KeyTypekey。*bst=NULL。scanf("%d",&key>。while(key!=0>{InsertBST(bst,key>。scanf("%d",&key>。}}voidInOrder(BSTreeroot>{if(root!=NULL>{InOrder(root->lchild>。printf("%d",root->key>。InOrder(root->rchild>。}}BSTNode*DelBST(BSTreeT,KeyTypex>{BSTNode*p,*f,*s,*q。p=T。f=NULL。個(gè)人資料整理 僅限學(xué)習(xí)使用while(p>/*查找關(guān)鍵字為x的待刪結(jié)點(diǎn)p*/{if(p->key==x>break。f=p。 /*f指向p結(jié)點(diǎn)的雙親結(jié)點(diǎn)*/if(p->key>x>p=p->lchild。elsep=p->rchild。}if(p==NULL>returnT。/*若找不到，返回原來(lái)的二叉排序樹(shù)*/if(p->lchild==NULL>/*p無(wú)左子樹(shù)*/{if(f==NULL>T=p->rchild。elseif(f->lchild==p>f->lchild=p->rchild。elsef->rchild=p->rchild。deletep。}else/*p有左子樹(shù)*/{個(gè)人資料整理 僅限學(xué)習(xí)使用q=p。s=p->lchild。while(s->rchild>/*在p的左子樹(shù)中查找最右下結(jié)點(diǎn) */{q=s。s=s->rchild。}if(q==p>q->lchild=s->lchild。/*將s的左子樹(shù)鏈到q上*/elseq->rchild=s->lchild。p->key=s->key。deletes。}returnT。}voidmain(>{BSTreeT。intx。BSTreeresult。printf("建立二叉排序樹(shù)，請(qǐng)輸入序列 L:\n">。CreateBST(&T>。個(gè)人資料整理 僅限學(xué)習(xí)使用printf("中序遍歷輸出序列為:">。InOrder(T>。cin>>x。result=DelBST(T,x>。if(result!=NULL>{InOrder(result>。}elseprintf("無(wú)x\n">。}2、用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)#include<iostream>usingnamespacestd。typedefintKeyType。typedefstructNode{KeyTypekey。structNode*next。}BSTNode,*BSTree。intA[40]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}。intj,i=0。個(gè)人資料整理 僅限學(xué)習(xí)使用voidInsertBST(intA[],KeyTypekey>{intj=0。while(A[j]!=-1>{if(key<A[j]>j=2*j+1。elsej=2*j+2。}A[j]=key。}voidCreateBST(intA[]>{intkey。scanf("%d",&key>。while(key!=-1>{InsertBST(A,key>。scanf("%d",&key>。}}voidTraverse(intA[],inti>{if(A[i]!=-1>{個(gè)人資料整理 僅限學(xué)習(xí)使用Traverse(A,2*i+1>。cout<<A[i]<<'\t'。Traverse(A,2*i+2>。}}voidDelBST(intA[],KeyTypex>{for(i=0。i<40。i++>if(A[i]==x>A[i]=-1。}voidmain(>{intx。//intkey。printf("建立二叉排序樹(shù)，請(qǐng)輸入序列 L:\n">。CreateBST(A>。printf("中序遍歷輸出序列為:">。Traverse(A,0>。cin>>x。if(A[i]!=-1>{DelBST(A,x>。printf("刪除x后中序遍歷輸出序列為 :">。個(gè)人資料整理 僅限學(xué)習(xí)使用Traverse(A,0>。}elseprintf("無(wú)X\n">。}五、測(cè)試分析程序運(yùn)行：1、用二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：個(gè)人資料整理 僅限學(xué)習(xí)使用2、用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：六、總結(jié)與體會(huì)通過(guò)一周的課程設(shè)計(jì)，對(duì)計(jì)算機(jī)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及 C++的使用都有了更深的了解。在理論學(xué)習(xí)和上機(jī)實(shí)踐的各個(gè)環(huán)節(jié)中，通過(guò)自主學(xué)習(xí)和請(qǐng)教老師，我收獲了不少。當(dāng)然也遇到不少的問(wèn)題，也正是因?yàn)檫@些問(wèn)題引發(fā)的思考給我?guī)Я藗€(gè)人資料整理 僅限學(xué)習(xí)使用收獲。從當(dāng)初不喜歡上機(jī)寫(xiě)程序到現(xiàn)在能主動(dòng)寫(xiě)程序，從當(dāng)初拿著程序不知如何下手到現(xiàn)在知道如何分析問(wèn)題，如何用專業(yè)知識(shí)解決實(shí)際問(wèn)題的轉(zhuǎn)變，我發(fā)現(xiàn)無(wú)論是專業(yè)知識(shí)還是動(dòng)手能力，自己都有很大程度的提高。通過(guò)課程設(shè)計(jì)題目的練習(xí)，強(qiáng)化學(xué)生對(duì)所學(xué)知識(shí)的掌握及對(duì)問(wèn)題分析和任務(wù)定義的理解。在這段時(shí)間里，我遇到過(guò)的問(wèn)題主要就是 C語(yǔ)言和C++語(yǔ)言有些