数据结构课程设计报告

1、数据结构课程设计报告 专业：xxxxxxx 学号：xxxxxxxxx 姓名：xxxxxxxx 指导老师：xxxxxxxxx 日期：2011-12-29 目录一、实验要求3二、实验内容32.1实验一（线性表的顺序存储）32.1.1实验一内容32.1.2实验一算法描述32.2实验二（线性表的链式存储）62.2.1实验二内容62.2.2实验二算法描述62.3实验三（栈的应用）92.3.1实验三内容92.3.2实验三算法描述92.4实验四（队列的应用）112.4.1实验四内容112.4.2实验四算法描述122.5实验五（二叉树的遍历和应用）142.5.1实验五内容142.5.2实验五算法描述152.6

2、实验六（图的邻接矩阵和遍历）162.6.1实验六内容172.6.2实验六算法描述172.7实验七（图的邻接表和遍历）192.7.1实验七的内容192.7.2实验七算法描述202.8实验八（查找）222.8.1实验八内容222.8.2实验八算法描述232.9实验九（排序）252.9.1实验九内容252.9.2实验九算法描述252.10实验十（综合应用）282.10.1实验十内容282.10.2实验十算法描述28二、实验总结29一、 实验要求将整个系统采用菜单控制，一级菜单为各章的名称，二级菜单为每章的算法。整个系统应包括数据结构的典型算法30个以上。了解每个算法的设计思想，能够熟练的分析各个算法

3、的执行过程。二、实验内容2.1实验一（线性表的顺序存储）掌握线性表的顺序存储结构；能熟练利用顺序存储结构实现线性表的基本操作；能熟练掌握线性表创建、插入、删除、查找和显示线性表中元素等基本操作。2.1.1实验一内容建立含有不少于3个元素的顺序表，并将结果在屏幕上输出；对刚建立的顺序表实现插入、删除、查找，并将结果在屏幕上输出；设计一个选择式菜单。2.1.2实验一算法描述#include iostream.hconst int maxsize1=10; /maxlen表示线性表允许的最大长度#define elemtype1 intstruct sequenlist elemtype1 amax

4、size1;/表示线性表（a1，a2，.,an）int len;/len表示线性表的实际长度 ;int length(sequenlist L)/求顺序表的长度length(L) return L.len;/插入运算Insert(&L,x,i), 线性表L的第 i 个位置上插入一个值为 x 的新元素void Insert(sequenlist &L,elemtype1 x,int i) int j;if(L.len=maxsize1-1) coutoverflowendl;else if (iL.len+1) coutposition is not correct!=i;j-)L.aj+1=L

5、.aj;/元素后移L.ai=x;/插入元素L.len+;/表长度增加/删除运算Delete(&L,i),线性表L中删除序号为i的数据元素void Delete(sequenlist &L,int i) int j; if(iL.len) couttttt输入的i不合法!endl; else for(j=i+1;j=L.len;j+) L.aj-1=L.aj;/元素前移 L.len-;/表长度减1 void setnull(sequenlist &L) /置空表setnull(&L) L.len=0;/*定位算法Locate(L,x),表L中查找值为的数据元素，其结果返回在L中首次出现的值为的那

6、个元素的序号或地址，称为查找成功; 否则，在L中未找到值为的数据元素，返回一特殊值表示查找失败。 */int Locate(sequenlist L, elemtype1 x) int j=1; while(j=L.len)&(L.aj!=x) j+; if(j=L.len) return j; else return 0;/取元素Get(L,i),返回线性表L中序号为i的数据值elemtype1 Get(sequenlist L,int i) if(iL.len) return NULL; else return L.ai;void print(sequenlist L) /打印线性表 in

7、t i; for (i=1;i=L.len;i+) coutL.ai ; coutendl;void main1() sequenlist L; int i,j,k; elemtype1 x;setnull(L); coutnn; coutttt 线性表子系统n;couttt*n;couttt* 1-插入元素*n;couttt* 2-删除元素*n;couttt* 3-查找数据*n;couttt* 4-显示线性表*n;couttt* 0-返回*n;couttt*n;do coutk;switch(k) case 1: /在线性表第i位置处插入值为X的元素couti;coutx;Insert(L,

8、x,i);cout插入后线性表的顺序存储为:;print(L); break;case 2: /删除线性表中值为X的元素 couti;cout删除前线性表为:;print(L); Delete(L,i);cout删除后线性表为:;print(L); break;case 3: /查找线性表中元素值为x的位置coutx; coutn线性表的顺序存储为：;j=Locate(L,x) ;coutendl;if (j !=0 ) print(L);cout线性表中值为X所在的位置是：j;elsecouttt线性表中无此元素!n;coutendl;break;case 4: /输出线性表 coutnex

9、t=NULL;for(i=1;is-data; s-next=p-next; p-next=s;return p;/按值查询link *link:Locate(link *head , elemtype x1) link *p; p=head-next; while(p!=NULL)&(p-data!=x1) p=p-next; return p;/在头指针head所指带头结点的单链表中，在值为y的结点之后插入值为x1的结点void link:Insert(link *head , elemtype x1 , elemtype y) link *p,*s; s=new link; s-data

10、=x1; if(head-next=NULL) /链表为空 head-next=s; s-next=NULL; p=Locate(head,y); /调用查找算法 if(p=NULL) cout插入位置非法next=p-next; p-next=s; /删除值为x1的结点void link:dele(link *head , elemtype x1) link *p,*q; q=head; p=head-next; while(p!=NULL)&(p-data!=x1) q=p; p=p-next; if(p=NULL) cout要删除的结点不存在next=p-next; delete(p);

11、/打印单链表void link:print(link *h) link *p=h-next;while(p) coutdata;p=p-next;coutNULLendl;void main2() link *head=new link; link *p=new link;int k; elemtype x1,y;coutnnnn;couttt 单链表的子系统 n;couttt*n;couttt* 1查询元素 *n;couttt* 2删除元素 *n;couttt* 3插入元素 *n;couttt* 4打印链表 *n;couttt* 0返回主菜单 *n;couttt*n; couthcreat(

12、5); do coutk; switch(k)case 1:coutx1; cout元素所在的位置：pLocate(head,x1);break;case 2:coutx1; head-dele(head ,x1);break;case 3:couty; coutx1; head-Insert(head,x1,y);break;case 4:coutprint(head);break;while(k);2.3实验三（栈的应用）掌握栈的数据类型描述及栈的特点；掌握栈的顺序和链式两种存储结构的特点及算法描述；掌握栈的5种基本运算及算法在两种不同存储结构上的实现。2.3.1实验三内容编写链式栈进栈、

13、出栈、显示栈中全部元素的程序；将一个正整数n转换成R进制，要求用顺序栈的来实现；用switch语句设计一个选择式菜单，以菜单方式执行上述操作。2.3.2实验三算法描述#include iostream.h#include stdlib.hconst int maxsize3=10000; /定义栈的最大容量为maxlentypedef int elemtype3; class seqstack public:elemtype3 stackmaxsize3; /将栈中元素定义为elemtype类型 int top; /指向栈顶位置的指针void inistack(seqstack &s); /将

14、栈s置为一个空栈（不含任何元素）void push(seqstack &s , elemtype3 x) ; /将元素x插入到栈s中，也称为“入栈”、“插入”、“压入”void pop(seqstack &s) ; /删除栈s中的栈顶元素，也称为“退栈”、“删除”、“弹出”elemtype3 gettop(seqstack s) ; /取栈s中栈的顶元素bool empty(seqstack s) ; /判栈s是否为空void print(seqstack s);/初始化栈算法void seqstack:inistack(seqstack &s ) s.top=0; /进栈算法void seq

15、stack:push(seqstack &s, elemtype3 x) if (s.top=maxsize3-1) coutoverflow; else s.top+; s.stacks.top=x;/出栈算法void seqstack:pop(seqstack &s ) if (s.top=0) coutunderflow; else s.top-; /取栈顶元素算法elemtype3 seqstack:gettop(seqstack s ) if (s.top=0) coutunderflow;return 0;else return s.stacks.top;/判断栈空算法bool s

16、eqstack:empty(seqstack s) if (s.top=0) return 1;else return false ;/打印栈算法void seqstack:print(seqstack s) for(int i=1;i=s.top;i+)couts.stacki ; coutendl;void main3() seqstack s;int k;bool t;elemtype3 x,y;s.inistack(s);couttt 顺序栈的操作 n;couttt*n; couttt* 1-进栈 *n;couttt* 2-出栈 *n;couttt* 3-取栈顶元素 *n;couttt

17、* 4-判栈空 *n;couttt* 5-输出栈 *n;couttt* 0-退出 *n;couttt*n; docoutk;switch(k)case 1:coutx;s.push(s,x);break;case 2:s.pop(s);break;case 3:y=s.gettop(s);cout栈顶的值=yendl;break;case 4:t=s.empty(s); if(t) cout栈为空！n; else cout栈非空！n;break;case 5:cout栈中的结果是：;s.print(s);break;while(k!=0);2.4实验四（队列的应用）掌握队列的数据类型描述及队列

18、的特点；掌握队列的顺序和链式两种存储结构的特点及算法描述；掌握队列的5种基本运算及算法在两种不同存储结构上的实现。2.4.1实验四内容实现顺序循环或链式队列的进队列、出队列、判断队列空否、显示队列中全部元素的运算；设计一个选择式菜单，以菜单方式选择队列的各种操作。2.4.2实验四算法描述#include iostream.h#include stdlib.hconst int maxsize4= 10; /定义队列的最大容量为maxlentypedef int elemtype4;class seqqueuepublic:elemtype4 queuemaxsize4; /将队列中元素定为数组

19、型，元素类型为elemtype4int front; /队头指针int rear; /队尾指针void INIQUEUE4(seqqueue &Q);/将队列Q设置成一个空队列void ENQUEUE4(seqqueue &Q,elemtype4 x);/将元素X插入到队尾中，也称“进队”，“插入”void DLQUEUE4(seqqueue &Q);/将队列Q的队头元素删除，也称“退队”、“删除”elemtype4 GETHEAD4(seqqueue Q);/得到队列Q的队头元素之值bool EMPTY4(seqqueue Q);/判断队列Q是否为空，若为空返回真，否则返回假void pri

20、nt4(seqqueue Q );/初始化void seqqueue:INIQUEUE4(seqqueue &Q )Q.front=Q.rear=maxsize4-1; /进队列void seqqueue:ENQUEUE4 (seqqueue &Q, elemtype4 x) if (Q.rear+1)%maxsize4 = Q.front) coutoverflow; else Q.rear=(Q.rear+1)%maxsize4; Q.queueQ.rear=x;/出队列void seqqueue:DLQUEUE4(seqqueue &Q ) if (Q.rear=Q.front) cou

21、tunderflow; else Q.front =(Q.front+1)%maxsize4;/取队头元素elemtype4 seqqueue:GETHEAD4(seqqueue Q ) if (Q.rear=Q.front) coutunderflow;return NULL; else return Q.queue(Q.front+1)%maxsize4; /判队列空否bool seqqueue:EMPTY4(seqqueue Q ) if (Q.rear=Q.front) return true; else return false;/打印队列void seqqueue:print4(s

22、eqqueue Q) while(Q.front!=Q.rear)Q.front=(Q.front+1)%maxsize4; coutQ.queueQ.front ;coutendl;void main4() seqqueue Q;int t,k;elemtype4 x,y;Q.INIQUEUE4(Q);coutnnnn;couttt 队列的子系统 n;couttt*n;couttt* 1进队列 *n;couttt* 2出队列 *n;couttt* 3取队头元素 *n;couttt* 4判队列空 *n; couttt* 5打印队列 *n;couttt* 0返回主菜单 *n;couttt*n;

23、docoutk;switch(k)case 1:coutx;Q.ENQUEUE4 (Q, x);break;case 2:Q.DLQUEUE4(Q);break;case 3:y=Q.GETHEAD4(Q);cout队头的值=yendl;break;case 4:t=Q.EMPTY4(Q); if(t) cout队列为空！n; else cout队列非空！n;break;case 5:cout队列中的结果是：;Q.print4(Q);break;while(k);2.5实验五（二叉树的遍历和应用）掌握二叉树的数据类型描述及二叉树的特性；掌握二叉树的链式存储结构的建立算法；掌握二叉链表上二叉树的

24、基本运算的实现。2.5.1实验五内容用递归或非递归的方法建立一棵二叉树；用递归实现二叉树的先序、中序、后序三种遍历；求二叉树的高度；设计一个选择式菜单，以菜单方式实现各种操作。2.5.2实验五算法描述#includetypedef char elemtype5;const int maxsize5=1024;struct bitreeelemtype5 data; /结点数据类型bitree *lchild,*rchild; /定义左、右孩子为指针型;bitree *create()bitree *T;elemtype5 x;cinx;if (x=0) T=NULL;else T=new bi

25、tree;T-data=x;cout 请输入datalchild=create();cout 请输入datarchild=create();return T;void preorder(bitree *root)/前根遍历二叉树的递归遍历算法 bitree *p;p=root;if(p!=NULL) coutdatalchild); preorder (p-rchild);/中根遍历二叉树的递归遍历算法void inorder(bitree *root) bitree *p; p=root; if (p!=NULL) inorder(p-lchild); coutdatarchild);/后根

26、遍历二叉树的递归遍历算法void postorder( bitree *root) bitree *p;p=root;if (p!=NULL) postorder (p-lchild); postorder (p-rchild); coutdatalchild );rh=treehigh(T-rchild );if (lhrh) return lh+1;else return rh+1;void lorder (bitree * t)/按层次遍历一棵二叉树 bitree *qmaxsize5,*p; / maxsize5为最大容量 int f,r; / f,r类似于头尾指针q1=t; f=r=

27、1;while (f=r) p=qf; f+; /出队 coutdatalchild!=NULL) r+; qr=p-lchild; /入队 if (p-rchild!=NULL) r+; qr=p-rchild; /入队void main5() bitree *T;int k; coutnnnn; coutttt 树的子系统n;couttt*n;couttt* 1-建二叉树 *n;couttt* 2-前序遍历 *n;couttt* 3-中序遍历 *n;couttt* 4-后序遍历 *n;couttt* 5-求树高度 *n;couttt* 6-层次遍历 *n;couttt* 0-返回 *n;c

28、outtt*n;do coutk;if (k=1)coutn 请输入此树的根结点:;T=create(); coutendl; /建立二叉树 else if (k=2) coutn 此树前序遍历的顺序:;preorder(T);coutendl;else if (k=3)cout(n 此树中序遍历的顺序:);inorder(T);coutendl;else if (k=4) coutn 此树后序遍历的顺序:;postorder(T);coutendl;else if (k=5) /树的高度 int h=treehigh(T); coutn此树的高度是：h; coutendl; else if

29、(k=6) /按层次遍历一棵二叉树 coutn 此树层次遍历的顺序:;lorder (T);coutendl; else if (k=0) break;while(k!=0);2.6实验六（图的邻接矩阵和遍历）掌握图的基本概念和邻接矩阵的存储结构；掌握图的邻接矩阵存储结构的算法实现；掌握图在邻接矩阵存储结构上遍历算法的实现。2.6.1实验六内容对给定的图，建立图的邻接矩阵；实现该图的深度优先搜索遍历；实现该图的广度优先搜索遍历；设计一个选择式菜单，以菜单方式实现各种操作。2.6.2实验六算法描述#include#includeiomanip.htypedef int elemtype6;con

30、st int N=20; / 图中顶点数 const int E6=100 ; / 图中边数struct graphelemtype6vN+1; / 存放顶点信息v1,v2,.vn，不使用v0存储空间int arcsN+1N+1; / 邻接矩阵;struct graph g;int visitedN+1;int n1,e; /实际图的顶点数和边数void creatadj()/建立无向图的邻接矩阵 int i, j,k ;for (k=1; k=n1; k+)g.vk=k; /输入顶点信息 for (i=1; i=n1; i+ )for (j=1; j=n1; j+)g.arcsij=0;co

31、ut输入e条无向边n;for (k=1; k=e; k+)cout输入kij; /输入一条边(i,j) g.arcsij=1;g.arcsji=1;void dfs (int i) / 从顶点i 出发深度遍历int j; coutg.vi ; /输出访问顶点visitedi=1; /全局数组访问标记置1表示已经访问for(j=1; j=n1; j+)if (g.arcsi j=1)&(!visitedj) dfs(j); void bfs( int i) /从顶点i出发广度遍历int qN+1 ; /Q为队列int f,r,j ; / f,r分别为队列头，尾指针f=r=0 ; /设置空队列co

32、utg.vi ; / 输出访问顶点visitedi=1 ; /全局数组标记置1表示已经访问r+; qr=i ; /入队列while (fr) f+; i=qf ; /出队列for (j=1; j=n1; j+)if (g.arcsij=1)&(!visitedj)coutg.vj ;visitedj=1 ;r+; qr=j ; void print()int i,j;coutendl ;for (i=1; i=n1; i+) coutsetw(5)g.vi;coutendl;for (i=1; i=n1; i+) for (couti,j=1; j=n1;j+) coutsetw(5)g.ar

33、csij; coutendl;void main6() int i,k;coutnnnn;couttt 图的邻接矩阵子系统n;couttt*n;couttt* 1-更 新 图 *n;couttt* 2-深度遍历 *n;couttt* 3-广度遍历 *n;couttt* 0-返回 *n;couttt*n;do coutk;switch(k) case 1:coutn1;coute;creatadj();cout图的邻接矩阵如下n;print();break;case 2:for (i=0; i=n1; i+) /标志向量初始化visited i=0; coutn请输入从图的哪个顶点(1-n1i;

34、cout深度遍历的结果为：;dfs(i);coutendl;break;case 3:for (i=0; i=n1; i+) /标志向量初始化visited i=0; coutn请输入从图的哪个顶点(1-n1i;cout广度遍历的结果为：;bfs(i);coutendl;break; while (k!=0);2.7实验七（图的邻接表和遍历）掌握图的基本概念和邻接表的存储结构；掌握图的邻接表存储结构的算法实现；掌握图在邻接表存储结构上遍历算法的实现。2.7.1实验七的内容对给定的图，建立图的邻接表；实现该图的深度优先搜索遍历；实现该图的广度优先搜索遍历；设计一个选择式菜单，以菜单方式实现各种操

35、作。2.7.2实验七算法描述#includeiostream.htypedef int elemtype7;const int m =20; /表示图中最大顶点数const int E= 100; / 图中最大边数struct link7 /定义链表类型elemtype7 data ;link7 *next ;link7 am+1;int n7; /实际图的顶点数int e7; /实际图的边数int visited7m+1;void creatlink7( ) /建立无向的邻接表int i,j,k ; link7 *s ;for(i=1; i=n7;i+) /建立邻接表头结点 ai.data=i ; ai.next=NULL;cout输入e7条无向边n;for(k=1; k=e7;k+)cout输入kij ; /输入一条边 (i,j)s=new link7; /申请一个动态存储单元s-data=j ;s-next=ai.next;ai.next=s;s=new link7; s-data=i ;s-next=aj.next;aj.next=s;void dfsl(int i) /邻接表实现图的深度优先搜索link7 *p; coutai.datadata) dfsl(p-data);p=p-next;