数据结构课程设计报告(共30页).doc

精选优质文档-倾情为你奉上数据结构课程设计报告 专业：xxxxxxx 学号：xxxxxxxxx 姓名：xxxxxxxx 指导老师：xxxxxxxxx 日期：2011-12-29 目录一、 实验要求将整个系统采用菜单控制，一级菜单为各章的名称，二级菜单为每章的算法。整个系统应包括数据结构的典型算法30个以上。了解每个算法的设计思想，能够熟练的分析各个算法的执行过程。二、实验内容2.1实验一（线性表的顺序存储）掌握线性表的顺序存储结构；能熟练利用顺序存储结构实现线性表的基本操作；能熟练掌握线性表创建、插入、删除、查找和显示线性表中元素等基本操作。2.1.1实验一内容建立含有不少于3个元素的顺序表，并将结果在屏幕上输出；对刚建立的顺序表实现插入、删除、查找，并将结果在屏幕上输出；设计一个选择式菜单。2.1.2实验一算法描述#include "iostream.h"const int maxsize1=10; /maxlen表示线性表允许的最大长度#define elemtype1 intstruct sequenlist elemtype1 amaxsize1;/表示线性表（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) cout<<"overflow"<<endl;else if (i<1)|(i>L.len+1) cout<<"position is not correct!"<<endl;else for(j=L.len;j>=i;j-)L.aj+1=L.aj;/元素后移L.ai=x;/插入元素L.len+;/表长度增加/删除运算Delete(&L,i),线性表L中删除序号为i的数据元素void Delete(sequenlist &L,int i) int j; if(i<1)|(i>L.len) cout<<"tttt输入的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中首次出现的值为的那个元素的序号或地址，称为查找成功; 否则，在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(i<1)|(i>L.len) return NULL; else return L.ai;void print(sequenlist L) /打印线性表 int i; for (i=1;i<=L.len;i+) cout<<L.ai<<" " cout<<endl;void main1() sequenlist L; int i,j,k; elemtype1 x;setnull(L); cout<<"nn" cout<<"ttt 线性表子系统n"cout<<"tt*n"cout<<"tt* 1-插入元素*n"cout<<"tt* 2-删除元素*n"cout<<"tt* 3-查找数据*n"cout<<"tt* 4-显示线性表*n"cout<<"tt* 0-返回*n"cout<<"tt*n"do cout<<"tt 请选择菜单项04："cin>>k;switch(k) case 1: /在线性表第i位置处插入值为X的元素cout<<"n 请输入插入的位置i:"cin>>i;cout<<" 请输入数据X:"cin>>x;Insert(L,x,i);cout<<"插入后线性表的顺序存储为:"print(L); break;case 2: /删除线性表中值为X的元素 cout<<"n 请输入要删除元素的位置i:"cin>>i;cout<<"删除前线性表为:"print(L); Delete(L,i);cout<<"删除后线性表为:"print(L); break;case 3: /查找线性表中元素值为x的位置cout<<"n 请输入要查找的数值X:"cin>>x; cout<<"n线性表的顺序存储为："j=Locate(L,x) ;cout<<endl;if (j !=0 ) print(L);cout<<"线性表中值为X所在的位置是："<<j;elsecout<<"tt线性表中无此元素!n"cout<<endl;break;case 4: /输出线性表 cout<<"n线性表为：" print(L); while(k!=0);2.2实验二（线性表的链式存储）掌握线性表的链式存储结构；能熟练利用链式存储结构实现线性表的基本操作；能熟练掌握链式存储结构中算法的实现。2.2.1实验二内容用头插法或尾插法建立带头结点的单链表，并在屏幕上输出显示此链表；实现单链表上的插入、删除、修改、查找、计数等操作，并将结果在屏幕上输出；设计一个选择式菜单。2.2.2实验二算法描述#define elemtype int#include "iostream.h"#include "stdlib.h"class link public:elemtype data; link *next; void Insert(link *head,elemtype x1,elemtype y); void dele(link *head , elemtype x1); link *Locate(link *head,elemtype x1) ; link *hcreat(int x1) ; void print(link *h); ;/建立单链表link *link:hcreat(int n ) link *s,*p;int i;p=new link;p->next=NULL;for(i=1;i<=n;i+) s=new link; cin>>s->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=x1; if(head->next=NULL) /链表为空 head->next=s; s->next=NULL; p=Locate(head,y); /调用查找算法 if(p=NULL) cout<<"插入位置非法"<<endl; else s->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<<"要删除的结点不存在"<<endl; else q->next=p->next; delete(p);/打印单链表void link:print(link *h) link *p=h->next;while(p) cout<<p->data<<"->"p=p->next;cout<<"NULL"<<endl;void main2() link *head=new link; link *p=new link;int k; elemtype x1,y;cout<<"nnnn"cout<<"tt 单链表的子系统 n"cout<<"tt*n"cout<<"tt* 1查询元素 *n"cout<<"tt* 2删除元素 *n"cout<<"tt* 3插入元素 *n"cout<<"tt* 4打印链表 *n"cout<<"tt* 0返回主菜单 *n"cout<<"tt*n" cout<<"请输入链表元素："head=head->hcreat(5); do cout<<"请选择菜单项0-4: "cin>>k; switch(k)case 1:cout<<"请输入要查询的元素："cin>>x1; cout<<"元素所在的位置："<<p<<endl; head->Locate(head,x1);break;case 2:cout<<"请输入要删除的元素："cin>>x1; head->dele(head ,x1);break;case 3:cout<<"请输入插入新元素的位置："cin>>y; cout<<"请输入插入的新元素："cin>>x1; head->Insert(head,x1,y);break;case 4:cout<<"链表为："head->print(head);break;while(k);2.3实验三（栈的应用）掌握栈的数据类型描述及栈的特点；掌握栈的顺序和链式两种存储结构的特点及算法描述；掌握栈的5种基本运算及算法在两种不同存储结构上的实现。2.3.1实验三内容编写链式栈进栈、出栈、显示栈中全部元素的程序；将一个正整数n转换成R进制，要求用顺序栈的来实现；用switch语句设计一个选择式菜单，以菜单方式执行上述操作。2.3.2实验三算法描述#include "iostream.h"#include "stdlib.h"const int maxsize3=10000; /定义栈的最大容量为maxlentypedef int elemtype3; class seqstack public:elemtype3 stackmaxsize3; /将栈中元素定义为elemtype类型 int top; /指向栈顶位置的指针void inistack(seqstack &s); /将栈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 seqstack:push(seqstack &s, elemtype3 x) if (s.top=maxsize3-1) cout<<"overflow" else s.top+; s.stacks.top=x;/出栈算法void seqstack:pop(seqstack &s ) if (s.top=0) cout<<"underflow" else s.top-; /取栈顶元素算法elemtype3 seqstack:gettop(seqstack s ) if (s.top=0) cout<<"underflow"return 0;else return s.stacks.top;/判断栈空算法bool seqstack: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+)cout<<s.stacki<<" " cout<<endl;void main3() seqstack s;int k;bool t;elemtype3 x,y;s.inistack(s);cout<<"tt 顺序栈的操作 n"cout<<"tt*n" cout<<"tt* 1-进栈 *n"cout<<"tt* 2-出栈 *n"cout<<"tt* 3-取栈顶元素 *n"cout<<"tt* 4-判栈空 *n"cout<<"tt* 5-输出栈 *n"cout<<"tt* 0-退出 *n"cout<<"tt*n" docout<<"tt 请选择（0-5）："cin>>k;switch(k)case 1:cout<<"请输入进栈的值="cin>>x;s.push(s,x);break;case 2:s.pop(s);break;case 3:y=s.gettop(s);cout<<"栈顶的值="<<y<<endl;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实验四（队列的应用）掌握队列的数据类型描述及队列的特点；掌握队列的顺序和链式两种存储结构的特点及算法描述；掌握队列的5种基本运算及算法在两种不同存储结构上的实现。2.4.1实验四内容实现顺序循环或链式队列的进队列、出队列、判断队列空否、显示队列中全部元素的运算；设计一个选择式菜单，以菜单方式选择队列的各种操作。2.4.2实验四算法描述#include "iostream.h"#include "stdlib.h"const int maxsize4= 10; /定义队列的最大容量为maxlentypedef int elemtype4;class seqqueuepublic:elemtype4 queuemaxsize4; /将队列中元素定为数组型，元素类型为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 print4(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) cout<<"overflow" else Q.rear=(Q.rear+1)%maxsize4; Q.queueQ.rear=x;/出队列void seqqueue:DLQUEUE4(seqqueue &Q ) if (Q.rear=Q.front) cout<<"underflow" else Q.front =(Q.front+1)%maxsize4;/取队头元素elemtype4 seqqueue:GETHEAD4(seqqueue Q ) if (Q.rear=Q.front) cout<<"underflow"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(seqqueue Q) while(Q.front!=Q.rear)Q.front=(Q.front+1)%maxsize4; cout<<Q.queueQ.front<<" "cout<<endl;void main4() seqqueue Q;int t,k;elemtype4 x,y;Q.INIQUEUE4(Q);cout<<"nnnn"cout<<"tt 队列的子系统 n"cout<<"tt*n"cout<<"tt* 1进队列 *n"cout<<"tt* 2出队列 *n"cout<<"tt* 3取队头元素 *n"cout<<"tt* 4判队列空 *n" cout<<"tt* 5打印队列 *n"cout<<"tt* 0返回主菜单 *n"cout<<"tt*n" docout<<"请选择（0-5）："cin>>k;switch(k)case 1:cout<<"请输入进队列的值="cin>>x;Q.ENQUEUE4 (Q, x);break;case 2:Q.DLQUEUE4(Q);break;case 3:y=Q.GETHEAD4(Q);cout<<"队头的值="<<y<<endl;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实验五（二叉树的遍历和应用）掌握二叉树的数据类型描述及二叉树的特性；掌握二叉树的链式存储结构的建立算法；掌握二叉链表上二叉树的基本运算的实现。2.5.1实验五内容用递归或非递归的方法建立一棵二叉树；用递归实现二叉树的先序、中序、后序三种遍历；求二叉树的高度；设计一个选择式菜单，以菜单方式实现各种操作。2.5.2实验五算法描述#include<iostream.h>typedef char elemtype5;const int maxsize5=1024;struct bitreeelemtype5 data; /结点数据类型bitree *lchild,*rchild; /定义左、右孩子为指针型;bitree *create()bitree *T;elemtype5 x;cin>>x;if (x='0') T=NULL;else T=new bitree;T->data=x;cout<<" 请输入"<<T->data<<"结点的左孩子："T->lchild=create();cout<<" 请输入"<<T->data<<"结点的右孩子："T->rchild=create();return T;void preorder(bitree *root)/前根遍历二叉树的递归遍历算法 bitree *p;p=root;if(p!=NULL) cout<<p->data<<" " preorder(p->lchild); preorder (p->rchild);/中根遍历二叉树的递归遍历算法void inorder(bitree *root) bitree *p; p=root; if (p!=NULL) inorder(p->lchild); cout<<p->data<<" " inorder(p->rchild);/后根遍历二叉树的递归遍历算法void postorder( bitree *root) bitree *p;p=root;if (p!=NULL) postorder (p->lchild); postorder (p->rchild); cout<<p->data<<" "int treehigh(bitree *T) int lh,rh;if (T=NULL) return 0;elselh=treehigh(T->lchild );rh=treehigh(T->rchild );if (lh>rh) return lh+1;else return rh+1;void lorder (bitree * t)/按层次遍历一棵二叉树 bitree *qmaxsize5,*p; / maxsize5为最大容量 int f,r; / f,r类似于头尾指针q1=t; f=r=1;while (f<=r) p=qf; f+; /出队 cout<<p->data<<" " if(p ->lchild!=NULL) r+; qr=p->lchild; /入队 if (p->rchild!=NULL) r+; qr=p->rchild; /入队void main5() bitree *T;int k; cout<<"nnnn" cout<<"ttt 树的子系统n"cout<<"tt*n"cout<<"tt* 1-建二叉树 *n"cout<<"tt* 2-前序遍历 *n"cout<<"tt* 3-中序遍历 *n"cout<<"tt* 4-后序遍历 *n"cout<<"tt* 5-求树高度 *n"cout<<"tt* 6-层次遍历 *n"cout<<"tt* 0-返回 *n"cout<<"tt*n"do cout<<"tt 请选择菜单项05："cin>>k;if (k=1)cout<<"n 请输入此树的根结点:"T=create(); cout<<endl; /建立二叉树 else if (k=2) cout<<"n 此树前序遍历的顺序:"preorder(T);cout<<endl;else if (k=3)cout<<("n 此树中序遍历的顺序:");inorder(T);cout<<endl;else if (k=4) cout<<"n 此树后序遍历的顺序:"postorder(T);cout<<endl;else if (k=5) /树的高度 int h=treehigh(T); cout<<"n此树的高度是："<<h; cout<<endl; else if (k=6) /按层次遍历一棵二叉树 cout<<"n 此树层次遍历的顺序:"lorder (T);cout<<endl; else if (k=0) break;while(k!=0);2.6实验六（图的邻接矩阵和遍历）掌握图的基本概念和邻接矩阵的存储结构；掌握图的邻接矩阵存储结构的算法实现；掌握图在邻接矩阵存储结构上遍历算法的实现。2.6.1实验六内容对给定的图，建立图的邻接矩阵；实现该图的深度优先搜索遍历；实现该图的广度优先搜索遍历；设计一个选择式菜单，以菜单方式实现各种操作。2.6.2实验六算法描述#include<iostream.h>#include"iomanip.h"typedef int elemtype6;const 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;cout<<"输入"<<e<<"条无向边n"for (k=1; k<=e; k+)cout<<"输入"<<k<<"条无向边的顶点对："cin>>i>>j; /输入一条边(i,j) g.arcsij=1;g.arcsji=1;void dfs (int i) / 从顶点i 出发深度遍历int j; cout<<g.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 ; /设置空队列cout<<g.vi<<" " / 输出访问顶点visitedi=1 ; /全局数组标记置1表示已经访问r+; qr=i ; /入队列wh