实验三链表及其多项式相加(答案)

1、实验三、 链表及其多项式相加、程序流程图1. 主过程 2. 建立多项式链表流程开始建立多项式链表LA建立多项式链表LB调用ADD过程：LA+LB输出相加后的多项式结束 开始FLAG:=1 读第一个结点的系数系数=0？建立空白多项式建立第一个结点FLAG=1 ?读入系数、指数系数=0 ？FLAG: = 0结 束 N Y N Y 参考程序/* 链表及其多项式相加 */typedef struct linkline int coef; int exp; struct linkline *next; line; line *creat() /*建立多项式列表*/ int n; line *head;

2、line *p1,*p2; n=0; printf("(输入的数必须是整数，指数须从小到大依次输入,系数为零表示多项式结束)n"); p1=p2=(line *)malloc(sizeof(line); /*开辟一个新单元*/ scanf("%d%d",&p1->coef,&p1->exp); /*录入多项式*/ if (p1->coef=0) head=0; else while(p1->coef!=0) n+; if (n=1) head=p1; else p2->next=p1; p2=p1; p1=(

3、line *)malloc(sizeof(line); scanf("%d%d",&p1->coef,&p1->exp); p2->next=0; return(head); /* 以下是输出多项式的函数 */ void print(line *p) line *p0; p0=p; printf(" "); if(p0!=0) do printf("%dx的%d次幂",p0->coef,p0->exp); p0=p0->next; if(p0!=0) printf("+&q

4、uot;); while(p0!=0); else printf(" 空多项式!"); printf("n"); int compare(int m,int n) /*比较两个整数的大小的函数*/ int j; if (m<n) j=-1; if (m=n) j=0; if (m>n) j=1; return(j);void freeNode(line *w1) /* 释放一个表中的所有结点 */ line *w2; w2=w1->next; while(w1) free(w1); w1=w2; w2=w2->next; line

5、 *AddLine(line *ha,line *hb) /*两个非空多项式相加*/ line *la,*lb,*lc; int a,b,sum; lc=ha; la=ha; lb=hb; if (ha=0)&&(hb!=0) return(hb); while (la!=0)&&(lb!=0) a=la->exp; b=lb->exp; switch( compare(a,b) ) /*比较当前结点指数的大小 */ case -1: ha=la; /*只修改la的指针*/ la=la->next; break; case 0: sum=la-

6、>coef+lb->coef; if(sum!=0) /* 将其不为零的系数和保存 */ la->coef=sum; ha=la; la=la->next; /* end if*/ else /* 分别删除系数和为零的对应的两个结点 */ if (lc=la) lc=lc->next;ha=lc;la=ha; /* 刚开始时特殊处理头结点 */ else ha->next=la->next; la=ha->next; /*end else*/ hb=lb; lb=lb->next; break; case 1: /* 将指数小的项插入到la

7、的前部 */ hb=lb->next; if(ha=la) lc=lb;lb->next=ha;la=la->next; else ha->next=lb; lb->next=la; ha=la; la=la->next; lb=hb->next; break; /*end swtich*/ /*end while*/ if (lb!=0) ha->next=lb; return(lc); /*end AddLine */ /*以下为主程序*/ main() line *la,*lb,*lc; printf("请输入多项式La: &qu

8、ot;); la=creat(); printf("请输入多项式Lb: "); lb=creat(); printf("多项式La:n"); print(la); printf("多项式Lb:n"); print(lb); printf("多项式La与Lb的和是: n"); lc=AddLine(la,lb); print(lc); freeNode(lb); 一、 实验目的：1 了解栈存储结构的特点；2 掌握栈存储结构的应用。二、 实验原理：栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶

9、，另一个固定端称为栈底。由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解。数制转换问题：将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3456，r=8为例转换方法如下： N N / 8 （整除） N % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高所以：（3456）10 =（6600）8我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。算法思想如下：当N>0时重复1，21

10、若 N0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束。2 用N / r 代替 N三、 实验要求1参照书上的原理说明分析程序，深入理解栈的物理存储模式和逻辑模式。2看懂书上程序，编出程序上机调试。参考代码：算法如下： typedef int datatype; #define L 10void conversion(int N，int r) void conversion(int N，int r) SeqStack s; int sL,top; /*定义一个顺序栈*/datetype x; int x;Init_SeqStack(&s); top =-

11、1; /*初始化栈*/while ( N ) while ( N ) Push_SeqStack ( &s ，N % r ); s+top=N%r; /*余数入栈 */ N=N / r ; N=N / r ; /* 商作为被除数继续 */ while ( Empty_SeqStack(& s ) ) while (top!=-1) Pop_SeqStack (&s ，&x ) ; x=stop-; printf ( “ %d ”，x ) ; printf(“%d”,x); 算法(a) 算法(b)实验五、队列的应用实验原理：一种“先进先出” (FIFO-First

12、 In First Out)的数据结构：即插入在队尾一端进行，而删除在队头进行。键盘缓冲区问题：设计算法实现模拟键盘缓冲区问题。假设有两个进程同时存在于一个应用程序之中，第一个进程连续在屏幕上显示字符“X”，第二个进程不断检查键盘上是否有输入，若有则读入用户键入的字符，将其保存到键盘缓冲区之中。程序约定当用户键入一个逗号“，”，则表示第一进程结束，系统开始显示那些在键盘缓冲区中的字符；接着继续执行第一个进程，即，在屏幕上显示字符“X”；当用户输入“；”的时候，刚结束整个程序。 算法提示：为了充分利用缓冲区的空间往往将缓冲区设计成循环队列的结构，并为循环队列结构的缓冲区设置一个队首指针和一个队尾

13、指针。每输入法一个字符到缓冲区中，就将尾指针后移，链入缓冲区的循环队列之中；每输出一个字符号，就将队头指针前移，将它从缓冲队列中删除。参考代码：/*键盘缓冲区问题*/#define MAXSIZE 20#define TRUE 1#define FALSE 0#include "stdio.h"#include "conio.h"#include "dos.h"typedef charelemtype;typedef structelemtype elemMAXSIZE;int front, rear;queuetype;int en

14、que(queuetype *s, elemtype x) /*数据入队列*/if ( s->rear+1)%MAXSIZE=s->front ) /*队列已满*/return (FALSE);else s->rear=(s->rear+1) % MAXSIZE; s->elems->rear=x;return(true);elemtype delqueue (queuetype *s )/*数据出队列*/if (s-front=s->rear)/*队列为空*/return(NULL);else/*队列非空*/s->front=(s->fr

15、ont+1)%MAXSIZE;return(s->elems->front);main()char ch1,ch2;queuetype*p;int t,f;p=(queuetype *)malloc(sizeof(queuetype);p->front=0;p->rear=0;while(1) /*开始交替执行*/while(1)/*第一个进程的执行*/if(kbhit() /*检测是否有键盘输入*/ch1=bdos(7,0,0); /*中断调用,键入字符存入ch1*/f=enqueue( p, ch1 ); /*字符入循环队列*/if ( f= FALSE )prin

16、tf(" The queue is already full !n");break;if ( ch1='' | ch1=',' )break;/*第一个进程正常结束情况*/printf("X");/*执行第一个进程*/ch2=delqueue(p);while( ch2 != NULL )putchar(ch2);/*在屏幕上显示输入缓冲区中的内容*/ch2=delqueue(p);/*字符出队列*/ getchar(); /*为看清屏幕内容, 在此暂停, 按回车继续if (ch1=''|f=FALSE)/

17、*程序结束*/break;else/*继续执行*/ch1=''/*先置空ch1*/实验六、稀疏矩阵的建立与转置一、 实验目的：1、 了解稀疏矩阵的三元组存储形式。2、 熟悉掌握三元表存储矩阵的转置算法。二、 实验内容：矩阵是很多的科学与工程计算中研究的数学对象。在此，我们感兴趣的是，从数学结构这门学科着眼，如何存储矩阵的元从而使矩阵的各种运算有效的进行。本来，用二维数组存储矩阵，在逻辑上意义是很明确的，也很容易理解，操作也很容易和方便。但是在数值分析中经常出现一些阶数很高的矩阵，同时，在矩阵中又有很多值相同或者都为零的元素，可以对这种矩阵进行压缩存储：对多个值相同的元素只分配一

18、个存储空间；对零元素不分配空间。稀疏矩阵的定义是一个模糊的定义：即非零元个数较零元个数较少的矩阵。例如下图所示的矩阵： 0 12 9 0 0 0 00 0 0 0 0 0 0 3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0 为一个稀疏矩阵。为了实现稀疏矩阵的这种存储结构，引入三元组这种数据结构。三元组的线性表顺序存储形式如下图：MUNUTUIIVIJVIJVA， B：ARRAY1。MAXNUMOF TUPLE3TP 实验步骤看懂书上的算法，参考书上的程序编写程序上机调试、输入数据、检验结果。程序流程图开始置B为A的空转置矩阵非

19、零元个数=0 ？ Q = 1 ;COL = 1;COL列值？P非零元个数？若三元组的列号为所寻列，则置换之。Q = Q+1结 束开 始调用建立稀疏矩阵过程调用转置矩阵过程调用输出矩阵过程结 束 Y N Y N COL+1 Y P+1参考程序struct tuple3tp /*稀疏矩阵的建立和转置*/int i,j;int v;struct sparmattpint mu,nu,tu;struct tuple3tp data31;struct sparmattp a,b;void crt_sparmat()int i;printf("输入稀疏矩阵行值,列值,最大非零元个数:"

20、);scanf("%d%d%d",&a.mu,&a.nu,&a.tu);for(i=1;i<=a.tu;i+)printf("输入行坐标,列坐标,非零元");scanf("%d%d%d",&a.datai.i,&a.datai.j,&a.datai.v);void trans_sparmat()int col,p,q;b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if(b.tu!=0) q=1;for(col=1;col<=a.nu;col+)for(p=1;p

21、<=a.tu;p+) if (a.datap.j=col) b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;q+; out(struct sparmattp x)int i,j,k,flag;for(i=1;i<=x.mu;i+)for(j=1;j<=x.nu;j+)flag=0;for(k=1;k<=x.tu;k+)if(x.datak.i)=i)&&(x.datak.j)=j)flag=1;printf("%5d",x.datak.v);if(flag=0)p

22、rintf(" 0");printf("n");main()printf("稀疏矩阵的建立与转置n");crt_sparmat();trans_sparmat();printf("原矩阵为:n");out(a);printf("转置矩阵为:n");out(b);实验七、 二叉树及其先序遍历实验内容：1树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。2节点的

23、有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅有一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。3二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉树的子树有左右之分，其次序不能颠倒。4二叉树的结点存储结果示意图如下：左指针域数据域右指针域 实验步骤1理解实验原理，读懂实验参考程序。2（1）在纸上画出一棵二叉树。 A B E C D G F (2) 输入各个结点的数据。(3) 验证结果的正确性。程序代码#include "stdio.h"

24、#include "stdlib.h"#define Max 50 /*预先定义结点数目最大为50*/typedef char elemtype;typedef struct btnodeelemtype data;struct btnode *lchild, *rchild;bitnode, *bitree; /*自定义结点类型*/bitree CreateBiTree()/*先序遍历生成二叉树的递归算法*/bitree t;/*定义二叉树t*/char ch;scanf("%c",&ch);if( ch='.' )t=NULL

25、;elset=( bitnode *)malloc(sizeof(bitnode) ); /*生成新的结点*/t->data=ch;/*对数据域赋值*/t->lchild=CreateBiTree();/*递归构造左子树*/t->rchild=CreateBiTree();/*递归构造右子树*/return t;/*CreateBiTree*/void PreOrderTraverse(bitree bt)/*先序遍历二叉树递归算法*/ if (bt!=NULL) printf("%c",bt->data);/*访问根结点*/PreOrderTrav

26、erse(bt->lchild);/*先序遍历左子树*/PreOrderTraverse(bt->rchild);/*先序遍历右子树*/ /*PreOrderTraverse*/void main()bitree bt1;printf("creatbitree：n");bt1=CreateBiTree();printf("preorder:n");PreOrderTraverse(bt1)；/*main*/实验八、中序、后序遍历二叉树一、 实验目的：1. 掌握二叉树遍历的算法。2. 掌握二叉树遍历非递归的实现算法。二、 实验内容：递归算法实现

27、先序树遍历生成二叉树，并写出其中序、后序遍历非递归算法，并要求有输出结果验证。三、程序代码：#include "stdio.h"#include "stdlib.h"#define Max 50 /*预先定义结点数目最大为50*/typedef char elemtype;typedef struct btnodeelemtype data;struct btnode *lchild, *rchild;bitnode, *bitree; /*自定义结点类型*/bitree CreateBiTree()/*先序遍历生成二叉树的递归算法*/bitree t;

28、/*定义二叉树t*/char ch;scanf("%c",&ch);if( ch='.' )t=NULL;elset=( bitnode *)malloc(sizeof(bitnode) ); /*生成新的结点*/t->data=ch;/*对数据域赋值*/t->lchild=CreateBiTree();/*递归构造左子树*/t->rchild=CreateBiTree();/*递归构造右子树*/return t;/*CreateBiTree*/void InOrderTraverse2(bitree t)int top=0; bi

29、tree p, sMax;int m;m = Max-1;p = t;dowhile(p!=NULL) if (top>m) return;top=top+1; stop=p;p=p->lchild; /* 遍历左子树 */if(top!=0) p=stop;top=top-1;printf("%ct", p->data); /* 访问根结点 */p=p->rchild; /* 遍历右子树 */ while(p!=NULL | top!=0);/*InOrderTraverse2*/void PostOrderTraverse2(bitree t)/

30、*二叉树后序遍历的非递归算法*/int s2Max;/*标志进栈次数的栈s2*/int top=0,flag; /*定义整型栈顶指针和标志值*/bitree p, s1Max;/*定义指针和指针型栈*/p=t;/*从根结点开始遍历*/dowhile(p!=NULL)s1top=p;/*p所指向的结点入栈*/s2top+=0; /*标志p所指向的结点首次入栈*/p=p->lchild; /*遍历p所指向结点的左子树*/if (top>0)flag=s2-top;p=s1top;if (flag=0)s1top=p; /*p所指向的结点入栈*/s2top+=1;/*标志p所指向的结点第

31、二次入栈*/p=p->rchild;/*遍历p所指向结点的右子树*/elseprintf("%ct", p->data);/*第三次遇到该结点，将该结点打印*/p=NULL;while(top>0);/*PostOrderTraverse2*/void main()bitree bt1;printf("createbitree:n");bt1=CreateBiTree();printf("inordertraverse2:n");InOrderTraverse2(bt1);printf("n,postorder2:n");PostOrderTraverse2(bt1);/*main*/实验九、查找一、实验目的：1 掌握线性查找常用方法；2、掌握二分查找的应用。二、写出二分查找算法，并调试运行。1复习教材内容，深入理解线性查找算法。2编出程序上机调试。三、代码实现：四、结果验证：#includ