數(shù)據(jù)結(jié)構(gòu)實驗報告

PAGE2PAGE5數(shù)據(jù)結(jié)構(gòu)實驗報告學號：08055140班級：計算機86姓名：鄧凱提交日期：091216第一次上機實習題目運用鏈表實現(xiàn)數(shù)據(jù)的排序，并檢測：（一）、12、21、34、56、23、36、87、13、987。（二）、9、2、4、1、5、3、6、7、8、12、13、11、10。（三）、234、162、289、999、435、90三組數(shù)據(jù)。二、相關(guān)知識或技術(shù)（對應(yīng)DS部分）C++的一些基本知識，以及鏈表的創(chuàng)建以及應(yīng)用之類的知識。算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計（算法設(shè)計）voidsort(Lnode*L)//鏈表中元素按遞增排序{Lnode*p,*q,*r,*s;if(L->next!=NULL){p=L->next->next;L->next->next=NULL;}while(p){q=p;p=p->next;r=L;s=L->next;while(s&&s->data.shuju<=q->data.shuju){r=s;s=s->next;}r->next=q;q->next=s;}四、上機環(huán)境和使用語言（計算機程序?qū)崿F(xiàn)）Microsoftvisualc++;使用c++語言輸入：9、2、4、1、5、3、6、7、8、12、13、11、10運行結(jié)果：輸入：234、162、289、999、435、90運行結(jié)果：T（n）=n;六、上機總結(jié)本最近正在學線性表、棧、對列之類，我對這些知識真是陌生，嘗試著寫了，可總是調(diào)試不過，總會出現(xiàn)大堆的問題。有時候沒有錯誤，可也沒有運行結(jié)果，已經(jīng)到了最后的期限了，也只能和老師打個擦邊球，運用以前還算熟悉的鏈表，也就是線性表做了做編程最為基礎(chǔ)，最為常見的事情，排序。不過，雖說如此但也是有所感悟，線性表大都會用到指針，而用指針則往往會出錯，也就是說，學習數(shù)據(jù)結(jié)構(gòu)，出錯是在所難免的。而且學習一定要學個清楚，在這里，只要有一絲含糊，就會出錯，一定要認真對待。七、參考資料1．數(shù)據(jù)結(jié)構(gòu)（c語言版）清華大學出版社2．數(shù)據(jù)結(jié)構(gòu)習題集清華大學出版社3．C++面向?qū)ο蟪绦蛟O(shè)計西安交大出版社第二次上機實習題目建立二叉樹，并對其進行先序、中序、后序三種不同的遍歷，并測試以下數(shù)據(jù)（一）、ab##c###（二）、abc##de#g##f###（三）、abc#de##f##i##g#hj###三組數(shù)據(jù)。二、相關(guān)知識或技術(shù)（對應(yīng)DS部分）C語言，C++的一些基本知識，樹的建立、遍歷以及應(yīng)用之類的知識。算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計（算法設(shè)計）先序遍歷voidPreOrder(BinTreeroot)//{if(root!=NULL){printf("%c",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}}中序遍歷voidInOrder(BinTreeroot)/{if(root!=NULL){PreOrder(root->lchild);printf("%c",root->data);PreOrder(root->rchild);}}/后序遍歷voidPostOrder(BinTreeroot)/{if(root!=NULL){PreOrder(root->lchild);PreOrder(root->rchild);}printf("%c",root->data);}四、Microsoftvs6.0五、源程序（帶注釋或說明）、運行結(jié)果（數(shù)據(jù)或屏幕顯示、結(jié)果分析、討論T(n)）#include<stdio.h>#include<stdlib.h>typedefstructBNode{chardata;structBNode*lchild;structBNode*rchild;}BTNode;typedefBTNode*BinTree;voidCreateBinTree(BinTree*root)//以先序來建立二叉樹{charch;ch=getchar();if(ch=='')//空格*root=NULL;//建立空二叉樹else{*root=(BTNode*)malloc(sizeof(BTNode));//開辟空間，生成節(jié)點(*root)->data=ch;CreateBinTree(&((*root)->lchild));CreateBinTree(&((*root)->rchild));}}voidPreOrder(BinTreeroot)//先序遍歷{if(root!=NULL){printf("%c",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}}voidInOrder(BinTreeroot)//中序遍歷{if(root!=NULL){PreOrder(root->lchild);printf("%c",root->data);PreOrder(root->rchild);}}voidPostOrder(BinTreeroot)//后序遍歷{if(root!=NULL){PreOrder(root->lchild);PreOrder(root->rchild);}printf("%c",root->data);}voidmain(){BinTreeroot;CreateBinTree(&root);printf("先序遍歷:");PreOrder(root);printf("\n");printf("中序遍歷:");InOrder(root);printf("\n");printf("后序遍歷:");PostOrder(root);printf("\n");}輸入ab##c###運行結(jié)果輸入：abc##de#g##f###運行結(jié)果：輸入：abc#de##f##i##g#hj###運行結(jié)果：六、上機總結(jié)課上的速度飛快，還沒來得及看書，一章就過去了?，F(xiàn)在聽課更還是像以前一樣，云里霧里，都快成仙了，不過有些時候還是能聽懂，但總也聽不完全，因此做這樣的實驗真可謂是難啊，先得看上半天的書，然后再在網(wǎng)上看有沒有類似的程序，忙得不可開交，好不容易找到個，編輯器通不過，只是一個錯誤卻半天也找不到，哎，何苦呢，與其如此還不如自己寫，浪費時間，卻什么也沒學到。這個程序我又在網(wǎng)上看，看到底怎么個寫法，寫了半天最后還得請隔壁宿舍的同學幫忙調(diào)試，大半天弄不好。不過，還算是搞出來了，這樣簡單的一個程序，卻也難倒了我，哎，前路多艱，我將努力學習。七、參考資料1．數(shù)據(jù)結(jié)構(gòu)（c語言版）清華大學出版社2．數(shù)據(jù)結(jié)構(gòu)習題集清華大學出版社3．C++面向?qū)ο蟪绦蛟O(shè)計西安交大出版社第三次上機實習題目對于十個輸入的整形數(shù)據(jù)進行快速排序，并按照從小到大的順序輸出排序后結(jié)果并測試以下數(shù)據(jù)：（一）、0987654321（二）、12，23，89，90，78，76，45，34，43，60（三）、1，123，12，45，876，345，24，37，0，876三組數(shù)據(jù)。二、相關(guān)知識或技術(shù)（對應(yīng)DS部分）C語言，C++的一些基本知識，快速排序的算法以及應(yīng)用之類的知識。算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計（算法設(shè)計）快速排序中的一趟：intpartition(inta[],intlow,inthigh){intpivotkey;pivotkey=a[low];while(low<high){while(low<high&&a[high]>=pivotkey)--high;a[low]=a[high];while(low<high&&a[low]<=pivotkey)++low;a[high]=a[low];}a[low]=pivotkey;returnlow;}快速排序的遞歸形式：voidqsort(inta[],intlow,inthigh){intpivotloc;if(low<high){pivotloc=partition(a,low,high);//一趟排序結(jié)果的調(diào)用qsort(a,low,pivotloc-1);qsort(a,pivotloc+1,high);}四、Microsoftvs6.0五、源程序（帶注釋或說明）、運行結(jié)果（數(shù)據(jù)或屏幕顯示、結(jié)果分析、討論T(n)）#include"stdio.h"#include"stdlib.h"#defineN10#include"iostream.h"intpartition(inta[],intlow,inthigh){//快速排序中的一趟intpivotkey;pivotkey=a[low];while(low<high){while(low<high&&a[high]>=pivotkey)--high;a[low]=a[high];while(low<high&&a[low]<=pivotkey)++low;a[high]=a[low];}a[low]=pivotkey;returnlow;}voidqsort(inta[],intlow,inthigh){//快速排序的遞歸形式intpivotloc;if(low<high){pivotloc=partition(a,low,high);//一趟排序結(jié)果的調(diào)用qsort(a,low,pivotloc-1);qsort(a,pivotloc+1,high);}}voidinit(inta[]){//輸入要拍的數(shù)據(jù)inti;cout<<"請輸入將要排序的十個數(shù)字"<<endl;for(i=0;i<N;i++)cin>>a[i];}voidmain() { inta[N],i; init(a); qsort(a,0,N); printf("排序后的結(jié)果\n"); for(i=1;i<=N;i++){//輸出排序后的數(shù)據(jù) printf("%d",a[i-1]); if(i%10==0) printf("\n\n"); }printf("\n\n");}測試數(shù)據(jù)1．輸入：0987654321運行結(jié)果：2.輸入：12，23，89，90，78，76，45，34，43，60運行結(jié)果：3.輸入：1，123，12，45，876，345，24，37，0，876運行結(jié)果：六、上機總結(jié)課終于上完了，但這門課還沒有結(jié)束，除了實驗還有考試，迄今為止，還是很不懂，費了大半天的功夫，也只能做出這類的極其簡單的程序，還是多半用的過去的知識，真是慚愧啊。不過總還算是有些收獲，至少這個程序所運用的快速排序還是學會了。也只有慢慢來了，前路多艱，也不僅僅是數(shù)據(jù)結(jié)構(gòu)這門課程，其實好多事情也正如數(shù)據(jù)結(jié)構(gòu)這門課程，難，但是不得不學，對于計算機的同學，應(yīng)該是不得不學會。選擇了計算機就無可避免的選擇了數(shù)據(jù)結(jié)構(gòu)，選擇了人生也就選擇了努力與奮斗，這算是這次實驗的一點心得吧。七、參考資料1．數(shù)據(jù)結(jié)構(gòu)（c語言版）清華大學出版社2．數(shù)據(jù)結(jié)構(gòu)習題集清華大學出版社3．C++面向?qū)ο蟪绦蛟O(shè)計西安交大出版社第四次上機實習題目實現(xiàn)樹與二叉樹的轉(zhuǎn)化，并測試一組數(shù)據(jù)。二、相關(guān)知識或技術(shù)（對應(yīng)DS部分）C語言，C++的一些基本知識，樹、二叉樹的基本知識。算法及數(shù)據(jù)結(jié)構(gòu)設(shè)計（算法設(shè)計）voidChangeToBinary(Node*pNode){if(pLChild==NULL)return;Node*pL=newNode(pLChild->val);pNode->pLeft=pL;pLChild->ChangeToBinary(pNode->pLeft);if(pLChild->pRSibling){Node*pR=newNode(pLChild->pRSibling->val);pNode->pRight=pR;pLChild->pRSibling->ChangeToBinary(pNode->pRight);}四、Microsoftvs6.0五、源程序（帶注釋或說明）、運行結(jié)果（數(shù)據(jù)或屏幕顯示、結(jié)果分析、討論T(n)）#include<iostream>usingnamespacestd;structNode;structTreeNode;structNode{charval;Node*pLeft;Node*pRight;Node(){pLeft=NULL;pRight=NULL;}Node(charch){val=ch;pLeft=NULL;pRight=NULL;}~Node(){if(pLeft)pLeft->~Node();if(pRight)pRight->~Node();deletethis;}voidInsert(charch){if(ch>=val){if(pRight)pRight->Insert(ch);else{Node*add=newNode(ch);pRight=add;}}else{if(pLeft)pLeft->Insert(ch);else{Node*add=newNode(ch);pLeft=add;}}}voidShow(){cout<<val<<endl;if(pLeft)pLeft->Show();if(pRight)pRight->Show();}};structTreeNode{charval;TreeNode*pLChild;TreeNode*pRSibling;TreeNode(){pLChild=NULL;pRSibling=NULL;}TreeNode(charch){val=ch;pLChild=NULL;pRSibling=NULL;}~TreeNode(){if(pLChild)pLChild->~TreeNode();if(pRSibling)pRSibling->~TreeNode();deletethis;}voidInsert(charch){if(ch>=val){if(pRSibling)pRSibling->Insert(ch);else{TreeNode*pR=newTreeNode(ch);pRSibling=pR;}}else{if(pLChild)pLChild->Insert(ch);else{TreeNode*pL=newTreeNode(ch);pLChild=pL;}}}voidShow(){cout<<val<<endl;if(pLChild)pLChild->Show();if(pRSibling)pRSibling->Show();}voidChangeToBinary(Node*pNode){if(pLChild==NULL)return;Node*pL=newNode(pLChild->val);pNode->pLeft=pL;pLChild->ChangeToBinary(pNode->pLeft);if(pLChild->pRSibling){Node*pR=newNode(pLChild->pRSibling->val);pNode->pRight=pR;pLChild->pRSibling->ChangeToBinary(pNode->pRight);}}};classBinaryTree;classTree;classBinaryTree{public:Node*root;public:BinaryTree(){root=NULL;}~BinaryTree(){if(root)root->~Node();}voidInsert(charch){if(!root)root=newNode(ch);elseroot->Insert(ch);}voidShow(){if(root)root->Show();}};classTree{public:TreeNode*root;public:Tree(){root=NULL;}~Tree(){if(root)root->~TreeNode();}voidInsert(charch){if(!root)root=newTreeNode(ch);elseroot->Insert(ch);}voidShow(){if(root)root->Show();}BinaryTree*ChangeToBinary(){if(root==NULL)returnNULL;Binary