《数据结构》课程设计


指导书

数据结构课程设计要求


1、 课设需完成的题目：
[1] 一元多项式运算问题

[2] 学生学籍管理系统

[3] 通讯电文压缩处理问题

[4] 最佳旅游路线规划问题

[5] 图书租借管理问题

[6] 网络布线问题



学号尾号为偶数的同学，请完成[1][3]课题；学号尾号为奇数的同学，请完成
[2][4]课题。

在完成了上述 2 个必做课题后，【5】【6】题为选做题，有精力的同学可以完成一个或两个，有加分。


2、 课设目的：

1) 通过课程设计实践，掌握常用数据结构的定义以及基本操作；

2) 熟练进行 VC++编程；



3、 内容与具体要求：
1) 每位同学按照自己的学号根据题目进行程序设计。编程时请注意：尽量不要把所有程序代码写在一个.cpp 文件中。要求.h 头文件存放数据结构的定义；.cpp 文件存放算法实现代码以及 main( )函数。

2) 提交运行的软件系统――每完成一个小程序，当即检查代码运行情况。在机房检查程序；

3) 撰写课程设计报告：

要求写出系统的主要功能和使用说明；写出主要模块实现的代码，并给出详细解释；给出系统操作过程的截图；写出心得和体会，包括已解决和尚未解决的



问题、进一步完善的设想与建议。



――7 月 9 日（周一）11:30 之前提交书面报告。



4) 课设报告：报告要求正反面双面打印。格式参见《课程设计报告样本.doc》



4、课程设计时间安排：（2 学分，32 学时）


19 周

周一

7 月 2 日

周二

7 月 3 日

周三

7 月 4 日

周四

7 月 5 日

周五

7 月 6 日



上午

8:00-11:45

下午

13:30-16:30


(1-5)(6-9)节

设计代码地点：计算中

心机房


(1-5)(6-9)节


设计代码检查程序


(1-5)(6-9)节


设计代码检查程序


(1-5)节


设计代码检查程序


地点：计算中心机房

地点：计算中

心机房

地点：计算中

心机房


20 周

周一

7 月 9 日

周二

7 月 10 日

周三

7 月 11 日

周四

7 月 12 日

周五

7 月 13 日


(1-5)节












设计代码

上午

检查程序

8:00-11:45

下午


课设答辩

13:30-16:30

交报告

地点：实验楼

10 楼 1006 理

综实验室



上机地点：小营校区图书馆楼 7 楼计算中心



课设题目介绍：



一元多项式运算问题
两个一元多项式均采用（带有头结点的）单链表形式存放。编程求解一元多项式加、减法问题。

提示：程序实现时，可能用到的函数有

void InitList(LinkList &L); //初始化一个空链表void CreatList(LinkList &,int); //生成一个单链表void LinkList_reverse(LinkList &);//单链表逆置

void ListPrint(LinkList); //显示单链表所有元素void PolyAdd(LinkList &c, LinkList a, LinkList b);  void PolySubstract(LinkList &c, LinkList a, LinkList b); bool InsertAfter(LinkList &L, ElemType e);

bool DeleteAfter(LinkList &L, ElemType &e);

链表定义可以参考：

typedef struct

{ float coef; //系数域int expn; //指数域

}ElemType; typedef struct node

{ ElemType data;

struct node *next;//指向下一个节点的指针

}LNode,*LinkList;





学生学籍管理系统
请利用单链表结构，编程实现一个学生学籍管理系统，该系统可以实现学生信息的添加、查找、删除、插入和显示功能。



程序功能包括：

[1] 定义学生信息结构（参考后面的“提示”信息）

[2] 编写显示信息模块（显示学生所有信息）

[3] 编写添加模块（分 3 种添加操作，可以将学生信息添加到单链表的首部、末尾、或插入到指定位置），非法位置要给必要提示信息

[4] 编写查找模块（按照姓名查找学生信息，若有重名的学生，则显示多个同名学生信息），非法位置要给必要提示信息

[5] 编写删除模块（按照学号删除一名学生信息），非法位置要给必要提示信息

[6] 编写主模块调用上面的各个功能模块。



提示：链表定义可以参考：

typedef enum {XJ, DJ, TJ } ClassKind;

//定义“专业”枚举类型，分别为信计、电技、统计。

//在进行程序输入时，用 0、1、2 表示这四种专业类型，即输入 0 表示“信计”专业；但调用输出函数时，不能只输出 0，而应该输出其含义，即“信计” typedef struct

{ char No[10]; //学生学号char name[20]; //学生姓名ClassKind major; //专业float GPA; //绩点

}DATA; //数据结点类型typedef struct Node

{ DATA data;

struct Node *next;

}ChainListType;





通讯电文压缩处理问题
数据压缩是一个减小数据存储空间的过程，它是信息理论最重要的成果之



一。广义上，数据压缩的方法分为两大类：有损压缩和无损压缩。在有损压缩中， 我们接受数据有一定的损失来换取更大的压缩比，如图像处理和音频处理，因为这种损失是可接受的，不会影响其效果。然而，我们通常使用的是无损压缩，它能保证解压缩时准确地还原原始数据。

最小冗余编码是无损压缩的一种常用的、主要的方法。它使用更少的位对出现更为频繁的字符进行编码，用较长的位对出现频率较低的字符进行编码。哈夫曼编码是一种最古老而最优雅的数据压缩方法，它是一种基于最小冗余编码的压缩算法。

通过键盘输入一串小写字母（a~z）组成的字符串。请编写一个字符串压缩程序，将字符串中连续出席的重复字母进行压缩，并输出压缩后的字符串。压缩规则：

1、仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符， 压缩后的字符串还是"abcbc"。

2、压缩字段的格式为"字符重复的次数+字符"。例如：字符串"xxxyyyyyyz" 压缩后就成为"3x6yz"，并试着为这些单词设计哈夫曼编码，以此减少数据需要的存储空间。


提示：数据结构定义可以参考如下

typedef struct

{ int weight; //结点权值

int parent, lchild, rchild; //结点的父指针，左右孩子指针

}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树typedef struct {

char ch； //存储单词

char bits[n+1]； //存放编码位串 ，n 为哈夫曼树中叶子结点个数

}CodeNode；

typedef CodeNode *HuffmanCode； //动态数组存储哈夫曼编码表

【测试数据】

1、（必做）待编码数据为{CAS;CAT;SAT;AT}，可以手工统计每个字符的出



现次数，即输入数据为：

image.png


则输出的编码结果应该是：

image.png