太原理工大学数据结构实验报告2016

《数据结构》实验报告专业：软件工程班级：软件姓名：2016年12月太原理工大学学生实验报告学院名称软件学院专业班级软件学号2实验成绩学生姓名实验题目线性表实验日期一．目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。二．例题[问题描述]用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。[输入]初始字符串，插入位置，插入字符，删除字符。[输出]已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。[存储结构]采用链式存储结构[算法的基本思想]建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。[参考源程序]#defineNULL0typedefstructnode{chara;structnode*link;}node,*nodelink;voidreadlink(nodelinkhead){nodelinkp,q;charc;p=head;printf(Inputalinktable(astring):);scanf(%c,&c);if(c=='\n')printf(Thisstringisempty。);while(c!='\n'){q=(nodelink)malloc(sizeof(node));q-a=c;p-link=q;p=q;scanf(%c,&c);}p-link=NULL;}voidwritelink(nodelinkhead){nodelinkq;if(head-link==NULL)printf(Thislinkisempty。\n);for(q=head-link;q;q=q-link)printf(%c,q-a);printf(\n);}intinsert(nodelinkhead,chark1,chark2){nodelinkp,q;p=head-link;while(p-a!=k1&&p)p=p-link;if(p){q=(nodelink)malloc(sizeof(node));q-a=k2;q-link=p-link;p-link=q;return1;}else{printf(Thereisno%c\n,k1);return0;}}intdelete(nodelinkhead,chark){nodelinkp,q;q=head;p=head-link;while(((p-a)!=k)&&p){q=q-link;p=p-link;}if(p){q-link=p-link;return1;}else{printf(Thereisno%c\n,k);return0;}}voidopside(nodelinkhead){nodelinkp,q;p=head-link;while(p-link){q=p-link;p-link=q-link;q-link=head-link;head-link=q;}}main(){chark1,k2,k3;nodelinkhead;head=(nodelink)malloc(sizeof(node));head-link=NULL;readlink(head);if(head-link!=NULL){printf(Buildlinkis:);writelink(head);}if(head-link!=NULL){printf(Pleaseinputacharyouwanttoinsertafter:);k1=getch();printf(%c\n,k1);printf(Pleaseinputacharyouwanttoinsert:);k2=getch();printf(%c\n,k2);if(insert(head,k1,k2)){printf(After%cinsert%c,linkis:,k1,k2);writelink(head);}printf(Pleaseinputacharyouwanttodelete:);k3=getch();printf(%c\n,k3);if(delete(head,k3)){printf(afterdelete%c,linkis:,k3);writelink(head);}if(head-link!=NULL){printf(Opsiteresultis:);opside(head);writelink(head);free(head);}}}[运行情况]Inputalinktable(astring):lopui↙Buildlinkis:lopuiPleaseinputacharyouwanttoinsertafter:p↙Pleaseinputacharyouwanttoinsert:y↙Afterpinserty,linkis:lopyuiPleaseinputacharyouwanttodelete:p↙afterdeletep,linkis:loyuiOpsiteresultis:iuyol三．实习题用单链表ha存储多项式A（x）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb存储多项式B（x）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x）=A（x）+B（x），结果存到单链表hc中。试写出程序。实验程序：#includestdio.h#includemalloc.h#includestdafx.h#includemalloc.hstaticintn;staticintm;staticintmax;structPolynomial{floatdata;structPolynomial*next;};structPolynomial*Creat_H(intk){structPolynomial*L;structPolynomial*p;p=(structPolynomial*)malloc(sizeof(structPolynomial));L=p;floattemp;inti;printf(请依次输入系数(中间用空格隔开)：\n);for(i=0;i=k;i++){scanf_s(%f,&temp);p-data=temp;if(i==k){p-next=NULL;break;}p-next=(structPolynomial*)malloc(sizeof(structPolynomial));p=p-next;}returnL;}structPolynomial*Calculate(structPolynomial*Pa,structPolynomial*Pb){structPolynomial*Pc;structPolynomial*L;inti;max=n=m?n:m;Pc=(structPolynomial*)malloc(sizeof(structPolynomial));L=Pc;for(i=0;i=max;i++){if(i==max){Pc-next=NULL;break;}Pc-next=(structPolynomial*)malloc(sizeof(structPolynomial));Pc=Pc-next;}Pc=L;while(Pa!=NULL&&Pb!=NULL){Pc-data=Pa-data+Pb-data;Pc=Pc-next;Pa=Pa-next;Pb=Pb-next;}if(Pa==NULL){while(Pb!=NULL){Pc-data=Pb-data;Pc=Pc-next;Pb=Pb-next;}}elseif(Pb==NULL){while(Pa!=NULL){Pc-data=Pa-data;Pc=Pc-next;Pa=Pa-next;}}returnL;}intmain(){inti;structPolynomial*Ha,*Hb,*Hc;printf(请输入多项式a的最高次系n:\n);scanf_s(%d,&n);Ha=Creat_H(n);printf(请输入多项式b的最高次系m:\n);scanf_s(%d,&m);Hb=Creat_H(m);Hc=Calculate(Ha,Hb);printf(系数:次数:\n);for(i=0;i=max;i++){printf(%f%-4d\n,Hc-data,i);if(i==max){break;}Hc=Hc-next;}return0;}实验室名称致远楼指导教师姓名张月琴太原理工大学学生实验报告学院名称软件学院专业班级软件1学号实验成绩学生姓名实验题目树实验日期.一．目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。二．例题[问题描述]任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。[输入]一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD..EH...CF.I..G..。ABCDEFGHI[输出]若为空二叉树，则输出：THISISAEMPTYBINARYTREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。[存储结构]采用二叉链表存储。[算法的基本思想]采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。[参考源程序]#includestdio.h#includealloc.hstructnode{charinfo;structnode*llink,*rlink;};typedefstructnodeNODE;NODE*creat(){charx;NODE*p;scanf(%c,&x);printf(%c,x);if(x!='.'){p=(NODE*)malloc(sizeof(NODE));p-info=x;p-llink=creat();p-rlink=creat();}elsep=NULL;returnp;}voidrun(NODE*t){if(t){run(t-llink);run(t-rlink);printf(%c,t-info);}}main(){NODE*T;printf(PLeaseinputatree:\n);T=creat();printf(\n);if(!T)printf(Thisisaemptybinarytree.);else{printf(Theresultofposttraveseis:\n);run(T);}printf(\n);}三．实习题编写递归算法，计算二叉树中叶子结点的数目。#includestdio.hstructBiTree{chardata;structBiTree*lchild;structBiTree*rchild;};structBiTree*CreatBiTree(){charx;structBiTree*p;scanf(%c,&x);if(x!='.'){p=(structBiTree*)malloc(sizeof(structBiTree));p-data=x;p-lchild=CreatBiTree();p-rchild=CreatBiTree();