《数据结构》课程设计规范.doc

《数据结构》课程设计规范
一、课程设计教学目的及基本要求
1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4．训练用系统的观点和软件开发一般规范进行软件开发。
二、课程设计题目
1．学生信息管理
要求每条学生信息至包含学号(xh)、姓名(xm)、性别(xb)、年龄(nl)、专业(zy)等，完成如下功能：
（1）输入学生基本信息记录——enter()
（2）增加一名学生记录（可和功能1合并）——insert()
（3）删除指定（按姓名）学生的信息——delete()
（4）修改指定（按姓名）学生的信息）——modify( )
（5）查询符合条件的学生（按专业）——search()
（6）显示学生管理库中的信息——display( )
2．计算一元稀疏多项式
要求完成如下功能：
（1） 输入并建立多项式——creatpolyn()
（2） 输出多项式，输出形式为整数序列，序列按指数升序排列——printpolyn()
（3） 多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn()
（4） 多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn()
用带表头结点的单链表存储多项式。
测试数据：
（1）(2x+5x8-3.1x11)+(7-5x8+11x9)
（2） (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)
（3）(x+x2+x3)+0
（4）(x+x3)-(-x-x-3)
3．通讯录的制作
要求每条信息至包含姓名（name ）城市（city）电话（tel）QQ号（qq），完成如下功能：
（1） 输入信息—— enter();
（2） 显示信息——display( );
（3） 查找以姓名作为关键字 ——search( );
（4） 删除信息——delete( );
（5） 存盘（将数据保存在文件中，此功能选做）——save ( );
4．实现两个链表的合并，编一程序将A表和B表归并成一个新的递增有序的单链表C（值相同的元素均保留在C表中），并要求利用原表的空间存放C
测试数据：
（1） A表（30，41，15，12，56，80）
B表（23，56，78，23，12，33，79，90，55）
（2） A表（30，41，15，12，56，80，23，12，34）
B表（23，56，78，23，12）
5．实现字符串的基本操作
完成如下功能：
（1）插入子串——　StrInsert()
（2）取子串—— SubString()
（3）串连接—— StrCat()
（4）查找子串的位置——　Index()
注：以上题目仅供参考，同学们可以自定题目，要求在题目难度和任务量上相当。
三、课程设计报告的规范
课程设计报告要求规范书写。应当包括如下六个部分：
1、设计目的与内容。
进行需求分析，确定每个模块的功能要求。即根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）
2、算法的基本思想
进行概要设计和详细设计。说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。并用自然语言描述每个模块所涉及的算法。
3、测试数据
列出对于给定的输入所产生的输出结果。
4、源程序及系统文件使用说明
附上关键数据结构的定义及关键算法的源代码。
5、心得体会
谈谈课程设计过程的收获、遇到问题及解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。
6、参考文献
参考文献要注明作者、出版社、出版日期。
四、设计最终需提交的内容包括：
1．完整的程序系统（电子方式提交）
（1）．能够对输入产生相应的输出，并在输入输出做必要的提示。
（2）．该部分包括源代码和可执行文件两个部分。
（3）．所有以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用Winrar或Winzip均可），压缩后的文件按规定格式进行命名，命名格式为：学号+姓名.rar（如z04043120张文.rar）。
(4)将提交作品发送到邮箱xialh@
2．课程设计报告,字数不少于1000字
四、课程设计考核方法及成绩评定
课程设计成绩分两部分，设计报告占30％，设计作品占60％，答辩表现占10%。
课程设计报告书写格式：

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

题目——事件排列表

班 级：
学 号：
姓 名：
同 组 者：
时 间： 2006/11/17---2006/12/20
一、设计目的与内容（下面为组员介绍，组长要谈谈整个小组完成的内容）
1．设计目的
熟练掌握队列的顺序存储表示和基本操作的实现，能够利用队列设计算法解决简单的应用问题。
2．设计内容：
利用循环队列编写一个简单的事件处理表。用户可以输入和保存一系列事件；当一个事件处理完毕后，它就会从事件处理表中被删除；还可以查询事件处理表中剩余的事件。
二、 算法的基本思想
（此处可加框图描述基本功能模块）
被处理事件的数目限定在100以内，并用宏MAX来表示。
算法的主要思路是：
1．函数enter()用来输入事件，调用函数EnQueue()将事件字符串指针保存到事件队列中；
基本思路如下：
（1）提示并等待输入事件
（2）若有事件输入，执行步骤3，否则执行步骤5
（3）动态申请存放新事件串的空间，并将输入事件串复制到新申请的内存单元
（4）调用EnQuue()函数将新事件插入到队尾
（5）结束
2．函数review()用来显示还没有处理的事件；
基本思路如下：
（1）
（2）
（3）
3．函数delete()将处理完毕的事件从事件队列中删除，并释放事件内容的存储空间，其中删除事件调用函数DeQueue()完成。
基本思路如下：
（1）
（2）
（3）
三、测试数据
程序运行实例如下：
******************************"
队列示例--事件表
1--录入,2--显示,3--删除,4--退出
******************************"
请选择(1-4)：1
输入事件1：Marry have a math at 8:00.
输入事件2：Marry will learn dancing at 1:00 pm.
输入事件3：Marry will watch TV at 6:30 pm.
输入事件4：<cr>
请选择(1-4)：2
事件1.Marry have a math at 8:00.
事件2.Marry will learn dancing at 1:00 pm.
事件3.Marry will watch TV at 6:30 pm.
请选择(1-4)：3
Marry have a math at 8:00.
请选择(1-4)：2
事件1.Marry will learn dancing at 1:00 pm.
事件2.Marry will watch TV at 6:30 pm.
请选择(1-4)：4
四、源程序及系统文件使用说明
1．循环队列的基本操作函数放在seqqueue.h头文件中，程序清单如下：
typedef struct{
DataType data[MaxSize];
int front, rear;
} SeqQueue;
void QueueInit ( SeqQueue *q )
{
q->rear = q->front = 0;
}
int QueueEmpty ( SeqQueue q )
{
if(q.rear == q.front)return 1;
else return 0;
}
int EnQueue ( SeqQueue *q, DataType x )
{
if ((q->rear+1) % MaxSize == q->front)
return 0;
q->data[q->rear] = x;
q->rear = (q->rear+1) % MaxSize;
return 1;
}
int DeQueue ( SeqQueue *q, DataType *x )
{
if ( QueueEmpty (*q) ) return 0;
*x = q->data[q->front];
q->front = ( q->front+1) % MaxSize;
return 1;
}
2．Shijianbiao.cpp文件代码清单如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxSize 100
typedef char* DataType;
#include "SeqQueue.h" /*循环队列的基本操作函数*/

void enter(SeqQueue *q);
void review(SeqQueue q);
void del(SeqQueue *q);

void main()
{
char ch;
SeqQueue q;
QueueInit(&q);
system("cls"); //调用系统的CLS清屏命令清屏
printf("\n******************************");
printf("\n队列示例--事件表");
printf("\n1--录入,2--显示,3--删除,4--退出：");
printf("\n******************************");
while(1)
{
printf("\n请选择(1-4)：");
ch=getchar ();getchar();
switch(ch)
{
case '1':enter(&q);break;
case '2':review(q);break;
case '3':del(&q);break;
case '4':return;
}
}
}
void enter(SeqQueue *q)
{
char s[64],*p;
int len;
while(1)
{
printf("输入事件 %d:",(q->rear-q->front+1)%MaxSize);
gets(s);
len= strlen(s);
if(len==0)break; /*没有事件*/
p=(char *)malloc(len+1);
if(!p){ printf("memory not available.\n "); return;}
strcpy(p,s);
EnQueue(q,p);
};
}
void review(SeqQueue q)
{
int i=1,pos=q.front;
do{
printf("事件%d.%s:\n",i,q.data[pos]);
pos=(pos+1) % MaxSize;
i++;
}while(pos!=q.rear);
}
void del(SeqQueue *q)
{
char *p;
if(DeQueue(q,&p)){ printf("%s\n",p);
free(p);}
}
五、心得体会
通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。
对于数据结构有了更深层次的理解，循环队列中对边界条件的处理，满足什么条件为队满，满足什么条件为队空。
六、参考文献
1．《数据结构（C语言版）》 严蔚敏，吴伟民 清华大学出版社 p58~p69
2．《数据结构》 张世和 清华大学出版社 p41~p51