数据结构实验报告

1、实验一：线性表一，实验目的（1）理解和掌握线性顺序表元素建立，查找，插入、删除等算法。（2)熟悉C语言的上机环境，掌握C语言的基本结构。（3) 熟悉对单链表的一些基本操作和具体的函数定义。（4) 通过单链表的定义掌握线性表的链式存储结构的特点。（5) 熟悉对单链表的一些其它操作。二，实验内容实现单链表的定义和操作是最为基础的内容，共有如下几个环节：（1）建立结点类型。（2）初始化单链表。（3）求单链表的长度。（4）用前插法建立单链表。（5）从单链表表中查找元素。（6）向单链表中插入元素。（7）从单链表中删除元素。三，问题描述（1）建立一个线性顺序表，要求从键盘输入几个数，并将该线性顺序表的 元

2、素从屏幕显示出来；（2) 编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插 入后的线性顺序表输出；由用户输入删除第几个元素，将完成删除 的线性顺序表输出。（3) 编写查找函数，在上面的线性顺序表中查找其中一个元素，如果找到， 返回该元素在线性顺序表中该元素的值。（4）编写求单链表长度的函数，结果为输出元素的个数。四，实验代码/*本实验程序要求单链表的数据域是字符串,完成单链表的初始化、插入、删除操作插入时不允许重复的串插入表中。*/#include #include #include using namespace std;typedef char DataType;/定义Data

3、Type为字符类型，后面用字符数组表示字符串typedef struct LNodeDataType string10; LNode *next;LNode,*Listpointer;/定义单链表的结点类型Listpointer Creatnullnode()/创建一个空结点 Listpointer p; /定义头指针p=(Listpointer)malloc(sizeof(LNode);p-next=NULL;return p;int ListpointerLength(Listpointer L)int k=0;while(L-next)k+;L=L-next;return k;/求单链表

4、的长度void ListpointerTraverse(Listpointer L)Listpointer p=L;printf(当前链表为：n);while(L-next)printf(%s,L-next-string);printf(n);L=L-next;cout共ListpointerLength(p)个元素endlnext=NULL);/检查单链表是否为空Listpointer ListpointerGet(Listpointer L,int i)if(iListpointerLength(L)return NULL;for(int k=0;knext;return L;/从单链表表

5、中查找元素int ListpointerLocate(Listpointer L,DataType* x)int k=0;while(L-next)k+;if(strcmp(L-next-string,x)=0)return k;L=L-next;return -1;/从单链表表中查找与给定元素值相同的元素在链表中的位置void ListpointerInsert(Listpointer L,int i,DataType* x)Listpointer p=L;if(iListpointerLength(L)+1)cout位置越界，未插入！endlnext)&(strcmp(p-next-str

6、ing,x)!=0)p=p-next;if(p-next)printf(该数据之前结点已存在，未插入n);return;elsep=L;for(int k=1;knext; Listpointer q=(Listpointer)malloc(sizeof(LNode); strcpy(q-string,x); q-next=L-next; L-next=q; ListpointerTraverse(p);/向单链表中插入元素void ListpointerDel(Listpointer L,DataType* x)Listpointer s=L;while(L-next&strcmp(L-ne

7、xt-string,x)!=0)L=L-next;if(L-next=NULL)cout没有该数据，链表未修改endlnext;L-next=L-next-next;free(q);ListpointerTraverse(s);/从单链表中删除元素Listpointer ListpointerCreat(Listpointer L)char s10;Listpointer p,q,r=NULL;r=L;printf(请输入各个结点的数据，每个结点不超过10个字符，依次回车确认，输入#回车结束：n);scanf(%s,s);while(strcmp(s,#)!=0)p=L;while(p-nex

8、t)&(strcmp(p-next-string,s)!=0)p=p-next;if(p-next)printf(该数据之前结点已存在，未插入，请继续输入：n);scanf(%s,s);elseq=(Listpointer)malloc(sizeof(LNode);strcpy(q-string,s);q-next=NULL;r-next=q; r=q; scanf(%s,s);r-next=NULL;coutendl;ListpointerTraverse(L);return L;/用尾插法建立单链表int main()Listpointer first=Creatnullnode();in

9、t flag=1,i;while(flag) if(ListpointerEmpty(first)cout链表为空，按以下提示创建：endl;first=ListpointerCreat(first); int ch;/功能编号 cout欢迎您光临 n;cout*n;cout* 1,插入 *n;cout* 2,删除 *n;cout* 3,查找已知下标对应的数据 *n;cout* 4,查找已知数据对应的下标 *n; cout* 5,退出本系统 *n;cout*n;coutch; switch(ch)case 1:int k;DataType s10;coutk; couts; Listpoint

10、erInsert(first,k,s); break;case 2:DataType s10;couts;ListpointerDel(first,s);break;case 3:int k;coutk;if(ListpointerGet(first,k)coutstringendlendl;elsecout下标越界！endlendl;break;case 4:DataType s10;couts;if(ListpointerLocate(first,s)!=-1)cout下标为：ListpointerLocate(first,s)endlendl;elsecout没有该数据！endlnext

11、) first=first-next; free(first); free(first);break;default:cout输入不正确，请重试！endlendl;system(CLR);/主函数五，程序运行结果1，建立链表2，插入数据3，删除数据4，查找已知下标对应的数据5，查找已知数据对应的下标实验二：二叉树 一实验目的：1) 掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围。2) 掌握用指针类型描述、访问和处理二叉树的运算。3) 掌握二叉树的建立方法，熟悉二叉树结点的结构和对二叉树的基本操作4) 掌握对二叉树每一种操作的具体实现，掌握二叉树遍历的基本方法（前序、 中序、后序）

12、5）学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二实验内容：该程序的功能是实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体函数定义和主函数。共有如下几个环节：1，建立二叉树2，编写先序、递归遍历函数3，编写先序、非递归遍历函数4，编写中序、递归遍历函数5，编写中序、非递归遍历函数6，编写后序、递归遍历函数7，编写后序、非递归遍历函数3 问题描述实现二叉树的定义和操作共有如下几个环节：1，初始化二叉树(即把树根指针置空)2，按先序次序建立一个二叉树3，检查二叉树是否为空4，按任一种遍历次序（包括先序、中序、后序）输出二叉树中的所有结点四，

13、实验代码#include #include#include #include #include using namespace std; struct btnode char data; struct btnode *Lchild; struct btnode *Rchild; ; /建立二叉树结点的结构体类型 struct btnode *createbt(struct btnode *bt ) /先序建立二叉树 char c; c=getchar(); if(c=.) /如果输入为空，则子树为空 bt=NULL; else if(!(bt=(struct btnode *)malloc(s

14、izeof(struct btnode) printf(error!); /检验bt空间分配是否成功 bt-data=c; bt-Lchild=createbt(bt-Lchild); /递归建立左子树 bt-Rchild=createbt(bt-Rchild); /递归建立右子树 return(bt); void preOrder(struct btnode *bt) /递归先序遍历 if(bt!=NULL) printf(%c,bt-data); preOrder(bt-Lchild); preOrder(bt-Rchild); void preOrder1(struct btnode *

15、bt) /非递归先序遍历 int i=0; struct btnode *p; stack s; /定义栈 p=bt; while(p!=NULL|!s.empty() while(p!=NULL) printf(%c,p-data); s.push(p); /将根结点压栈 p=p-Lchild; /遍历左子树 if(!s.empty() p=s.top(); /提取栈顶元素值 s.pop(); /栈顶元素出栈 p=p-Rchild; /访问右子树 void midOrder(struct btnode *bt) /递归中序遍历 if(bt!=NULL)midOrder(bt-Lchild);

16、 printf(%c,bt-data); midOrder(bt-Rchild); void midOrder1(struct btnode *bt) /非递归中序遍历 int i=0; struct btnode *p; stack s; p=bt; while(p!=NULL|!s.empty() while(p!=NULL) s.push(p); p=p-Lchild; if(!s.empty() p=s.top(); printf(%c,p-data); s.pop(); p=p-Rchild; void postOrder(struct btnode *bt) /递归后序遍历 if(

17、bt!=NULL) postOrder(bt-Lchild); postOrder(bt-Rchild); printf(%c,bt-data); void postOrder1 (struct btnode *bt) /非递归后序遍历 struct btnode *p,*pre=NULL; stack s; s.push(bt); while(!s.empty() p=s.top(); if(p-Lchild=NULL&p-Rchild=NULL)|(pre!=NULL&(pre=p-Lchild|pre=p-Rchild) /判断p是否为空或是pre的根结点 printf(%c,p-dat

18、a); s.pop(); pre=p; else if(p-Rchild!=NULL) s.push(p-Rchild); /先将右结点压栈 if(p-Lchild!=NULL) s.push(p-Lchild); /后将左结点压栈，因为先入后出 void main() /主函数 printf(注意空格符用“.”来表示：nn); printf(请按照前序遍历的顺序输入：n); struct btnode *root=NULL; root=createbt(root); printf(n先序递归遍历结果：); preOrder(root); printf(n中序递归遍历结果：); midOrde

19、r(root); printf(n后序递归遍历结果：); postOrder(root); printf(nn先序非递归遍历结果：); preOrder1(root); printf(n中序非递归遍历结果：); midOrder1(root); printf(n后序非递归遍历结果：); postOrder1(root); printf(nn); system(pause);五，运行结果实验三：图一实验目的 （1）掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。（2）遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。二实验内容（1) 采

20、用邻接矩阵作为图的存储结构，完成有向图和无向图的DFS和BFS操作；（2) 采用邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。三问题具体描述（1）在图的邻接矩阵表示法中： 用邻接矩阵表示顶点间的相邻关系建立它的邻接矩阵，然后利用队列的五种基本运算（置空队列、进队、出队、 取队头元素、判队空）实现图的广度优先搜索周游。具体过程：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发

21、的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。（2）图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited 。广度优先搜索是一种分层的搜索过程, 每向前走一步可能访问一批顶点, 不像深度优先搜索那样有往回退的情况。因此, 广度优先搜索不是一个递归的过程。四，实验代码#includestdio.h #includestdlib.h #define MaxVertexNum 100 /定义最大顶点数/ typ

22、edef struct char vexsMaxVertexNum; /顶点表/ int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表/ int n,e; /图中的顶点数n和边数e/ MGraph; /用邻接矩阵表示的图的类型/ /=建立邻接矩阵=/ void CreatMGraph(MGraph *G) int i,j,k; char a; printf(请输入顶点的数目 和 边的数目： ); scanf(%d,%d,&G-n,&G-e); /输入顶点数和边数/ scanf(%c,&a); printf(请输入图的每个顶点：); for(i=0;in;

23、i+) scanf(%c,&a); G-vexsi=a; /读入顶点信息，建立顶点表/ for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; /初始化邻接矩阵/ printf(请输入每条边对应的起始点 和 终点：n); for(k=0;ke;k+) /读入e条边，建立邻接矩阵 / scanf(%d%d,&i,&j); /输入边（Vi，Vj）的顶点序号/ G-edgesij=1; G-edgesji=1; /若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句/ /=定义标志向量，为全局变量=/ typedef enumFALSE,TRUE Boolean; B

24、oolean visitedMaxVertexNum; /=DFS：深度优先遍历的递归算法=/ void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j; printf(%c,G-vexsi); /访问顶点Vi/ visitedi=TRUE; /置已访问标志/ for(j=0;jn;j+) /依次搜索Vi的邻接点/ if(G-edgesij=1 & ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未访问过，故Vj为新出发点/ void DFS(MGraph *G) int i; for(i

25、=0;in;i+) visitedi=FALSE; /标志向量初始化/ for(i=0;in;i+) if(!visitedi) /Vi未访问过/ DFSM(G,i); /以Vi为源点开始DFS搜索/ /=BFS：广度优先遍历= void BFS(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索/ int i,j,f=0,r=0; int cqMaxVertexNum; /定义队列 / for(i=0;in;i+) visitedi=FALSE; /标志向量初始化/ for(i=0;in;i+) cqi=-1; /队列初始化/ printf(%c,G-ve

26、xsk); /访问源点Vk/ visitedk=TRUE; cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队/ while(cqf!=-1) /队非空则执行/ i=cqf; f=f+1; /Vf出队/ for(j=0;jn;j+) /依次Vi的邻接点Vj/ if(G-edgesij=1 & !visitedj) /Vj未访问/ printf(%c,G-vexsj); /访问Vj/ visitedj=TRUE; r=r+1; cqr=j; /访问过Vj入队/ /=main=/ void main() int i; MGraph *G; G=(MGraph *)malloc(siz

27、eof(MGraph); /为图G/ CreatMGraph(G); /建立邻接矩阵/ printf(图的深度遍历为： ); DFS(G); /深度优先遍历/ printf(n); printf(图的广度遍历为： ); BFS(G,0); /以序号为0的顶点开始广度优先遍历/ printf(n); 五，程序运行结果实验四：快速排序及折半排序一实验目的（1) 掌握线性结构上排序的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。（2) 掌握树形结构（二叉排序树）实现查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。二实验内容（1) 有序表

28、的二分查找,建立有序表，然后进行二分查找（2) 二叉排序树的查找,建立二叉排序树，然后查找三，实验代码1，快速排序#include #include #include #include malloc.husing namespace std; struct sqlist int key11; int length; ; /链表的结构型定义 int partition(struct sqlist *l,int low,int high) int pivotkey; l-key0=l-keylow;pivotkey=l-keylow;while(lowhigh) while(lowkeyhigh=

29、pivotkey) high-;l-keylow=l-keyhigh; while(lowkeylowkeyhigh=l-keylow; l-keylow=l-key0;return low; /找到序列的枢轴 void qsort(struct sqlist *l,int low,int high) int pivotloc; if(lowlength); /“快速调用”的函数定义void main() /主函数 int n; int i; struct sqlist num; printf(请输入排序的个数:n); scanf(%d,&n); printf(请输入数值:n); num.le

30、ngth=n; for(i=1; i=num.length; i+) scanf(%d,&(num.keyi); quicksort(&num); printf(n快速排序后的结果为n); for(i=1;i=num.length;i+) printf(%d ,num.keyi); printf(nn); system(pause);2，折半排序#include #include#include #include malloc.husing namespace std; #define maxlen 50typedef struct int datamaxlen+1; int last;Seq

31、uenlist; /结构体类型定义 Sequenlist *Sqlset() Sequenlist *L; int i; L= (Sequenlist*) malloc(sizeof(Sequenlist); L-last=0; printf(请输入表长:n); scanf(%d,&i); printf(请输入数值:n); if(i0) for(L-last=1; L-lastlast+) scanf(%d, & L- dataL-last); L-last-; return (L); /单链表的建立void zhe_ban(Sequenlist *L) /折半插入 int i,j,low,high,mid; for(i=1; ilast; i+)L