青岛理工大学

数据结构课程设计报告

题目： 宿舍管理查询软件

院（系）： 计算机工程学院

学生姓名: 谢茂盛

班级： 网络121 学号: 201207131

起迄日期: 2014.07.07-2014.07.20

指导教师: 张艳

一、需求分析（所有大标题宋体加粗四号，下同）（小标题宋体加粗小四，下同）

1.问题描述：

以无歧义的陈述详细说明对自己所选题目的解释性描述，可以补充说明该设计中要做的具体任务。强调的是程序要做什么？

2.基本功能

要求分别列出该设计要实现的功能，（每个功能要尽量和概要设计中的模块函数对应起来）。

二、 概要设计

1.设计思路：

解决问题的思路概述，拟采用的算法的简介。

2.数据结构设计：

要求分别列出拟采用的数据结构及其定义，分为逻辑结构（线性？树状？图状？）和存储结构（顺序？链式？）。采用该结构的原因，如果有定义的抽象数据类型，可以列出其定义及各种操作。如下为抽象数据类型定义的模板。

定义程序中用到的抽象数据类型；

设计中所用到的数据结构或抽象数据类型的说明，以及在程序中的作用

抽象数据类型线性表的定义如下：

ADT List{

数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}

数据关系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,3,……，n}

基本操作：

Insert(&L,i,j)

初始条件：线性表L已存在，1≤i≤n+1。

操作结果：在L中第i个位置之前插入新的数据元素j,L的长度加1。

Del(&L,i,j)

初始条件：线性表L已存在，1≤i≤n。

操作结果：删除L的第i个数据元素,L的长度减1

Xg(&L,i,j)

初始条件：线性表L已存在。

操作结果：用新的输入数据项j代替原有的指定要修改的数据项i。

Search(&L,i,e)

初始条件：线性表L已存在。

操作结果：查找指定的某元素i，并将值赋给e,用e 输出。

}

3.软件结构设计：

按需求分析中的功能进行模块划分，建立模块的层次结构及调用关系。

三、 详细设计

实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、活动图进行描述，画

出函数和过程的调用关系图。

实现设计中主程序和其他子模块的算法，以流程图的形式表示，需画出函数和过程的调用关系图。

本小节内所有的图均要求用Visio或Word进行绘制，不允许用bmp或其他格式的图片。绘图内文字均采用宋体五号（如果图比较大，排版不好看的话，可以根据需要缩小字体），单倍行间距，段前段后均设置为0行。

1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；

2．主函数和其他函数的伪码算法；

3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。

4. 画出函数之间的调用关系图。

四、 调试分析

内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析。

1.实际完成的情况说明（完成的功能，支持的数据类型等）；

2.程序的性能分析，包括时空分析；

3.上机过程中出现的问题及其解决方案；

4.程序中可以改进的地方说明；

5.程序中可以扩充的功能及设计实现假想。

五、测试结果

列出你的测试结果，包括输入和输出。注意测试数据应该完整和严格，至少给出2组测试结果（含合法数据与非法数据）。

六、用户手册

说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行结果抓图。用户手册与开发过程无关，只与使用有关，必须是Step by Step的。

所有运行结果截图均要求有实际数据的内容，截图尺寸要求按页宽排版两张大小，且要求有每张图下面有规范的标题说明如何使用你编写的程序，详细列出每一步的操作步骤。

七、体会与自我评价

写出本设计的总结思考，收获心得体会，要求不少于600字，不得摘抄网上资料，只能参考。

正文（各标题除外），均采用宋体和Times New Roman字体，小四号字，1.25倍行距。

八、参考文献 （列出你参考的书，格式按照下面的例子来写） 例如：

[1]严蔚敏．数据结构(C语言)．清华大学出版社，2007

 

第二篇：数据结构课程设计报告撰写模板(参考)

目录

1需求分析 ............................................ 2

1.1 输入的形式和输入值的范围 ..................................................................................

1.2 输出的形式 ..........................................................................................................

1.3 程序所能达到的功能 ..........................................................................................

1.4 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果 .............................................................................................................................................

2概要设计 ............................................ 3

3详细设计 ............................................ 4

3.1 姓名（结构体数组）初始化………………………………………………………………………………

3.2 建立哈希表 ……………………………………………………………………………………………………….

3.2.1 用除留余数法构建哈希函数………………………………………………………………………………..

3.2.2 用伪随机探测再散列法处理冲突……………………………………………………………………….

4调试分析 .............................................. 10

5用户使用说明 ....................................... 11

6测试结果 ........................................... 12

7参考文献 ........................................... 13

1需求分析

以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：

1.1 输入的形式和输入值的范围；

1.2 输出的形式；

1.3 程序所能达到的功能；

1.4 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2概要设计（系统概要、基本功能要求）

说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间

的层次(调用)关系。

存储结构设计

typedef struct

{ char *py; //名字的拼音

int k;

}NAME;

typedef struct

{ char *py;

int k;

int si;

}HASH;

//拼音所对应的整数 //哈希表 //名字的拼音 //拼音所对应的整数 //查找长度

3详细设计（列出函数首部+注释）

例如：void show(listlink head) /*显示所有的信息*/

实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序

和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；可采用流程图 N – S 图或PAD图进行描述，画出函数和过程的调用关系图。

3.1 姓名（结构体数组）初始化

名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。

void InitNameList()

{ char *f;

int r,s0,i;

NameList[0].py="zengqinghui";

NameList[1].py="mayuelong";

NameList[2].py="chenzhicheng";

NameList[3].py="sunpeng";

NameList[4].py="wanghui";

NameList[5].py="liqingbo";

NameList[6].py="liujunpeng";

NameList[7].py="jiangquanlei";

NameList[8].py="xingzhengchuan";

NameList[9].py="luzhaoqian";

NameList[10].py="gaowenhu";

NameList[11].py="zhuhaoyin";

NameList[12].py="chenlili";

NameList[13].py="wuyunyun";

NameList[14].py="huangjuanxia";

NameList[15].py="wangyan";

NameList[16].py="zhoutao";

NameList[17].py="jiangzhenyu";

NameList[18].py="liuxiaolong";

NameList[19].py="wangziming";

NameList[20].py="fengjunbo";

NameList[21].py="lilei";

NameList[22].py="wangjia";

NameList[23].py="zhangjianguo";

NameList[24].py="zhuqingqing";

NameList[25].py="huangmin";

NameList[26].py="haoyuhan";

NameList[27].py="zhoutao";

NameList[28].py="zhujiang";

NameList[29].py="lixiaojun";

for(i=0;i<NAME_NO;i++)

{ s0=0;

f=NameList[i].py;

for(r=0;*(f+r)!='\0';r++) */将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/

s0=*(f+r)+s0;

NameL

ist[i].k=s0;

}

}

3.2 建立哈希表

3.2.1 用除留余数法构建哈希函数

3.2.2 用伪随机探测再散列法处理冲突

void CreateHashList()

{ int i;

for(i=0; i<HASH_LENGTH;i++)

{ HashList[i].py="";

HashList[i].k=0;

HashList[i].si=0;

}

for(i=0;i<HASH_LENGTH;i++)

{ int sum=0;

int adr=(NameList[i].k)%M; //哈希函数 int d=adr;

if(HashList[adr].si==0) //如果不冲突 { HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1;

}

else //冲突

{ do

{ d=(d+NameList[i].k%10+1)%M; //伪随机探测再散列法处理冲突 sum=sum+1; //查找次数加1

}while (HashList[d].k!=0);

HashList[d].k=NameList[i].k;

HashList[d].py=NameList[i].py;

HashList[d].si=sum+1;

}

3.3 查找哈希表

在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度

void FindList()

{ char name[20]={0}; } }

int s0=0,r,sum=1,adr,d;

printf("请输入姓名的拼音:");

scanf("%s",name);

for(r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)

s0+=name[r];

adr=s0%M; //使用哈希函数

d=adr;

if(HashList[adr].k==s0) //分3种情况进行判断

printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);

else if (HashList[adr].k==0)

printf("无此记录!");

else

{ int g=0;

do

{ d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突 sum=sum+1;

if(HashList[d].k==0)

{ printf("无此记录! ");

g=1;

}

if(HashList[d].k==s0)

{ printf("\n姓名:%s 关键字:%d 查找长度

为:%d",HashList[d].py,s0,sum);

g=1;

}

3.4 显示哈希表

显示哈希表的的格式：

\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n

void Display()

{ int i; } } }while(g==0);

float average=0;

printf("\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"); //显示的格式 for(i=0; i<50; i++)

{ printf("%d ",i);

printf("\t%d ",HashList[i].k);

printf("\t\t%d ",HashList[i].si);

printf("\t\t%d ",HashList[i].k%M);

printf("\t %s ",HashList[i].py);

printf("\n");

}

for(i=0;i<HASH_LENGTH;i++)

average+=HashList[i].si;

average/=NAME_NO;

printf("\n平均查找长度：ASL(%d)=%f \n",NAME_NO,average); }

3.5 主函数设计

void main()

{

char ch1; InitNameList();

CreateHashList ();

do { printf("D. 显示哈希表\nF. 查找\nQ. 退出\n请选择：");

}

cin>>&ch1; switch(ch1) { case 'D':Display(); cout<<endl;break; case 'F':FindList();cout<<endl;break; case 'Q':exit(0); } cout<<"come on !(y/n):"; cin>>&ch1; }while(ch1!='n');

4调试分析

内容包括：

4.1调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析； 题目中明确规定了用除留余数法创建哈希函数和用伪随机探测再散列法处理冲突，程序设计的方法几乎已经被规定，只要按照题目要求写程序不会太难。不过在写程序过程中还是发现了一些小问题，主要是因为自己上机试验少，以后多上机实践能够避免的。 b．算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)

和 改进设想；

c．经验和体会等。

5用户使用说明

说明如何使用你编写的程序，详细列出每一步的操作步骤。

6测试结果

列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。

7参考文献

列出参考的相关资料和书籍。