数据结构课程设计任务书
课题一 一元多项式加法、减法、乘法运算的实现 ............................................... 2 课题二 迷宫问题实现 ............................................................................................... 4 课题三 停车场管理 ................................................................................................... 6 课题四 课题五 课题六 课题七 课题八 课题九 课题十 哈夫曼码编、译码器的实现 ....................................................................... 8 校园导游咨询 ............................................................................................. 11 利用栈实现表达式求解 ............................................................................. 13 跳舞搭配问题 ............................................................................................. 15 散列表的设计与实现 ................................................................................. 16 简单文本编辑器的设计与实现 ................................................................. 18 词索引表的建立 ......................................................................................... 20
课题一 一元多项式加法、减法、乘法运算的实现
一、 课题名称
一元多项式的加法、减法、乘法运算的实现 二、 设计目的
1、熟悉并掌握线性表的顺序存储和链式存储结构； 2、熟悉并掌握线性表插入、删除等基本操作；
3、掌握线性表的典型应用—多项式的加、减、乘运算的实现。 三、 课题内容及要求： 1、课题内容
（1）使用顺序存储结构实现多项式加、减、乘运算； 例如：
f(x)?8x6?5x5?10x4?32x2?x?10，g(x)?7x5?10x4?20x3?10x2?x
求和结果：f(x)?g(x)?8x6?12x5?20x3?32x2?10 （2）使用链式存储结构实现多项式加、减、乘运算 例如：
f(x)?100x100?5x50?30x10?10，g(x)?150x90?5x50?40x20?20x10?3x
求和结果：f(x)?g(x)?100x100?150x90?40x20?10x10?3x?10 根据下面给出的存储结构定义
#define MAXSIZE 20 //定义线性表最大容量 //定义多项式项数据类型 typedef struct {
float coef; //系数 int expn;//指数 } term,elemType;
typedef struct {
term terms[MAXSIZE];//线性表中数组元素 int last;//指向线性表中最后一个元素位置 } SeqList;
typedef SeqList polynomial;
2
―――――――――基本操作的函数说明―――――――― polynomial* Init_Polynomial(); //初始化空的多项式
int PloynStatus(polynomial* p); //判断多项式的状态
int Location_Element(polynomial* p,term x);
//在多项式p中查找与x项指数相同的项是否存在 bool Insert_ElementByOrder(polynomial *p,term x); //在多项式p中插入一个的指数项x int CreatePolyn(polynomial *p, int m)
//输入m项系数和指数，建立表示一元多项式的有序表p char compare(term term1,term term2); //比较指数项term1和指数项term2
polynomial* addPloyn(polynomial* p1,polynomial* p2) //将多项式p1和多项式p2相加，生成一个新的多项式
polynomial* subStractPloyn(polynomial* p1,polynomial* p2) //多项式p1和多项式p2相减，生成一个新的多项式 polynomial* mulitPloyn(polynomial* p1,polynomial* p2) //多项式p1和多项式p2相乘，生成一个新的多项式 void printPloyn(polynomial* p) //输出在顺序储存结构的多项式p 2、设计要求
（1）编程实现上述课题内容中的结构定义和算法。
（2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。 （3）课题完成后撰写课题报告。 （4）课题完成后把打印好的课题报告以及电子版的课题报告和源程序一并上交。（电子版的课题报告和源程序放在以学号姓名命名的文件夹中压缩后上交到指定的ftp处）
（5）用switch语句设计如下选择式菜单。
**********数据结构综合性课题********** ***一、多项式的加法、减法、乘法运算*** *---- 1.多项式创建 * *---- 2.多项式相加 * *---- 3.多项式相减 * *---- 4.多项式相乘 * *---- 5.清空多项式 * *---- 0.退出系统 * *---- 请选择(0-5) * ************************************** *请选择(0-5):
3
课题二 迷宫问题实现
一、 课题名称
迷宫问题的实现 二、 课题目的
1、熟练栈的结构特性，掌握在实际问题背景下的应用。 2、熟悉并掌握栈的基本操作；
3、掌握栈的典型应用—迷宫问题的实现。 三、 课题内容及要求：
1、课题内容：
以一个 m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路。或得出没有通路的结论。
根据以上问题给出存储结构定义： typedef struct//定义坐标 {
int x; int y; } item;
//定义坐标和方向 typedef struct {
int x; int y; int d; } dataType;
//定义顺序栈的类型定义 typedef struct {
dataType data[MAXLEN]; int top; }SeqStack;
item move[8];//8邻域试探方向数组 int maze[M+2][N+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,1,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1},
4
{1,0,1,1,1,0,1,1,1,1}, {1,1,0,0,1,1,0,0,0,1}, {1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1}
};//定义迷宫数组，0表示有路径，1表示不存在路径
―――――――定义基本操作的函数说明―――――――――――― void print_Path(SeqStack* s);//输出迷宫路线 SeqStack* InitSeqStack();
//该函数初始化一个空栈,并返回指向该栈的存储单元首地址 int Push(SeqStack *s,dataType x)
//将元素x入栈s,若入栈成功返回结果1;否则返回0 int StackEmpty(SeqStack *s)
//该函数判断栈是否为空,若栈空返回结果1;否则返回0 int Pop(SeqStack *s,dataType *x)
//将栈顶元素出栈,放入x所指向的存储单元中,若出栈返回结果1;否则返回0 void init_move(item move[8]) //初始化8邻域方向
int find_Path(int maze[M+2][N+2],item move[8])
//在迷宫maze二维数组中按move的8邻域方向探测迷宫路线,存在返回1,否则 //返回0
void print_Path(SeqStack* s) //输出栈s中所有迷宫路径 2、课题要求
（1）编程实现上述课题内容中的结构定义和算法。
（2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。 （3）课题完成后撰写课题报告。 （4）课题完成后把打印好的课题报告以及电子版的课题报告和源程序一并上交。（电子版的课题报告和源程序放在以学号姓名命名的文件夹中压缩后上交到指定的ftp处）
5
数据结构课程设计任务书
