最新数据结构课程设计哈夫曼编码(五篇)

下面是小编为大家整理的最新数据结构课程设计哈夫曼编码(五篇),供大家参考。

在日常的学习、工作、生活中，肯定对各类范文都很熟悉吧。范文书写有哪些要求呢？我们怎样才能写好一篇范文呢？以下是小编为大家收集的优秀范文，欢迎大家分享阅读。

数据结构课程设计哈夫曼编码篇一

1.赫夫曼编码器

设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求：

1)将权值数据存放在数据文件(文件名为，位于执行程序的当前目录中)

2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树；

3)编码：利用建好的哈夫曼树生成哈夫曼编码；

4)输出编码（首先实现屏幕输出，然后实现文件输出）；

5)界面优化设计。

代码如下：

#include #include #include #include #define n 200typedef struct htnode

//结构体 { int weight;

char ch;int parent,lchild,rchild;}htnode;typedef char * * hcode;

void save(int n,htnode *ht)

//把权值保存到文件 {

file * fp;

int i;

if((fp=fopen(“”,“wb”))==null)

{

printf(“cannot open filen”);

return;

}

for(i=0;i

if(fwrite(&ht[i].weight,sizeof(struct htnode),1,fp)!=1)

printf(“file write errorn”);

fclose(fp);

system(“cls”);

printf(“保存成功！”);

}

void create_h(int n,int m,htnode *ht)

//建立赫夫曼树，进行编码 {

int w,k,j;char c;for(k=1;k<=m;k++){

if(k<=n)

{

printf(“n请输入权值和字符(用空格隔开): ”);

scanf(“%d”,&w);

scanf(“ %c”,&c);ht[k].ch=c;

ht[k].weight=w;

}

else ht[k].weight=0;

ht[k].parent=ht[k].lchild=ht[k].rchild=0;}

int p1,p2,w1,w2;

for(k=n+1;k<=m;k++){

p1=0;p2=0;

w1=32767;w2=32767;

for(j=1;j<=k-1;j++)

{

if(ht[j].parent==0)

{

if(ht[j].weight

{

w2=w1;p2=p1;

w1=ht[j].weight;

p1=j;

}

else if(ht[j].weight

{

w2=ht[j].weight;

p2=j;

}

}

} ht[k].lchild=p1;ht[k].rchild=p2;ht[k].weight=ht[p1].weight+ht[p2].weight;

ht[p1].parent=k;ht[p2].parent=k;

} printf(“输入成功！”);}

void coding_h(int n,htnode *ht)

//对结点进行译码 { int k,sp,fp,p;char *cd;hcode hc;

hc=(hcode)malloc((n+1)*sizeof(char *));

cd=(char *)malloc(n*sizeof(char));cd[n-1]="";

printf(“************************n”);printf(“char codingn”);

for(k=1;k<=n;k++)

{

sp=n-1;p=k;fp=ht[k].parent;

for(;fp!=0;p=fp,fp=ht[fp].parent)

if(ht[fp].lchild==p)

cd[--sp]="0";

else

cd[--sp]="1";

hc[k]=(char *)malloc((n-sp)*sizeof(char));

strcpy(hc[k],&cd[sp]);

printf(“%c

%sn”,ht[k].ch,hc[k]);

}

printf(“************************n”);free(cd);} void read(int n,htnode *ht)

//从文件中读出数据 {

int i;file * fp;if((fp=fopen(“”,“rb”))==null){

printf(“cannot open filen”);

exit(0);} for(i=0;i

fread(&ht[i].weight,sizeof(struct htnode),1,fp);// printf(“%d n”,ht[i].weight);

} coding_h(n,ht);

fclose(fp);}

void print_h(int m,htnode *ht)

//输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“num weight

par lch rch n”);for(k=1;k<=m;k++){

printf(“%d ”,k);

printf(“

%d”,ht[k].weight);

printf(“

%d”,ht[k].parent);

printf(“

%d”,ht[k].lchild);

printf(“

%dn”,ht[k].rchild);

} printf(“************************n”);}

void decode(int m,htnode *ht)

//对输入的电文进行译码 { int i,j=0;char a[10];char endflag="2";i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!="2"){

if(a[j]=="0")

i=ht[i].lchild;

else i=ht[i].rchild;

if(ht[i].lchild==0)

//ht[i]是叶结点

{

printf(“%c”,ht[i].ch);

i=m;

//回到根结点

}

j++;} printf(“n”);if(ht[i].lchild!=0&&a[j]!="2")

printf(“error”);}

int main()

//主函数 { int n,m,c;htnode ht[n];do {

system(“color 2f”);

//(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt 赫夫曼编译码系统 ttt”);

printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”);

printf(“6.从文件中读出数据nttt7.退出”);

printf(“nnttt请选择:”);

scanf(“%d”,&c);

switch(c)

{

case 1:system(“cls”);printf(“输入多少结点:”);

scanf(“%d”,&n);m=2*n-1;create_h(n,m,ht);break;

case 2:system(“cls”);save(n,ht);break;

case 3:system(“cls”);print_h(m,ht);break;

case 4:system(“cls”);coding_h(n,ht);break;

case 5:system(“cls”);decode(m,ht);break;

case 6:system(“cls”);read(n,ht);break;

case 7:system(“cls”);exit(0);

}

}while(1);return 0;}

运行界面如下：

2.学生成绩管理（链表实现）要求：

实现如下功能：增加、查找、删除、输出、退出。

代码如下：

#include #include #include typedef struct score//定义成绩信息结构体 {

char number[20];char name[20];char chinese[20];char english[20];char math[20];}score;typedef struct node_score

//定义成绩信息链表结点，包括数据域和指针域 {

score data;struct node_score *next;}node_score,*p_node_score;p_node_score headscore;//定义链表的头指针为全局变量 void printscore(score s)//输出信息函数 { printf(“ %10s”,);printf(“ |

%-6s”,);printf(“

|

%-3s”,e);printf(“

|

%-3s”,h);

printf(“ |

%-3sn”,);} void view()//输出函数 {

p_node_score pnodescore;

pnodescore=headscore;printf(“

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩n”);while(pnodescore!= null){

printscore(pnodescore->data);//输出学生信息和成绩信息

pnodescore=pnodescore->next;} } void add(){

p_node_score pnodescore;// 定义一个节点

pnodescore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间

printf(“请输入学号：”);scanf(“%s”,pnodescore->);printf(“请输入姓名：”);scanf(“%s”,pnodescore->);printf(“请输入语文成绩：”);scanf(“%s”,pnodescore->e);printf(“请输入英语成绩：”);scanf(“%s”,pnodescore->h);printf(“请输入高数成绩：”);scanf(“%s”,pnodescore->);if(headscore==null){ //如果头结点为空

headscore=pnodescore;

pnodescore->next=null;} else

{ //如果头结点不为空

pnodescore->next=headscore;

headscore=pnodescore;//将头结点新结点

} } void input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i

add();printf(“输入成功！”);} int delete(){ p_node_score pnodescore,p1;//p1为pnodescore的前驱

p1=headscore;if(p1==null){

printf(“成绩表中没有数据！请先添加数据！n”);

return 0;} char deletenumber[20];

printf(“请数入要删除的学生学号:”);scanf(“%s”,deletenumber);if(strcmp(p1->,deletenumber)==0)

{ //如果要删除的结点在第一个

headscore=p1->next;

pnodescore=p1;

printf(“学号为%s的学生信息已经删除！n”,deletenumber);

return 0;} else

{

pnodescore=p1->next;

while(pnodescore!=null)

{

if(strcmp(pnodescore->,deletenumber)==0)

{

p1->next=pnodescore->next;

printf(“学号为%s的学生信息已经删除！n”,deletenumber);

return 0;

}

else

{ //否则，结点向下一个，p1仍为pnodescore的前驱

p1=pnodescore;

pnodescore=pnodescore->next;

}

} } printf(“没有此学号的学生！”);} int change(){

p_node_score pnodescore;

pnodescore=headscore;if(pnodescore==null){

printf(“成绩表中没有数据！请先添加数据！n”);

return 0;} char editnumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,editnumber);while(pnodescore!=null){

if(strcmp(pnodescore->,editnumber)==0)

{ //用strcmp比较两字符串是否相等，相等则返回0

printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息

printf(“

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩n”);

printscore(pnodescore->data);

printf(“语文新成绩:”);

scanf(“%s”,pnodescore->e);

printf(“英语新成绩:”);

scanf(“%s”,pnodescore->h);

printf(“高数新成绩:”);

scanf(“%s”,pnodescore->);

printf(“成绩已经修改！”);

return 0;

}

pnodescore=pnodescore->next;//如果不相等，pnodescore则指向下一个结点

} printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生

} int find(){

p_node_score pnodescore;

pnodescore=headscore;if(pnodescore==null){

printf(“成绩表中没有数据！请先添加数据！n”);

return 0;} char findnumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,findnumber);while(pnodescore!=null){

if(strcmp(pnodescore->,findnumber)==0)

{

printf(“你要查找的学生成绩信息如下：n”);

printf(“

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩n”);

printscore(pnodescore->data);

return 0;

}

pnodescore=pnodescore->next;} printf(“没有此学号的学生！n”);} int main()

//主函数 { int choice=0;headscore=null;int c;do {

system(“color 2f”);

//(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt 学生成绩管理系统 ttt”);

printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”);

printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”);

printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”);

printf(“nnttt请选择:”);

scanf(“%d”,&c);

switch(c)

{

case 1:system(“cls”);input();break;

case 2:system(“cls”);view();break;

case 3:system(“cls”);add();break;

case 4:system(“cls”);change();break;

case 5:system(“cls”);delete();break;

case 6:system(“cls”);find();break;

case 7:system(“cls”);exit(0);

}

}while(1);return 0;}

运行界面如下：

数据结构课程设计哈夫曼编码篇二

数据结构课程设计

计算机科学与技术2008级1班

课程设计题目：图书借阅管理系统

姓名：

学号：

一．需求分析说明

图书借阅处理过程简述处理过程主要包含：新增图书上架、办理图证、图书查询、借书、还书等。

（1）新增图书上架新书上架时，需要登记新书的：书名、作者、出版社、总册数的信息。

（2）办理图书借阅证读者办理借书证时，需要登记读者（学生）的学号、姓名。（3）图书查询读者按照图书编号查询图书基本信息，并可以得知现还有几册可以借阅。

（4）借书每个学生读者最多借５本书。读者借书时，应登记书号、借书日期（年月日）。

2．数据分析数据处理过程中涉及到两个实体：图书和会员；
各实体应具有的属性如下：图书（书号、书名、作者，总册数）读者（学号、姓名、班级）由于同一种图书可以有多册上架，每个读者最多可以借阅５本书，图书借阅的属性如下：借阅（书号、借书日期）3．功能分析系统功能模块包括：图书增加、图书删除、图书查询、借书、还书；
另外还包括图书信息修改和读者信息修改。

二．基本功能

1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)；

2)会员管理(增加会员、查询会员、删除会员、借书信息)；

3)系统管理（初始化、载入数据、保存数据、退出程序）；

三．程序设计

#include #include #include#define null 0

typedef struct bookinfo{ /////图书结构

int b_code;////图书编号

char b_name[20];/////名称

int b_total;/////总数

int b_out;///借出数 bookinfo* nextbook;//////下一类图书

}bookinfo;

typedef struct memberinfo{ ///会员结构

long m_code;/////会员编号

char m_name[20];////会员名字

int l_codes[6];/////以借书的编号,最多5

memberinfo* nextmember;////下一会员

}memberinfo;

typedef struct system{ ///管理系统结构

bookinfo* bi;

memberinfo* mi;

int booktotal;////图书类库存量

int membertota;/////会员数量

}system;

system* initsystem();/////

void addbook(system*);////增加图书 bookinfo* searchbook(system*,int);////查询图书信息

void delbook(system*);/////删除图书

void brrowbook(system*);///////借书处理

void turnbackbook(system*);////还书处理

void addmember(system*);/////添加会员

void delmember(system*);////删除会员

memberinfo* searchmember(system*,int);/////查询会员信息

void storedata(system*);

void loaddata(system*);

void exitsystem();

void main(){ system* s=initsystem();

int sel;do{

cout<<“ntttt图书管理系统”<

cout<<“ttt******************************”<

cout<<“ttt******************************”<

cout<<“ttt 1.增加图书.t 3.删除图书.t 6.添加会员.t 8.查询会员.t 10.保存数据.t11.退出程序.n”;

cout<<“ttt******************************”<

cout<<“ttt******************************”<

cout<<“请选择:”;

do{

cin>>sel;

if(sel>=1&&sel<=11)break;

cout<<“选择错误!n重新输入:”<

}while(1);

switch(sel){

case 1:addbook(s);break;

case 2:searchbook(s,-1);break;

case 3:delbook(s);break;

case 4:brrowbook(s);;break;

case 5:turnbackbook(s);break;case 6:addmember(s);break;

case 7:delmember(s);break;

case 8:searchmember(s,-1);break;

case 9:loaddata(s);break;

case 10:storedata(s);break;

default:exitsystem();}

}while(1);}

system* initsystem(){

system* s=(system*)malloc(sizeof(system));

s->bi=(bookinfo*)malloc(sizeof(bookinfo));

s->booktotal=0;

s->bi->nextbook=null;

s->mi=(memberinfo*)malloc(sizeof(memberinfo));

s->membertota=0;

s->mi->nextmember=null;

return s;}

void addbook(system* s){ int tempcode;

char sel;

bookinfo* p=s->bi;

bookinfo* t;

bookinfo* m;

int num;do{

cout<<“输入图书编号:”;

cin>>tempcode;

if(m=searchbook(s,tempcode)){

cout<<“这类书以有库存.n输入图书的入库量:”<

cin>>num;

m->b_total+=num;}

else{

t=(bookinfo*)malloc(sizeof(bookinfo));

t->b_code=tempcode;

cout<<“输入图书的名称:”;

cin>>t->b_name;

cout<<“输入图书的入库量:”;

cin>>t->b_total;

t->b_out=0;t->nextbook=p->nextbook;

p->nextbook=t;

s->booktotal++;}

cout<<“添加完毕!”<

cout<<“还要添加吗?(y/n)”;

cin>>sel;

if(sel=="n"||sel=="n"){

cout<<“结束添加”<

return;}

}while(1);}

bookinfo* searchbook(system* s,int code){

bookinfo* bi=s->bi->nextbook;

int bookcode;

if(code==-1){

cout<<“请输入要查询的图书编号:”;

cin>>bookcode;}

else bookcode=code;

while(bi&&bi->b_code!=bookcode)bi=bi->nextbook;if(code==-1){

if(!bi)cout<<“没找到你所要的图书.”<

else {

cout<<“图书编号为:”<b_code<

cout<<“图书名称为:”<b_name<

cout<<“图书库存量为:”<b_total<

cout<<“图书借出量为:”<b_out<

return bi;}

void delbook(system* s){

bookinfo* bi;

bookinfo* pl=s->bi;

memberinfo* memi;

char sel;

int tempcode;

int i;do{

pl=s->bi;bi=pl->nextbook;

memi=s->mi->nextmember;

cout<<“请输入要删除的图书的编号:”;

cin>>tempcode;

while(bi){

if(bi->b_code==tempcode)break;

pl=bi;

bi=bi->nextbook;}

if(bi==0)cout<<“没有找到要删除的图书”<

else{

pl->nextbook=bi->nextbook;

s->booktotal--;

while(memi){

for(i=1;i<=memi->l_codes[0];i++){

if(memi->l_codes[i]==tempcode)break;

}

if(i<=memi->l_codes[0]){

for(;il_codes[0];i++)memi->l_codes[i]=memi->l_codes[i+1];memi->l_codes[0]--;}

memi=memi->nextmember;}

free(bi);}

cout<<“还有图书要删除吗?(y/n)”;

cin>>sel;

if(sel=="n"||sel=="n"){

cout<<“删除图书结束”<

return;}

}while(1);}

void brrowbook(system* s){

bookinfo* bi=s->bi->nextbook;

bookinfo* p;

char sel;

int memcode;

memberinfo* mp;

int tempcode;do{

cout<<“输入要借出的书号:”;

cin>>tempcode;

p=searchbook(s,tempcode);

if(!p){

cout<<“没有找到要借出的图书.”<

else{

cout<<“此书的现存量为”<<(p->b_total-p->b_out)<

if(!(p->b_total-p->b_out))cout<<“没有足够的书了,外借失败.”<

else{

cout<<“请输入会员编号:”;

cin>>memcode;

mp=searchmember(s,memcode);

if(!mp)cout<<“会员编号输入错误,外借失败”<

else{

if(mp->l_codes[0]==5)cout<<“借书量不能超过5本”;

else{

p->b_out++;

mp->l_codes[++mp->l_codes[0]]=tempcode;

cout<<“外借成功.”<

} } } }

cout<<“n还有图书要借出吗?(y/n)”;

cin>>sel;

if(sel=="n"||sel=="n"){

cout<<“外借操作结束.”<

return;}

}while(1);}

void turnbackbook(system* s){

bookinfo* bi=s->bi->nextbook;

bookinfo* p;

memberinfo* mp;

int membercode;

int tempcode;

int i;

char sel;do{

cout<<“输入归还书号:”;cin>>tempcode;

p=searchbook(s,tempcode);

if(!p){

cout<<“书号输入错误.”<

else{

cout<<“此书的现存量为”<<(p->b_total-p->b_out)<

cout<<“请输入会员编号:”;

cin>>membercode;

if(!(mp=searchmember(s,membercode)))cout<<“会员编号输入错误,归还失败”<

else{

p->b_out--;

for(i=1;i<=mp->l_codes[0];i++){

if(mp->l_codes[i]==tempcode)break;

}

while(il_codes[0]){mp->l_codes[i]=mp->l_codes[i+1];

i++;

}

mp->l_codes[0]--;

cout<<“归还成功.”<

cout<<“还有要归还的图书吗?(y/n)”;

cin>>sel;

if(sel=="n"||sel=="n"){

cout<<“归还结束.”<

return;}

}while(1);}

void addmember(system* s){

int tempcode;

char sel;

memberinfo* p=s->mi;

memberinfo* t;do{

cout<<“输入会员编号:”;

cin>>tempcode;

t=(memberinfo*)malloc(sizeof(memberinfo));

t->m_code=tempcode;

cout<<“输入会员姓名:”;

cin>>t->m_name;

t->l_codes[0]=0;

t->nextmember=p->nextmember;

p->nextmember=t;

s->membertota++;

cout<<“添加完毕!”<

cout<<“还要添加吗?(y/n)”;

cin>>sel;

if(sel=="n"||sel=="n"){

cout<<“结束添加”<

return;}

}while(1);}

memberinfo* searchmember(system* s,int code){

memberinfo* bi=s->mi->nextmember;

int membercode;

int i;

if(code==-1){

cout<<“请输入要查询的会员编号:”;

cin>>membercode;}

else membercode=code;

while(bi&&bi->m_code!=membercode)bi=bi->nextmember;

if(code==-1){

if(!bi)cout<<“没找到指定会员.”<

else {

cout<<“会员编号为:”<m_code<

cout<<“名称为:”<m_name<

cout<<“已借的图书有:”<l_codes[0]<<“本.”<

for(i=1;i<=bi->l_codes[0];i++)

cout<l_codes[i]<<" ";cout<

return bi;}

void delmember(system* s){

memberinfo* bi;

memberinfo* pl;

bookinfo* book;

char sel;

int i;

int tempcode;do{

bi=s->mi->nextmember;

pl=s->mi;

cout<<“请输入要删除的会员的编号:”;

cin>>tempcode;

while(bi){

if(bi->m_code==tempcode)break;

pl=bi;

bi=bi->nextmember;}

if(!bi)cout<<“没有找到要删除的会员编号.”;

else{

pl->nextmember=bi->nextmember;

s->membertota--;

for(i=1;i<=bi->l_codes[0];i++){

if(!(book=searchbook(s,bi->l_codes[i]))){

cout<<“删除会员出错!”<

}

else{

book->b_out--;

book->b_total--;

} }

free(bi);}

cout<<“还有会员要删除吗?(y/n)”;

cin>>sel;

if(sel=="n"||sel=="n"){

cout<<“删除会员结束”<

return;}

}while(1);}

void storedata(system* s){

file* fp;

bookinfo* bi=s->bi->nextbook;

if(!(fp=fopen(“booksys”,“wb”))){

cout<<“打开文件booksys失败!”<

exit(0);}

fwrite(&(s->booktotal),sizeof(int),1,fp);

while(bi){

fwrite(bi,sizeof(bookinfo),1,fp);

bi=bi->nextbook;}

memberinfo* mi=s->mi->nextmember;

fwrite(&(s->membertota),sizeof(int),1,fp);

while(mi){

fwrite(mi,sizeof(memberinfo),1,fp);

mi=mi->nextmember;}

fclose(fp);}

void loaddata(system* s){

file* fp;

if(!(fp=fopen(“booksys”,“rb”))){

cout<<“打开文件booksys失败”<

exit(0);}

bookinfo* bi=s->bi;

bookinfo* tempbi;

fread(&(s->booktotal),sizeof(int),1,fp);

for(int i=1;i<=s->booktotal;i++){

tempbi=(bookinfo*)malloc(sizeof(bookinfo));

fread(tempbi,sizeof(bookinfo),1,fp);

bi->nextbook=tempbi;

bi=tempbi;}

bi->nextbook=null;

memberinfo* mi=s->mi;

memberinfo* tempmi;

fread(&(s->membertota),sizeof(int),1,fp);

for(i=1;i<=s->membertota;i++){

tempmi=(memberinfo*)malloc(sizeof(memberinfo));

fread(tempmi,sizeof(memberinfo),1,fp);

mi->nextmember=tempmi;

mi=tempmi;} mi->nextmember=null;

fclose(fp);}

void exitsystem(){

char select;

cout<<“警告: 程序结束后未存储的数据将消失.”<

cout<<“确定要退出吗?(y/n)”;

cin>>select;

if(select=="y"||select=="y")exit(0);

if(select=="n"||select=="n")return;}

四．心得体会

历经大半个学期的努力，我的图书管理系统终于如期完成了。此次做系统给我最大的感触有两个。

第一个就是有了一个利用本专业所学到的知识，来练习，实践的机会。

第二个就是增强了自己的自信心。通过进行图书借阅管理系统的设计，进一步明确了研制一个管理信息系统的方法和思路，将系统开发的各阶段的基本活动贯穿起来，使我更加形象、具体的了解了管理信息系统。系统开发的过程是一个巩固以前所学的计算机知识，掌握新技能的过程。我从这一阶段工作中收益非浅，通过前段时间的课程设计，我能够融会贯通所学的专业基础知识和专业理论知识，培养我们综合运用专业知识分析问题、解决问题的能力及运用工具软件的能力。不仅弄清了以前对系统开发的一些模糊的认识，而且提高了写代码的水平，培养了严谨的工作作风，为今后在工作岗位上用好管好计算机打下了坚实的基础。

在做系统的过程中，我遇到的最大的困难是调程序方面的。在运行程序的过程中经常会出现程序自行中断，需要进行调试的信息。这些信息使得我不得不反复看书，琢磨程序。在一遍一遍的调试之下，程序终于被调通了。那时，我终于可以上上的舒一口气了。

我的系统规模比较小同时由于我的时间和能力等多方面的因素影响，我们的系统也存在一定的缺陷。

数据结构课程设计哈夫曼编码篇三

数 据 结 构

课程设计报告

题 目：
一元多项式计算 专 业：
信息管理与信息系统 班 级：
2012级普本班 学 号：
201201011367 姓 名：
左帅帅 指导老师：
郝慎学 时 间：

一、课程设计题目分析

本课程设计要求利用c语言或c++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。

二、设计思路

本程序采用c语言来完成课程设计。

1、首先，利用顺序存储结构来构造两个存储多项式a(x)和 b(x)的结构。

2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。

3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。

4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。

三、设计算法分析

1、相关函数说明：

(1)定义数据结构类型为线性表的链式存储结构类型变量

typedef struct polynomial{}

(2)其他功能函数

插入函数void insert(polyn p,polyn h)

比较函数int compare(polyn a,polyn b)

建立一元多项式函数polyn create(polyn head,int m)

求解并建立多项式a+b，polyn add(polyn pa,polyn pb)

求解并建立多项式a-b，polyn subtract(polyn pa,polyn pb)2

求解并建立多项式a*b，polyn multiply(polyn pa,polyn pb)

求解并建立多项式a/b，void device(polyn pa,polyn pb)

输出函数输出多项式，void print(polyn p)

销毁多项式函数释放内存，void destroy(polyn p)

主函数，void main（）

2、主程序的流程基函数调用说明(1)typedef struct polynomial {

float coef;

int expn;

struct polynomial *next;} *polyn,polynomial;

在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，polynomial表示的是结构体中的数据对象名。

(2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下：

polyn createpolyn(polyn head,int m)建立一个头指针为head、项数为m的一元多项式

p=head=(polyn)malloc(sizeof(struct polynomial));为输入的多项式申请足够的存储空间

p=(polyn)malloc(sizeof(struct polynomial));建立新结点以接收数据

insert(p,head);调用insert函数插入结点

这就建立一元多项式的关键步骤

(3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void insert(polyn p,polyn h)进行插入操作。(4)加、减、乘、除、的算法实现：

在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；
对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。

(5)另一个子函数是输出函数 printpolyn（）；

输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。

四、程序新点

通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“color e0”);可以函数解决，这里“e0，”e是控制台背景颜色，0是控制台输出字体颜色。

五、设计中遇到的问题及解决办法

首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4

代码编写。

其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。

最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。

六、测试（程序截图）

1.数据输入及主菜单

2.加法和减法模块

3.乘法和除法模块

七、总结

通过本次应用c语言设计一元多项式基本计算程序，使我更加巩固了c语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；
另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。

八、指导老师评语及成绩

附录：（课程设计代码）

#include #include #include typedef struct polynomial {float coef;6

int expn;

struct polynomial *next;} *polyn,polynomial;

//polyn为结点指针类型 void insert(polyn p,polyn h){

if(p->coef==0)free(p);

//系数为0的话释放结点

else

{

polyn q1,q2;

q1=h;q2=h->next;

while(q2&&p->expnexpn)//查找插入位置{

q1=q2;q2=q2->next;}

if(q2&&p->expn==q2->expn)//将指数相同相合并 {

q2->coef+=p->coef;

free(p);

if(!q2->coef)//系数为0的话释放结点

{ q1->next=q2->next;free(q2);}

}

else { p->next=q2;q1->next=p;

}//指数为新时将结点插入

} 7

} //建立一个头指针为head、项数为m的一元多项式 polyn create(polyn head,int m){

int i;

polyn p;

p=head=(polyn)malloc(sizeof(struct polynomial));

head->next=null;

for(i=0;i

{

p=(polyn)malloc(sizeof(struct polynomial));//建立新结点以接收数据

printf(“请输入第%d项的系数与指数:”,i+1);

scanf(“%f %d”,&p->coef,&p->expn);

insert(p,head);

//调用insert函数插入结点

}

return head;} //销毁多项式p void destroy(polyn p){

polyn q1,q2;

q1=p->next;8

q2=q1->next;

while(q1->next)

{

free(q1);

q1=q2;//指针后移

q2=q2->next;

} } //输出多项式p int print(polyn p){

polyn q=p->next;

int flag=1;//项数计数器

if(!q)//若多项式为空，输出0

{

putchar("0");

printf(“n”);

return;

}

while(q)

{

if(q->coef>0&&flag!=1)putchar("+");//系数大于0且不是第一项 9

if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况

{

printf(“%g”,q->coef);

if(q->expn==1)putchar("x");

else if(q->expn)printf(“x^%d”,q->expn);

}

else

{

if(q->coef==1){

if(!q->expn)putchar("1");

else if(q->expn==1)putchar("x");

else printf(“x^%d”,q->expn);}

if(q->coef==-1){

if(!q->expn)printf(“-1”);

else if(q->expn==1)printf(“-x”);

else printf(“-x^%d”,q->expn);}

}

q=q->next;

flag++;

}

printf(“n”);} int compare(polyn a,polyn b){

if(a&&b)

{

if(!b||a->expn>b->expn)return 1;

else if(!a||a->expnexpn)return-1;else return 0;

}

else if(!a&&b)return-1;//a多项式已空，但b多项式非空

else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 polyn add(polyn pa,polyn pb){

polyn qa=pa->next;

polyn qb=pb->next;

polyn headc,hc,qc;

hc=(polyn)malloc(sizeof(struct polynomial));//建立头结点 11

hc->next=null;

headc=hc;

while(qa||qb){

qc=(polyn)malloc(sizeof(struct polynomial));

switch(compare(qa,qb))

{

case 1:

qc->coef=qa->coef;

qc->expn=qa->expn;

qa=qa->next;

break;

case 0:

qc->coef=qa->coef+qb->coef;

qc->expn=qa->expn;

qa=qa->next;

qb=qb->next;

break;

case-1:

qc->coef=qb->coef;

qc->expn=qb->expn;

qb=qb->next;

break;12

}

if(qc->coef!=0)

{

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

else free(qc);//当相加系数为0时，释放该结点

}

return headc;} //求解并建立多项式a-b，返回其头指针 polyn subtract(polyn pa,polyn pb){

polyn h=pb;

polyn p=pb->next;

polyn pd;

while(p)//将pb的系数取反

{ p->coef*=-1;p=p->next;}

pd=add(pa,h);

for(p=h->next;p;p=p->next)

//恢复pb的系数

p->coef*=-1;13

return pd;} //求解并建立多项式a*b，返回其头指针 polyn multiply(polyn pa,polyn pb){

polyn hf,pf;

polyn qa=pa->next;

polyn qb=pb->next;

hf=(polyn)malloc(sizeof(struct polynomial));//建立头结点

hf->next=null;

for(;qa;qa=qa->next)

{

for(qb=pb->next;qb;qb=qb->next)

{

pf=(polyn)malloc(sizeof(struct polynomial));

pf->coef=qa->coef*qb->coef;

pf->expn=qa->expn+qb->expn;

insert(pf,hf);//调用insert函数以合并指数相同的项

}

}

return hf;}

//求解并建立多项式a/b，返回其头指针 void device(polyn pa,polyn pb){

polyn hf,pf,temp1,temp2;

polyn qa=pa->next;

polyn qb=pb->next;

hf=(polyn)malloc(sizeof(struct polynomial));//建立头结点,存储商

hf->next=null;

pf=(polyn)malloc(sizeof(struct polynomial));//建立头结点，存储余数

pf->next=null;

temp1=(polyn)malloc(sizeof(struct polynomial));

temp1->next=null;

temp2=(polyn)malloc(sizeof(struct polynomial));

temp2->next=null;

temp1=add(temp1,pa);

while(qa!=null&&qa->expn>=qb->expn)

{

temp2->next=(polyn)malloc(sizeof(struct polynomial));

temp2->next->coef=(qa->coef)/(qb->coef);

temp2->next->expn=(qa->expn)-(qb->expn);

insert(temp2->next,hf);

pa=subtract(pa,multiply(pb,temp2));15

qa=pa->next;

temp2->next=null;

}

pf=subtract(temp1,multiply(hf,pb));

pb=temp1;

printf(“商是:”);

print(hf);

printf(“余数是:”);

print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“color e0”);polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值null printf(“请输入a(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=create(pa,m);//建立多项式a printf(“n”);printf(“请输入b(x)的项数:”);16

scanf(“%d”,&n);printf(“n”);pb=create(pb,n);//建立多项式b printf(“n”);printf(“**********************************************n”);printf(“*

多项式操作菜单

printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){

printf(”执行操作:“);

scanf(”%d“,&flag);

switch(flag)

{

case 1:

printf(”多项式a(x):“);print(pa);*n”);

printf(“多项式b(x):”);print(pb);

break;

case 2:

pc=add(pa,pb);

printf(“多项式a(x)+b(x):”);print(pc);

destroy(pc);break;

case 3:

pd=subtract(pa,pb);

printf(“多项式a(x)-b(x):”);print(pd);

destroy(pd);break;

case 4:

pf=multiply(pa,pb);

printf(“多项式a(x)*b(x):”);

print(pf);

destroy(pf);

break;

case 5:

device(pa,pb);18

break;

case 6:

exit(0);

break;

} }

destroy(pa);

destroy(pb);}

数据结构课程设计哈夫曼编码篇四

课 程 设 计 任 务 书

信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏一、二、课程设计题目：
迷宫求解、一元多项式

课程设计主要参考资料：
数据结构（c语言版）严蔚敏、吴伟民 编著

数据结构题集（c语言版）严蔚敏、吴伟民、米宁 编著

数据结构课件

三、设计应解决下列各主要问题：

1.实现迷宫的路径求解，并输出最终路径，标记走过却未选择的路径和最终选择的路径

2.对一元多项式实现加法，减法，乘法，求导的计算，并按指数由大到小排序输出

四、课程设计相关附件（如：图纸、软件等）：

五、命题发出日期：2011-3-15 设计应完成日期：
2010-6-20

设计指导教师（签章）：

系主任（签章）：

指导教师对课程设计的评语

指导教师（签章）：

年 月 日

山东科技大学学生课程设计

课程设计1 迷宫问题

一、需求分析：

1.2.3.4.以二维数组maze[][]表示迷宫

用户输入迷宫的数据：构建迷宫，行数m，列数n 迷宫的入口位置和出口位置可由用户随时设定

若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“@”表示“死胡同”，即曾经途径然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。

5.本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数做小量修改，便可求得全部路径。

二、概要设计：

抽象数据类型线性表的定义如下：
⒈ 设计栈的抽象数据类型定义：

adt stack { 数据对象：d={ai:|ai∈positionset,i=1„n,n≥0} 数据关系：r1={|ai-1,ai∈d,i=2,„n} 基本操作：的初始化s gettop(s,&e)素

push(&s,e)pop(&s,e)

返回其值 }adt stack；

⒉ 迷宫的抽象数据类型定义：
adt maze{ 数据对象：d：={aij,start,end|aij,start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0}

数据关系：r={} row={|ai-1,aij∈d i=1,„,m+2,j=1,„,n+2}

第1页

操作结果

构造一个空栈，完成栈用e返回栈s的栈顶元将新的元素e压入栈顶 删除栈顶元素，并用einitstack(&s)

山东科技大学学生课程设计

col={|aijaij-1∈d}

基本操作: masepath(int i,int j,int m,int n,sqstack &s)初始条件：已知目前迷宫状态, 传过起始位置，和终止位置 操作结果：搜索迷宫，用sqstack s返回搜索所得路径。如不存在，返回2 }adt maze

三、详细设计：

#include #include #include #define overflow-2 #define ok 1 #define error 0 #define true 1 #define false 0 #define stack_init_size 100 //存储空间初始量 #define stack_increment 10//存储空间初始增量typedef int status;

typedef struct { int r;int c;}posttype;//坐标位置

迷宫的r行c列 typedef struct { int ord;//通道块在路径上的序号

posttype seat;//通道块的当前坐标位置

int di;//通道块指向下一通道块的方向 }selemtype;//栈元素的类型 typedef struct { selemtype *base;//栈底指针

selemtype *top;//栈顶指针

int stacksize;//栈的最大容量 }stack;//栈的类型

第2页 山东科技大学学生课程设计

status initstack(stack &s)//初始化栈 { =(selemtype *)malloc(stack_init_size*sizeof(selemtype));if(!)

exit(overflow);//存储分配失败;=;ize=stack_init_size;return ok;}//initstack

status stackempty(stack s)//判断栈是否为空,如果为空返回true,否则返回false { if(==)

return true;

return false;}//stackempty

status push(stack &s,selemtype e)//插入元素为e的栈顶元素 { if(->=ize){

=(selemtype*)realloc(,(ize+stack_increment)*sizeof(selemtype));

if(!)

exit(overflow);

=+ize;

ize+=stack_increment;} *++=e;return ok;}//push

status pop(stack &s,selemtype &e)//删除栈顶元素存入e { if(==)

return error;e=*--;

第3页 山东科技大学学生课程设计

return ok;}//pop

status destroystack(stack &s)//销毁栈 { free();=;return ok;}//destroystack

// #define maxlen 20//迷宫包括外墙最大行列数目 typedef struct{

int r;

int c;

char adr[maxlen][maxlen];//可取" ""*" "@" "#" }mazetype;

//迷宫类型

status initmaze(mazetype &maze){ //初始化迷宫若成功返回true,否则返回false

int m,n,i,j,k=1;

printf(“输入迷口的行数和列数: ”);

scanf(“%d%d”,&maze.r,&maze.c);//迷宫行和列数

for(i=0;i<=maze.c+1;i++){//迷宫行外墙

[0][i]="#";

[maze.r+1][i]="#";

}//for

for(i=0;i<=maze.r+1;i++){//迷宫列外墙

[i][0]="#";

[i][maze.c+1]="#";

}

for(i=1;i<=maze.r;i++)

for(j=1;j<=maze.c;j++)

[i][j]=" ";//初始化迷宫

printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k);

scanf(“%d%d”,&m,&n);

k++;

while(m!=0)

{

if(m>maze.r || n>maze.c)//越界

第4页 山东科技大学学生课程设计

exit(error);

[m][n]="#";//迷宫障碍用"#"标记

printf(“输入障碍物%d的坐标(以坐标(0,0)结束输入): ”,k);

scanf(“%d%d”,&m,&n);

k++;

}

return ok;}//initmaze

status pass(mazetype maze,posttype curpos){ //当前位置可通则返回ture,否则返回false

if([curpos.r][curpos.c]==" ")//可通

return true;

else

return false;}//pass

status footprint(mazetype &maze,posttype curpos){ //若走过并且可通返回true,否则返回false //在返回之前销毁栈s

[curpos.r][curpos.c]="*";//“*”表示可通

return ok;}//footprint

posttype nextpos(posttype &curpos,int i){ //指示并返回下一位置的坐标

posttype cpos;

cpos=curpos;

switch(i){

//1.2.3.4分别表示东,南,西,北方向

case 1 : cpos.c+=1;break;

case 2 : cpos.r+=1;break;

case 3 : cpos.c-=1;break;

case 4 : cpos.r-=1;break;

default: exit(error);

}

return cpos;}//nextpos

status markprint(mazetype &maze,posttype curpos){ //曾走过但不是通路标记并返回ok

第5页 山东科技大学学生课程设计

[curpos.r][curpos.c]="@";//“@”表示曾走过但不通

return ok;}//markprint

void printmaze(mazetype &maze)//将最后标记好的迷宫输出 { int i,j;printf(“n输出迷宫的路径:n”);for(i=0;i<=maze.c+1;i++)

printf(“%4d”,i);//输出列数

printf(“n”);for(i=0;i<=maze.r+1;i++){

printf(“%d”,i);//输出行数

for(j=0;j<=maze.c+1;j++)

printf(“%4c”,[i][j]);//输出迷宫

printf(“n”);} }//printmaze

status mazepath(mazetype &maze,posttype start,posttype end)//若迷宫从入口start到end的通道则求得一条存放在栈中 { stack s;//初始化栈

posttype curpos;int curstep;selemtype e;initstack(s);curpos=start;curstep=1;do {

if(pass(maze,curpos))//当前位置可通过而未曾走过留下足迹

{

footprint(maze,curpos);

=curstep;=curpos;=1;

push(s,e);//加入栈路径中

if(curpos.r==end.r && curpos.c==end.c)//到达出口返回true

{

第6页 山东科技大学学生课程设计

if(!destroystack(s))

exit(overflow);

else return true;

}

else

{

curpos=nextpos(curpos,1);//下一位置是当前位置

curstep++;//探索下一步

}

}//if

else//当前位置不能通过

{

if(!stackempty(s))

{

pop(s,e);//提取前一位置

while(==4 &&!stackempty(s))//4个方向都不能通过则留下记号@ 提取前一个位置进行判断是否是能通过

{

markprint(maze,);

pop(s,e);

}

if(<4)//换下一个方向探索

设定当前位置为该新方向上的邻位

{

++;

push(s,e);

curpos=nextpos(,);

}

}//if

} }while(!stackempty(s));if(!destroystack(s))

exit(error);else return false;}//mazepath

int main(){ mazetype maze;posttype start,end;char c;

第7页 山东科技大学学生课程设计

do {

printf(“**********迷宫求解**********n”);

if(!initmaze(maze))

{

printf(“n 初始化迷宫失败！!”);

exit(error);

}

do

{

printf(“n请输入入口的坐标:”);

scanf(“%d%d”,&start.r,&start.c);//输入入口坐标

if(start.r>maze.r || start.c>maze.c)

printf(“n输入错误,请重新输入入口的坐标！n”);

continue;

}

while(start.r>maze.r || start.c>maze.c);

do

{

printf(“n请输入出口的坐标:”);//输入出口的坐标

scanf(“%d%d”,&end.r,&end.c);

if(end.r>maze.r || end.c>maze.c)

printf(“n输入错误,请重新输入出口坐标！n”);

continue;

}

while(end.r>maze.r || end.c>maze.c);

if(!mazepath(maze,start,end))

printf(“n不能找到一条路径！!n”);

else printmaze(maze);//输出迷宫

printf(“是否要继续?(y/n):”);

scanf(“%s”,&c);} while(c=="y" || c=="y");}。测试结果：

第8页

四、山东科技大学学生课程设计

课程设计2 一元多项式

一、需求分析：

第9页 山东科技大学学生课程设计

1.2.3.首先定义一个结构体，其中定义一元多项式中的两个参数:系数和指数和链表中结点的指针域；

然后一一罗列每个在主程序中用到的函数，并一一实现；

最后在主程序中主要完成用户的输入和相关函数的调用。

二、概要设计：

void insert(ploylist *head,ploylist *input)

//查找位置插入新链节的函数，且让输入的多项式呈降序排列 ploylist *creat(char ch)//输入多项式

ploylist *add(ploylist *head,ploylist *pre)//多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头

ploylist *sub(ploylist *head,ploylist *pre)//多项式相减

ploylist *mul(ploylist *head,ploylist *pre)//多项式相乘

ploylist *der(ploylist *head)//多项式求导

void print(ploylist *fun)//输出多项式，fun指要输出的多项式链表的表头 void start()//用户选择界面

三、详细设计：

#include #include typedef struct node//定义节点类型 { float coef;

//多项式的系数

int expn;

//多项式的指数

struct node * next;//结点指针域 }ploylist;void insert(ploylist *head,ploylist *input)

//查找位置插入新链节的函数，且让输入的多项式呈降序排列 {

ploylist *pre,*now;

int signal=0;

pre=head;

第10页 山东科技大学学生课程设计

if(pre->next==null){pre->next=input;} //如果只有一个头结点，则把新结点直接连在后面

else {

now=pre->next;//如果不是只有一个头结点，则设置now指针

while(signal==0)

{

if(input->expn < now->expn)

{

if(now->next==null)

{

now->next=input;

signal=1;

}

else

{

pre=now;

now=pre->next;//始终让新输入的数的指数与最后一个结点中的数的指数比较，小于则插在其后面

}

}

else if(input->expn > now->expn)

{

input->next=now;

pre->next=input;

signal=1;

}//若新结点中指数比最后一个结点即now中的指数大，则插入now之前

else//若指数相等则需合并为一个结点，若相加后指数为0则释放该结点

{

now->coef=now->coef+input->coef;

signal=1;

free(input);

if(now->coef==0)

{

pre->next=now->next;

free(now);

}

}//else } //while

第11页 山东科技大学学生课程设计

}//else }//void

ploylist *creat(char ch)

//输入多项式 {

ploylist *head,*input;

float x;

int y;

head=(ploylist *)malloc(sizeof(ploylist));

//创建链表头

head->next=null;

scanf(“%f %d”,&x,&y);//实现用户输入的第一个项，包括其指数和系数

while(x!=0)

{

input=(ploylist *)malloc(sizeof(ploylist));//创建新链节

input->coef=x;

input->expn=y;

input->next=null;

insert(head,input);//每输入一项就将其排序，是的链表中多项式呈降序排列

scanf(“%f %d”,&x,&y);

} return head;}

ploylist *add(ploylist *head,ploylist *pre)

//多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头 {

ploylist *input;

int flag=0;

while(flag==0)

{

if(pre->next==null)

flag=1;//若该链表为空，则无需进行加法运算，跳出循环

else

{

pre=pre->next;

input=(ploylist *)malloc(sizeof(ploylist));

第12页 山东科技大学学生课程设计

input->coef=pre->coef;

input->expn=pre->expn;

input->next=null;

insert(head,input);// 把g(x)插入到f(x）中，相当于两者相加，结果保存于f(x)

}

} return head;}

ploylist *sub(ploylist *head,ploylist *pre)//多项式相减 {

ploylist *input;

int flag=0;

while(flag==0)

{

if(pre->next==null)

flag=1;

else

{

pre=pre->next;

input=(ploylist *)malloc(sizeof(ploylist));

input->coef=0-pre->coef;//将第二个多项式里的数变为其相反数，再用和加法一样的方法实现减法

input->expn=pre->expn;

input->next=null;

insert(head,input);

}

} return head;}

ploylist *mul(ploylist *head,ploylist *pre)//多项式项乘 { ploylist *hf,*pf,*qa,*qb;

qa = head-> next;

qb = pre-> next;//定义指针指向表头后一个元素，即链表中第一个元素

hf =(ploylist *)malloc(sizeof(ploylist));//新创建一个结点，当做表头

hf-> next = null;for(;qa;qa = qa-> next)

第13页 山东科技大学学生课程设计

{

for(qb = pre-> next;qb;qb= qb-> next)//用两个循环，实现两个多项式之间每个项相乘，结果用insert函数进行排序与合并

{

pf =(ploylist *)malloc(sizeof(ploylist));

pf-> coef = qa-> coef * qb-> coef;//系数相乘

pf-> expn = qa-> expn + qb-> expn;//指数相加

pf-> next = null;

insert(hf,pf);

} } return hf;}

ploylist *der(ploylist *head)//多项式求导 { ploylist *p;p = head-> next;while(p){

p-> coef = p-> coef * p-> expn;

p-> expn = p-> expn--;

p = p-> next;} return head;}//将多项式的每项系数和指数相乘得到新的系数，指数减一得到新的指数即完成求导

void print(ploylist *fun)//输出多项式，fun指要输出的多项式链表的表头 {

ploylist *printing;

int flag=0;

printing=fun->next;

if(fun->next==null)//若为空表，则无需输出

{

printf(“0n”);

return;

}

while(flag==0)

{

第14页 山东科技大学学生课程设计

if(printing->coef>0&&fun->next!=printing)

printf(“+”);

if(printing->coef==1);

else if(printing->coef==-1)

printf(“-”);

else

printf(“%f”,printing->coef);

if(printing->expn!=0)printf(“x^%d”,printing->expn);

else if((printing->coef==1)||(printing->coef==-1))

printf(“1”);

if(printing->next==null)

flag=1;

else

printing=printing->next;

} printf(“n”);}

void start()//用户选择界面 { printf(“

#n”);

printf(“

用户选择界面

n”);

printf(“ ************************************n”);

printf(“ *

*n”);

printf(“ *

1.两个一元多项式相加

*n”);

printf(“ *

2.两个一元多项式相减

*n”);

printf(“ *

3.两个一元多项式相乘

*n”);

printf(“ *

4.对一个一个一元多项式求导 *n”);

printf(“ *

0.退出系统

*n”);

printf(“ *

*n”);

printf(“ ************************************n”);

printf(“

n”);

printf(“ 注释：输入多项式格式（可无序）：系数1 指数1 系数2 指数2 „„，并以0 0 结束：n”);

printf(“

n”);

printf(“ 请选择操作: ”);}

int main(){ ploylist *f,*g,*pf,*hf,*p;

第15页 山东科技大学学生课程设计

int sign=-1;

start();

while(sign!=0)

{

scanf(“%d”,&sign);

switch(sign)

{

case 0:

break;

case 1://多项式相加

{

printf(“ 你选择的操作是多项式相加:n”);

printf(“ 请输入第一个多项式f(x)：”);

f=creat("f");

printf(“ 第一个多项式为：f(x)=”);

print(f);

printf(“ 请输入第二个多项式g(x)：”);

g=creat("g");

printf(“ 第二个多项式为：g(x)=”);

print(g);

printf(“ 结果为：f(x)=f(x)+g(x)=”);

f=add(f,g);

print(f);

printf(“nn”);

printf(“ 继续请选择相应操作，;

}

case 2://多项式相减

{

printf(” 你选择的操作是多项式相减:n“);

printf(” 请输入第一个多项式f(x)：“);

f=creat("f");

printf(” 第一个多项式为：f(x)=“);

print(f);

printf(” 请输入第二个多项式g(x)：“);

g=creat("g");

printf(” 第二个多项式为：g(x)=“);

print(g);

printf(” 结果为：f(x)=f(x)-g(x)=“);

f=sub(f,g);

print(f);

”);第16页

山东科技大学学生课程设计

printf(“nn”);

printf(“ 继续请选择相应操作，退出请按0.”);

break;

}

case 3://多项式相乘

{

printf(“ 你选择的操作是多项式相乘:n”);

printf(“ 请输入第一个多项式f(x)：”);

f=creat("f");

printf(“ 第一个多项式为：f(x)=”);

print(f);

printf(“ 请输入第二个多项式g(x)：”);

g=creat("g");

printf(“ 第二个多项式为：g(x)=”);

print(g);

printf(“ 结果为：f(x)=f(x)* g(x)=”);

pf=mul(f,g);

print(pf);

printf(“nn”);

printf(“ 继续请选择相应操作，退出请按0.”);

break;

}

case 4://多项式求导

{

printf(“您选择的是对一个一元多项式求导：n”);

printf(“请输入一个一元多项式：”);

f = creat("f");

printf(“这个多项式为：f(x)= ”);

print(f);

printf(“求导结果为：f(x)=f"(x)= ”);

f=der(f);

print(f);

printf(“nn”);

printf(“ 继续请选择相应操作，退出请按0.”);

break;

}

}//swith

}//while }//void

四、测试结果：

第17页 山东科技大学学生课程设计

第18页

数据结构课程设计哈夫曼编码篇五

课程设计题目

1、运动会分数统计

任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；
取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；
哪些取前五名或前三名由学生自己设定。（m=10 , w=8 , n=15）功能要求：

1).可以输入各个项目的前三名或前五名的成绩；

2).能统计各学校总分（用链表）；

3).可以按学校编号、学校总分、男女团体总分排序输出（快速、基数）；

4).可按学校编号查询学校某个项目的情况；
可按项目编号查询取得前三或前五名的学校。

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。

测试数据：要求使用

1、全部合法数据；

2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

2、迷宫求解

任务：可以读入一个任意大小的迷宫数据，分别用广度和深度搜索的方法求出一条走出迷宫的路径，并将路径输出（最佳路径）；

要求：以较为直观的方式显示结果

3、huffman编码

任务 ：对一篇英文文章，统计各字符出现的次数，实现huffman编码；

要求：输出每个字符出现的次数和编码，其中求最小权值要求用堆实现；

4、营业窗口队列模拟

任务：实现具有n（n=3）个窗口的现实队列模拟，统计每人的等待时间。要求：

1).随机产生顾客的到达时间和服务时间存盘。2).利用存盘数据实现队列的插入和删除。2).当有顾客离开时，根据队列长度调整队尾。3).考虑顾客中途离队的情况。4).考虑顾客具有优先级的情况。

5、公交线路提示

任务：建立南京主要公交线路图。要求：输入任意两站点，给出最佳的乘车线路和转车地点。

6、家谱管理系统

任务：实现具有下列功能的家谱管理系统 功能要求：

1).输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。

2).实现数据的存盘和读盘。3).以图形方式显示家谱。

4).显示第n 代所有人的信息。

5).按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。6).按照出生日期查询成员名单。7).输入两人姓名，确定其关系。8).某成员添加孩子。

9).删除某成员（若其还有后代，则一并删除）。10).修改某成员信息。

11).按出生日期对家谱中所有人排序。

12).打开一家谱时，提示当天生日的健在成员。

要求：建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用

1、全部合法数据；

2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

7、排序算法比较

设计要求：利用随机函数产生10个样本，每个样本有50000随机整数，利用直接插入排序、折半插入排序，表插入排序，希尔排序，起泡排序、快速排序、选择排序、堆排序，归并排序，基数排序十种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间（统计为图表坐标形式）。

8、算术表达式求值 [问题描述]

一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。

9、电子小字典

基本要求：建立一个微型电子字典，实现生词的加入，单词的查找、删除，修改等操作。

数据结构：键树

10、校园导游程序

[问题描述]用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求]（1）查询各景点的相关信息；

（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。

（4）增加、删除、更新有关景点和道路的信息。

11、稀疏矩阵相乘

任务：以三元组形式存储稀疏矩阵，实现矩阵相乘。

12、平衡二叉树

任务：平衡二叉树的建立、结点的插入和删除。

13、b-树

任务：3阶b-树的结点的插入和删除。

14、hash表

任务：以班级学生姓名（拼音）为关键字，建立hash涵数，实现hash表存储，用链地址方法解决冲突。

15、„„（自选合适的题目）

成绩评定细则：

1.正确性：程序是否可以运行，结果是否正确（20分）2.功能的完备性：是否实现要求的所有子功能（20分）

3.课程设计报告中的算法说明的清晰程度，课程设计报告中总结的深刻程度（20分）4.独立完成情况(40分）总计：100分

加分项目：

1.健壮性：异常处理的情况

2.可读性：代码编写是否规范，是否便于阅读。如函数、变量命名，‘{ }’的缩进，关键位置适量注释等

3.功能的完善：除要求实现的功能外，完成了其它的功能，实现了功能的完善 4.界面的设计：可视化界面，或者交互良好的dos界面 5.……（自荐加分项目）

代码量要求：>=1000行。

代码总量 = 课设题目1 代码量 + 课设题目2 代码量…… 若代码总量低于1000行，则成绩按比例打折。

编程语言：c或c++语言

编程环境：microsoft visual c++ 6.0

检查方式: 1.总体上检查程序的代码量，正确性，可读性，健壮性，功能的完备性,代码量，程序的结构是否合理；
局部检查三个以上函数块 2.检查程序时同时检查课程设计报告的电子文档

时间安排：
上机时间安排 课程设计报告上交时间 3 课程设计检查时间

课程设计报告要求：

1.所有的课程设计报告，均要有封面，包括：课题名称、班级、学号、学生姓名、成绩和指导教师；

2.给出自己采用的数据结构；

3.给出算法设计思想；

4.给出实现的源程序，并在必要的代码处给出注释；

5.给出测试数据和结果；

6.给出算法的时间复杂度、另外可以提出算法的改进方法；

7.给出结束语：说明完成课程设计的情况，心得体会；
课程设计报告的电子文档在上机检查程序时一并检查；
书面文档在指定的时间内上交。