數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告_4127

1、實(shí)驗(yàn)一單鏈表的插入，刪除，初始化一、實(shí)驗(yàn)環(huán)境Windows xp操作系統(tǒng)Turbo C 2.0二、實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)對(duì)鏈表的實(shí)際操作， 鞏固鏈表的基本知識(shí)， 關(guān)鍵是掌握指針的操作。三、實(shí)驗(yàn)容生成一個(gè)頭指針是 head 的單鏈表，然后對(duì)該鏈表進(jìn)行插入和刪除運(yùn)算。四、實(shí)驗(yàn)要求1 編寫(xiě)程序生成一個(gè)單鏈表；2 插入、刪除用子程序?qū)崿F(xiàn)；3 輸出每次運(yùn)算前后的鏈表，進(jìn)行比較與分析。五、實(shí)驗(yàn)步驟#include <stdlib.h>#include <stdio.h>#define NULL 0typedef struct LNodeint data;struct LNode *next;

2、LNode, *LinkList;/ 假設(shè)下面的單鏈表均為帶頭結(jié)點(diǎn)。void CreatLinkList(LinkList &head,int j)/建立一個(gè)單鏈表L;, 數(shù)據(jù)為整數(shù)，數(shù)據(jù)由鍵盤(pán)隨機(jī)輸入。int i;LinkList p,q;head=(LinkList)malloc(sizeof(LNode);head->next=NULL;q=head;printf("在單鏈表輸入整數(shù)：n");for(i=0;i<j;i+) p=(LinkList)malloc(sizeof(LNode); scanf("%d",&p-&

3、gt;data);p->next=q->next;q->next=p;q=p;int PrintLinkList(LinkList &L)/輸出單鏈表L 的數(shù)據(jù)元素LNode *p;p=L->next;if(L->next=NULL)printf("鏈表沒(méi)有元素 !n");return 0;printf("單鏈表的數(shù)據(jù)元素為:");while(p)printf("%d ",p->data);p=p->next;printf("n");/return 1;void L

4、inkListLengh(LinkList &L)/計(jì)算單鏈表L 的數(shù)據(jù)元素個(gè)數(shù)。int i=0;LinkList p;p=L->next;while(p)i+;p=p->next;printf(" 單鏈表的數(shù)據(jù)元素個(gè)數(shù)為 :%d",i); printf("n");int InsertLinkList(LinkList &L, int i, int x)/在單鏈表 L 的第 I 個(gè)元素前插入一個(gè)數(shù)據(jù)元素X。LinkList p,s;int j=0;p=L;while(p&&j<i-1)p=p->ne

5、xt;+j;if(!p|j>i-1)printf("插入元素的位置不合理!");return 0;s=(LinkList)malloc(sizeof(LNode);s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i)/刪除單鏈表L 的第 I 個(gè)數(shù)據(jù)元素。LinkList p,q;int j=0;p=L;while(p->next&&j<i-1)p=p->next;+j;if(!(p->n

6、ext)|j>i-1)printf("刪除元素的位置不合理!");return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void ClearLinkList(LinkList &L)/將單鏈表 L 置為空表。L->next=NULL;void DestroyLinkList(LinkList &L)/銷(xiāo)毀單鏈表L。LinkList p,q;p=L->next;while(L->next!=NULL)q=p->next;L->nex

7、t=q;free(p);p=q;free(L);printf("鏈表已經(jīng)被銷(xiāo)毀!n");void main()/調(diào)用上面的各函數(shù)，運(yùn)行并檢驗(yàn)程序是否正確。LinkList L;int i,j,x;printf("-");printf("n");printf("單鏈表實(shí)驗(yàn)，按提示操作");printf("n");printf("-");printf("n");printf("輸入的元素的個(gè)數(shù):");scanf("%d"

8、,&j);CreatLinkList(L,j);LinkListLengh(L);PrintLinkList(L);printf("在第幾個(gè)元素前插入:");scanf("%d",&i);printf("輸入插入的元素:");scanf("%d",&x);InsertLinkList(L,i,x);LinkListLengh(L);PrintLinkList(L);printf("輸入刪除元素的位置:");scanf("%d",&i);Dele

9、teLinkList(L,i);LinkListLengh(L);PrintLinkList(L);ClearLinkList(L);printf("清空鏈表后 :n");LinkListLengh(L);PrintLinkList(L);DestroyLinkList(L);六、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)二棧及其應(yīng)用一、實(shí)驗(yàn)環(huán)境Windows xp操作系統(tǒng)Turbo C 2.0二、實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)一個(gè)實(shí)際問(wèn)題、加深對(duì)棧的理解；掌握進(jìn)棧、出棧、清棧運(yùn)算的實(shí)現(xiàn)方法。三、實(shí)驗(yàn)容十進(jìn)制轉(zhuǎn)換成八進(jìn)制四、實(shí)驗(yàn)要求進(jìn)棧、出棧和清棧的運(yùn)算以子程序的方式實(shí)現(xiàn)。五、實(shí)驗(yàn)步驟#include <iostr

10、eam.h>#include "malloc.h"#include "stdlib.h"#define stack_init_size100#define stackincrement10#define N8typedef structint *base ;int *top ;int stacksize ;sqstack ;int initstack ( sqstack &s )s.base=(int*)malloc(stack_init_size*sizeof( int ) ) ;if ( ! s.base )exit(0) ;s.top

11、 = s.base ;s.stacksize = stack_init_size ;return 0 ;int gettop ( sqstack s , int &e )if ( s.top = s.base )return 1 ;e = * ( s.top - 1 ) ;return 0 ;int push ( sqstack &s , int e )if( s.top - s.base >= s.stacksize )s.base = ( int * ) realloc ( s.base ,(s.stacksize + stackincrement ) * sizeo

12、f ( int ) ) ; if (!s.base) return 1 ;s.top = s.base + s.stacksize ;s.stacksize += stackincrement ;*s.top+ = e ;return 0 ;int pop ( sqstack &s , int &e )if ( s.top = s.base ) return 1 ;e = * -s.top ;return 0 ;int stackempty (sqstack s)if ( s.top = s.base )return 1 ;return 0 ;int destroystack

13、(sqstack &s )free( s.base ) ;s.base = s.top = 0 ;return 0 ;void main()int n , e ;sqstack s ;initstack( s ) ;cout<<"請(qǐng)輸入一個(gè)正整數(shù)："<<endl;cin>>n;while(n)push( s , n % 8 ) ;n /= N;cout<<" 轉(zhuǎn)換出的八進(jìn)制為"<<endl;while( ! stackempty( s ) )pop( s , e ) ;cout<&

14、lt;e;cout<<endl;destroystack( s ) ;六實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)三二叉樹(shù)的建立及輸出一、實(shí)驗(yàn)環(huán)境Windows xp 操作系統(tǒng) Turbo C 2.0 二、 實(shí)驗(yàn)?zāi)康氖煜ざ骀湵肀硎镜亩鏄?shù)結(jié)構(gòu)及其遞歸遍歷，掌握建立二叉鏈表要領(lǐng)，深入理解遞歸遍歷二叉鏈表的執(zhí)行路徑。三、 實(shí)驗(yàn)容（ 1）建立一顆二叉鏈表表示的二叉樹(shù)；（ 2）對(duì)其進(jìn)行前序，中序，后序輸出。四、 實(shí)驗(yàn)要求先將二叉樹(shù)通過(guò)加入虛節(jié)點(diǎn)的方式使其完全化，然后按層將其輸入?？梢杂枚鏄?shù)中不會(huì)出現(xiàn)字符表示虛節(jié)點(diǎn)例如，另一二叉樹(shù)中不會(huì)出現(xiàn)的字符表示輸入序列結(jié)束例如 # 。如下二叉樹(shù)須輸入序列 abc# ?；蛞詮V義

15、表的形式輸入二叉樹(shù)的節(jié)點(diǎn)。 按先序，中序，后序序列將其遍歷輸出。五、實(shí)驗(yàn)步驟/A Header Files Source Files bitree.cpp#include"bitree.h"int main(int argc, char* argv)int array = 5,6,3,7,67,1,24,8,21,16,78,9;Tree tr(array, sizeof(array)/sizeof(array0);tr.traverse();return 0;/B. Header Files bitree.h#include <iostream>#includ

16、e <stack>/here delete #include<cassert>using namespace std;typedef int telemtype;struct bitnode /change to typedef struct bitnode and it will be/'typedef ' : ignored on left of 'struct bitnode' when no variable is declared at last it will be ok bitnode* lchild;bitnode* rc

17、hild;telemtype data;bitnode(inte=0,bitnode*left=NULL,bitnode*right=NULL)data = e;lchild = left;rchild = right;class Treepublic:Tree()root = NULL;Tree(int array, int size);Tree();void traverse();void postTraverse();void recur_postTraverse(bitnode* cur);void preTraverse();void recur_preTraverse(bitnod

18、e* cur);void inTraverse();void recur_inTraverse(bitnode* cur);private:Tree(const Tree& t);Tree& operator=(const Tree& t);bitnode* createTree(int array, int size);void destroyTree(bitnode* cur);private:bitnode* root;Tree:Tree(int array, int size)if (array=NULL)|(size<=0)root = NULL;els

19、eroot = createTree(array, size);/create a treebitnode* Tree:createTree(int array, int size)if (array=NULL)|(size<=0)return NULL;int mid=size/2;bitnode* cur=new bitnode(arraymid); cur->lchild = createTree(array, mid); cur->rchild = createTree(array+mid+1, size-mid-1); return cur;Tree:Tree()d

20、estroyTree(root);void Tree:destroyTree(bitnode* cur)if (cur != NULL)destroyTree(cur->lchild);destroyTree(cur->rchild);delete cur;/ 后序遞歸遍歷void Tree:recur_postTraverse(bitnode* cur)if (cur!=NULL)recur_postTraverse(cur->lchild);recur_postTraverse(cur->rchild);cout << cur->data <

21、< " "/ 先序遞歸遍歷void Tree:recur_preTraverse(bitnode* cur)if (cur!=NULL)cout << cur->data << " "recur_preTraverse(cur->lchild);recur_preTraverse(cur->rchild);/ 中序遞歸遍歷void Tree:recur_inTraverse(bitnode* cur)if (cur!=NULL)recur_inTraverse(cur->lchild);cout &l

22、t;< cur->data << " "recur_inTraverse(cur->rchild);/ 后序非遞歸遍歷void Tree:postTraverse()stack<bitnode*> treeStack;bitnode *pre, *cur;cur = root;pre = NULL;if (cur!=NULL)treeStack.push(cur);while(!treeStack.empty()cur = treeStack.top();if(cur->lchild=NULL)&&(cur-&

23、gt;rchild=NULL)|/沒(méi)有孩子結(jié)點(diǎn)或者(pre!=NULL)&&(pre=cur->lchild)|(pre=cur->rchild)/ 孩子遍歷過(guò)了treeStack.pop();cout << cur->data << " " pre = cur;elseif (cur->rchild!=NULL)treeStack.push(cur->rchild);if (cur->lchild!=NULL)treeStack.push(cur->lchild);/ 中序非遞歸遍歷void

24、 Tree:inTraverse()stack<bitnode*> treeStack;bitnode *cur;/the first is bitnode *pre, *cur; delete *pre is ok;cur = root;if (cur!=NULL)treeStack.push(cur);while(!treeStack.empty()cur = treeStack.top();treeStack.pop();if (cur = NULL)continue;if (cur->lchild=NULL)| /沒(méi)有左孩子或者(!treeStack.empty()&

25、amp;&(treeStack.top()=cur->rchild)/ 右孩子已經(jīng)入過(guò)棧cout << cur->data << " "elsetreeStack.push(cur->rchild);treeStack.push(cur);if (cur->lchild!=NULL)treeStack.push(cur->lchild);/ 先序非遞歸遍歷void Tree:preTraverse()stack<bitnode*> treeStack;bitnode *cur;cur = root;i

26、f (cur!=NULL)treeStack.push(cur);while(!treeStack.empty()cur = treeStack.top();treeStack.pop();cout << cur->data << " "if (cur->rchild!=NULL)treeStack.push(cur->rchild);if (cur->lchild!=NULL)treeStack.push(cur->lchild);void Tree:traverse()cout<<" 遞歸前序遍

27、歷二叉樹(shù) "<<endl; recur_preTraverse(root); cout << endl;cout<<" 非遞歸前序遍歷二叉樹(shù) "<<endl; preTraverse();cout << endl << endl;cout<<" 遞歸中序遍歷二叉樹(shù) "<<endl; recur_inTraverse(root); cout << endl;cout<<" 非遞歸中序遍歷二叉樹(shù) "<&l

28、t;endl; inTraverse();cout << endl << endl;cout<<"遞歸后序遍歷二叉樹(shù)"<<endl;recur_postTraverse(root);cout << endl;cout<<"非遞歸后序遍歷二叉樹(shù)"<<endl;postTraverse();cout << endl << endl;六、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)四圖及其遍歷一、實(shí)驗(yàn)環(huán)境Windows xp 操作系統(tǒng) Turbo C 2.0 二、 實(shí)驗(yàn)?zāi)康模?1）熟悉

29、圖的鄰接矩陣及鄰接表的表示方法；（ 2）掌握建立圖的鄰接矩陣算法， 并由鄰接矩陣轉(zhuǎn)化為鄰接表；（ 3）熟悉對(duì)圖遍歷算法；（ 4）熟悉隊(duì)列這種基本的數(shù)據(jù)結(jié)構(gòu)。三、 實(shí)驗(yàn)容（ 1）建立圖的鄰接表及鄰接矩陣；（ 2）對(duì)其進(jìn)行深度優(yōu)先及廣度優(yōu)先遍歷。四、 實(shí)驗(yàn)要求將圖以鄰接矩陣的存儲(chǔ)形式存入計(jì)算機(jī)， 然后輸出其深度優(yōu)先及廣度優(yōu)先序列。五、實(shí)驗(yàn)步驟#include <iostream>/#include <malloc.h>#define INFINITY 32767#define MAX_VEX 20 /最大頂點(diǎn)個(gè)數(shù)#define QUEUE_SIZE (MAX_VEX+1)

30、/ 隊(duì)列長(zhǎng)度 using namespace std;bool *visited; /訪問(wèn)標(biāo)志數(shù)組/ 圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)typedef structchar *vexs; /頂點(diǎn)向量int arcsMAX_VEXMAX_VEX; /鄰接矩陣int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)Graph;/ 隊(duì)列類(lèi)class Queuepublic:void InitQueue()base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0;void EnQueue(int e)baserear=e;rear=(rear+1)%QUEU

31、E_SIZE;void DeQueue(int &e)e=basefront;front=(front+1)%QUEUE_SIZE;public:int *base;int front;int rear;/ 圖 G中查找元素 c的位置int Locate(Graph G,char c)for(int i=0;i<G.vexnum;i+)if(G.vexsi=c) return i;return -1;/ 創(chuàng)建無(wú)向網(wǎng)void CreateUDN(Graph &G)int i,j,w,s1,s2;char a,b,temp;printf("輸入頂點(diǎn)數(shù)和弧數(shù):&quo

32、t;);scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar(); /接收回車(chē)G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配頂點(diǎn)數(shù)目printf("輸入%d個(gè)頂點(diǎn).n",G.vexnum);for(i=0;i<G.vexnum;i+) /初始化頂點(diǎn)printf("輸入頂點(diǎn)%d:",i);scanf("%c",&G.vexsi);temp=getchar(); /接收回車(chē)for(i=0;i<G

33、.vexnum;i+) /初始化鄰接矩陣for(j=0;j<G.vexnum;j+)G.arcsij=INFINITY;printf("輸入 %d條弧 .n",G.arcnum);for(i=0;i<G.arcnum;i+) /初始化弧printf("輸入弧 %d:",i);scanf("%c %c %d",&a,&b,&w); /輸入一條邊依附的頂點(diǎn)和權(quán)值temp=getchar(); /接收回車(chē)s1=Locate(G,a);s2=Locate(G,b);G.arcss1s2=G.arcss2s1

34、=w;/ 圖 G中頂點(diǎn) k 的第一個(gè)鄰接頂點(diǎn)int FirstVex(Graph G,int k)if(k>=0 && k<G.vexnum) /k 合理 for(int i=0;i<G.vexnum;i+)if(G.arcski!=INFINITY) return i;return -1;/ 圖 G中頂點(diǎn) i 的第 j 個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)int NextVex(Graph G,int i,int j)if(i>=0 && i<G.vexnum && j>=0 && j<G.vex

35、num) /i,j 合理 for(int k=j+1;k<G.vexnum;k+)if(G.arcsik!=INFINITY) return k;return -1;/ 深度優(yōu)先遍歷void DFS(Graph G,int k)int i;if(k=-1) /第一次執(zhí)行 DFS時(shí) ,k 為 -1for(i=0;i<G.vexnum;i+)if(!visitedi)DFS(G,i);/ 對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFSelsevisitedk=true;printf("%c ",G.vexsk); /訪問(wèn)第 k 個(gè)頂點(diǎn)for(i=FirstVex(G,k);i>=

36、0;i=NextVex(G,k,i)if(!visitedi)DFS(G,i);/ 對(duì)k的尚未訪問(wèn)的鄰接頂點(diǎn)i 遞歸調(diào)用 DFS/ 廣度優(yōu)先遍歷void BFS(Graph G)int k;Queue Q; /輔助隊(duì)列 QQ.InitQueue();for(int i=0;i<G.vexnum;i+)if(!visitedi) /i尚未訪問(wèn)visitedi=true;printf("%c ",G.vexsi);Q.EnQueue(i); /i入列while(Q.front!=Q.rear)Q.DeQueue(k); /隊(duì)頭元素出列并置為kfor(int w=First

37、Vex(G,k);w>=0;w=NextVex(G,k,w)if(!visitedw) /w為k的尚未訪問(wèn)的鄰接頂點(diǎn)visitedw=true;printf("%c ",G.vexsw);Q.EnQueue(w);/ 主函數(shù)void main()int i;Graph G;CreateUDN(G);visited=(bool *)malloc(G.vexnum*sizeof(bool);printf("n廣度優(yōu)先遍歷 : ");for(i=0;i<G.vexnum;i+)visitedi=false;DFS(G,-1);printf(&quo

38、t;n深度優(yōu)先遍歷 : ");for(i=0;i<G.vexnum;i+)visitedi=false;BFS(G);printf("n程序結(jié)束 .n");六、實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)五樹(shù)表的查找一、實(shí)驗(yàn)環(huán)境Windows xp 操作系統(tǒng) Turbo C 2.0 二、 實(shí)驗(yàn)?zāi)康模?1）加深對(duì)二叉樹(shù)的理解，掌握二叉排序樹(shù)的基本特性。（ 2）進(jìn)一步鞏固二叉樹(shù)的遍歷這一重要概念， 掌握用二叉排序樹(shù)進(jìn)行排序，查找的方法。三、 實(shí)驗(yàn)容（ 1）對(duì)于給定的整數(shù)序列建立二叉排序樹(shù)；（ 2）對(duì)其進(jìn)行插入，刪除；（ 3）對(duì)插入，刪除后的二叉樹(shù)進(jìn)行中序遍歷輸出；（ 4）在二叉排序樹(shù)中進(jìn)行查找

39、。四、實(shí)驗(yàn)要求各算法以子程序的方式實(shí)現(xiàn)，輸入輸出要給出明確的提示。五、實(shí)驗(yàn)步驟#include "stdio.h"#include "stdlib.h"typedef int datatype;#define n 10typedef struct nodeint key; struct node *lchild,*rchild;bitree; void inorder(bitree *bt)if(bt!=0)inorder(bt- >lchild);printf(“ t%d” ,bt->key);inorder(bt->rchild);

40、bitree *bstsearch(bitree *t, int key)if (t=0 | t->key=key) return(t);else if (t->key<key) return(bstsearch(t->rchild,key); else return(bstsearch(t->rchild,key);bitree *bstsearch1(bitree *t, int key)bitree *p=t;while(p!=0) if (p->key=key) return(p);else if (p->key>key)p=p->

41、lchild; else p=p->rchild;return(0);void bstinsert(bitree *&bt,int key)if (bt=0)bt=(bitree *)malloc(sizeof(bitree); bt->key=key;bt->lchild=bt->rchild=0;elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);void createbsttree(bitree *&bt)int i;for(i

42、=1;i<=n;i+) bstinsert(bt,random(100);main( )bitree *bt=0;createbsttree(bt);inorder(bt); printf(n” );“if(bstsearch(bt,44) !=0)printf(“ found”);elseprintf(“ notn”);例如 :二叉排序樹(shù)50308020409035853288查找關(guān)鍵字=50,35,90,95,實(shí)驗(yàn)六排序一、實(shí)驗(yàn)環(huán)境Windows xp 操作系統(tǒng) Turbo C 2.0 二、 實(shí)驗(yàn)?zāi)康模?1）熟悉選擇排序與快速排序；（ 2）對(duì)兩種排序算法的穩(wěn)定性進(jìn)行比較。三、 實(shí)驗(yàn)容對(duì)于給定的 N 個(gè)關(guān)鍵字進(jìn)行選擇排序與快速排序輸出。四、 實(shí)驗(yàn)要求設(shè)計(jì)的關(guān)鍵字序列應(yīng)有關(guān)鍵字值相同或不同的情況。 這樣才能比較出各算法的穩(wěn)定性不同。五、實(shí)驗(yàn)步驟#include <stdlib.h>#include <ctime>#include <iostream.h>void CreatStable(int a, int n)/利用隨機(jī)函數(shù)產(chǎn)生一個(gè)含有n 個(gè)整數(shù)的數(shù)組a ，元素為a1,an。int i;srand(time(0);for(i=0;i<=n;i+) ai=rand()%1000;void disp(int a,int l