实验三链表及其多项式相加答案DOC.docx
- 文档编号:13421630
- 上传时间:2023-06-14
- 格式:DOCX
- 页数:27
- 大小:168.41KB
实验三链表及其多项式相加答案DOC.docx
《实验三链表及其多项式相加答案DOC.docx》由会员分享,可在线阅读,更多相关《实验三链表及其多项式相加答案DOC.docx(27页珍藏版)》请在冰点文库上搜索。
实验三链表及其多项式相加答案DOC
实验三、
链表及其多项式相加
建立多项式链表流程
2.
{
、程序流程图
1.主过程
intcoef;
intexp;
structlinkline*next;
line;
line*creat()
/*
建立多项式列表*/
intn;
line*head;
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;
elsep2->next=p1;
p2=p1;
p1=(line*)malloc(sizeof(line));
scanf("%d%d",&p1->coef,&p1->exp);
p2->next=0;
return(head);
/*以下是输出多项式的函数*/
voidprint(line*p)
line*p0;
p0=p;
printf("");
if(p0!
=0)
do
printf("%dx
的%(次幕",p0->coef,pO->exp);
p0=p0->next;
if(p0!
=0)printf("+");
while(p0!
=0);
elseprintf("
空多项式!
!
");
printf("\n");
intcompare(intm,intn)
/*
比较两个整数的大小的函数*/
intj;
if(m if(m==n)j=0; if(m>n)j=1; return(j); voidfreeNode(line*w1) /* 释放一个表中的所有结点*/ line*w2; w2=w1->next; while(w1) {free(w1); w1=w2; 两个非空多项式相加*/ w2=w2->next;}line*AddLine(line*ha,line*hb)/*line*la,*lb,*lc; inta,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: la=la->next; break; case0: {sum=la->coef+lb->coef; if(sum! =0) la->coef=sum; ha=la;la=la->next; }/*endif*/ else /*刚开始时特殊处 if(lc==la){lc=lc->next;ha=lc;la=ha;} 理头结点*/ else{ ha->next=la->next; la=ha->next; }/*endelse*/ hb=lb; lb=lb->next; break; case1: 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; }/*endswtich*/ }/*endwhile*/ if(lb! =0)ha->next=lb; return(lc); }/*endAddLine*/ main() line*la,*lb,*lc; printf("请输入多项式La: "); 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.掌握栈存储结构的应用。 二、实验原理: 栈是限制在表的一端进行插入和删除的线性表。 允许插入、删除的这一端称 为栈顶,另一个固定端称为栈底。 由于栈的“先进先出”结构来进行求解。 数制转换问题: 将十进制数N转换为r r=8为例转换方法如下: 特点,在很多实际问题中都利用栈做一个辅助的数据 进制的数,其转换方法利用辗转相除法: N=3456 N 3467 433 54 6 N/8 433 54 6 0 所以: (3456)10= (整除) 3 1 6 6 (6600)8 (求余) 4 我们看到所转换的8进制数按底位到高位的顺序产生的,而通常的输出是从高位到低位的,恰好与计算过程相反,因此转换过程中每得到一位8进制数则进栈保存,转换完毕后依次出栈则正好是转换结果。 算法思想如下: 当N>0时重复1,2 1.若N工0,则将N%r压入栈s中,执行2;若N=0,将栈s的内容依次出栈,算法结束。 2.用N/r代替N 实验要求 参照书上的原理说明分析程序,深入理解栈的物理存储模式和逻辑模式。 实验原理: 一种"先进先出"(FIFO---FirstInFirstOut)的数据结构: 即插入在队尾一端进行,而 删除在队头进行。 键盘缓冲区问题: 设计算法实现模拟键盘缓冲区问题。 假设有两个进程同时存在于一个应用程序之中,第 一个进程连续在屏幕上显示字符“X”,第二个进程不断检查键盘上是否有输入,若有则读入用户键入的字符,将其保存到键盘缓冲区之中。 程序约定当用户键入一个逗号“,”,则表示第一进程结束,系统开始显示那些在键盘缓冲区中的字符;接着继续执行第一个进程,即,在屏幕上显示字符“X”;当用户输入“;”的时候,刚结束整个程序。 算法提示: 为了充分利用缓冲区的空间往往将缓冲区设计成循环队列的结构,并为循环 队列结构的缓冲区设置一个队首指针和一个队尾指针。 每输入法一个字符到缓冲区中,就将尾指针后移,链入缓冲区的循环队列之中;每输出一个字符号,就将队头指针前移,将它从缓冲队列中删除。 参考代码: /*键盘缓冲区问题*/#defineMAXSIZE20#defineTRUE1#defineFALSE0#include"stdio.h"#include"conio.h" #include"dos.h" typedefstruct elemtypeelem[MAXSIZE]; intfront,rear; }queuetype; /*数据入队列*/ /*队列已满*/ intenque(queuetype*s,elemtypex) if((s->rear+1)%MAXSIZE==s->front) return(FALSE); else s->rear=(s->rear+1)%MAXSIZE; s->elem[s->rear]=x; return(true); elemtypedelqueue(queuetype*s) /* 数据出队列*/ if(s-front==s->rear) /* 队列为空 */ return(NULL); else /* 队列非空 */ s->front=(s->front+1)%MAXSIZE; return(s->elem[s->front]); main() charch1,ch2; queuetype*p; intt,f; p=(queuetype*)malloc(sizeof(queuetype)); p->front=0; p->rear=0; if(f==FALSE) break; if(ch1==';'||ch1==',') ch2=delqueue(p); while(ch2! =NULL) break; else ch1=''; /*继续执行*/ /*先置空ch1*/ 实验六、 稀疏矩阵的建立与转置 实验目的: 1、了解稀疏矩阵的三元组存储形式。 2、熟悉掌握三元表存储矩阵的转置算法。 实验内容: 矩阵是很多的科学与工程计算中研究的数学对象。 在此,我们感兴趣的是,从数学结构这门学科着眼,如何存储矩阵的元从而使矩阵的各种运算有效的进行。 本来,用二维数组存储矩阵,在逻辑上意义是很明确的,也很容易理解,操作也很容易和方便。 但是在数值分析中经常出现一些阶数很高的矩阵,同时,在矩阵中又有很多值相同或者都为零的元素,可以对这种矩阵进行压缩存储: 对多个值相同的元素只分配一个存储空间;对零元素不分配空间。 稀疏矩阵的定义是一个模糊的定义: 示的矩阵: 即非零元个数较零元个数较少的矩阵。 例如下图所 0 0 3 0 12 0 0 0 9 0 0 24 0 0 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 为了实现稀疏矩阵的这种存储结构,式如下图: 0 J15 18 0 0 -7 0 0 引入三元组这种数据结构。 为一个稀疏矩阵。 三元组的线性表顺序存储形 MU NU TU I I V I J1v|,, I J V * A,B: ARRAY[1。 。 MAXNUM]OFTUPLE3TP 实验步骤 看懂书上的算法,参考书上的程序编写程序上机调试、输入数据、检验结果。 程序流程图 参考程序 structtuple3tp/*稀疏矩阵的建立和转置*/inti,j; intv; }; structsparmattp{intmu,nu,tu; structtuple3tpdata[31]; }; structsparmattpa,b; voidcrt_sparmat()inti; printf("输入稀疏矩阵行值,列值,最大非零元个数: "); scanf("%d%d%d",&a.mu,&a.nu,&a.tu); for(i=1;i<=a.tu;i++){printf("输入行坐标,列坐标,非零元"); scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); voidtrans_sparmat()intcol,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<=a.tu;p++)if(a.data[p].j==col){ b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; q++; out(structsparmattpx) inti,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.data[k].i)==i)&&((x.data[k].j)==j)){ flag=1; printf("%5d",x.data[k].v); if(flag==0)printf("0"); printf("\n"); main() printf("稀疏矩阵的建立与转置\n"); crt_sparmat(); trans_sparmat(); out(a); out(b); 实验七、二叉树及其先序遍历 实验内容: 1树型结构是一种非常重要的非线性结构。 树在客观世界是广泛存在的,在计算机领域里也得到了广泛的应用。 在编译程序里,也可用树来表示源程序的语法结构,在数据库系 统中,数形结构也是信息的重要组织形式。 2•节点的有限集合(N大于等于0)。 在一棵非空数里: (1)、有且仅有一个特定的根节点; (2)、当N大于1时,其余结点可分为M(M大于0)个互不相交的子集,其中每一个集合又是一棵树,并且称为根的子树。 树的定义是以递归形式给出的。 其次序不能颠倒。 3•二叉树是另一种树形结构。 它的特点是每个结点最多有两棵子树,并且,二叉树的子树有左右之分, 4.二叉树的结点存储结果示意图如下: 左指针域数据域右指针域 实验步骤 1•理解实验原理,读懂实验参考程序。 2. (1)在纸上画出一棵二叉树。 (2)输入各个结点的数据。 (3)验证结果的正确性。 程序代码 /*预先定义结点数目最大为50*/ #include"stdio.h"#include"stdlib.h"#defineMax50typedefcharelemtype;typedefstructbtnode{ elemtypedata;structbtnode*lchild,*rchild; }bitnode,*bitree;/*自定义结点类型*/ bitreeCreateBiTree() { /*先序遍历生成二叉树的递归算法*/bitreet;/*定义二叉树t*/charch; scanf("%c",&ch); if(ch=='.') t=NULL; else {t=(bitnode*)malloc(sizeof(bitnode));/*生成新的结点*/ t->data=ch; t->lchild=CreateBiTree();t->rchild=CreateBiTree(); /*对数据域赋值*/ /*递归构造左子树 /*递归构造右子树 */ */ }returnt; }/*CreateBiTree*/ voidPreOrderTraverse(bitreebt) { /*先序遍历二叉树递归算法*/if(bt! =NULL) { printf("%c",bt->data); PreOrderTraverse(bt->lchild);PreOrderTraverse(bt->rchild); /*访问根结点*/ /*先序遍历左子树 /*先序遍历右子树 */ */ } }/*PreOrderTraverse*/ voidmain() { bitreebt1; printf("creatbitree: \n");bt1=CreateBiTree();printf("preorder: \n"); PreOrderTraverse(bt1);}/*main*/ 实验八、中序、后序遍历二叉树 一、实验目的: 1.掌握二叉树遍历的算法。 2.掌握二叉树遍历非递归的实现算法。 实验内容: 并写出其中序、后序遍历非递归算法,并要求有 递归算法实现先序树遍历生成二叉树,输出结果验证。 三、程序代码: #include"stdio.h"#include"stdlib.h" #defineMax50 /*预先定义结点数目最大为50*/ typedefcharelemtype; typedefstructbtnodeelemtypedata; structbtnode*lchild,*rchild; }bitnode,*bitree; /*自定义结点类型*/ bitreeCreateBiTree()/*先序遍历生成二叉树的递归算法*/ bitreet; /*定义二叉树t*/ charch; scanf("%c",&ch); if(ch=='.') t=NULL; /*生成新的结点*/ else t=(bitnode*)malloc(sizeof(bitnode)); t->data=ch; /*对数据域赋值*/ /*递归构造左子树*/ /*递归构造右子树*/ t->lchild=CreateBiTree(); t->rchild=CreateBiTree(); returnt; }/*CreateBiTree*/voidInOrderTraverse2(bitreet) inttop=0; bitreep,s[Max]; intm; m=Max-1; p=t; do while(p! =NULL) if(top>m)return; top=top+1; s[top]=p; p=p->lchild; };/*遍历左子树*/if(top! =0) p=s[top]; 访问根结点*/ top=top-1; printf("%c\t",p->data);/*p=p->rchild;/*遍历右子树*/ while(p! =NULL||top! =0); }/*InOrderTraverse2*/ voidPostOrderTraverse2(bitreet) ints2[Max]; /*标志进栈次数的栈s2*/ inttop=0,flag; /*定义整型栈顶指针和标志值 */ bitreep,s1[Max]; /*定义指针和指针型栈*/ p=t; /*从根结点开始遍历*/ do while(p! =NULL) s1[top]=p; /*p所指向的结点入栈*/ s2[top++]=0; p=p->lchild; if(top>0) flag=s2[--top]; p=s1[top]; if(flag==0) s1[top]=p; s2[top++]=1; p=p->rchild; else 打印*/ /*标志p所指向的结点首次入栈*/ /*遍历p所指向结点的左子树*/ /*p所指向的结点入栈*/ /*标志p所指向的结点第二次入栈*/ /*遍历p所指向结点的右子树*/ printf("%c\t",p->data); /*第三次遇到该结点,将该结点 p=NULL; }while(top>0); }/*PostOrderTraverse2*/voidmain() bitreebt1; printf("createbitree: \n"); bt1=CreateBiTree(); printf("inordertraverse2: \n"); InOrderTraverse2(bt1); printf("\n,postorder2: \n"); PostOrderTraverse2(bt1); }/*main*/ 一、实验目的: 1.掌握线性查找常用方法;2、掌握二分查找的应用。 二、写出二分查找算法,并调试运行。 1.复习教材内容,深入理解线性查找算法。 2.编出程序上机调试。 三、代码实现: 四、结果验证: #include #include #defineLIST_SIZE20 typedefcharKeyType; typedefintOtherType; typedefstruct KeyTypekey; OtherTypeother_data; }RecordType; 为工作单元*/ typedefstruct RecordTyper[LIST_SIZE+1];/*r[0] intlength; }RecordList; voidcreatelist(RecordList*l) inti; intlen; KeyTypech; printf("请输入线性表的长度: "); scanf("%d",&len); l->length=len; for(i=1;i<=len;i++) printf(”请输入线性表的第%c个元素: ",i); fflush(stdin); scanf("%c",&ch); l->r[i].key=ch; intBinSrch(RecordListl,KeyTypek)/*在有序表l中折半查找其关键字等于k的元素,若找到,则函数值为该元素在表中的位置*/ intlow,high,mid; low=1; high=l.length;/*置区间初值*/ while(low<=high) mid=(low+high)/2; if(k==l.r[mid].key) return(mid);/*找到待查元素*/ else */ if(k high=mid-1;/*未找到,则继续在前半区间进行查找 else low=mid+1;/*继续在后半区间进行查找*/ return(0); voidmain() RecordListl; intlocate; KeyTypek; createlist(&l); printf("请输入要查找的元素: "); fflush(stdin); scanf("%c",&k); locate=BinSrch(l,k); if(locate==0) printf("未找到! \n"); else printf("该元素在表中的位置为%d\n",locate);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 三链表 及其 多项式 相加 答案 DOC