数据结构课程设计是什么
.需求分析
1.运行环境
硬件：计算机486/64M以上
操作系统： WIN9x 以上/WIN2000/WIN XP/WIN ME
相关软件：vistualC++
2．程序所实现的功能：
（1）建立并显示图的邻接表。
（2）深度优先遍历，显示遍历结果。
（3）对该图进行拓扑排序，显示排序结果。
（4）给出某一确定顶点到所有其它顶点的最短路径。
3.程序的输入，包含输入的数据格式和说明
(1)输入顶点数,及各顶点信息(数据格式为整形)
(2)输入边数,及权值(数据格式为整形)
4.程序的输出，程序输出的形式
(1)输出图的邻接表、深度优先遍历结果、拓扑排序结果。
(2)输入某一确定顶点到其它所有顶点的最短路径。
5.测试数据
二、设计说明
1、 算法设计的思想
建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。
2、 主要的数据结构设计说明
图邻接矩阵、邻接表的建立。图的深度优先遍历、拓扑排序、顶点之间的最短路径。
3、 程序的主要模板template <class Type>class Graph
4、 程序的主要函数
Graph、link()、DFTraverse()、TopologicalOrder()、
TopologicalOrder()、GetVertexPos()、ShortestPath
三、上机结果及体会
1、 实际完成的情况说明
主要程序参考教材《数据结构——C++版》。
2、 程序的性能分析
可连续建图
3、 上机过程中出现的问题及其解决方案。
编译没有错误，但结果有问题。解决方案：虽然程序的编译通过，只能说明语法上没有问题，结果只所以不正确是因为算法上原因。
4、 程序中可以改进的地方说明
程序中的深度优先遍历，浪费空间较大，可以考虑用循环来做。但这样将付出代码长度度加长的代价。
5、 程序中可以扩充的功能及设计实现假想
实现假想：随用户的输入可以随时动态的显示图的生成。
6、 收获及体会
编写程序即是一件艰苦的工作，又是一件愉快的事情。最大的收获：编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析。要勇敢的面对问题，勇敢的接受问题，勇敢的处理问题，最后最勇敢的解决问题。
四、参考文献
数据结构（C++版） 叶核亚 主编 机械工业出版社
数据结构经典算法实现与习题解答 汪杰 编著 人民邮电出版社
数据结构课程设计 苏仕华 编著 机械工业出版社
数据结构程序设计题典 李春葆 编著 清华大学出版社
数据结构课程与题解（用C/C++描述） 胡圣荣 编著 北京大学出版社
[程序运行流程图]
char op //程序控制变量
一 需求分析：
在该部分中根据设计题目的要求，充分地分析和理解问题，叙述系统的功能要求，明确问题要求做什么？以及限制条件是什么？
1．1问题描述
1．2基本要求
(1) 输入的形式和输入值的范围；
(2) 输出的形式；
(3) 程序所能达到的功能；
二 概要设计
说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。
1、 数据结构
2、 程序模块
3、各模块之间的调用关系以及算法设计
三 详细设计
实现概要设计中定义的所有数据类型,对每个操作写出伪码算法对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)写出出函数和过程的调用关系.
四 测试与分析
测试数据，输出测试的结果，这里的测试数据应该完整和严格。并对结果进行分析。
五 总结
总结可以包括 : 课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。
#include<stdlib.h>
#include <math.h>
#define L 8 //排序元素个数
#define FALSE 0
#define TRUE 1
typedef struct
{
int key
char otherinfo
}RecType
typedef RecType Seqlist[L+1]
int num//定义排序趟数的全局变量
Seqlist R
//直接插入排序
void Insertsort()
{
int i,j,k,m=0
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t")
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
for(i=2i<=Li++)
{
if(R[i].key<R[i-1].key)
{
R[0]=R[i]
j=i-1
while(R[0].key<R[j].key)
{
R[j+1]=R[j]
j--
}
R[j+1]=R[0]
}
m++
printf("\t\t第%d趟排序结果为（按回车键继续）：\n\t\t",m)
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
}
printf("\n\t\t排序的最终结果是：\n\t\t")
for(i=1i<=Li++)
{
printf("%5d",R[i].key)
}
printf("\n")
}
//希尔排序
void Shellsort()
{
int i,j,gap,x,m=0,k
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t")
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
gap=L/2
while(gap>0)
{
for(i=gap+1i<=Li++)
{
j=i-gap
while(j>0)
{
if(R[j].key>R[j+gap].key)
{
x=R[j].key
R[j].key=R[j+gap].key
R[j+gap].key=x
j=j-gap
}
else
{
j=0
}
}
}
gap=gap/2
m++
printf("\t\t第%d趟排序结果为（按回车键开始排序）：\n\t\t",m)
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
}
printf("\n\t\t排序的最终结果是：\n\t\t")
for(i=1i<=Li++)
{
printf("%5d",R[i].key)
}
printf("\n")
}
//冒泡排序
void Bubblesort()
{
int i,j,k
int exchange
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t")
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
for(i=1i<Li++)
{
exchange=FALSE
for(j=Lj>=i+1j--)
{
if(R[j].key<R[j-1].key)
{
R[0].key=R[j].key
R[j].key=R[j-1].key
R[j-1].key=R[0].key
exchange=TRUE
}
}
if(exchange)
{
printf("\t\t第%d趟排序结果为（按回车键开始排序）：\n\t\t",i)
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
}
}
printf("\n\t\t排序的最终结果是：\n\t\t")
for(i=1i<=Li++)
{
printf("%5d",R[i].key)
}
printf("\n")
}
int Partition(int i,int j) //i和j为形式参数，分别代表low和high
{
RecType pirot=R[i]
while(i<j)
{
while(i<j&&R[j].key>=pirot.key)
{
j--
}
if(i<j)
{
R[i++]=R[j]
}
while(i<j&&R[j].key<=pirot.key)
{
i++
}
if(i<j)
{
R[j--]=R[i]
}
}
R[i]=pirot
return i
}
//递归形式为快速排序
void Quicksort(int low,int high)
{
int pirotpos,k
if(low<high)
{
pirotpos=Partition(low,high)
num++
printf("\t\t第%d趟排序结果为（按回车键开始排序）：\n\t\t",num)
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
Quicksort(low,pirotpos-1)
Quicksort(pirotpos+1,high)
}
}
//选择排序
void Selectsort()
{
int i,j,k,h
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t")
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
for(i=1i<Li++)
{
h=i
for(j=i+1j<=Lj++)
{
if(R[j].key<R[h].key)
{
h=j
}
}
if(h!=j)
{
R[0]=R[i]
R[i]=R[h]
R[h]=R[0]
}
printf("\t\t第%d趟排序结果为（按回车键开始排序）：\n\t\t",i)
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
}
printf("\n\t\t排序的最终结果是：\n\t\t")
for(i=1i<=Li++)
{
printf("%5d",R[i].key)
}
printf("\n")
}
void Merge(int low,int mm,int high)
{
int i=low,j=mm+1,p=0
RecType *R1
R1=new RecType[high-low+1]
if(!R1)
{
printf("内存容量不够！")
}
while(i<=mm&&j<=high)
{
R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++]
}
while(i<=mm)
{
R1[p++]=R[i++]
}
while(j<=high)
{
R1[p++]=R[j++]
}
for(p=0,i=lowi<=highp++,i++)
{
R[i]=R1[p]
}
}
void MergePass(int length)
{
int i
for(i=1i+2*length-1<=Li=i+2*length)
{
Merge(i,i+length-1,i+2*length-1)
}
if(i+length-1<L)
{
Merge(i,i+length-1,L)
}
}
//归并排序
void Mergesort()
{
int length,k,m=0,i
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t")
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
for(length=1length<Llength*=2)
{
MergePass(length)
m++
printf("\t\t第%d趟排序结果为（按回车键开始排序）：\n\t\t",m)
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
}
printf("\n\t\t排序的最终结果是：\n\t\t")
for(i=1i<=Li++)
{
printf("%5d",R[i].key)
}
printf("\n")
}
//堆建
void CreateHeap(int root,int index)
{
int j,temp,finish
j=2*root
temp=R[root].key
finish=0
while(j<=index&&finish==0)
{
if(j<index)
{
if(R[j].key<R[j+1].key)
{
j++
}
}
if(temp>=R[j].key)
{
finish=1
}
else
{
R[j/2].key=R[j].key
j=j*2
}
}
R[j/2].key=temp
}//堆排序
void Heapsort()
{
int i,j,temp,k
for(i=(L/2)i>=1i--)
{
CreateHeap(i,L)
}
for(i=L-1,k=1i>=1i--,k++)
{
temp=R[i+1].key
R[i+1].key=R[1].key
R[1].key=temp
CreateHeap(1,i)
printf("\t\t第%d趟排序结果为（按回车键开始排序）：\n\t\t",k)
for(j=1j<=Lj++)
{
printf("%5d",R[j].key)
}
getchar()
printf("\n")
}
}
void Heap()
{
int i
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t")
for(i=1i<=Li++)
{
printf("%5d",R[i].key)
}
getchar()
printf("\n")
Heapsort()
printf("\n\t\t排序的最终结果是：\n\t\t")
for(i=1i<=Li++)
{
printf("%5d",R[i].key)
}
printf("\n")
}
main()
{
Seqlist S
int i,k
char ch1,ch2,q
printf("\n\t\t1000个随机数产生：\n\t\t")
for(i=1i<=1000i++)
{
S[i].key = rand() % 999 + 1 //产生1-1000的随机数
//printf("%d\n", number)// 去掉注释显示随机数的输出}
printf("\n\t\t排序数据已经输入完毕！")
ch1='y'
while(ch1=='y'||ch1=='Y')
{
printf("\n")
printf("\n\t\t 排 序 子 系 统 \n")
printf("\n\t\t*******************************************\n")
printf("\n\t\t* 1--------更新排序数据 *\n")
printf("\n\t\t* 2--------直接插入排序 *\n")
printf("\n\t\t* 3--------希 尔 排 序 *\n")
printf("\n\t\t* 4--------冒 泡 排 序 *\n")
printf("\n\t\t* 5--------快 速 排 序 *\n")
printf("\n\t\t* 6--------选 择 排 序 *\n")
printf("\n\t\t* 7--------归 并 排 序 *\n")
printf("\n\t\t* 8--------堆 排 序 *\n")
printf("\n\t\t* 0--------返 回 *\n")
printf("\n\t\t*******************************************\n")
printf("\n\t\t 请选择菜单号（0--8）：")
scanf("%c",&ch2)
getchar()
for(i=1i<=Li++)
{
R[i].key=S[i].key
}
switch(ch2)
{
case '1':
printf("\n\t\t请输入%d个待排序数据（按回车键分隔）：\n\t\t",L)
for(i=1i<=Li++)
{
scanf("%d",&S[i].key)
getchar()
printf("\t\t")
}
printf("\n\t\t排序数据已经输入完毕！")
break
case '2':
Insertsort()
break
case '3':
Shellsort()
break
case '4':
Bubblesort()
break
case '5':
printf("\n\t\t原始数据为（按回车键开始排序）：\n\t\t")
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
getchar()
printf("\n")
num=0
Quicksort(1,L)
printf("\n\t\t排序的最终结果是：\n\t\t")
for(k=1k<=Lk++)
{
printf("%5d",R[k].key)
}
printf("\n")
break
case '6':
Selectsort()
break
case '7':
Mergesort()
break
case '8':
Heap()
break
case '0':
ch1='n'
break
default:
system("cls")
printf("\n\t\t 对不起，您的输入有误，请重新输入！\n")
break
}
if(ch2!='0')
{
if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')
{
printf("\n\n\t\t排序输出完毕！")
printf("\n\t\t按回车键返回。")
q=getchar()
if(q!='\xA')
{
getchar()
ch1='n'
}
}
}
}
}
为栈顶。基本操作：Push(&s,e)
初始条件：栈s已经存在。
操作结果：插入元素e为新的栈顶元素
Pop(&s,&e)
初始条件：栈s已经存在且非空。
操作结果：删除s的栈顶元素，并用e返回其值
