数据结构课程设计题目

数据结构课程设计题目 以下8个题目任选其一。

1．排序算法比较

利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并且 （1）统计每一种排序上机所花费的时间。

（2）统计在完全正序，完全逆序情况下记录的比较次数和移动次数。 （3）比较的指标为关键字的比较次数和记录的移动次数(一次记录交换计为3次移动) 。

（4）对结果作简单分析，包括对各组数据得出结果波动大小的解释。 2．图的深度遍历

对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。画出搜索顺序示意图。 3．图的广度遍历

对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。画出搜索顺序示意图。 4．二叉树的遍历

对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。 5．链表操作

利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。画出搜索顺序示意图。 6．一元稀疏多项式简单计数器 （1） 输入并建立多项式

（2） 输出多项式，输出形式为整数序列：n ，c1，e1，c2，e2……cn，en ，其中n 是多项式的项数，ci ，ei 分别为第i 项的系数和指数。序列按指数降序排列。 （3） 多项式a 和b 相加，建立多项式a+b，输出相加的多项式。 （4） 多项式a 和b 相减，建立多项式a-b ，输出相减的多项式。 用带头结点的单链表存储多项式。 测试数据：

（1）(2x+5x8-3.1x11)+(7-5x8+11x9)

（2） (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15) （3）(x+x2+x3)+0 （4）(x+x3)-(-x-x-3) 7．实现两个链表的合并 基本功能要求：

（1）建立两个链表A 和B ，链表元素个数分别为m 和n 个。

（2）假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线性表C ，使得：

当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm 当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn 输出线性表C ：

（1） 用直接插入排序法对C 进行升序排序，生成链表D ，并输出链表D 。 测试数据：

（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） 8．哈夫曼编码的实现与应用

（1）从文件中读入任意一篇英文短文（至少含3000个字符，文件为ASCII 编码的文本文件）

（2）统计不同字符在文章中出现的频率（空格、换行、标点等也按字符处理） （3）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码。

（4）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率

（5）根据相应哈夫曼编码，对编码后的文件进行解码，恢复成ASCII 编码的英文短文后输出。

分析及设计步骤 （供参考）

1. 分析问题，给出数学模型，设计相应的数据结构。

1) 分析问题特点，用数学表达式或其它形式描述其数学模型。 2) 选择能够体现问题本身特点的一种或几种逻辑结构。

3) 依据逻辑结构和问题特点，设计并选择相应的存储结构（顺序存储结构和链式

存储结构对应的算法实现有区别）。

2. 算法设计

1) 确定所需模块：对于复杂的程序设计，要充分利用模块化程序设计方法和面向

对象思想，自顶向下，逐步细化。

2) 各子模块功能描述：给出主要模块的算法描述，用流程图或伪代码表示。 3) 模块之间的调用关系：给出算法各模块之间的关系图示。 3. 上机实现程序

为提高工作效率，充分利用上机调试时间，在上机之前应列出程序清单。

4. 用有代表性的各种测试数据去验证算法及程序的正确性

5. 算法分析及优化

经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度，如有可能对程序进行优化改进。

课程设计报告范例（参考）

约瑟夫环问题。

问题描述：设编号为1,2,…,n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m ，从第一个人开始顺时针方向自1起顺序报数，报到m 时停止报数，抱m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人起重新自1起顺序报数；如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。 基本要求：

（1）初始报数上限值m 和测试数据在程序中确定； （2）用带头结点的单循环链表作数据元素的存储结构； （3）把带头结点的单循环链表作为抽象数据类型设计。 测试数据：

n = 7，七个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m = 20 算法思想：

JesephRing()函数是实现问题要求的主要函数，其算法思想是：从1至m 对带头结点的单循环链表循环计数，到m 时，输出该结点的编号值，将该结点的密码作为新的m 值，再从该结点的下一个结点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。 模块划分：

（1）带头结点的单循环链表抽象数据类型SCLinList ，其中包括基本操作的函数有：初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为SCLinList.h 。

（2）void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针p 所指结点的下一个结点。这是对带头结点的单循环链表抽象数据类型SCLinList ，补充本问题需要的一个操作函数。 （3）void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表head, 以m 为初始报数上限值实现问题要求。

（4）void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用JesephRing()函数实现问题要求。 数据结构：

（1）数据类型DataType 定义如下： typedef struct {

int number; int cipher; } DataType;

（2）带头结点单循环链表抽象数据类型SCLinList 。

（3）带头结点单循环链表抽象数据类型的结点结构定义如下： typedef struct node {

DataType data; struct node *next; } SCLNode;

源程序：

源程序存放在两个文件中，文件SCLinList.h 是带头结点单循环链表抽象数据类型，文件Exam3-9.c 是主程序。

文件SCLinList.h ： typedef struct node {

DataType data; struct node *next;

} SCLNode; /*结点结构定义*/

void SCLLInitiate(SCLNode **head) /*初始化*/ {

if((*head = (SCLNode *)malloc(sizeof(SCLNode))) == NULL) exit(1); (*head)->next = *head; }

int SCLLInsert(SCLNode *head, int i, DataType x) /*插入一个结点*/ {

SCLNode *p, *q; int j;

p = head->next; j = 1; while(p != head && j

p = p->next; j++; }

if(j != i - 1 && i != 1) {

printf("插入位置参数错！"); return 0; }

if((q = (SCLNode *)malloc(sizeof(SCLNode))) == NULL) exit(1); q->data = x; q->next = p->next; p->next = q; return 1; }

int SCLLDelete(SCLNode *head, int i, DataType *x) /*删除一个结点*/ {

SCLNode *p, *q; int j;

p = head; j = 0;

while(p->next != head && j

p = p->next; j++; }

if(j != i - 1)

{

printf("删除位置参数错！"); return 0; }

q = p->next;

p->next = p->next->next; *x = q->data; free(q); return 1; }

int SCLLGet(SCLNode *head, int i, DataType *x) /*取一个结点数据元素值*/ {

SCLNode *p; int j;

p = head; j = 0;

while(p->next != head && j

p = p->next; j++; } if(j != i) {

printf("取元素位置参数错！"); return 0; }

*x = p->data; return 1; }

int SCLLNotEmpty(SCLNode *head) /*链表非空否*/ {

if(head->next == head) return 0; else return 1; }

文件Exam3-9.c ： #include #include typedef struct {

int number; int cipher;

} DataType; /*定义具体的数据类型DataType*/

#include "SCLinList.h" /*包含SCLinList 抽象数据类型*/

void SCLLDeleteAfter(SCLNode *p) /*删除p 指针所指结点的下一个结点*/ {

SCLNode *q = p->next;

p->next = p->next->next; free(q); }

void JesephRing(SCLNode *head, int m)

/*对带头结点单循环链表head ，初始值为m 的约瑟夫环问题函数*/ {

SCLNode *pre, *curr; int i; pre = head; curr = head->next;

while(SCLLNotEmpty(head) == 1) {

for(i = 1; i next; if(curr == head) { pre = curr; curr = curr->next; } }

printf(" %d ", curr->data.number); m = curr->data.cipher; curr = curr->next;

if(curr == head) curr = curr->next; SCLLDeleteAfter(pre); } }

void main(void) {

DataType test[7]={{1,3},{2,1},{3,7},{4,2},{5,4},{6,8},{7,4}}; int n = 7, m = 20, i; SCLNode *head;

SCLLInitiate(&head); /*初始化*/

for(i = 1; i

JesephRing(head, m); /*约瑟夫环问题函数*/ }

测试情况： 程序输出为： 6 1 4 7 2 3 5

各种排序比较结果（参考）