1.设计目的
数据结构课程设计是学习了数据结构课程后的一个综合性实践教学环节，是对课程理论和课程实验的综合和补充。它主要培养学生综合运用已学过的理论和技能去分析和解决实际问题的能力，对加深课程理论的理解和应用、切实加强学生的实践动手能力和创新能力具有重要意义。
2.设计要求
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具有一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
(4) 根据实验报告模板详细书写实验报告文档。
(5) 上交源程序和实验报告文档。实验报告文档命名：学号姓名班级，源程序文件夹名称同实验报告文档名称。
3.设计内容
3.1 题目1 链表综合算法设计
3.1.1 题目分析
我组设计了一个图书信息管理系统，信息采用链式存储。图书信息结构为：图书编号（no）、图书名称（name）、图书价格（price）、图书编号指针（data.no）、图书名称指针（data.name）、图书价格指针（data.price）等，并实现了如下功能：
(1) 根据指定的记录本数，逐个输入图书的信息并记录；
(2) 逐个显示表中所有图书相关信息；
(3) 根据某一关键字进行图书名称查找，返回该本图书的其他数据项；
(4) 根据指定的结点位置，可返回该本图书信息的完整记录；
(5) 给定一条图书记录信息，插入到表中指定的位置；
(6) 删除指定位置的图书记录；
(7) 统计表中图书的记录个数。
3.1.2 模块结构
结构类型为：
typedef struct LNode
{
Book data;
struct LNode *next;
}LNode,*Linklist;3.1.3 程序流程图
3.1.4 算法实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct {
char no[20]; //图书编号
char name[20]; //图书名称
int price; //图书价格
}Book;
typedef struct LNode
{
Book data;
struct LNode *next;
}LNode,*Linklist;
Linklist creatlist()//（头插入法）输入图书信息。
{
Linklist L,p;
int i,n;
L=(Linklist)malloc(sizeof(LNode));
L->next=NULL;
printf("请输入要录入图书的本数：");
scanf("%d",&n);
for(i=0;i<n;i++)
{
p=(Linklist)malloc(sizeof(LNode));
printf("请输入图书的信息：\n");
printf("图书名称：");
scanf("%s",&p->data.name);
printf("图书编号：");
scanf("%s",&p->data.no);
printf("图书价格：");
scanf("%d",&p->data.price);
p->next=L->next;
L->next=p; //头插法
}
return L; // 返回L结点
}
void putlist(Linklist L)//输出图书信息。
{
Linklist p;
p=L->next;
while(p){
printf("图书名称：%s\n图书编号：%s\n图书价格：%d\n",p->data.name,p->data.no,p->data.price);
p=p->next;
}
printf("\n");
}
int lengthlist(Linklist L)//求图书的总数。
{
Linklist p;
int j;
p=L->next;
j=0;
while(p!=NULL) {
j++;
p=p->next;
}
printf("表中的总数为:%d\n",j);
}
void namegetlist(Linklist L) //根据图书的名称查找图书的信息
{
char name[20];
int j=1;
Linklist p;
printf("请输入查找图书的名称:");
scanf("%s",&name);
p=L->next;
while(p&&strcmp(p->data.name,name)!=0) { //字符串比较，如果指针p不为空并且p->data.name与name相等返回1，p&&strcmp不等于0则执行
p=p->next;
j++;
}
if(p)
printf("该图书的信息：\n图书编号：%s\n图书价格：%d\n",p->data.no,p->data.price);
else
printf("该表中没有该图书的信息。");
}
void getlist(Linklist L)//根据图书结点位置查找图书信息。
{
int i,j=1,l=0;
Linklist p;
printf("请输入查找图书的位置结点：");
scanf("%d",&i);
p=L->next;
while(p!=NULL) { //计算当前节点数
l++;
p=p->next;
}
p=L->next;
while((p->next)&&(j<i)) { //p有后继节点
p=p->next;
++j;
}
while(i>l) {
printf("输入的结点值超过图书总数 ，请重新输入图书的位置结点：");
scanf("%d",&i);
}
while((p!=NULL)&&(j<i)) {
p=p->next;
j++;
}
printf("查找图书信息：\n图书名称:%s\n图书编号：%s\n图书价格：%d\n",p->data.name,p->data.no,p->data.price);
}
void insertlist(Linklist L)//图书信息插入
{
int i,j,l;
Linklist p,s;
p=L;l=0;
while(p!=NULL) { //计算一共有多少本图书（节点数）
l++;
p=p->next;
}
printf("请输入插入图书的结点位置:");
scanf("%d",&i);
while(l<i) {
printf("输入的结点值已超过总数,请重新输入插入图书的结点位置:");
scanf("%d",&i);
}
p=L;j=1;
while(p&&(j<i)) //找到要插入的位置
{
p=p->next;
++j;
}
s=(Linklist)malloc(sizeof(LNode));
printf("请输入图书的信息：\n");
printf("图书名称：");
scanf("%s",&s->data.name);
printf("图书编号：");
scanf("%s",&s->data.no);
printf("图书价格：");
scanf("%d",&s->data.price);
s->next=p->next;//头插法
p->next=s;
printf("图书信息插入成功！");
printf("\n");
}
void deletelist(Linklist L)//图书信息的删除。
{
int i,j,l=0;
Linklist p,q;
p=L->next;
while(p!=NULL)//计算一共有多少本图书（节点数）
{
l++;p=p->next;
}
printf("请输入要删除图书的位置结点：");
scanf("%d",&i);
while(l<i) {
printf("输入的结点值超过总数,请重新输入要删除图书的位置结点：");
scanf("%d",&i);
}
p=L; j=1;
while((p->next)&&(j<i)) //找到要删除的节点位置
{
p=p->next;
++j;
}
q=p->next;
p->next=q->next;
free(q);
printf("删除成功！\n");
}
int main()//主函数
{
Linklist L;
int k;
L=creatlist();
printf("\n");
printf("图书信息输入成功！\n\n");
printf("图书信息管理系统的操作目录:\n");
printf("__________________________\n\n");
printf("0、结束使用，退出本系统；\n");
printf("1、逐个显示表中所有图书相关信息；\n");
printf("2、根据图书的名称查找图书信息；\n");
printf("3、根据图书的结点位置查找图书信息；\n");
printf("4、插入图书的信息；\n");
printf("5、删除图书的信息；\n");
printf("6、求表中图书的总数。\n");
printf("__________________________\n");
while(1) {
printf("请选择操作：");
scanf("%d",&k);
switch(k) {
case 0:printf("谢谢使用");exit(0);
case 1:putlist(L);break;
case 2:namegetlist(L);break;
case 3:getlist(L);break;
case 4:insertlist(L);putlist(L);break;
case 5:deletelist(L);putlist(L);break;
case 6:lengthlist(L);break;
}
}
return 0;
}3.1.5 测试数据
3.2 题目2 停车场管理
3.2.1 题目分析
停车场管理系统，分为停车区和便道两区域。停车区停满后，再进来的车辆需要在便道等候。另设了一个栈，为给要离去的汽车让路而从停车场退出来的汽车临时停靠。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应缴的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以顺序循环结构实现。
3.2.2 模块结构
3.2.3 程序流程图
3.2.4 算法实现
#include <stdio.h>
#include <stdlib.h>
#define price 0.15
#define max 3
int flag;
typedef struct time {
int hour;
int min;
}
Time;
typedef struct node {
long num;
Time reach;
Time leave;
}
CarNode;
//车辆信息结点
typedef struct NODE {
CarNode *stack[10];
int top;
}
SeqStackCar;
//模拟车场
typedef struct car {
CarNode *data;
struct car *next;
}
QueueNode;
typedef struct Node {
QueueNode *head;
QueueNode *rear;
}
LinkQueueCar;
//模拟通道
void InitStack(SeqStackCar *s) //初始化栈
{
int i;
s->top=0;
for(i=0;i<=max;i++)
s->stack[s->top]=NULL;
}
void InitQueue(LinkQueueCar *Q) //初始化便道
{
Q->head=(QueueNode *)malloc(sizeof(QueueNode));
if(Q->head!=NULL) {
Q->head->next=NULL
;
Q->rear=Q->head;
return (1);
}
else return (-1);
}
void PRINT(CarNode *p, int room)//输出出场车的信息
{
int A1, A2, B1, B2;
printf("\n请输入车辆离开的时间（格式：mm:ss）:\n");
scanf("%d:%d", &p->leave.hour, &p->leave.min);
printf("\n\n离开车辆的车牌号为:%ld\n\n",p->num);
printf("其到达时间为: %d:%d\n",p->reach.hour,p->reach.min);
printf("\n离开时间为: %d:%d\n",p->leave.hour,p->leave.min);
A1=p->reach.hour;
A2=p->reach.min;
B1=p->leave.hour;
B2=p->leave.min;
printf("\n应交费用为:%2.1f元\n\n",((B1-A1)*60+(B2-A2))*price);
free(p);
}
void Arrive(SeqStackCar *Enter, LinkQueueCar *W) {
CarNode *p;
QueueNode *t;
p=(CarNode *)malloc(sizeof(CarNode));
printf("请输入车牌号(格式：例如12345):\n");
scanf("%ld", &p->num);
if(Enter->top<max) { //车辆未满，车进场
Enter->top++;
printf("车辆请停在停车场的第%d个位置。\n\n",Enter->top);
printf("请输入到达时间(格式：mm:ss):\n");
scanf("%d:%d", &p->reach.hour, &p->reach.min);
Enter->stack[Enter->top]=p;
}
else { //车辆已满
printf("该车须在便道等待！\n\n");
t=(QueueNode *)malloc(sizeof(QueueNode));
t->data=p;
t->next=NULL;
W->rear->next=t;
W->rear=t;
}
printf("\n请输入操作(1.返回主菜单 0.退出本程序)\n");
scanf("%d", &flag);
switch(flag) {
case 0: printf("\n谢谢您的使用，请按任意键退出本程序\n"); exit(0);
case 1: printf("\n请继续操作\n"); ;
}
}
void Leave(SeqStackCar *Enter, SeqStackCar *Temp, LinkQueueCar *W) {
int i, room;
CarNode *p, *t;
QueueNode *q;
if(Enter->top>0) { //判断车场内是否有车
while(1) {
printf("\n请输入车在车场的位置（1--%d）:\n",Enter->top);
scanf("%d", &room);
if(room>=1&&room<=Enter->top)
break;
}
while(Enter->top>room) {//车辆离开
Temp->top++;
Temp->stack[Temp->top]=Enter->stack[Enter->top];
Enter->stack[Enter->top]=NULL;
Enter->top--;
}
p=Enter->stack[Enter->top];
Enter->stack[Enter->top]=NULL;
Enter->top--;
while(Temp->top>=1) {
Enter->top++;
Enter->stack[Enter->top]=Temp->stack[Temp->top];
Temp->stack[Temp->top]=NULL;
Temp->top--;
}
PRINT(p, room);
//判断通道上是否有车及车场是否已满
if((W->head!=W->rear)&&Enter->top<max) { //便道的车辆进场
q=W->head->next;
t=q->data;
Enter->top++;
printf("\n便道的%s号车进入车场的第%d位置.\n",t->num,Enter->top);
printf("\n请输入现在的时间(格式：mm:ss):\n");
scanf("%d:%d", &t->reach.hour, &t->reach.min);
W->head->next=q->next;
if(q==W->rear) W->rear=W->head;
Enter->stack[Enter->top]=t;
free(q);
}
else
printf("\n便道里没有车。\n");
}
else
printf("\n车场里没有车。\n");
printf("\n请输入操作(1.返回主菜单 0.退出本程序)\n");
scanf("%d", &flag);
switch(flag) {
case 0: printf("\n谢谢您的使用，请按任意键退出本程序\n"); exit(0);
case 1: printf("\n请继续操作\n"); ;
}
}
void List1(SeqStackCar *S) { //显示存车信息
int i;
if(S->top>0) { //判断车场内是否有车
printf("车场\n");
for(i=1;i<=S->top;i++) {
printf("位置%d\到达时间:%d:%d\t号码:%ld\n",i,S->stack[i]->reach.hour,S->stack[i]->reach.min,S->stack[i]->num);
}
}
else
printf("\n车场里没有车。\n");
printf("请输入操作(1.返回主菜单 0.退出本程序)\n");
scanf("%d", &flag);
switch(flag) {
case 0: printf("\n谢谢您的使用，请按任意键退出本程序\n"); exit(0);
case 1: printf("\n请继续操作\n"); ;
}
}
void List2(LinkQueueCar *W) {
QueueNode *p;
p=W->head->next;
if(W->head!=W->rear) {
printf("\n等待车辆的号码为:");
while(p!=NULL) {
printf("%ld\n",p->data->num);
p=p->next;
}
}
else
printf("\n便道里没有车。\n");
printf("\n请输入操作(1.返回主菜单 0.退出本程序)\n");
scanf("%d", &flag);
switch(flag) {
case 0: printf("\n谢谢您的使用，请按任意键退出本程序\n"); exit(0);
case 1: printf("\n请继续操作\n"); ;
}
}
void List(SeqStackCar S, LinkQueueCar W) {
int tag;
printf("1.车场\n2.便道\n0.返回\n");
scanf("%d", &tag);
switch(tag) {
case 0: break;
case 1: List1(&S); break;
case 2: List2(&W); break;
}
}
int main() {
SeqStackCar Enter, Temp;
LinkQueueCar Wait;
int ch;
InitStack(&Enter);
InitStack(&Temp);
InitQueue(&Wait);
MENU:printf("\n停车场车辆管理系统\n");
printf("\n1.车辆到达\n");
printf("2.车辆离开\n");
printf("3.列表显示\n");
printf("0.退出系统\n\n");
printf("请输入您的操作：");
scanf("%d", &flag);
printf("\n");
switch(flag) {
case 0: printf("\n谢谢您的使用，请按任意键退出本程序\n"); return 0;
case 1: Arrive(&Enter, &Wait); goto MENU;
case 2: Leave(&Enter, &Temp, &Wait); goto MENU;
case 3: List(Enter, Wait); goto MENU;
}
return 0;
}3.2.5 测试数据
3.3 题目3 学生成绩管理系统
3.3.1 题目分析
本题目采用顺序存储的方式编写了一个学生信息管理程序，运用直接插入排序方法、希尔排序、快速排序方法以及折半查找方法实现了对学生信息的输入（INPUT）、总分的统计（COUNT）、DataStructure项排序、C项排序、SUM项排序以及输入C成绩查找该成绩位置的功能，并且能在指定位置插入，查找，删除学生信息。
①直接插入排序：对DataStructure项排序，将待插入的记录暂存到监视哨中，STU[i-1]后移，从后向前寻找插入位置直到找到位置，再将STU[0] 插入位置。
②希尔排序：将C项排序，步长为初始化为一半，每次遍历步长减半，x为每次分组第一个元素下标，对步长k进行直接排序将STU[i]插入有序增量子表，暂存在STU[0],记录后移直到找到插入位置，将STU[0]插入到正确位置，然后输出。
③快速排序：将SUM排序，将STU[0]的第一个记录做枢轴记录，枢轴关键字保存在pivotkey中，从表的两端交替向中间扫描，再将比枢轴记录小的记录移到低端，将比枢轴记录大的记录移到高端，当枢轴记录到位，返回枢轴位置。在QSort中：长度大于1，将l[low..high]一分为二，pivotloc为枢轴，再对左右子表递归排序。最后输出。
3.3.2 模块结构
3.3.3 程序流程图
3.3.4 算法实现
#include<stdio.h>
#include<stdlib.h>
#define N 50
#include<string.h>
struct Student //定义一个学生
{
int num; //学号
char name[4]; //姓名
float DataStructure;//DataStructure成绩
float C; //C成绩
float sum; //总分
}Stu[N];
typedef struct Student Student;
int n;
int d;
int flag=0;
void menu()
{
printf("************（1）：信息输入（INPUT） ************\n");
printf("************（2）：总分统计（COUNT） ************\n");
printf("************（3）：按Data项排序 ************\n");
printf("************（4）：按C项排序 ************\n");
printf("************（5）：按SUM项排序 ************\n");
printf("************（6）：输入C成绩查找位置 ************\n");
printf("请输入你的选项: \n");
scanf("%d",&n);
system("cls");
}
int InputStudent() //输入学生信息
{
int i;
for(i=1;i<=d;i++)
{
printf("\n请输入第%d个学生的信息:\n",i);
printf("学号: \n");
scanf("%d",&Stu[i].num);
printf("姓名: \n");
scanf("%s",Stu[i].name);
printf("DataStructure成绩: \n");
scanf("%f",&Stu[i].DataStructure);
printf("C成绩:\n ");
scanf("%f",&Stu[i].C);
Stu[i].sum=Stu[i].DataStructure+Stu[i].C;
printf("总成绩: %.2f\n",Stu[i].sum);
}
flag=1;
}
void PrintStudent() //显示学生信息
{
int i;
system("cls");
for(i=1; i<=d; i++)
{
printf("学号:%d\n",Stu[i].num);
printf("姓名:%s\n",Stu[i].name);
printf("DataStructure成绩:%.2f\n",Stu[i].DataStructure);
printf("C成绩:%.2f\n",Stu[i].C);
printf("总分:%.2f\n",Stu[i].sum);
}
flag=1;
}
void SortDataStructure()//直接排序
{
struct Student stu; //定义另一个结构体用来互换
int i;
int j;
system("cls");
for(j=1;j<=d;j++)
for(i=1;i<=d-j;i++)
{
if(Stu[i+1].DataStructure>Stu[i].DataStructure)
{
stu=Stu[i];
Stu[i]=Stu[i+1];
Stu[i+1]=stu;
}
}
for(i=1;i<=d;i++)
{
printf("按照DataStructure成绩排名，第%d名学生：\n",i);
printf("学号:%d\n",Stu[i].num);
printf("姓名:%s\n",Stu[i].name);
printf("DataStructure成绩:%.2f\n",Stu[i].DataStructure);
printf("C成绩:%.2f\n",Stu[i].C);
printf("总分:%.2f\n",Stu[i].sum);
}
flag=1;
}
void SortC()//希尔排序
{
int i;
int j;
int k;
int dk=5;
for(k=0;k<d;++k)
for(i = dk+1;i <= d;++i)
{
if(Stu[i-dk].C>Stu[i].C)
{
Stu[0]=Stu[i];
for (j = i-dk;j>0&&Stu[0].C<Stu[j].C; j-=dk)
{
Stu[j+dk]=Stu[j];
}
Stu[j+dk] = Stu[0];
}
}
for(i=1;i<=d;i++)
{
printf("按照C成绩排名，第%d名学生：\n",i);
printf("学号:%d\n",Stu[i].num);
printf("姓名:%s\n",Stu[i].name);
printf("DataStructure成绩:%.2f\n",Stu[i].DataStructure);
printf("C成绩:%.2f\n",Stu[i].C);
printf("总分:%.2f\n",Stu[i].sum);
}
flag=1;
}
int partition(Student stu[], int low, int high)
{
Student st=stu[low];
while(low<high)
{
while(low<high&&stu[high].sum>=st.sum) --high;
st.sum=stu[high].sum;
low++;
while(low<high&&stu[low].sum<=st.sum) ++low;
stu[high]=stu[low];
}
stu[high]=stu[low];
return low;
}
void Sortsum(Student stu[],int low,int high)//快速排序
{
int i;
int mid=partition(stu,low,high);
Sortsum(stu,low,high);
Sortsum(stu,mid+1,high);
for(i=1;i<=d;i++)
{
printf("按照学生：\n",i);
printf("学号:%d\n",Stu[i].num);
printf("姓名:%s\n",Stu[i].name);
printf("DataStructure成绩:%.2f\n",Stu[i].DataStructure);
printf("C成绩:%.2f\n",Stu[i].C);
printf("总分:%.2f\n",Stu[i].sum);
}
flag=1;
}
void print(Student stu[])//用于输出数组元素
{
int i;
for (i = 1; i <= d; i++) {
printf("按照总分排名，第%d名学生：",i);
printf("学号:%d\n",Stu[i].num);
printf("姓名:%s\n",Stu[i].name);
printf("DataStructure成绩:%.2f\n",Stu[i].DataStructure);
printf("C成绩:%.2f\n",Stu[i].C);
printf("总分:%.2f\n",Stu[i].sum);
}
flag=1;
}
void FindC() //查找学生信息
{
int grade;
int i,q;
system("cls");
printf("请输入要查找的科目C的成绩: ");
scanf("%d",&grade);
for(i=1;i<=d;i++)
{
if(grade==Stu[i].C)
{
printf("\n查找成功!\n\n\n");
printf("该学生的学号:%d\n",Stu[i].num);
printf("该学生的姓名:%s\n",Stu[i].name);
printf("DataStructure成绩:%.2f\n",Stu[i].DataStructure);
printf("C成绩:%.2f\n",Stu[i].C);
printf("总分:%.2f\n",Stu[i].sum);
}
}
flag=1;
}
int main()
{
do
{
menu();
switch (n)
{
case 1: //输入学生信息
{
printf("请输入学生记录个数:\n");
scanf("%d",&d);
InputStudent();
}break;
case 2: //显示学生信息
PrintStudent();break;
case 3: //按照DataStructure排序
SortDataStructure();break;
case 4: //按照C排序
SortC();break;
case 5: //按照sum排序
{
Sortsum(Stu,1,d);
}break;
case 6: //按照C的成绩查找
FindC();
break;
}
} while (flag==1);
return 1;
}3.3.5 测试数据
3.4 题目4 哈夫曼编码/译码的设计与实现
3.4.1 题目分析
本题目利用哈夫曼编码设计了一个简单编码/译码系统，具有接收原始数据（从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树）、编码（利用已建好的哈弗曼树，对输入的正文进行编码，存储编码结果）、译码（利用编码后的结果进行译码，存储译码结果）、输出编码规则及哈夫曼树的功能。
3.4.2 模块结构
3.4.3 程序流程图
3.4.4 算法实现
#include <stdio.h>
#include<stdlib.h>
#define MAXBIT 100
#define MAXVALUE 100
#define MAXLEAF 10
#define MAXNODE MAXLEAF*2 -1
//编码结构体
typedef struct
{
int bit[MAXBIT]; //保存字符的哈夫曼编码
int start; //编码在数组 bit 中的开始位置
}HCodeType;
//结点结构体
typedef struct
{
int weight; //权值
int parent; //双亲节点
int lchild; //左子节点
int rchild; //右子节点
}HNodeType;
//构造哈夫曼树
void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)
{
int i, j, m1, m2, x1, x2;
//i、j： 循环变量
//m1、m2：两个最小权值结点的权值
//x1、x2：两个最小权值结点在数组中的序号
for(i=0; i<2*n-1; i++) //初始化存放哈夫曼树数组 HuffNode[] 中的结点,2n-1是有n个节点，要进行n-1次合并所以共有2n-1个节点
{
HuffNode[i].weight = 0; //权值
HuffNode[i].parent =-1; //初始化
HuffNode[i].lchild =-1; //初始化
HuffNode[i].rchild =-1; //初始化
}
//输入n个叶子结点的权值
printf("\n");
for(i=0; i<n; i++)
{
printf ("输入叶子结点的权值: ",i);
scanf ("%d", &HuffNode[i].weight);
}
//循环构造哈夫曼树
for(i=0; i<n-1; i++) //最大不超过n-1层
{
m1=m2=MAXVALUE; //初始化为最大值
x1=x2=0;
for(j=0; j<n+i; j++) //找出所有结点中权值最小、无双亲结点的两个结点，并合并之为一颗二叉树
{
if(HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//设置找到的两个子结点 x1、x2 的父结点信息
HuffNode[x1].parent = n+i; //依次递增
HuffNode[x2].parent = n+i; //依次递增
HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight; //两个最小权值相加
HuffNode[n+i].lchild = x1; //x1赋给左子节点
HuffNode[n+i].rchild = x2; //x2赋给右子节点
printf ("两个权值最小的数 %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight); //用于测试其正确性
printf ("\n");
}
}
//输出哈夫曼树
void PrintHuffTree(HNodeType HuffNode[MAXNODE],int n){
int i;
printf("\n哈夫曼树各项数据如下表所示:\n");
printf(" 结点i 权值 双亲结点 左子节点 右子节点\n");
for(i=0;i<2*n-1;i++)
printf("\t%d\t%d\t%d\t%d\t%d\n",i,HuffNode[i].weight,HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild);
printf("\n");
}
int main()
{
HNodeType HuffNode[MAXNODE]; //定义一个结点结构体数组
HCodeType HuffCode[MAXLEAF]; //定义一个编码结构体数组
HCodeType cd; //定义一个临时变量来存放求解编码时的信息
int i,j,c,p,n;
printf("请输入叶子结点数:");
scanf("%d",&n);
HuffmanTree(HuffNode, n); //调用哈夫曼
PrintHuffTree(HuffNode, n);
//哈夫曼编码 (自底向上开始(也就是从数组序号为零的结点开始)向上层判断)
for(i=0;i<n;i++)
{
cd.start = n-1; //编码起始位是n-1 ，有n个元素则得到哈夫曼树最高为n-1
c = i; //c的编号(从叶子结点向上)
p = HuffNode[c].parent; //c的双亲结点的编号
while(p != -1) //双亲结点存在
{
if(HuffNode[p].lchild == c)
cd.bit[cd.start] = 0; //左子树编为0
else
cd.bit[cd.start] = 1; //右子树编为1
cd.start--; //求编码的低一位（往前指一位）
c=p; //移动
p=HuffNode[c].parent; //设置下一循环条件（找当前节点的双亲）
}
//保存求出的每个叶结点的哈夫曼编码和编码的起始位
for (j=cd.start+1; j<n; j++)
{
HuffCode[i].bit[j] = cd.bit[j];
}
HuffCode[i].start = cd.start;
}
//输出已保存好的所有存在编码的哈夫曼编码
for (i=0; i<n; i++)
{
printf ("哈夫曼编码%d是: ",i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf ("\n");
}
return 0;
}3.4.5 测试数据
4.课程设计总结
通过这次的课程设计，我们对数据结构与算法分析这门课有了充分的理解。在本学期的数据结构与算法分析课中，我学习了线性表、栈和队列以及串、数组和广义表，并学习了树和二叉树、图、查找、排序等相关知识。我掌握了数据、数据结构和抽象数据类型的基本概念，并从抽象数据类型的角度学习了线性表分为顺序表和链表及其应用，并能设计出线性表的建立、合并、删除等常用算法。我掌握了栈和队列的特点及栈的顺序栈和链栈的进栈和出栈算法、循环队列和链队列的进队和出队算法，并能灵活运用栈和队列、递归算法设计解决实际应用问题。我学会了各种查找的算法，理解了排序算法及其执行的过程，并能选择最优排序办法解决不同问题。实验中我出现过一次次的错误和不顺，但在同组队员和其他同学的共同讨论、对书籍和网络资料的理解以及马老师的帮助下，我们成功地将课程设计实验圆满完成。我在实验中认识到了熟练掌握编程语言对于计算机专业学习的重要性，并感谢学校和老师给我学习数据结构与算法分析这门课程的机会，这对于我日后计算机专业的学习极其重要，我们一定会努力学习，不负韶华。
标签：课程设计,int,top,Enter,next,算法,printf,数据结构,图书 From： https://blog.51cto.com/u_16090538/6407820