1、数据结构课程设计报告题目： 一、图子系统 二、查找子系统 1一、课程设计的目的 1二、课程设计的内容和要求 2三、题目一设计过程 2四、题目二设计过程 8五、设计总结 16六、参考文献 16题目： 一、图子系统 二、查找子系统一、课程设计的目的本学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握数据结构中的各方面知识，还要求学生具备一定的C语言基础和编程能力。（1）题目一的目的： 1、掌握土邻接表的存储方法 2、掌握图深度优先遍历的基本思想 3、掌握图广表度优先遍历的
2、基本思想（2）题目二的目的： 1、理解查找的基本算法 2、掌握静态查找和动态查找的区别3、掌握顺序查找和二叉排序树的基本思想及其算法二、课程设计的内容和要求（1）题目一的内容和要求：1、对任意给定的图（顶点数和边数自定），建立它的邻接表并输出。 2、编写图的深度优先遍历程序。 3、利用队列的基本运算实现广度优先遍历。（2）题目二的内容和要求：1、 设计一个选择式菜单。查找子系统* 1.顺序查找 * 2.二叉排序树 * 3.返回 * *请选择菜单号（02） 2、分别实现顺序查找和二叉排序树。 3、二叉排序树必须实现构建、查找、插入的基本操作。三、题目一设计过程1、题目分析对图的每个顶点建立一个带
3、头结点的线性链表，用于存储图中于顶点相邻接的边或弧的信息。头结点中存放该结点的信息。所有头结点用一个顺序表存放，对图进行深度优先遍历和广度优先遍历。2、算法描述void CreateUDN(Graph &G)任意建立一个图void DFS(Graph G,int k)从图的某一点k出发，进行深度优先遍历算法 void BFS(Graph G,int k)从图的某一点k出发，进行广度优先遍历算法3、源代码#include #include #define INFINITY 32767#define MAX_VEX 20 #define QUEUE_SIZE (MAX_VEX+1) using n
4、amespace std;bool *visited; typedef struct char *vexs; int arcsMAX_VEXMAX_VEX; int vexnum,arcnum; Graph;class Queue public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(fro
5、nt+1)%QUEUE_SIZE; public: int *base; int front; int rear;int Locate(Graph G,char c) for(int i=0;iG.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(输入顶点数和弧数:); scanf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); G.vexs=(char *)malloc(G.vexnum*
6、sizeof(char); printf(输入%d个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) printf(输入顶点%d:,i); scanf(%c,&G.vexsi); temp=getchar(); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(输入%d条弧.n,G.arcnum); for(i=0;i=0 & kG.vexnum) for(int i=0;i=0 & i=0 & jG.vexnum) for(int k=j+1;kG.vexnum;k+) if(
7、G.arcsik!=INFINITY) return k; return -1;void DFS(Graph G,int k) int i; if(k=-1) for(i=0;i=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); void BFS(Graph G) int k; Queue Q; Q.InitQueue(); for(int i=0;i=0;w=NextVex(G,k,w) if(!visitedw) visitedw=true; printf(%c ,G.vexsw); Q.EnQueue(w); void main() int i; Gr
8、aph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); printf(n广度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; DFS(G,-1); printf(n深度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; BFS(G); printf(n程序结束.n);4、运行结果通过输入图的顶点数、弧数可以得到图的深度优先遍历序列和广度优先遍历序列，如下图所示。四、题目二设计过程1、题目分析顺序查找是从线性表的一端开始，顺序扫描线性
9、表，依次将扫描到的关键字于给定值x相比较，若相等则查找成功；若扫描结束后，仍未找到与关键字x相等的结点，则查找失败。对于二叉排序树，从根结点出发，当访问树中某个结点时，如果访问的关键字值等于给定的关键字值就访问成功。反之，如果关键字值大或小于已给定的关键字值则考虑查找左或右子树。2、算法描述void SequenceSearch()顺序查找BSTree CreateBST(void)建立二叉树void InsBST(BSTree *T,KeyType Key)在二叉树中插入数据void BSTSearch()查询二叉树数据3、源代码#include#include #include #defi
10、ne LENGTH 20#define N 10void SequenceSearch()int aN,i,x,y;printf(ntt建立一个整数的顺序表(回车间隔,-1结束):n);for(i=0;i=0&ai!=x)i-;if(i=-1) printf(未能查找到数据%d.n); else printf(经过%d次查找，查找到数据%d.n,i+1,x); return ; typedef int KeyType;typedef struct node KeyType Key;struct node *lchild,*rchild;BSTNode; typedef BSTNode *BST
11、ree; BSTree CreateBST(void); void SearchBST(BSTree T,KeyType Key); void InsBST(BSTree *Tptr,KeyType Key);void BSTSearch() BSTree T; char ch1,ch2; KeyType Key;printf(建立一棵二叉树:n);T=CreateBST();ch1=y;getchar();while(ch1=y|ch2=Y)printf(n);printf(ntt*);printf(ntt* 1-更新二叉排序树- *);printf(ntt* 2-查找结点- *);prin
12、tf(ntt* 3-插入结点- *);printf(ntt* 0-返回- *);printf(ntt*ntt);scanf( %c,&ch2);getchar();switch(ch2) case1:T=CreateBST();break; case2:printf(ntt请输入要查找的数据:); scanf(%d,&Key); getchar(); SearchBST(T,Key);break; case3:printf(ntt请输入要插入的数据:);scanf(%d,&Key); getchar();InsBST(&T,Key);break; case0:ch2=n;return; def
13、ault:printf(输入错误,请重新输入!n); BSTree CreateBST(void)BSTree T;KeyType Key;T=NULL;printf(ntt请输入一个关键字（输入0时结束）:);scanf(%d,&Key);while(Key)InsBST(&T,Key);printf(ntt请输入一个关键字（输入0时结束）:);scanf(%d,&Key);return T;void SearchBST(BSTree T,KeyType Key)BSTNode *p=T;while(p)if(p-Key=Key)printf(ntt已经找到你输入的数据.);return;p
14、=(KeyKey)?p-lchild:p-rchild;printf(ntt没有找到你输入的数据.);void InsBST(BSTree *T,KeyType Key) BSTNode *f,*p;p=(*T);while(p)if(p-Key=Key) printf(ntt树中已有%d,不需插入.n,Key);return;f=p;p=(KeyKey)?p-lchild:p-rchild;p=new BSTNode;p-Key=Key;p-lchild=p-rchild=NULL;if(*T)=NULL)(*T)=p;elseif(KeyKey)f-lchild=p;elsef-rchil
15、d=p;main() int choise; char ch=y;while(ch=y|ch=Y) printf(ntt*);printf(ntt* 1-顺序查找-*);printf(ntt* 2-二叉排序树-*);printf(ntt* 0-返回-*);printf(ntt*ntt); scanf(%d,&choise); switch(choise) case 1:SequenceSearch();break; case 2:BSTSearch();break; case 0:ch=n;break; default:printf(输入错误,请重新输入!n);4、运行结果 五、设计总结开始的时候总是很头疼，为了这次的课程设计，我泡了很多天的图书馆和机房，查阅了大量的资料书籍，并对数据结构课本知识点进行了系统的复习，巩固了基础，但是还是遇到了一些困难。直到最后快要答辩的时候彻底的吧程序搞懂了，往往都是这样当工作快接近尾声的时候才有一种焕然一新的感觉！六、参考文献1.杨路明.C语言程序设计教程.北京邮电大学出版社
