电大数据结构实验报告

实验一单链表的插入，删除，初始化实验环境Windowsxp操作系统TurboC2.0二、实验目的通过对链表的实际操作，巩固链表的基本知识，关键是掌握指针的操作。三、实验内容生成一个头指针是head的单链表，然后对该链表进行插入和删除运算。四、实验要求1编写程序生成一个单链表；2插入、删除用子程序实现；3输出每次运算前后的链表，进行比较与分析。五、实验步骤#include<stdlib.h>#include<stdio.h>#defineNULL0typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;//假设下面的单链表均为带头结点。voidCreatLinkList(LinkList&head,intj){//建立一个单链表L;,数据为整数，数据由键盘随机输入。 inti; LinkListp,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->data);p->next=q->next; q->next=p; q=p;}}intPrintLinkList(LinkList&L){//输出单链表L的数据元素LNode*p; p=L->next; if(L->next==NULL) { printf("链表没有元素!\n"); return0; } printf("单链表的数据元素为:"); while(p) { printf("%d",p->data); p=p->next; } printf("\n"); //return1;}voidLinkListLengh(LinkList&L){//计算单链表L的数据元素个数。 inti=0; LinkListp; p=L->next; while(p) { i++; p=p->next; } printf("单链表的数据元素个数为:%d",i);printf("\n");}intInsertLinkList(LinkList&L,inti,intx){//在单链表L的第I个元素前插入一个数据元素X。 LinkListp,s; intj=0; p=L; while(p&&j<i-1) { p=p->next; ++j; } if(!p||j>i-1) { printf("插入元素的位置不合理!"); return0; } s=(LinkList)malloc(sizeof(LNode)); s->data=x; s->next=p->next; p->next=s; return1;}intDeleteLinkList(LinkList&L,inti){//删除单链表L的第I个数据元素。 LinkListp,q; intj=0; p=L; while(p->next&&j<i-1) { p=p->next; ++j; } if(!(p->next)||j>i-1) { printf("删除元素的位置不合理!"); return0; } q=p->next; p->next=q->next; i=q->data; free(q); return1;}voidClearLinkList(LinkList&L){//将单链表L置为空表。L->next=NULL;}voidDestroyLinkList(LinkList&L){//销毁单链表L。 LinkListp,q; p=L->next; while(L->next!=NULL) { q=p->next; L->next=q; free(p); p=q; }free(L);printf("链表已经被销毁!\n");}voidmain(){//调用上面的各函数，运行并检验程序是否正确。LinkListL; inti,j,x; printf("---------------------------------------"); printf("\n"); printf("《单链表实验，按提示操作》"); printf("\n"); printf("---------------------------------------");printf("\n"); printf("输入的元素的个数:"); scanf("%d",&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);;DeleteLinkList(L,i);LinkListLengh(L);PrintLinkList(L);ClearLinkList(L); printf("清空链表后:\n");LinkListLengh(L);PrintLinkList(L);DestroyLinkList(L);}六、实验结果实验二栈及其应用实验环境Windowsxp操作系统TurboC2.0二、实验目的通过一个实际问题、加深对栈的理解；掌握进栈、出栈、清栈运算的实现方法。三、实验内容十进制转换成八进制四、实验要求进栈、出栈和清栈的运算以子程序的方式实现。五、实验步骤#include<iostream.h>#include"malloc.h"#include"stdlib.h"#definestack_init_size100#definestackincrement10#defineN8typedefstruct{int*base;int*top;intstacksize;}sqstack;intinitstack(sqstack&s){s.base=(int*)malloc(stack_init_size*sizeof(int));if(!s.base)exit(0);s.top=s.base;s.stacksize=stack_init_size;return0;}intgettop(sqstacks,int&e){if(s.top==s.base)return1;e=*(s.top-1);return0;}intpush(sqstack&s,inte){if(s.top-s.base>=s.stacksize){s.base=(int*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(int));if(!s.base)return1;s.top=s.base+s.stacksize;s.stacksize+=stackincrement;}*s.top++=e;return0;}intpop(sqstack&s,int&e){if(s.top==s.base)return1;e=*--s.top;return0;}intstackempty(sqstacks){if(s.top==s.base)return1;return0;}intdestroystack(sqstack&s){free(s.base);s.base=s.top=0;return0;}voidmain(){intn,e;sqstacks;initstack(s);cout<<"请输入一个正整数："<<endl;cin>>n;while(n){push(s,n%8);n/=N;}cout<<"转换出的八进制为"<<endl;while(!stackempty(s)){pop(s,e);cout<<e;}cout<<endl;destroystack(s);}六实验结果：实验三二叉树的建立及输出实验环境Windowsxp操作系统TurboC2.0二、实验目的熟悉二叉链表表示的二叉树结构及其递归遍历，掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。三、实验内容（1）建立一颗二叉链表表示的二叉树；（2）对其进行前序，中序，后序输出。四、实验要求先将二叉树通过加入虚节点的方式使其完全化，然后按层将其输入。可以用二叉树中不会出现字符表示虚节点例如@，另一二叉树中不会出现的字符表示输入序列结束例如#。如下二叉树须输入序列a@b@@@c#。或以广义表的形式输入二叉树的节点。按先序，中序，后序序列将其遍历输出。五、实验步骤//A．HeaderFilesSourceFilesbitree.cpp#include"bitree.h"intmain(intargc,char*argv[]){intarray[]={5,6,3,7,67,1,24,8,21,16,78,9};Treetr(array,sizeof(array)/sizeof(array[0]));tr.traverse();return0;}//B.HeaderFilesbitree.h#include<iostream>#include<stack>//heredelete#include<cassert>usingnamespacestd;typedefinttelemtype;structbitnode//changetotypedefstructbitnodeanditwillbe//'typedef':ignoredonleftof'structbitnode'whennovariableisdeclaredatlastitwillbeok{bitnode*lchild;bitnode*rchild;telemtypedata;bitnode(inte=0,bitnode*left=NULL,bitnode*right=NULL){data=e;lchild=left;rchild=right;}};classTree{public:Tree(){root=NULL;}Tree(intarray[],intsize);~Tree();voidtraverse();voidpostTraverse();voidrecur_postTraverse(bitnode*cur);voidpreTraverse();voidrecur_preTraverse(bitnode*cur);voidinTraverse();voidrecur_inTraverse(bitnode*cur);private:Tree(constTree&t);Tree&operator=(constTree&t);bitnode*createTree(intarray[],intsize);voiddestroyTree(bitnode*cur);private:bitnode*root;};Tree::Tree(intarray[],intsize){if((array==NULL)||(size<=0))root=NULL;elseroot=createTree(array,size);}//createatreebitnode*Tree::createTree(intarray[],intsize){if((array==NULL)||(size<=0))returnNULL;intmid=size/2;bitnode*cur=newbitnode(array[mid]);cur->lchild=createTree(array,mid);cur->rchild=createTree(array+mid+1,size-mid-1);returncur;}Tree::~Tree(){destroyTree(root);}voidTree::destroyTree(bitnode*cur){if(cur!=NULL){destroyTree(cur->lchild);destroyTree(cur->rchild);deletecur;}}//后序递归遍历voidTree::recur_postTraverse(bitnode*cur){if(cur!=NULL){recur_postTraverse(cur->lchild);recur_postTraverse(cur->rchild);cout<<cur->data<<"";}}//先序递归遍历voidTree::recur_preTraverse(bitnode*cur){if(cur!=NULL){cout<<cur->data<<"";recur_preTraverse(cur->lchild);recur_preTraverse(cur->rchild);}}//中序递归遍历voidTree::recur_inTraverse(bitnode*cur){if(cur!=NULL){recur_inTraverse(cur->lchild);cout<<cur->data<<"";recur_inTraverse(cur->rchild);}}//后序非递归遍历voidTree::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->rchild==NULL))||//没有孩子结点或者((pre!=NULL)&&((pre==cur->lchild)||(pre==cur->rchild))))//孩子遍历过了{treeStack.pop();cout<<cur->data<<"";pre=cur;}else{if(cur->rchild!=NULL)treeStack.push(cur->rchild);if(cur->lchild!=NULL)treeStack.push(cur->lchild);}}}//中序非递归遍历voidTree::inTraverse(){stack<bitnode*>treeStack;bitnode*cur;//thefirstisbitnode*pre,*cur;delete*preisok;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())&&(treeStack.top()==cur->rchild)))//右孩子已经入过栈cout<<cur->data<<"";else{treeStack.push(cur->rchild);treeStack.push(cur);if(cur->lchild!=NULL)treeStack.push(cur->lchild);}}}//先序非递归遍历voidTree::preTraverse(){stack<bitnode*>treeStack;bitnode*cur;cur=root;if(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);}}voidTree::traverse(){cout<<"递归前序遍历二叉树"<<endl;recur_preTraverse(root);cout<<endl;cout<<"非递归前序遍历二叉树"<<endl;preTraverse();cout<<endl<<endl;cout<<"递归中序遍历二叉树"<<endl;recur_inTraverse(root);cout<<endl;cout<<"非递归中序遍历二叉树"<<endl;inTraverse();cout<<endl<<endl;cout<<"递归后序遍历二叉树"<<endl;recur_postTraverse(root);cout<<endl;cout<<"非递归后序遍历二叉树"<<endl;postTraverse();cout<<endl<<endl;}六、实验结果实验四图及其遍历实验环境Windowsxp操作系统TurboC2.0二、实验目的（1）熟悉图的邻接矩阵及邻接表的表示方法；（2）掌握建立图的邻接矩阵算法，并由邻接矩阵转化为邻接表；（3）熟悉对图遍历算法；（4）熟悉队列这种基本的数据结构。三、实验内容（1）建立图的邻接表及邻接矩阵；（2）对其进行深度优先及广度优先遍历。四、实验要求将图以邻接矩阵的存储形式存入计算机，然后输出其深度优先及广度优先序列。五、实验步骤#include<iostream>//#include<malloc.h>#defineINFINITY32767#defineMAX_VEX20//最大顶点个数#defineQUEUE_SIZE(MAX_VEX+1)//队列长度usingnamespacestd;bool*visited;//访问标志数组//图的邻接矩阵存储结构typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;//队列类classQueue{public:voidInitQueue(){base=(int*)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}voidEnQueue(inte){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int*base;intfront;intrear;};//图G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}//创建无向网voidCreateUDN(Graph&G){inti,j,w,s1,s2;chara,b,temp;printf("输入顶点数和弧数:");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.vexs[i]);temp=getchar();//接收回车}for(i=0;i<G.vexnum;i++)//初始化邻接矩阵for(j=0;j<G.vexnum;j++)G.arcs[i][j]=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.arcs[s1][s2]=G.arcs[s2][s1]=w;}}//图G中顶点k的第一个邻接顶点intFirstVex(GraphG,intk){if(k>=0&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//图G中顶点i的第j个邻接顶点的下一个邻接顶点intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j合理for(intk=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}//深度优先遍历voidDFS(GraphG,intk){inti;if(k==-1){//第一次执行DFS时,k为-1for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//对尚未访问的顶点调用DFS}else{visited[k]=true;printf("%c",G.vexs[k]);//访问第k个顶点for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接顶点i递归调用DFS}}//广度优先遍历voidBFS(GraphG){intk;QueueQ;//辅助队列QQ.InitQueue();for(inti=0;i<G.vexnum;i++)if(!visited[i]){//i尚未访问visited[i]=true;printf("%c",G.vexs[i]);Q.EnQueue(i);//i入列while(Q.front!=Q.rear){Q.DeQueue(k);//队头元素出列并置为kfor(intw=FirstVex(G,k);w>=0;w=NextVex(G,k,w))if(!visited[w]){//w为k的尚未访问的邻接顶点visited[w]=true;printf("%c",G.vexs[w]);Q.EnQueue(w);}}}}//主函数voidmain(){inti;GraphG;CreateUDN(G);visited=(bool*)malloc(G.vexnum*sizeof(bool));printf("\n广度优先遍历:");for(i=0;i<G.vexnum;i++)visited[i]=false;DFS(G,-1);printf("\n深度优先遍历:");for(i=0;i<G.vexnum;i++)visited[i]=false;BFS(G);printf("\n程序结束.\n");}六、实验结果实验五树表的查找实验环境Windowsxp操作系统TurboC2.0二、实验目的（1）加深对二叉树的理解，掌握二叉排序树的基本特性。（2）进一步巩固二叉树的遍历这一重要概念，掌握用二叉排序树进行排序，查找的方法。三、实验内容（1）对于给定的整数序列建立二叉排序树；（2）对其进行插入，删除；（3）对插入，删除后的二叉树进行中序遍历输出；（4）在二叉排序树中进行查找。四、实验要求各算法以子程序的方式实现，输入输出要给出明确的提示。五、实验步骤#include"stdio.h"#include"stdlib.h"typedefintdatatype;#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);printf(“%d\t”,bt->key);inorder(bt->rchild);}}bitree*bstsearch(bitree*t,intkey){if(t==0||t->key==key)return(t);elseif(t->key<key)return(bstsearch(t->rchild,key));elsereturn(bstsearch(t->rchild,key));}bitree*bstsearch1(bitree*t,intkey){bitree*p=t;while(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild;return(0);}voidbstinsert(bitree*&bt,intkey){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);}voidcreatebsttree(bitree*&bt){inti;for(i=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\n”);elseprintf(“notfound\n”);}5050308020908540358832例如:二叉排序树查找关键字==50,505035,503040355090,50809095,实验六排序实验环境Windowsxp操作系统TurboC2.0二、实验目的（1）熟悉选择排序与快速排序；（2）对两种排序算法的稳定性进行比较。三、实验内容对于给定的N个关键字进行选择排序与快速排序输出。四、实验要求设计的关键字序列应有关键字值相同或不同的情况。这样才能比较出各算法的稳定性不同。五、实验步骤#include<stdlib.h>#include<ctime>#include<iostream.h>voidCreatStable(inta[],intn){//利用随机函数产生一个含有n个整数的数组a[]，元素为a[1],…,a[n]。inti;srand(time(0));for(i=0;i<=n;i++)a[i]=rand()%1000;}voiddisp(inta[],intlow,inthigh){//显示数组元素a[low],...,a[high];inti;for(i=low;i<=high;i++)cout<<a[i]<<"";cout<<endl;}voidInsertSortA(inta[],i