《数据结构课程设计》课程设计报告.doc

上海应用技术学院课程设计报告
课程名称《数据结构课程设计》
设计题目数据结构课程设计(多道)
院系计算机科学与信息学院专业网络工程班级
姓名学号指导教师甘苹日期 2014-7-7~2014-7-11
目的与要求
巩固和加深对常见数据结构的理解和掌握
掌握基于数据结构进行算法设计的基本方法
掌握用高级语言实现算法的基本技能
掌握书写程序设计说明文档的能力
提高运用数据结构知识及高级语言解决非数值实际问题的能力
课程设计内容说明
项目一:有序表合并
对设计任务内容的概述
要求输入有序表的数据,利用顺序表和链表结构分别完成两个有序表合并功能,并输出合并后的信息。
需求分析或功能描述
分别设计顺序表和链表的合并功能,主界面供选择有序表的类型,选择后对两个有序表进行合并。函数是静态数据读取,顺序表读取有序的数组数据直接合并输出,单链表是对无序的集合排序后合并输出。
概要设计或程序流程图
开始
选择有序表类型
顺序表合并
链表合并
0、退出
创建顺序表
创建链表
输出顺序表
输出链表

程序的输入与输出描述
函数是静态数据读取,顺序表书有序表直接合并输出,单链表是对集合排序后合并输出。
数据结构
#define datatype int
/*定义数据结构*/
//顺序存储类型
typedef struct {
datatype data[MAXSIZE];
int length;
} SqList ;
/*定义数据结构*/
//单链表存储结构
typedef struct Lnode{
datatype data;
struct Lnode *next;
}LinkList ;
程序模块及其接口描述
程序包括以下几个模块:
建立
排序
输出
合并
Main函数
顺序表
CreateList
DispList1
squnion
单链表
CreateListR
Sort
DispList2
linkunion
详细设计或源代码说明
//list1:有序表合并
1)预处理与头文件
#include<>
#include<>
#include <>
#include <>
//建立顺序表
void CreateList(SqList *&L,datatype a[],int n)
{ int i;
L=(SqList*)malloc(sizeof(SqList));
for(i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
2)//建立单链表
void CreateListR(LinkList *&L,datatype a[],int n)
{ LinkList * s,*r;int i;
L=(LinkList*)malloc(sizeof(LinkList));
L->next=NULL;
r=L;
for(i=0;i<n;i++)
{s=(LinkList*)malloc(sizeof(LinkList));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
3)//单链表递增排序
void Sort(LinkList *&L) //单链表元素递增排序
{
LinkList *p,*pre,*q;
p=L->next->next; //p指向L的第2个数据节点
L->next->next=NULL; //构造只含一个数据结点的有序表
while (p!=NULL)
{
q=p->next; //q保存*p结点后继结点的指针
pre=L; //从有序表开头进行比较,pre指向插入*p的前驱结点
while (pre->next!=NULL && pre->next->data<p->data) //在有序表中找插入*p的前驱结点*pre
pre=pre->next;
p->next=pre->next; //将*pre插入到*p之后
pre->next=p;
p=q; //扫描原链表余下的节点
}
}
4)//输出顺序表
void DispList1(SqList *L) //输出线性表
{
int i;
//if (Listdatatype(L)) return;
for (i=0;i<L->length;i++)
printf("%d ",L->data[i]);
printf(