需打印出来的文档
- 格式：doc
- 大小：167.50 KB
- 文档页数：11
《数据结构》课程设计报告
班级：09计本（1）班 学号： 09011063 姓名： 张立东
学号：09011069 姓名：朱子涛
1. 问题名称：一元多项式运算
【问题描述】
计算任意两个一元多项式的加法、减法运算。由键盘输入二个多项式的每一项的指数、系数，输出这二个多项式的运算结果。
【存储结构】
链表结构
【主要算法】
void Creatlist(Lnode *L)//创建链表
{p=L;
L->next=NULL;
printf("请输入该表达式的项数\n");
scanf("%d",&m);
printf("请按升幂输入各项指数与系数\n");
for(k=1;k<=m;k++)
{q=(Lnode *)malloc(sizeof(Lnode));
scanf("%d%d",&(q->zhishu),&(q->xishu));
p->next=q;
p=q;
printf("请继续输入\n");}
p->next=NULL;
}
void Addlist(Lnode *LA,Lnode *LB,Lnode *LC)//加法运算
{p=LA->next;q=LB->next;
s=LC;
while(p!=NULL&&q!=NULL)
{if((*p).zhishu<(*q).zhishu)
{r=(Lnode *)malloc(sizeof(Lnode));
r->zhishu=(*p).zhishu;(*r).xishu=(*p).xishu;
p=p->next;s->next=r;s=r;
}
else if((*p).zhishu==(*q).zhishu)
{k=(*p).xishu+(*q).xishu;
if(k==0)
;
else
{r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*p).zhishu;
(*r).xishu=k;
s->next=r;s=r;
}
p=p->next;q=q->next;
}
else {r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*q).zhishu;(*r).xishu=(*q).xishu;
q=q->next; s->next=r;s=r;
}
}
while(p!=NULL)
{r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*p).zhishu;(*r).xishu=(*p).xishu;
p=p->next;s->next=r;s=r;
}
while(q!=NULL)
{r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*q).zhishu;(*r).xishu=(*q).xishu;
q=q->next;s->next=r;s=r;
}
s->next=NULL;
printf("相加后的结果（指数，系数）\n");
t=LC->next;
while(t!=NULL)
{printf("指数%d,系数%d\n",(*t).zhishu,(*t).xishu);
t=t->next;
}
}
void Abstractlist(Lnode *LA,Lnode *LB,Lnode *LC)//减法运算
{p=LA->next;q=LB->next;
s=LC;
while(p!=NULL&&q!=NULL)
{if((*p).zhishu<(*q).zhishu)
{r=(Lnode *)malloc(sizeof(Lnode));
r->zhishu=(*p).zhishu;(*r).xishu=(*p).xishu;
p=p->next;s->next=r;s=r;
}
else if((*p).zhishu==(*q).zhishu)
{k=(*p).xishu-(*q).xishu;
if(k==0)
;
else
{r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*p).zhishu;
(*r).xishu=k;
s->next=r;s=r;
}
p=p->next;q=q->next;
}
else {r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*q).zhishu;(*r).xishu=-(*q).xishu;
q=q->next; s->next=r;s=r;
}
}
while(p!=NULL)
{r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*p).zhishu;(*r).xishu=(*p).xishu;
p=p->next;s->next=r;s=r;
}
while(q!=NULL)
{r=(Lnode *)malloc(sizeof(Lnode));
(*r).zhishu=(*q).zhishu;(*r).xishu=-(*q).xishu;
q=q->next;s->next=r;s=r;
}
s->next=NULL;
printf("相减后的结果（指数，系数）\n");
t=LC->next;
while(t!=NULL)
{printf("指数%d,系数%d\n",(*t).zhishu,(*t).xishu);
t=t->next;
}
} 【测试和结果分析】经过测试运行结果正确。
2. 问题名称：算术表达式求值
【问题描述】
由键盘输入一表达式字符串，该表达式由数字、+、-、*、/、 (、)组成，输出这个表达式的值。
【存储结构】
顺序存储结构
【主要算法】
OperandYype EvaluateExpression()
{InitStack1(&OPTR);Push1('#',&OPTR);
InitStack2(&OPND);
c=getchar();
while(c!='#'||Gettop(OPTR)!='#'){
if((c-48)>=0&&(c-48)<=9)//不是运算符进栈
{a=0;
while((c-48)>=0&&(c-48)<=9)
{a=a*10+c-48;c=getchar();}
Push2(a,&OPND);
}
else
switch(Precede(Gettop(OPTR),c)){
case'<':Push1(c,&OPTR);//栈顶元素优先权低
c=getchar();
break;
case'=':OPTR.top--;//脱括号接受下一个字符
c=getchar();
break;
case'>':Push2(Operate(Poptop2(&OPND),Poptop2(&OPND),Poptop1(&OPTR)),&OPND);栈顶元素优先权高
break;
}
}
printf("\n表达式结果是:%d\n",Poptop2(&OPND));
}
【测试和结果分】
经过测试运行结果正确。
3. 问题名称：哈夫曼编码与译码的应用
【问题描述】
任意输入一串英文字符，针对各字符的出现频率值（可统计获得），给出给各字符哈夫曼编码。
【存储结构】
链式存储结构
【主要算法】
//--------构造赫夫曼树------//
void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
{void Select(HuffmanTree HT,int n,int *s);
int i,m,f,start,s1,s2;char *cd;unsigned int c;
m=2*n-1;
for(i=1;i<=n;i++)
{HT[i].weight=w[i];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;}
for( ;i<=m;i++)
{HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;}
for(i=n+1;i<=m;i++)
{Select(HT,i-1,&s1);
HT[s1].parent=i;
Select(HT,i-1,&s2);
HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//------求赫夫曼编码----//
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++){
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{if(HT[f].lchild==c)
cd[--start]='0';
else cd[--start]='1';}
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);}
free(cd);
}
