【正文】 ild,key)。return 1。Tdata=key。intInsertBST(BiTreeamp。structBiTNode *lChild, *rChild。//數(shù)據(jù)類(lèi)型 typedefint Status。第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告一． 題目要求1）編程實(shí)現(xiàn)二叉排序樹(shù)，包括生成、插入，刪除； 2）對(duì)二叉排序樹(shù)進(jìn)行先根、中根、和后根非遞歸遍歷；3）每次對(duì)樹(shù)的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹(shù)的形狀表示出來(lái)。優(yōu)點(diǎn)：簡(jiǎn)單，數(shù)據(jù)元素的提取速度快；缺點(diǎn)：（1）靜態(tài)存儲(chǔ)，無(wú)法預(yù)知問(wèn)題規(guī)模的大小，可能空間不足，或浪費(fèi)存儲(chǔ)空間；（2）插入元素和刪除元素時(shí)間復(fù)雜度高——O（n）求兩個(gè)集合的并集該算法是求兩個(gè)集合s1和s2的并集，并將結(jié)果存入s引用參數(shù)所表示的集合中帶回。Anext=qb。pb=pbnext。return OK。}} pb=B。qanext=Anext。qa=pa。qbnext=Anext。if(padatadata){} else{} qb=pb。qanext=Anext。pb){} while(pa){} qa=pa。while(paamp。Anext=NULL。// 保存pa的前驅(qū)指針 // 保存pb的前驅(qū)指針 pa=panext。qa=pa。pa=A。B,LinkList amp。j三．// 將合并逆置后的結(jié)果放在C表中，并刪除B表Status ListMergeOppose_L(LinkList amp。if(||)return INFEASIBLE。for(i=。a,int i,int k){//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i?！緦?shí)驗(yàn)結(jié)果】[實(shí)驗(yàn)數(shù)據(jù)、結(jié)果、遇到的問(wèn)題及解決]一． Status InsertOrderList(SqList amp。對(duì)線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤(pán)輸入（數(shù)據(jù)類(lèi)型為整型），建立相應(yīng)的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個(gè)集合的并的結(jié)果存儲(chǔ)在一個(gè)新的線性表集合中，并輸出。實(shí)驗(yàn)內(nèi)容：一、編寫(xiě)程序?qū)崿F(xiàn)順序表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能：（1）初始化順序表L；（2）依次在L尾部插入元素1,21,13,24,8；（3）輸出順序表L；（4）輸出順序表L長(zhǎng)度；（5）判斷順序表L是否為空；（6）輸出順序表L的第3個(gè)元素；（7）輸出元素24的位置；（8）在L的第4個(gè)元素前插入元素0；（9）輸出順序表L；（10）刪除L的第5個(gè)元素；（11）輸出順序表L。()。template int BiTree::i=0?！薄！薄！?。coutcoutLevelOrder(root)。coutcoutInOrder(root)。}BiTree(BiNode *root){ } ~BiTree(){Release(root)。elsereturn hr+1。int hr= Depth(rootrchild)。}}}int Depth(BiNode *root)//算法求二叉樹(shù)的深度{if(root==NULL)return 0。}else{showleaf(rootlchild)。(rootrchild==NULL)){coutdata。}else{if((rootlchild==NULL)amp。if(qrchild!=NULL)Q[++rear]=qrchild。coutdata。Q[++rear]=root。int front = 0, rear = 0。coutdata)。else {InOrder(rootlchild)。InOrder(rootrchild)。else {InOrder(rootlchild)。PreOrder(rootrchild)。else {coutdata。delete root。}}void Release(BiNode *root){if(root!=NULL){Release(rootlchild)。Creat(rootlchild)。else{root=new BiNode。39。cinch。void Creat(BiNode *amp。template class BiTree { private:static int i。BiNode *lchild,*rchild。（4）編寫(xiě)求二叉樹(shù)高度的函數(shù)（5）編寫(xiě)一主函數(shù)來(lái)驗(yàn)證算法實(shí)現(xiàn) 第一題源代碼：include using namespace std。（2）實(shí)現(xiàn)二叉樹(shù)層次遍歷的非遞歸算法。提交實(shí)驗(yàn)報(bào)告，報(bào)告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說(shuō)明、程序清單、調(diào)試情況、設(shè)計(jì)技巧、心得體會(huì)。二、實(shí)驗(yàn)要求：掌握二叉樹(shù)、哈夫曼樹(shù)和樹(shù)的特點(diǎn)。i++){coutcoutcoutreturn 0。for(i = 0。puts(“輸出三元表237。cin [i].item。i++){cin [i].row。//puts()與 cout 一樣for(i = 0。cin 。SparseMatrix AA,BB。pb++。[pb].col= [pa].row。pa 。for(int col = 0。=。B){ =。}。struct SparseMatrix { element data[MaxTerm]。T item。const int MaxTerm=100。i n *(n + 1)/ 2。k++。j {k = i *(i + 1)/ 2 + j。i n。int k = 0。j n。i n。a[j][i] = a[i][j]。j n。i n。cin n。int main(){ int n,i,j。int a[10][10]。（4）設(shè)計(jì)一個(gè)測(cè)試?yán)樱⒕帉?xiě)主程序進(jìn)行測(cè)試。（2）實(shí)現(xiàn)矩陣轉(zhuǎn)置算法。三、實(shí)驗(yàn)內(nèi)容：*n階的對(duì)稱(chēng)矩陣。掌握它們的常見(jiàn)算法。cout”心得體會(huì)：實(shí)驗(yàn)三 多維數(shù)組和廣義表的操作實(shí)驗(yàn)類(lèi)型：驗(yàn)證性 實(shí)驗(yàn)要求：必修 實(shí)驗(yàn)學(xué)時(shí)： 2學(xué)時(shí)一、實(shí)驗(yàn)?zāi)康模簠⒄战o定的多維數(shù)組類(lèi)和廣義表類(lèi)的程序樣例，驗(yàn)證給出的多維數(shù)組和廣義表的常見(jiàn)算法，并實(shí)現(xiàn)有關(guān)的操作。k = ()。} for(i = 1。i (i)。LinkQueue b。return x。if(pnext==NULL)rear=front。x=pdata。if(rear==front)throw“下溢”。} /***************************************/ template T LinkQueue::DeQueue(){ Node *p。rearnext=s。sdata=x。} /***************************************/ template void LinkQueue::EnQueue(T x){ Node *s。snext=NULL。/***************************************/ template LinkQueue::LinkQueue(){ Node *s。//取對(duì)頭元素} bool Empty()//判斷鏈隊(duì)列是否為空{(diào)front==rear?return 1:return 0。//將x入隊(duì)T DeQueue()。//隊(duì)頭隊(duì)尾指針 public: LinkQueue()。}。/*********************************************/ template struct Node { T data。return data[front]。} T DeQueue(){if(rear==front)throw “下溢”。int i=(front+1)% QueueSize。data[rear]=x。}~ CirQueue(){}void EnQueue(T x){if((rear+1)% QueueSize ==front)throw “上溢”。int front, rear。const int QueueSize=100。要求：：依次把 1,2,3,4,5入隊(duì)，然后出隊(duì)中的數(shù)據(jù)元素并在屏幕上顯示。cout”。coutint j=0。}coutfor(i=1。k=()。i(i)。LinkStack bb。return x。top=topnext。x=topdata。Node *p。top=s。//沒(méi)有申請(qǐng)空間時(shí) 會(huì)出現(xiàn)錯(cuò)誤！sdata=x。template void LinkStack::push(T x){ Node *s。} bool Empty(){top==NULL?return 1:return 0。T pop()。top=p。p=topnext。public: LinkStack(){top=NULL。}。}/****************************************************/ template struct Node { T data。x=da