第一篇:1长整数四则运算+数据结构课程设计
[实验名称] 长整数四则运算
[需求分析] 设计一个实现任意长的整数进行减法运算的演示程序,要求完成长整数的加减运算,乘除运算可选做。在这里长整数没有范围限制,可任意长。运算后的进位、借位等都要进行正确处理,可实现动态的输入,实时的输出。
测试数据:0、0; 输出“0”
2345,6789、-7654,3211; 输出“1,0000,0000”
1,0000,0000,0000、9999,9999; 输出“9999,0000,0001” 1,0001,0001、;1,0001,0001; 输出“0”
自选数据:1,2345,6789;9,8765,4321; 输出“11,1111,1110”
[概要设计] 数据结构
利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字,即不超过9999的非负整数。双向链表有头指针,它的data值存储长整数的符号,1为正,-1为负,0代表长整数为0;它的over值存储除头节点外节点的个数。其他节点的data值存储四位整数,over存储该四位整数溢出0~~9999范围的情况,一般over>0表示四位数超出9999,over<0表示四位数小于0。
选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算,需要对长整数进行存储,所以选择用链表对长整数存储,又由于存储的顺序是从左到右,而运算的顺序则是从右到左,这样位了操作方便选择循环链表,在运算过程中有进位和借位的操作,所以最终选择双向循环链表的数据结构。
[详细设计] typedef struct DoubleNode //定义链表元素
void InitNode(DLNode **head)//初始化链表 int InsertNode(DLNode *head,int n,DataType x)//向链表第N个位置插入元素X int digit(int n)//判断整数N有几位
void PrintNode(DLNode *head)//打印链表 void DestroyNode(DLNode **head)//销毁链表 void add(DLNode *h1,DLNode *h2)//两数相加 void jian(DLNode *h1,DLNode *h2)//两数相减 int main()//入口函数
[调试分析] 调试过程中的困难:
在数据的运算中,应为是根据数的大小来选择运算的,所以过程相对比较繁琐。而且对于双向链表的两个指针的定位以及链表的插入和删除等操作花费的较多的时间。在这查阅参照了大量的网络资料。
[测试结果] 1)输入0和0做加法运算,输出“0”,结果如下图:
2)输入2345,6789和-7654,3211做减法运算,输出“1,0000,0000”,结果如下图:
3)输入1,0000,0000,0000和9999,9999做减法运算,输出“9999,0000,0001”,结果如下图:
4)输入1,0001,0001和1,0001,0001做减法运算,输出“0”,结果如下图:
5)输入1,2345,6789 和9,8765,4321做减法运算,结果如下图:
[心得体会] 关于实验本身的收获是掌握了双向链表。而实验外的就是更好的利用了网路资源,通过网络的搜索引擎等。加深了自己在这方面知识的补充。并且在于同学交流中分析了彼此算法的优劣程度。我觉得这是本次实验最大的收获。
[源代码]
#include “iostream.h” #include
printf(“0”);printf(“%d”,p->data);p=p->next;} printf(“n”);} void DestroyNode(DLNode **head){ DLNode *p,*p1;p=(*head)->next;while(p!=*head){ p1=p;p=p->next;free(p1);} free(p);head=NULL;} void add(DLNode *h1,DLNode *h2)//两数相加 { DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2)//每个链表元素相加 { p1->data+=p2->data;p1=p1->prior;p2=p2->prior;} p1=h1->prior;while(p1!=h1->next)//处理链表元素 { if(p1->data>=10000){ p1->prior->data+=p1->data/10000;p1->data%=10000;} if(p1->data<0)//处理负数 { if(h1->next!=0){ p1->prior->data-=1;p1->data+=10000;} } p1=p1->prior;} if(h1->next->data>=10000)//处理最前面的数 { InsertNode(h1,0,h1->next->data/10000);h1->next->next->data%=10000;} if(h1->data<=-10000){ InsertNode(h1,0,h1->next->data/10000);h1->next->next->data%=-10000;} PrintNode(h1);} void jian(DLNode *h1,DLNode *h2)//两数相减 { DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2)//每个链表元素相减 { p1->data-=p2->data;p1=p1->prior;p2=p2->prior;} p1=h1->prior;while(p1!=h1->next)//处理链表元素 { if(p1->data>=10000){ p1->prior->data+=p1->data/10000;p1->data%=10000;} if(p1->data<0)//处理负数 { if(h1->next!=0){ p1->prior->data-=1;p1->data+=10000;} } p1=p1->prior;} if(h1->next->data>=10000)//处理最前面的数 { InsertNode(h1,0,h1->next->data/10000);h1->next->next->data%=10000;} if(h1->data<=-10000){ InsertNode(h1,0,h1->next->data/-10000);h1->next->next->data%=-10000;} PrintNode(h1);} int main()//入口函数 { DLNode *head1,*head2;InitNode(&head1);InitNode(&head2);char data1[N],data2[N];char d1[10],d2[10];int i,j,k;int xun;while(1){ printf(“输入数据:n”);scanf(“%s %s”,data1,data2);InitNode(&head1);InitNode(&head2);i=0;k=0;while(data1[i]!=';')//将数1用链表储存 { for(j=0;j<10;j++)d1[j]=0;j=0;while(data1[i]!=';'&&data1[i]!=',')d1[j++]=data1[i++];if(data1[i]==',')i++;if(data1[0]=='-')//处理正负数
j=-(int)fabs(atoi(d1));else j=atoi(d1);InsertNode(head1,k++,j);} i=0;k=0;while(data2[i]!=';')//将数2用链表储存 { for(j=0;j<10;j++)
d2[j]=0;j=0;while(data2[i]!=';'&&data2[i]!=',')d2[j++]=data2[i++];if(data2[i]==',')i++;if(data2[0]=='-')//处理正负数
j=-(int)fabs(atoi(d2));else j=atoi(d2);InsertNode(head2,k++,j);} printf(“选择加减法:1—加法,2-减法n”);scanf(“%d”,&xun);switch(xun){ case 1:if(strlen(data1)>strlen(data2))//较长的数作为被加数
add(head1,head2);else add(head2,head1);break;case 2:if(strlen(data1)>strlen(data2))//较长的数作为被减数
jian(head1,head2);else jian(head2,head1);break;default:break;} DestroyNode(&head1);DestroyNode(&head2);} return 0;}
第二篇:数据结构课程设计(矩阵的运算)
数 据 结 构
课程设计报告
题 目: 专 业: 班 级: 学 号: 姓 名: 指导老师: 时 间:
一、课程设计题目及所涉及知识点
设计题目是“矩阵的运算”,所涉及的知识点主要是:
1、数据结构中的对于结构体的定义,用typedef struct来实现,根据所设计的问题在结构体里面定义数据类型及其变量,用define定义数组的大小,然后利用typedef 来实现对于变量的未知类型确定正确的类型。
2、利用数组的形式来储存数据,在实现不同操作过程中,有的用一维结构体数组(三元组顺序表)来存储,有的用二维数组来储存。
3、转置的过程中利用的是快速转置的方法,附设了num和cpot两个辅助变量。
4、矩阵的加法、减法、乘法、逆运算的基本算法方式。
5、通过调用每个函数,来实现每个算法的功能。
二、课程设计思路及算法描述
设计思路:
1、首先是对于转置的考虑,要运用快速转置的方法实现,必须用三元组顺序表来储存数据,所以在第一个结构体中存在int类型的行数(mu)列数(nu)以及非零元素的个数(tu);然后第二个结构体中分别有非零元素的行下标(i)、列下标(j)和元素数值(e),最后在第一个结构体中实现对第二个结构体成为数组结构体类型。
2、对于其余加法、减法、乘法和逆运算则是运用另一个结构体来实现,里面只有矩阵的行数、列数和一个二维数组(用float来定义类型)。
3、在main函数里面,来实现对于数据的输入操作,利用if语句进行选择来执行操作,利用do……while语句来实现功能的循环操作。
4、分五个函数调用分别来实现转置、加法、乘法、和逆运算,每个里面都有最终输出结果的方式。
算法1:矩阵的转置
输入:mu中存放矩阵的行数,tu存放矩阵的列数,i接收行下标的数值,j接收列下标的数值,e来存储数据。输出:转置后的新矩阵。
输入两行两列数据,在第二行第一列中有个数据为12,其余都为0,则输出的结果为第一行第二列数据为12,其余为0。
算法2:矩阵的加法运算 输入:i中存放矩阵的行数,j中存放矩阵的列数,二维数组b中存放每个数据。
输出:矩阵加完后的另一个新矩阵。
输入两个两行三列的矩阵,在第一个矩阵里面第一行第一列有个数据20,其余为0,在第二个矩阵里面第一行第二列中有个数据30,其余为0,则输出的结果为一个两行三列的矩阵,其中第一行第一列数据为20,第一行第二列数据为30,其余为0。
算法3:矩阵的减法运算
输入:i中存放矩阵的行数,j中存放矩阵的列数,二维数组b中存放每个数据。
输出:矩阵相减后的另一个新矩阵。
输入两个两行三列的矩阵,在第一个矩阵里面第一行第一列有个数据20,其余为0,在第二个矩阵里面第一行第一列中有个数据30,其余为0,则输出的结果为一个两行三列的矩阵,其中第一行第一列数据为-10,其余为0。
算法4:矩阵的乘法运算
输入:i中存放矩阵的行数,j中存放矩阵的列数,二维数组b中存放每个数据。
输出:矩阵加完后的另一个新矩阵。
输入两行两列的矩阵,第一个矩阵里面第一行第一列有个数据2第二列有个数据3,其余为0,在第二个矩阵里面第一行第一列有个数据2第二列中有个数据3,其余为0,则输出的结果为一个两行两列的矩阵,其中第一行第一列数据为4,第二列为6,第一行第二列数据为30,其余为0。
算法五:矩阵的逆运算
输入:i中存放矩阵的行数,j中存放矩阵的列数,二维数组b中存放每个数据。
输出:矩阵进行逆运算完后的另一个新矩阵。
输入三行三列的矩阵,第一个矩阵里面第一行第一列有个数据3个数据分别为1,2,3;第二行的数据分别为2,2,1;第三行的暑假分别为3,4,3;则输出的结果为三行三列矩阵,其中第一行的数据为1,3,-2;第二行的数据分别为-1.5,-3,2.5;
第三行的数据分别为1,1,-1。
三、课程设计中遇到的难点及解决办法
1、在转置的过程中,要求把转置后的矩阵输出出来,因为用的是三元组顺序表的存储形式,所以不知道怎么去实现,然后通过进一步思考,运用先把一个矩阵存入零元素,然后在对其进行更改,最后完成了此项的工作。
2、就是对于矩阵的乘法运算和逆运算,掌握的不够熟练,先是通过书籍对于矩阵的乘 法和逆运算得到更深的了解,然后通过一步步写程序最后实现了矩阵的乘法运算和逆运算。
四、总结
通过此次课程设计,让我对于编程有了更深的认识,老师的精心指导让我学会到了很多,不仅仅是代码,最主要的让我的思维开阔了很多,在这个过程中,通过不断的尝试,不断的修改,最终克服了困难,完成了自己的任务,心里有种无比的喜悦,但同时又感觉到了自己的知识面的狭隘,还有好多知识的海洋还没有畅游,等待自己将是一回更大的考验。
对于现在的自己,对学习程序还是有很大的兴趣,它让我体验到了很多的快乐,我要进步跟进现在的课程,努力去发展自己,按照老师说的最主要的是具有了编程的思想,则具有了编程的能力,我想我可以成功完成自己的目标。
五、附录—主要源程序代码及运行结果
1、主要源程序代码: # include
elemtype e;}triple;typedef struct { triple data[maxsize+1];//非零元三元组,data[0]未用 int mu,nu,tu;//矩阵的行数、列数和非零元个数 }sqlist;void zhuanzhi(sqlist s1,tsmatrix &l2)//矩阵的转置
{ sqlist s2;int col,t9,p,q,a1,b1;int num[100],copt[100];s2.mu=s1.mu;s2.nu=s1.nu;s2.tu=s1.tu;if(s2.tu>0){ for(col=1;col<=s1.nu;++col)num[col]=0;for(t9=1;t9<=s1.tu;++t9)
++num[s1.data[t9].j];//求s1中每一列含非零元个数
copt[1]=1;//求第col列中第一个非零元在s2.data中序号
for(col=2;col<=s1.nu;++col)copt[col]=copt[col-1]+num[col-1];for(p=1;p<=s1.tu;++p)
{ col=s1.data[p].j;
q=copt[col];
s2.data[q].i=s1.data[q].j;s2.data[q].j=s1.data[q].i;s2.data[q].e=s1.data[q].e;++copt[col];
l2.b[s2.data[q].i][s2.data[q].j]=s2.data[q].e;} printf(“转置后的数据是:n”);printf(“**************************************n”);for(a1=1;a1<=s1.nu;a1++){ for(b1=1;b1<=s1.mu;b1++){printf(“%10.3f”,l2.b[a1][b1]);
printf(“t”);} printf(“n”);} printf(“************************************”);printf(“n”);} } void jiafa(tsmatrix l4, tsmatrix l5)//矩阵的加法 {tsmatrix l6;for(int t=0;t for(j=0;j<(2*s.i);j++) { if(j else if(j==s.i+i)s1.b[i][j]=1.0; else s1.b[i][j]=0.0; } for(i=0;i { for(k=0;k {if(k!=i) { t=s1.b[k][i]/s1.b[i][i]; for(j=0;j<(2*s.i);j++) { x=s1.b[i][j]*t; s1.b[k][j]=s1.b[k][j]-x; } } }} for(i=0;i s1.b[i][j]=s1.b[i][j]/t;} float y=1.0;for(i=0;i printf(“对不起,您输入的矩阵没有逆矩阵”); else { for(i=0;i for(j=0;j { for(j=0;j printf(“%10.3f”,s.b[i][j]); printf(“n”);}}} void main(){ tsmatrix l,l1,l3;sqlist s;int m,n,m1,n1,n4,n5,t,t1,t2,t3,t4,t5,t6,t7,t8;do{ printf(“请输入你要进行的操作:n”); printf(“******************************n”); printf(“矩阵转置运算请按1n矩阵的加法运算请按2n矩阵的乘法运算请按3n矩阵的减法运算请按4n矩阵的逆运算请按5n结束请按0:n”);printf(“******************************n”);scanf(“%d”,&m1);if(m1==1){ printf(“您选择进行的操作是矩阵的转置运算nn”); printf(“请输入你要转置矩阵的行数、列数和非零元的个数n”);scanf(“%d”,&t1); scanf(“%d”,&t2);scanf(“%d”,&t3);s.mu=t1;s.nu=t2;s.tu=t3;printf(“请输入你要转置矩阵非零元的行下标、列下标(从[1][1]开始由左至右由上到下)及其数据(按行逐个输入)n”);for(t4=1;t4<=s.tu;t4++){scanf(“%d”,&t5);scanf(“%d”,&t6); s.data[t4].i=t5;s.data[t4].j=t6; scanf(“%f”,&s.data[t4].e);} for(t7=1;t7<=s.nu;t7++){ for(t8=1;t8<=s.mu;t8++)l1.b[t7][t8]=0.0;} zhuanzhi(s,l1);} if(m1==2){ printf(“您选择进行的操作是矩阵的加法运算nn”);printf(“请输入矩阵的行数和列数:n”);scanf(“%d”,&n);scanf(“%d”,&m);l.i=n;l.j=m;l3.i=n;l3.j=m;printf(“******************************n”);printf(“请输入第一个%d行%d列的矩阵n”,l.i,l.j);{ for(t=0;t if(m1==5){ printf(“您选择进行的操作是矩阵的逆运算nn”);printf(“请输入矩阵的维数(即行和列相等的矩阵):n”);scanf(“%d”,&n);l.i=n;l.j=n;printf(“******************************n”);printf(“请输入%d行%d列的矩阵n”,l.i,l.j);{ for(t=0;t 2、运行结果(如下图): (1)、执行的首界面: (2)、矩阵的转置运算: (3)、矩阵的加法运算: (4)、矩阵的减法运算: (5)、矩阵的乘法 (6)、矩阵的逆运算: (7)、矩阵可以循环运算: 六、指导老师评语及成绩 长整数加减的运算 一、需求分析 问题描述: 设计一个实现任意长的整数进行加法运算的演示程序 基本要求: 利用双向循环链表实现长整数的存储,每个结点含一个整型变量。任何整型变量的范围是 -(2 15 -1)~(2 15 -1)。输入输出形式:按照中国对于长整数的表示习惯,每四位是一组,组间用逗号隔开 更高要求: (1)长整数的减法 (2)多个长整数的连续加减法,并带括号等。具体方式可以参见表达式的求值部分,利用栈 测试数据: (1)0;0;应输出“0” (2)-2345,6789;-7654,3211;应输出“-1,0000,0000” (3)-9999,9999;1,0000,0000,0000;应输出“9999,0000,0001”(4)1,0001,0001;-1,0001,0001;应输出“0”(5)1,0001,0001;-1,0001,0000;应输出“1” (6)-9999,9999,9999;-9999,9999,9999;应输出“-1,9999,9999,9998”(7)1,0000,9999,9999;1;应输出“1,0001,0000,0000” 一、概要设计 1.数据结构 此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型,代码如下:typedef struct Node // 双向链表的结构体定义 { int data; struct Node *prior;struct Node *next;}DLNode; 2.使用函数 1)void ListInitiate(DLNode **head) 操作结果:初始化一个头结点为head的双向循环链表; 2)int ListLength(DLNode *head) 操作结果:计算以head为头结点的链表的长度 3)int ListInsert(DLNode *head,int i,int x) 操作结果:将节点数据为x的节点插到第i个位置上去。4)int abs(int x) 操作结果:绝对值函数,返回x的绝对值。5)int InputNumber(DLNode *head) 操作结果:将从键盘中接收数据并把得到的数据存入以head为头结点的链表中。四位一存,中间以逗号区分,结束符为分号。6)void OutputNumber(DLNode *head,int sign) 操作结果:将以head为头结点的链表中的所有数据输出到显示屏上,7)void add(DLNode *head1,DLNode *head2,DLNode *head3)操作结果:实现正数加正数的加法操作。8)int change(DLNode *head1,DLNode *head2) 操作结果:判断存在俩个链表中的数的大小,如何head1中的数大于head2中的数那么返回值为0,反之返回值为1,相等时返回值为2; 9)void method(DLNode *head1,DLNode *head2,int x) 操作结果:计算正数乘以正数的乘法运算。 10)void minus(DLNode *head1,DLNode *head2,DLNode *head3)操作结果:计算正数减正数的减法运算。 11)void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch) 操作结果:正数,负数,加法,减法。计算式共分为八种运算,在这之前我已经实现了二种运算,那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。 12)void chengfa(DLNode *head1,DLNode *head2) 操作结果:在乘法中我只是实现了正数乘以正数的运算,那么这个函数就是通过调用method函数按照一定的规则来实现完整的乘法运算。13)void main() 操作结果:主函数。调用以上的各个函数来引导用户进行长整数的加法运算,加法运算,乘法运算。 二、详细设计 1.数据结构详细设计 typedef struct Node // 双向链表的结构体定义 { int data;struct Node *prior;struct Node *next;}DLNode;双向循环链表的节点由三个部分组成,第一是数据部分data存储此节点的数据,第二是此节点的前驱指针部分*prior指向此节点的前驱,第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量,前驱后继指针均为结构体Node类型。2.链表初始化函数: void ListInitiate(DLNode **head)//双向链表的初始化 { } if((*head=(DLNode *)malloc(sizeof(DLNode)))==NULL)exit(0);(*head)->prior=*head;(*head)->next=*head; 初始化之前需要定义一个类型为Node型的头结点变量,经过函数后完成链表的初始化即:头节点的前驱指针指向自己,同时他的后继指针也指向自己。3.计算已知的链表长度: int ListLength(DLNode *head)//双向链表的表长 { DLNode *p=head;int size=0;while(p->next!=head){ } p=p->next;size++;return size;} 此函数计算的是已知链表的长度。主要思想:从头结点开始寻找下一个节点,找到计数器加一。直到再次寻找到头结点时停止,计算完毕。 4.插入函数: int ListInsert(DLNode *head,int i,int x)//双向链表的数据插入,i表示是插入的第几个元素 { DLNode *p,*s;int j;p=head->next;j=0;while(p!=head&&j } if(j!=i){ } if((s=(DLNode *)malloc(sizeof(DLNode)))==NULL)exit(0);s->data=x;s->prior=p->prior;//插入 p->prior->next=s;s->next=p;p->prior=s;return 1;printf(“n插入位置不合法!”);return 0;p=p->next;j++; } 此函数是已知一双向链表实现在第i个位置插入data为x的节点。函数需要注意的是在什么位置插入才是合法的,在就是在该节点指针时的顺序不要搞错。5.绝对值函数: int abs(int x){ } if(x<0)return-x;else return x;此函数是实现求一个整数的绝对值。设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数,然后通过其他手段变相实现那种运算。6.读入数据并插入对应的链表函数: int InputNumber(DLNode *head)//读入输入的数据 { int input,i=0;//第i个节点 char c;scanf(“%d%c”,&input,&c);while(1){ if(input<0&&i==0)//输入数为负且是第一个节点 { } else if(input>=0&&i==0)//输入数为正且是第一个节点 { } else { } if(head->next->data>=0){ } //input=-1*input;ListInsert(head,i,input);ListInsert(head,i,input);//非第一个节点 else head->data=1;//将长整数的符号保存在头结点中 ListInsert(head,i,input);//插入数据 head->data=0;//将长整数的符号保存在头结点中 //input=abs(input);//取输入数字的绝对值 ListInsert(head,i,input);//插入数据 } } return 1;i++;if(c==';')break;//遇到数据输入完成标志,跳出循环 scanf(“%d%c”,&input,&c);此函数实现的是从键盘上得到数据根据三种情况进行不同的处理,判断是否是头结点,判断是否是整数,判断输入的字符是否是“;”分号。并且如果是正整数它的头结点data等于1否则为0。 7.输出函数 void OutputNumber(DLNode *head,int sign){ DLNode *r=head->next;while(r->data==0&&r!=head->prior){ r=r->next;} if(sign==1){ printf(“结果是:”);} else { printf(“结果是:-”);} printf(“%d”,r->data); r=r->next; while(r!=head) { if(r->data<10) { printf(“,000”); printf(“%d”,r->data); } else if(r->data<100) { printf(“,00”); printf(“%d”,r->data); } else if(r->data<1000){ //从表尾输出数据元素 } } printf(“n”); } else { } r=r->next; printf(“,%d”,r->data);printf(“,0”);printf(“%d”,r->data);此函数实现的是将最后的结果输出到显示屏上,经过判断数据的正负和数据的范围来进行不同的处理,以保证在显示屏上显示的是正确的格式。 8.不完整加法函数(只可实现正数加上正数) void add(DLNode *head1,DLNode *head2,DLNode *head3){ int z=0; if(p1==head1&&p2!=head2){ while(p2!=head2){ e=p2->data+z;if(e>=10000){ z=1;int e;DLNode *p1,*p2;p1=head1->prior;p2=head2->prior;while(p1!=head1&&p2!=head2){ e=p1->data+p2->data+z; } if(e>=10000){ } else z=0;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=1;e=e%10000; } else z=0;ListInsert(head3,0,e);p2=p2->prior;e=e%10000;} if(z==1)ListInsert(head3,0,z);} else if(p1!=head1&&p2==head2){ while(p1!=head1){ e=p1->data+z; if(e>=10000){ } z=1;e=e%10000;else z=0;p1=p1->prior;ListInsert(head3,0,e);} if(z==1)ListInsert(head3,0,z);} else{ if(z==1)ListInsert(head3,0,z);} } 此函数实现的是两个正数之间的相加运算,主要的算法和我们手算加法是一样的,首先设置一个进位计数的变量,根据存储的特点从低位开始相加带上进位即可得出相应的位和,最后更新进位变量。处理边界状况:如果两个链表一样长同时他们最高位在计算完成时仍然会有进位,那么应该考虑到在数据的更高位插入一个1表示最后的计算结果,这样才可以保证数据的完整性。9.判断俩正数大小函数: int change(DLNode *head1,DLNode *head2){ int length1,length2,r=2;length1=ListLength(head1);DLNode *p1,*p2;p1=head1->next;p2=head2->next;length2=ListLength(head2); if(length1>length2){ } else if(length1 } else { } return r;} int i=0;for(i=0;i } if(p1->data>p2->data){ } else if(p2->data>p1->data){ } else { } p1=p1->next;p2=p2->next;r=2;r=1;return r;break;r=0;return r;break;r=1;return r;r=0;return r;此函数实现的是判断俩个正数的大小。考虑俩正数的在链表中所占存储单元的多少,多的一定大,当他们一样长时,一位一位的比较直到找到一个节点中的data比另一个链表的对应节点的data大为止。如果最后仍是一样大那么这两个数就是一样大的。返回值为自己约定的参数r等于2表示俩数一样大,等于1表示第二个数大,等于 0表示第一个数大。 10.乘法函数: void method(DLNode *head1,DLNode *head2,int x){ void minus(DLNode *head1,DLNode *head2,DLNode *head3);DLNode *temp1;DLNode *temp2;DLNode *temp3;DLNode *temp4;DLNode *temp5;int e,z=0,i,j;ListInitiate(&temp1);ListInitiate(&temp2);ListInitiate(&temp3);ListInsert(temp2,0,0);DLNode *p1,*p2;p1=head1->prior;p2=head2->prior;for(i=0;i while(p1!=head1){ } if(z!=0)ListInsert(temp1,0,z);for(j=0;j } else z=0;ListInsert(temp1,0,e);p1=p1->prior;z=e/10000;e=e-z*10000;ListInitiate(&temp4);ListInsert(temp4,0,0);ListInitiate(&temp5); } p1=head1->prior;p2=p2->prior;}OutputNumber(temp2,x);此函数实现的是俩个整数的乘法运算。模仿手算乘法,乘数的每一位分别和被乘数相乘得到的结果相加,注意的是在每次乘完相加时注意把低位的空缺补上0,以保证数据可以按位相加。在每一位乘法时需要注意一定要加上低位的进位以及改变进位的值,这样才能保证每一位诚出来的结果是正确的。11.减法函数: void minus(DLNode *head1,DLNode *head2,DLNode *head3){ int z=0,x=-1;int e;DLNode *p1,*p2;p1=head1->prior;p2=head2->prior;x=change(head1,head2);if(x==0){ while(p1!=head1&&p2!=head2){ } p1->data=p1->data+z;p1->data=p1->data+z;if(p1->data>=p2->data){ } else { } e=10000+p1->data-p2->data;ListInsert(head3,0,e);z=-1;e=p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=0;p1=p1->prior;p2=p2->prior;while(p1!=head1){ e=p1->data; ListInsert(head3,0,e); p1=p1->prior;} else if(x==1){ p2=head1->prior;while(p1!=head2&&p2!=head1){ } p1->data=p1->data+z;p1->data=p1->data+z;if(p1->data>=p2->data){ } else { } e=10000+p1->data-p2->data;ListInsert(head3,0,e);z=-1;e=p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=0;p1=head2->prior;} p1=p1->prior;p2=p2->prior;while(p1!=head2){ e=p1->data;p1=p1->prior;ListInsert(head3,0,e);} head3->next->data=-1*head3->next->data;} else { } } head3->next->data=0;此函数实现的是两个正数的减法运算。整个函数分为俩大部分,第一部分处理第一个数大于第二个数,第而部分是处理第二个数大于第一个数。在这个为题上我自己想了好长 时间,感觉俩部分可以 结合成一部分,但是由于本人的知识所限没有想出更好的办法,这使得代码量增加了足足一倍之多。仍然模仿手算减法,先找到俩数字中最大的那个,用大的减去小的。最后判断符号位。12.整合八种情况函数: void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch){ DLNode *p1,*p2;p1=head1->next;p2=head2->next;if(head1->data==1&&head2->data==1){ } else if(head1->data==1&&head2->data==0){ } else if(head1->data==0&&head2->data==1){ } if(ch=='+'){ } else { } head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;head1->next->data*=-1;minus(head2,head1,head3);if(ch=='+'){ } else { } head2->next->data*=-1;add(head1,head2,head3);head2->next->data*=-1;minus(head1,head2,head3);if(ch=='+')add(head1,head2,head3);else minus(head1,head2,head3); else { } } 此函数实现的是八种情况的整合。八种情况分别是正数加正数、正数加负数、正数减正数、正数减负数、负数加负数、负数加正数、负数减正数、负数减负数。此函数调用已经做好的正数加正数和正数减正数函数判断符号位,根据一定的规则实现八种运算。if(ch=='+'){ } { } head1->next->data*=-1;head2->next->data*=-1;minus(head2,head1,head3);head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;else 13.整合乘法运算函数: void chengfa(DLNode *head1,DLNode *head2){ int i;if((head1->next->data*head2->next->data)<0){ } else { } } 此函数实现的是乘法运算的完整运算。调用已经实现的正数乘以正数的函数来计算函数值,在判断最head1->next->data=abs(head1->next->data);head2->next->data=abs(head2->next->data);i=1;method(head1,head2,i);head1->next->data=abs(head1->next->data);head2->next->data=abs(head2->next->data);i=0;method(head1,head2,i); 终的函数符号,得到最和的结果。 14.主函数: void main(){ } 此函数是主函数。主要的作用是为用户做一个提示,如何完成自己想要的运算。同时调用各个函数实现运算。char ch,ch1;while(1){ } //int w=-1;DLNode *a,*b,*c;ListInitiate(&a);ListInitiate(&b);ListInitiate(&c);printf(“请输入数A(以分号结束):”);InputNumber(a);//printf(“n”);printf(“请输入数B(以分号结束):”);InputNumber(b);//w=change(a,b);printf(“请选择操作符:<+,-,*>:n”);scanf(“%s”,&ch1);if(ch1=='+'||ch1=='-'){ } else if(ch1=='*')chengfa(a,b);else printf(“此版本不支持%c运算”,ch1);printf(“要继续吗?(y/n):”);scanf(“%s”,&ch);if(ch=='Y'||ch=='y'){ } else exit(0);printf(“n”);continue;yunsuan(a,b,c,ch1);OutputNumber(c,1); 三、调试分析 1.调试过程中遇到的问题 在函数编写之前我首先写出了所有函数的框架以及各个函数之间的关系,根据逐步求精的思想来完善整个程序。即使是这样我仍然遇到了不少错误。 例如:在实现正数减正数时,我一开始没有分为以上所说的俩个部分,而是把俩个部分整合到一起实现一个大函数,但是在我运行调试时结果大不如人意,出现的都是匪夷所思的数字,我根本就推算不出这些数字是怎么来的。没有办法我只好在另辟途径来完成函数的实现。于是我就分作两个部分来实现,这样逐步追踪可以使思绪更加清晰,所付出的代价是代码量增加。 四、使用说明和测试结果 1.使用说明 用户在使用该程序时,只需按照程序中的规定进行即可实现长整数的加减运算,具体使用步骤如下: 1)点击运行按钮,在DOS窗口下按照规定输入的数字需要从低位开始数四位一组用逗号隔开。输入第一个数字。2)同上输入第二个数; 3)选择要对这两个长整数进行的运算。 4)两个操作数与运算符选择完毕后,按回车键即可得到运算结果。2.测试结果 1)考虑边界数字,输入0和0做加法运算,输出“0”,结果如下图: 2)考虑加法进位(包括低位向高位的进位以及高位仍有进位情况),结果如下图: 3)考虑减法进位并且数A小于数B以及数A大于数B,结果如下图: 4)乘法结果为正数以及负数两种情况,结果如下图: 5)本试验要求的数据 0、0; 输出“0”(已证明) 2345,6789、-7654,3211; 输出“1,0000,0000” 1,0000,0000,0000、9999,9999; 输出“9999,0000,0001” 1,0001,0001、;1,0001,0001; 输出“0” 五、心得体会 本次试验是我感觉到了理论应用与实践的意义,以前我们也做过类似的题目,所以在试验中我感觉还是比较顺利的但是还是花了我十七个小时左右才完成。根据模块化思想来把握整体结构会使自己的思路更加清晰,更加明了。得到的东西往往是说不出来的只有自己心理面最清楚。 六、附录 程序的完整代码清单: #include int data;struct Node *prior;struct Node *next;}DLNode;void ListInitiate(DLNode **head)//双向链表的初始化 { if((*head=(DLNode *)malloc(sizeof(DLNode)))==NULL)exit(0);(*head)->prior=*head; } int ListLength(DLNode *head)//双向链表的表长 { } int ListInsert(DLNode *head,int i,int x)//双向链表的数据插入,i表示是插入的第几个元素 { } int abs(int x){ if(x<0)return-x;DLNode *p,*s;int j;p=head->next;j=0;while(p!=head&&j } if(j!=i){ } if((s=(DLNode *)malloc(sizeof(DLNode)))==NULL)exit(0);s->data=x;s->prior=p->prior;//插入 p->prior->next=s;s->next=p;p->prior=s;return 1;printf(“n插入位置不合法!”);return 0;p=p->next;j++;DLNode *p=head;int size=0;while(p->next!=head){ } p=p->next;size++;(*head)->next=*head;return size; } int InputNumber(DLNode *head)//读入输入的数据 { } void OutputNumber(DLNode *head,int sign)//从表尾输出数据元素 { DLNode *r=head->next;while(r->data==0&&r!=head->prior){ r=r->next;int input,i=0;//第i个节点 char c;scanf(“%d%c”,&input,&c);while(1){ } return 1;if(input<0&&i==0)//输入数为负且是第一个节点 { } else if(input>=0&&i==0)//输入数为正且是第一个节点 { } else { } i++;if(c==';')break;//遇到数据输入完成标志,跳出循环 scanf(“%d%c”,&input,&c);if(head->next->data>=0){ } //input=-1*input;ListInsert(head,i,input);ListInsert(head,i,input);//非第一个节点 else head->data=1;//将长整数的符号保存在头结点中 ListInsert(head,i,input);//插入数据 head->data=0;//将长整数的符号保存在头结点中 //input=abs(input);//取输入数字的绝对值 ListInsert(head,i,input);//插入数据 else return x; } void add(DLNode *head1,DLNode *head2,DLNode *head3){ int z=0;int e;DLNode *p1,*p2;} if(sign==1){ } else { } printf(“%d”,r->data);r=r->next;while(r!=head){ } printf(“n”); if(r->data<10){ } else if(r->data<100){ } else if(r->data<1000){ } else { } r=r->next; printf(“,%d”,r->data);printf(“,0”);printf(“%d”,r->data); printf(“,00”);printf(“%d”,r->data);printf(“,000”);printf(“%d”,r->data);printf(“结果是:-”);printf(“结果是:”); p1=head1->prior;p2=head2->prior;while(p1!=head1&&p2!=head2) if(p1==head1&&p2!=head2){ while(p2!=head2){ e=p2->data+z;if(e>=10000){ } else z=0;ListInsert(head3,0,e);p2=p2->prior;z=1;e=e%10000;{ e=p1->data+p2->data+z; } if(e>=10000){ } else z=0;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=1;e=e%10000;} if(z==1)ListInsert(head3,0,z);} else if(p1!=head1&&p2==head2){ while(p1!=head1){ e=p1->data+z; if(e>=10000){ } z=1;e=e%10000;else z=0;p1=p1->prior;ListInsert(head3,0,e);} if(z==1)ListInsert(head3,0,z);} else{ } int change(DLNode *head1,DLNode *head2){ int length1,length2,r=2;length1=ListLength(head1);DLNode *p1,*p2;p1=head1->next;p2=head2->next;if(length1>length2){ } else if(length1 } else { int i=0;for(i=0;i if(p1->data>p2->data){ } else if(p2->data>p1->data){ } else { p1=p1->next;p2=p2->next;r=1;return r;break;r=0;return r;break;r=1;return r;r=0;return r;if(z==1)ListInsert(head3,0,z);} length2=ListLength(head2); } void method(DLNode *head1,DLNode *head2,int x){ void minus(DLNode *head1,DLNode *head2,DLNode *head3);DLNode *temp1;DLNode *temp2;DLNode *temp3;DLNode *temp4;DLNode *temp5;int e,z=0,i,j;ListInitiate(&temp1);ListInitiate(&temp2);ListInitiate(&temp3);ListInsert(temp2,0,0);DLNode *p1,*p2;p1=head1->prior;p2=head2->prior;for(i=0;i while(p1!=head1){ } if(z!=0)ListInsert(temp1,0,z);for(j=0;j } else z=0;ListInsert(temp1,0,e);p1=p1->prior;z=e/10000;e=e-z*10000;ListInitiate(&temp4);ListInsert(temp4,0,0);ListInitiate(&temp5); } return r; } } r=2; } void minus(DLNode *head1,DLNode *head2,DLNode *head3){ int z=0,x=-1;int e;DLNode *p1,*p2;p1=head1->prior;p2=head2->prior;x=change(head1,head2);if(x==0){ while(p1!=head1&&p2!=head2){ } p1->data=p1->data+z;p1->data=p1->data+z;if(p1->data>=p2->data){ } else { } e=10000+p1->data-p2->data;ListInsert(head3,0,e);z=-1;e=p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=0; add(temp1,temp2,temp3);temp1=temp4;temp2=temp3;temp3=temp5;z=0;p1=head1->prior;p2=p2->prior;}OutputNumber(temp2,x);p1=p1->prior;p2=p2->prior;while(p1!=head1){ e=p1->data;p1=p1->prior;ListInsert(head3,0,e);} } } void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch){ DLNode *p1,*p2;p1=head1->next;p2=head2->next;if(head1->data==1&&head2->data==1)else if(x==1){ p2=head1->prior;while(p1!=head2&&p2!=head1){ } p1->data=p1->data+z;p1->data=p1->data+z;if(p1->data>=p2->data){ } else { } e=10000+p1->data-p2->data;ListInsert(head3,0,e);z=-1;e=p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=0;p1=head2->prior;p1=p1->prior;p2=p2->prior;while(p1!=head2){ e=p1->data;p1=p1->prior;ListInsert(head3,0,e);} head3->next->data=-1*head3->next->data;} else { } head3->next->data=0; { } else if(head1->data==1&&head2->data==0){ } else if(head1->data==0&&head2->data==1){ } else { if(ch=='+'){ } { head1->next->data*=-1;head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;if(ch=='+'){ } else { } head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;head1->next->data*=-1;minus(head2,head1,head3);if(ch=='+'){ } else { } head2->next->data*=-1;add(head1,head2,head3);head2->next->data*=-1;minus(head1,head2,head3);if(ch=='+')add(head1,head2,head3);else minus(head1,head2,head3);else } void chengfa(DLNode *head1,DLNode *head2){ } void main(){ char ch,ch1;while(1){ //int w=-1;DLNode *a,*b,*c;ListInitiate(&a);ListInitiate(&b);ListInitiate(&c);printf(“请输入数A(以分号结束):”);InputNumber(a);//printf(“n”);printf(“请输入数B(以分号结束):”);InputNumber(b);//w=change(a,b);printf(“请选择操作符:<+,-,*>:n”);scanf(“%s”,&ch1);if(ch1=='+'||ch1=='-'){ yunsuan(a,b,c,ch1);int i;if((head1->next->data*head2->next->data)<0){ } else { } head1->next->data=abs(head1->next->data);head2->next->data=abs(head2->next->data);i=1;method(head1,head2,i);head1->next->data=abs(head1->next->data);head2->next->data=abs(head2->next->data);i=0;method(head1,head2,i); } } head2->next->data*=-1;minus(head2,head1,head3); } } } else if(ch1=='*')chengfa(a,b);else printf(“此版本不支持%c运算”,ch1);printf(“要继续吗?(y/n):”);scanf(“%s”,&ch);if(ch=='Y'||ch=='y'){ } else exit(0);printf(“n”);continue;OutputNumber(c,1); 数 据 结 构 课程设计报告 题 目: 一元多项式计算 专 业: 信息管理与信息系统 班 级: 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 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->expn { 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->expn 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);} 数据结构课程设计 1.赫夫曼编码器 设计一个利用赫夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。要求: 1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中) 2)初始化:键盘输入字符集大小26、26个字符和26个权值(统计一篇英文文章中26个字母),建立哈夫曼树; 3)编码:利用建好的哈夫曼树生成哈夫曼编码; 4)输出编码(首先实现屏幕输出,然后实现文件输出); 5)界面优化设计。 代码如下: #include typedef 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(“data.txt”,“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(“data.txt”,“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”); //运行环境背景颜色.printf(“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”);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 //定义成绩信息结构体 { 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”,s.Number);printf(“ | %-6s”,s.Name);printf(“ | %-3s”,s.Chinese);printf(“ | %-3s”,s.English); printf(“ | %-3sn”,s.Math);} 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->data.Number);printf(“请输入姓名:”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩:”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩:”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩:”);scanf(“%s”,pNodeScore->data.Math);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->data.Number,DeleteNumber)==0) { //如果要删除的结点在第一个 headScore=p1->next; pNodeScore=p1; printf(“学号为%s的学生信息已经删除!n”,DeleteNumber); return 0;} else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,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->data.Number,EditNumber)==0) { //用strcmp比较两字符串是否相等,相等则返回0 printf(“原来的学生成绩信息如下:n”);//输出原来的成绩信息 printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); printf(“语文新成绩:”); scanf(“%s”,pNodeScore->data.Chinese); printf(“英语新成绩:”); scanf(“%s”,pNodeScore->data.English); printf(“高数新成绩:”); scanf(“%s”,pNodeScore->data.Math); 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->data.Number,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”); //运行环境背景颜色.printf(“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;} 运行界面如下:第三篇:长整数加减运算实验报告
第四篇:2012数据结构课程设计
第五篇:数据结构课程设计