数据结构实验报告_4127

1、实验一单链表的插入，删除，初始化一、实验环境Windows xp操作系统Turbo C 2.0二、实验目的通过对链表的实际操作， 巩固链表的基本知识， 关键是掌握指针的操作。三、实验容生成一个头指针是 head 的单链表，然后对该链表进行插入和删除运算。四、实验要求1 编写程序生成一个单链表；2 插入、删除用子程序实现；3 输出每次运算前后的链表，进行比较与分析。五、实验步骤#include <stdlib.h>#include <stdio.h>#define NULL 0typedef struct LNodeint data;struct LNode *next;

2、LNode, *LinkList;/ 假设下面的单链表均为带头结点。void CreatLinkList(LinkList &head,int j)/建立一个单链表L;, 数据为整数，数据由键盘随机输入。int i;LinkList p,q;head=(LinkList)malloc(sizeof(LNode);head->next=NULL;q=head;printf("在单链表输入整数：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 的数据元素LNode *p;p=L->next;if(L->next=NULL)printf("链表没有元素 !n");return 0;printf("单链表的数据元素为:");while(p)printf("%d ",p->data);p=p->next;printf("n");/return 1;void L

4、inkListLengh(LinkList &L)/计算单链表L 的数据元素个数。int i=0;LinkList p;p=L->next;while(p)i+;p=p->next;printf(" 单链表的数据元素个数为 :%d",i); printf("n");int InsertLinkList(LinkList &L, int i, int x)/在单链表 L 的第 I 个元素前插入一个数据元素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 个数据元素。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)/销毁单链表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("链表已经被销毁!n");void main()/调用上面的各函数，运行并检验程序是否正确。LinkList L;int i,j,x;printf("-");printf("n");printf("单链表实验，按提示操作");printf("n");printf("-");printf("n");printf("输入的元素的个数:");scanf("%d"

8、,&j);CreatLinkList(L,j);LinkListLengh(L);PrintLinkList(L);printf("在第几个元素前插入:");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);六、实验结果实验二栈及其应用一、实验环境Windows xp操作系统Turbo C 2.0二、实验目的通过一个实际问题、加深对栈的理解；掌握进栈、出栈、清栈运算的实现方法。三、实验容十进制转换成八进制四、实验要求进栈、出栈和清栈的运算以子程序的方式实现。五、实验步骤#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<<"请输入一个正整数："<<endl;cin>>n;while(n)push( s , n % 8 ) ;n /= N;cout<<" 转换出的八进制为"<<endl;while( ! stackempty( s ) )pop( s , e ) ;cout<&

14、lt;e;cout<<endl;destroystack( s ) ;六实验结果：实验三二叉树的建立及输出一、实验环境Windows xp 操作系统 Turbo C 2.0 二、 实验目的熟悉二叉链表表示的二叉树结构及其递归遍历，掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。三、 实验容（ 1）建立一颗二叉链表表示的二叉树；（ 2）对其进行前序，中序，后序输出。四、 实验要求先将二叉树通过加入虚节点的方式使其完全化，然后按层将其输入。可以用二叉树中不会出现字符表示虚节点例如，另一二叉树中不会出现的字符表示输入序列结束例如 # 。如下二叉树须输入序列 abc# 。或以广义

15、表的形式输入二叉树的节点。 按先序，中序，后序序列将其遍历输出。五、实验步骤/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)|/没有孩子结点或者(pre!=NULL)&&(pre=cur->lchild)|(pre=cur->rchild)/ 孩子遍历过了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)| /没有左孩子或者(!treeStack.empty()&

25、amp;&(treeStack.top()=cur->rchild)/ 右孩子已经入过栈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、历二叉树 "<<endl; recur_preTraverse(root); cout << endl;cout<<" 非递归前序遍历二叉树 "<<endl; preTraverse();cout << endl << endl;cout<<" 递归中序遍历二叉树 "<<endl; recur_inTraverse(root); cout << endl;cout<<" 非递归中序遍历二叉树 "<&l

28、t;endl; inTraverse();cout << endl << endl;cout<<"递归后序遍历二叉树"<<endl;recur_postTraverse(root);cout << endl;cout<<"非递归后序遍历二叉树"<<endl;postTraverse();cout << endl << endl;六、实验结果实验四图及其遍历一、实验环境Windows xp 操作系统 Turbo C 2.0 二、 实验目的（ 1）熟悉

29、图的邻接矩阵及邻接表的表示方法；（ 2）掌握建立图的邻接矩阵算法， 并由邻接矩阵转化为邻接表；（ 3）熟悉对图遍历算法；（ 4）熟悉队列这种基本的数据结构。三、 实验容（ 1）建立图的邻接表及邻接矩阵；（ 2）对其进行深度优先及广度优先遍历。四、 实验要求将图以邻接矩阵的存储形式存入计算机， 然后输出其深度优先及广度优先序列。五、实验步骤#include <iostream>/#include <malloc.h>#define INFINITY 32767#define MAX_VEX 20 /最大顶点个数#define QUEUE_SIZE (MAX_VEX+1)

30、/ 队列长度 using namespace std;bool *visited; /访问标志数组/ 图的邻接矩阵存储结构typedef structchar *vexs; /顶点向量int arcsMAX_VEXMAX_VEX; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和弧数Graph;/ 队列类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;/ 创建无向网void CreateUDN(Graph &G)int i,j,w,s1,s2;char a,b,temp;printf("输入顶点数和弧数:&quo

32、t;);scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar(); /接收回车G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目printf("输入%d个顶点.n",G.vexnum);for(i=0;i<G.vexnum;i+) /初始化顶点printf("输入顶点%d:",i);scanf("%c",&G.vexsi);temp=getchar(); /接收回车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); /输入一条边依附的顶点和权值temp=getchar(); /接收回车s1=Locate(G,a);s2=Locate(G,b);G.arcss1s2=G.arcss2s1

34、=w;/ 图 G中顶点 k 的第一个邻接顶点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中顶点 i 的第 j 个邻接顶点的下一个邻接顶点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;/ 深度优先遍历void DFS(Graph G,int k)int i;if(k=-1) /第一次执行 DFS时 ,k 为 -1for(i=0;i<G.vexnum;i+)if(!visitedi)DFS(G,i);/ 对尚未访问的顶点调用DFSelsevisitedk=true;printf("%c ",G.vexsk); /访问第 k 个顶点for(i=FirstVex(G,k);i>=

36、0;i=NextVex(G,k,i)if(!visitedi)DFS(G,i);/ 对k的尚未访问的邻接顶点i 递归调用 DFS/ 广度优先遍历void BFS(Graph G)int k;Queue Q; /辅助队列 QQ.InitQueue();for(int i=0;i<G.vexnum;i+)if(!visitedi) /i尚未访问visitedi=true;printf("%c ",G.vexsi);Q.EnQueue(i); /i入列while(Q.front!=Q.rear)Q.DeQueue(k); /队头元素出列并置为kfor(int w=First

37、Vex(G,k);w>=0;w=NextVex(G,k,w)if(!visitedw) /w为k的尚未访问的邻接顶点visitedw=true;printf("%c ",G.vexsw);Q.EnQueue(w);/ 主函数void main()int i;Graph G;CreateUDN(G);visited=(bool *)malloc(G.vexnum*sizeof(bool);printf("n广度优先遍历 : ");for(i=0;i<G.vexnum;i+)visitedi=false;DFS(G,-1);printf(&quo

38、t;n深度优先遍历 : ");for(i=0;i<G.vexnum;i+)visitedi=false;BFS(G);printf("n程序结束 .n");六、实验结果实验五树表的查找一、实验环境Windows xp 操作系统 Turbo C 2.0 二、 实验目的（ 1）加深对二叉树的理解，掌握二叉排序树的基本特性。（ 2）进一步巩固二叉树的遍历这一重要概念， 掌握用二叉排序树进行排序，查找的方法。三、 实验容（ 1）对于给定的整数序列建立二叉排序树；（ 2）对其进行插入，删除；（ 3）对插入，删除后的二叉树进行中序遍历输出；（ 4）在二叉排序树中进行查找

39、。四、实验要求各算法以子程序的方式实现，输入输出要给出明确的提示。五、实验步骤#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”);例如 :二叉排序树50308020409035853288查找关键字=50,35,90,95,实验六排序一、实验环境Windows xp 操作系统 Turbo C 2.0 二、 实验目的（ 1）熟悉选择排序与快速排序；（ 2）对两种排序算法的稳定性进行比较。三、 实验容对于给定的 N 个关键字进行选择排序与快速排序输出。四、 实验要求设计的关键字序列应有关键字值相同或不同的情况。 这样才能比较出各算法的稳定性不同。五、实验步骤#include <stdlib.h>#include <ctime>#include <iostream.h>void CreatStable(int a, int n)/利用随机函数产生一个含有n 个整数的数组a ，元素为a1,an。int i;srand(time(0);for(i=0;i<=n;i+) ai=rand()%1000;void disp(int a,int l