数据结构习题讲解

1、数据结构习题讲解数据结构习题讲解第1周作业试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义。理数的定义。ADT ComplexNum数据对象：数据对象：D=a,b|a,bR数据关系：数据关系：R1| a,bR基本操作：基本操作： InitComplexNum(&C,a,b)操作结果：构造一个复数操作结果：构造一个复数C，元素，元素a,b分别作为复数的实部和虚部分别作为复数的实部和虚部real(C,&r)操作结果：返回复数的实部操作结果：返回复数的实部imaginary (C,&i)操作结果：返回复数的虚部操作结果：返回复数的

2、虚部.ADT ComplexNum 抽象数据类型有理数的定义抽象数据类型有理数的定义ADT RationalNumber 数据对象：数据对象：D=a,b|a,bZ,b0数据关系：数据关系：R1| a,bZ,b0基本操作：基本操作： InitRationalNumber(&C,a,b)操作结果：构造一个有理数操作结果：构造一个有理数C，a,b分别作为有理数的分子和分别作为有理数的分子和分母分母molecule(C,&r)操作结果：返回有理数的分子操作结果：返回有理数的分子denominator (C,&i)操作结果：返回有理数的分母操作结果：返回有理数的分母.ADT RationalNumber

3、 试编写算法，计算试编写算法，计算i!*2i(i=0,1,2,.,n-1)的值的值并分别存入数组并分别存入数组aarrsize的各个分量中。的各个分量中。假设计算机中允许的整数最大值为假设计算机中允许的整数最大值为MAXINT，则当则当 narrsize， 或对某个或对某个k(0kMAXINT时时应按出错处理应按出错处理int f(int a ,int n)a0=1for(i=1;iMAXINT) return ERROR课堂练习课堂练习定义一个函数，函数原型为：定义一个函数，函数原型为：int StoI(char snum100,int num25)int StoI(char snum100

4、,int num25)函数的功能为：将函数的功能为：将snumsnum中的字符型数字转换成整中的字符型数字转换成整型数据存放在数组型数据存放在数组numnum中并返回其符号。中并返回其符号。如如若若snumsnum中存放的是下面的字符串：中存放的是下面的字符串： 123,4567,8901123,4567,8901则则num0=123,num1=4567,num2=8901num0=123,num1=4567,num2=8901，返回，返回1 1，若若snumsnum中的字符串为：中的字符串为：123,4567,8901123,4567,8901，12341234则则num0=123,num1

5、=4567,num2=8901num0=123,num1=4567,num2=8901，num3=1234,num3=1234,返回返回1.1.int StoI(char snum100,int num25)int StoI(char snum100,int num25)/函数的功能为：将函数的功能为：将snumsnum中的字符型数字转换成整型数中的字符型数字转换成整型数/据存放据存放在数组在数组numnum中并返回其符号中并返回其符号int i,j,k,sign;int i,j,k,sign;i=0;j=0;i=0;j=0;char s10;char s10;if(snum=-)sign=-

6、1;i+;/if(snum=-)sign=-1;i+;/若第若第1 1个符号为负则该数为负数个符号为负则该数为负数else sign=1;else sign=1;while(snum!=0)while(snum!=0)k=0;k=0;while(snumi=0&snumi=0&snumi=9) sk+=snumi+;if(k)numj+=atoi(s);if(k)numj+=atoi(s); return sign;return sign;课堂练习答案课堂练习答案实验二线性表的应用（实验二线性表的应用（4学时）学时） 一、实验目的：掌握线性表的基本结构和操作方法，一、实验目的：掌握线性表的基本

7、结构和操作方法，培养学生灵活使用结构解决实际问题的能力。培养学生灵活使用结构解决实际问题的能力。二、实验内容：二、实验内容： 设计一个设计一个100位以内的长整数加减运算的程序。位以内的长整数加减运算的程序。三、实验要求：三、实验要求：1，输入输出要求：每四位一组，组间用逗号分隔；，输入输出要求：每四位一组，组间用逗号分隔；2，加和减分别用不同的程序实现，加和减分别用不同的程序实现3，程序应考虑输入数据的符号，程序应考虑输入数据的符号四实验提示四实验提示#include#include#include#include#define LEN sizeof(struct student)struc

8、t studentint score;struct student *next;int lenm,lenn,lensum;/m与与n的长度的长度主函数主函数void main()struct student *creat(int *d,int *len);void print(struct student *head);struct student *add(struct student *m,struct student *n); struct student *sub(struct student *m,struct student *n);int compare(struct stude

9、nt *m,struct student *n);struct student *m,*n,*sum;int s1,s2,s3,k;char ch;主函数中的算法主函数中的算法，选择运算：或，选择运算：或，调用函数，调用函数createcreate输入第个数并放在链表输入第个数并放在链表m m中，中，s1s1为其符号为其符号 ，调用函数，调用函数createcreate输入第输入第,2,2个数并放在链表个数并放在链表n n中，中，s2s2为其符号为其符号 ，调用，调用comparecompare函数比较函数比较m,nm,n的大小的大小，处理加法运算，处理加法运算5.15.1若若m,nm,n同号

10、，则调用同号，则调用addadd函数相加函数相加5.25.2若若m,nm,n不同号，则调用不同号，则调用subsub函数相减函数相减( (大大- -小小) )，处理减法运算，处理减法运算，输出（先输出符号，然后调用，输出（先输出符号，然后调用printprint函数输出）函数输出）struct student *creat(int *sign,int *n) void print(struct student *head);struct student *p1,*p2;int i=0,j,k=0,len;char s5,c130;*sign=1;gets(c);if(c0=-)i=1;*sig

11、n=-1;p1=p2=(struct student *)malloc(LEN);/建立尾结点p1-score=0; p1-next=NULL;len=strlen(c);for(;i=0&ciscore=atoi(s);/将s转换成整数 p1-next=p2;/插入到链表头p2=p1;*n=k;return(p1);加减法运算函数提示加减法运算函数提示 链表是按表头数据为长整数的低位，表尾链表是按表头数据为长整数的低位，表尾为高位存放为高位存放 运算时要考虑进位和借位运算时要考虑进位和借位 运算结果参考运算结果参考creat函数存放到链表中（每函数存放到链表中（每得出一个结果均插入到链表表头

12、得出一个结果均插入到链表表头加减法运算函数算法加减法运算函数算法，生成首结点，将其地址保存到，生成首结点，将其地址保存到head，p1，p2中，其中中，其中p1指向新结点，指向新结点，p2指向链表的最后一个结点，指向链表的最后一个结点，head为链为链表的头指针表的头指针，给首结点赋值（其值为，给首结点赋值（其值为m,n中第个结点的和的万位以中第个结点的和的万位以下的数，保存进位下的数，保存进位，m,n指向下一结点指向下一结点，While(m&n) 生成新结点，其值为生成新结点，其值为m,n与进位之和，与进位之和，保存进位保存进位将新结点链接到链表的表尾将新结点链接到链表的表尾m,n指向下一结

13、点指向下一结点，处理，处理m中余下的结点中余下的结点，处理，处理n中余下的结点中余下的结点，返回，返回head比较函数与输出函数提示比较函数与输出函数提示 比较时先比较链表的长度比较时先比较链表的长度 若长度相同则比较每一个结点中的数据若长度相同则比较每一个结点中的数据 输出时先将链表中的数保存到数组中，然输出时先将链表中的数保存到数组中，然后逆序输出后逆序输出第第2周星期五作业周星期五作业 2.14:试写一算法在带头结点的单链表结构试写一算法在带头结点的单链表结构上实现表操作：上实现表操作：LENGTH(L) 设结点类型如下：设结点类型如下：typedef struct LNode Elem

14、Type data; / 数据域 struct LNode *next; / 指针域 LNode, *LinkList; int LENGTH(LinkList L)int i=0;while(L)L=L-next;i+;return i;第第3周星期二周星期二 2.41试以循环链表作稀疏多项式的存储结构，编写算法试以循环链表作稀疏多项式的存储结构，编写算法求其导函数的算法求其导函数的算法typedef struct polynomail float coef; / 系数系数 int expn; / 指数指数struct polynomail *next; *poly; poly deriva

15、tive(poly old)poly p,q,head;p=(poly)malloc(sizeof(struct polynomail);q=head=p;q-expn=-1;q-next=NULL;old=old-next;while(old)p=(poly)malloc(sizeof(struct polynomail); p-coef=old-coef*old-expn;p-expn=old-expn-1;p-next=NULL;q-next=p;old=old-next;q=p;return head; 2.42试编写算法，将一个用循环链表表试编写算法，将一个用循环链表表示的稀疏多项式

16、分解成两个多项式，使这示的稀疏多项式分解成两个多项式，使这两个多项式各自仅含奇次项和遇次项两个多项式各自仅含奇次项和遇次项 多项式类型定义与多项式类型定义与2.41同同void oddeven(poly old,poly &odd,poly &even)ploy p1,p2,q1,q2;p1=(poly)malloc(sizeof(struct polynomail);q1=odd=p1;q1-expn=-1;q1-next=NULL;p2=(poly)malloc(sizeof(struct polynomail);q2=even=p1;q2-expn=-1;q2-next=NULL;old

17、=old-next;while(old)if(old-expn%2)p1=(poly)malloc(sizeof(struct polynomail); p1-coef=old-coef;p1-expn=old-expn;p1-next=NULL;q1-next=p;old=old-next;q1=p;elsep2=(poly)malloc(sizeof(struct polynomail); p2-coef=old-coef;p2-expn=old-expn;p2-next=NULL;q2-next=p;old=old-next;q2=p;第周星期五作业，简述栈与线性表的区别，简述栈与线性表的区别栈是一种特殊的线性表，是只能在一端栈是一种特殊的线性表，是只能在一端进行插入与删除的线性表。而一般的线性表进行插入与删除的线性表。而一般的线性表则可在其他位置插入与删除则可在其他位置插入与删除，试写一个判别表达式中中括号是否配对，试写一个判别表达式中中括号是否配对出现的算法出现的算法中括号匹配算法中括号匹配算法Status matching(char a )InitStack(S);i=0;while(ai!=0)if(ai=) push(S,ai);i