太原理工数据结构实验报告完整版.doc

实验名称：线性表一目的与要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。二例题 问题描述 用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。输入初始字符串，插入位置，插入字符，删除字符。输出已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。存储结构采用链式存储结构算法的基本思想建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。参考源程序#define NULL 0typedef struct node char a; struct node *link;node,*nodelink;void readlink(nodelink head) nodelink p,q; char c; p=head; printf(Input a linktable(a string):); scanf(%c,&c); if (c=n) printf(This string is empty。); while(c!=n) q=(nodelink)malloc(sizeof(node); q-a=c; p-link=q; p=q; scanf(%c,&c); p-link=NULL;void writelink(nodelink head) nodelink q; if (head-link=NULL) printf( This link is empty。n); for(q=head-link;q;q=q-link) printf(%c,q-a); printf(n); int insert(nodelink head,char k1,char k2) nodelink p,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; return 1; else printf(There is no %cn,k1); return 0; int delete(nodelink head,char k) nodelink p,q; q=head; p=head-link; while(p-a)!=k)&p) q=q-link; p=p-link; if(p) q-link=p-link; return 1; else printf(There is no %cn,k); return 0; void opside(nodelink head) nodelink p,q; p=head-link; while(p-link) q=p-link; p-link=q-link; q-link=head-link; head-link=q; main() char k1,k2,k3; nodelink head; head=(nodelink)malloc(sizeof(node); head-link=NULL; readlink(head); if (head-link!=NULL) printf(Build link is :); writelink(head); if (head-link!=NULL) printf(Please input a char you want to insert after:); k1=getch(); printf(%cn,k1); printf(Please input a char you want to insert:); k2=getch(); printf(%cn,k2); if (insert(head,k1,k2) printf(After %c insert %c,link is:,k1,k2); writelink(head); printf(Please input a char you want to delete:); k3=getch(); printf(%cn,k3); if (delete(head,k3) printf(after delete %c,link is:,k3); writelink(head); if (head-link!=NULL) printf(Opsite result is :); opside(head); writelink(head); free(head); 运行情况Input a linktable(a string):lopuiBuild link is :lopuiPlease input a char you want to insert after:pPlease input a char you want to insert:yAfter p insert y,link is:lopyuiPlease input a char you want to delete:pafter delete p,link is:loyuiOpsite result is :iuyol三实习题 1设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。实验程序：#include stdio.h#include malloc.h#include conio.htypedef struct nodechar a;struct node *link;node,*nodelink;void readlink(nodelink head)nodelink p,q;char c;p=head;printf(请输入顺序表中的递增有序元素:);scanf_s(%c,&c);if(c=n) printf(顺序表为空nn);while(c!=n)q=(nodelink)malloc(sizeof(node);q-a=c;p-link=q;p=q;scanf_s(%c,&c);p-link=0;/构造顺序表int add(nodelink head)nodelink p;p=head;if(p-link=0) return 0;while(p-link!=0)if(p-a p-link-a)printf(输入有误请重新输入nn);return 0;p=p-link;return 1;/判断输入元素是否递增void insert(nodelink head,char x)nodelink p,q,m;int i=0;p=head;q=(nodelink)malloc(sizeof(node);q-a=x;m=p;while(p-link!=0)if(p-a = x)q-link=m-link;m-link=q;i=1;break;m=p;p=p-link;if(i=0)p-link=q;q-link=0;/插入元素void main()loop:nodelink head;nodelink p;char x,z;head=(nodelink)malloc(sizeof(node);head-link=0;readlink(head);while(add(head)=0)readlink(head);printf(您输入的顺序表为:);for(p=head-link;p!=0;p=p-link)printf(%c,p-a);printf(n请输入您要插入的字符:);x=getchar();insert(head,x);printf(插入%c后的顺序表为:,x);for(p=head-link;p!=0;p=p-link)printf(%c,p-a);printf(nn);scanf_s(%c,&z);goto loop;/goto语句仅仅为了达到循环使用的目的2用单链表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 #include static int n;static int m;static int max;struct Polynomial/多项式系数结构体float data;struct Polynomial* next;struct Polynomial* Creat_H(int k)/创建多项式系数的链表struct Polynomial* L;struct Polynomial* p; p=(struct Polynomial*)malloc(sizeof(struct Polynomial);L=p;float temp;int i;printf(请依次输入系数(中间用空格隔开)：n);for(i=0;idata=temp;if(i=k)p-next=NULL;break;p-next=(struct Polynomial*)malloc(sizeof(struct Polynomial);p=p-next;return L;struct Polynomial* Calculate(struct Polynomial* Pa,struct Polynomial* Pb)/计算两个多项式相加struct Polynomial* Pc; struct Polynomial* L;int i;max=n=m? n:m;Pc=(struct Polynomial*)malloc(sizeof(struct Polynomial);L=Pc;for(i=0;inext=NULL;break;Pc-next=(struct Polynomial*)malloc(sizeof(struct Polynomial);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)/Pa的长度小于Pbwhile(Pb!=NULL)Pc-data=Pb-data;Pc=Pc-next;Pb=Pb-next;else if(Pb=NULL)/Pb的长度小于Pawhile(Pa!=NULL)Pc-data=Pa-data;Pc=Pc-next;Pa=Pa-next;return L;int main() int i;struct Polynomial *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;idata,i);if(i=max)break;Hc=Hc-next;return 0;3设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。实验程序：#include stdio.h#include malloc.h#include conio.htypedef struct nodeint a;struct node *link;node,*nodelink;void make(nodelink head,int n)int i;nodelink p,q;p=head;for(i=0;ia=i+1;p-link=q;q-link=head-link;p=p-link;/构造循环链表void remake(nodelink head,nodelink link,int n,int m,int s)int i;nodelink p,q,r;p=head-link;q=p;for(i=1;ilink;if(p=head-link)for(i=1;ilink;r=link;dofor(i=1;ilink;q-link=p-link;p-link=NULL;r-link=p;r=r-link;p=q-link;while(p!=p-link);r-link=p;r-link-link=NULL;/轮流出列void write(nodelink link,int n)int i;nodelink p;p=link-link;for(i=0;ilink)printf(%d ,p-a);/输出按出列顺序得到的顺序表void main()loop:nodelink head,link;int m,n,s;head=(nodelink)malloc(sizeof(node);/保存初始顺序link=(nodelink)malloc(sizeof(node);/保存出列顺序printf(输入总人数n:);scanf_s(%d,&n);make(head,n);printf(输入开始的人s:);scanf_s(%d,&s);printf(输入要数的数字m:);scanf_s(%d,&m);remake(head,link,n,m,s);write(link,n);printf(nn);goto loop;/达到循环使用的目的实验名称：树的应用一目的与要求 熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计 算机科学及其它工程技术中的应用。二例题 问题描述任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它 进行遍历。输入一棵二叉树的结点若无子树，则可将其子树看作 “.”，输入时，按照前序序列的顺序输入该结点的内容。对 下图，其输入序列为ABD.EH.CF.I.G.。输出若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。存储结构采用二叉链表存储。算法的基本思想采用递归方法建立和遍历二叉树。首先建立二叉树的根 结点，然后建立其左右子树，直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。参考源程序#include#includestruct node char info; struct node *llink,*rlink; ;typedef struct node NODE;NODE *creat() char x; NODE *p; scanf(%c,&x); printf(%c,x); if(x!=.) p=(NODE *)malloc(sizeof(NODE); p-info=x; p-llink=creat(); p-rlink=creat(); else p=NULL; return p;void run(NODE *t) if(t) run(t-llink); run(t-rlink); printf(%c,t- info); main() NODE *T; printf(PLease input a tree:n); T=creat(); printf(n); if(!T) printf(This is a empty binary tree.); else printf(The result of post travese is:n ); run(T); printf(n);三实习题 1 编写递归算法，计算二叉树中叶子结点的数目。#includestruct BiTree char data; struct BiTree *lchild; struct BiTree *rchild; struct BiTree* CreatBiTree() char x; struct BiTree* p; scanf(%c,&x); if(x!=.) p=(struct BiTree*)malloc(sizeof(struct BiTree); p-data=x; p-lchild=CreatBiTree(); p-rchild=CreatBiTree(); else p=NULL; return p;int LeafNum(struct BiTree *T) if(!T) return 0; else if(!T-lchild&!T-rchild) return 1; else return LeafNum(T-lchild)+LeafNum(T-rchild); int main() int num; struct BiTree* T; printf(请按先序序列输入二叉树n); T=CreatBiTree(); while(T=NULL) printf(empoty,again:n); T=CreatBiTree(); num=LeafNum(T); printf(n二叉树叶子结点为:%dn,num); system(pause); return 0; 2 编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。#include#include#includestatic int m=0;static int n=0;int k;struct BiTree char data; struct BiTree* lchild; struct BiTree* rchild;struct BiTree* CreatBiTree() char x; struct BiTree* p; scanf(%c,&x); if(x!=.) p=(struct BiTree*)malloc(sizeof(struct BiTree); p-data=x; m+; p-lchild=CreatBiTree(); p-rchild=CreatBiTree(); else p=NULL; return p;void Search(struct BiTree* T) if(T) n+; if(n=k) printf(位于先序序列第K个结点的数据为：%cn,T-data); Search(T-lchild); Search(T-rchild); int main() struct BiTree* T; char temp; printf(请按先序序列输入二叉树（如：ab.表示a为根结点，b为左子树的二叉树）n); T=CreatBiTree(); while(T=NULL) printf(你输入的对叉树为空，请重新输入：n); temp=getchar(); T=CreatBiTree(); printf(请输入K的值：n); scanf(%d,&k); while(km) printf(你输入的K值不合理，请重新输入：n); scanf(%d,&k); Search(T); system(pause); return 0;3 将上述例题用非递归程序实现。1_2:#include#includestatic int m=0;struct BiTree char data; struct BiTree* lchild; struct BiTree* rchild;struct Statck struct BiTree* *base; struct BiTree* *top; ;void InitStatck(struct Statck &p) p.base=(struct BiTree* *)malloc(m*sizeof(struct BiTree*); p.top=p.base; void Push(struct Statck &s,struct BiTree* e) *(s.top)+=e;void Pop(struct Statck &s,struct BiTree* &e) e=*-s.top; int StatckEmpty(struct Statck s) if(s.top=s.base) return 1; else return 0; struct BiTree* CreatBiTree() char x; struct BiTree* p; scanf(%c,&x); if(x!=.) p=(struct BiTree*)malloc(sizeof(struct BiTree); p-data=x; m+; p-lchild=CreatBiTree(); p-rchild=CreatBiTree(); else p=NULL; return p;int LeafNum(struct BiTree* T) int i=0; int flag; struct Statck L; InitStatck(L); while(T|!StatckEmpty(L) if(T) Push(L,T); T=T-lchild; if(T=NULL) flag=1; else Pop(L,T); T=T-rchild; if(T=NULL&flag=1) i+; flag=0; return i;int main() int num; char temp; struct BiTree* T; printf(请按先序序列输入二叉树（如：ab.表示a为根结点，b为左子树的二叉树）n); T=CreatBiTree(); while(T=NULL) printf(你输入的对叉树为空，请重新输入：n); temp=getchar(); T=CreatBiTree(); num=LeafNum(T); printf(n你所输入的二叉树的叶子个数为：%dn,num); system(pause); return 0;2-2:#include#includestatic int m=0;static int n=0;int k;struct BiTree char data; struct BiTree* lchild; struct BiTree* rchild;struct Statck struct BiTree* *base; struct BiTree* *top; ;void InitStatck(struct Statck &p) p.base=(struct BiTree* *)malloc(m*sizeof(struct BiTree*); p.top=p.base; void Push(struct Statck &s,struct BiTree* e) *(s.top)+=e;void Pop(struct Statck &s,struct BiTree* &e) e=*-s.top; int StatckEmpty(struct Statck s) if(s.top=s.base) return 1; else return 0; struct BiTree* CreatBiTree() char x; struct BiTree* p; scanf(%c,&x); if(x!=.) p=(struct BiTree*)malloc(sizeof(struct BiTree); p-data=x; m+; p-lchild=CreatBiTree(); p-rchild=CreatBiTree(); else p=NULL; return p;void Search(struct BiTree* T) struct Statck L; InitStatck(L); while(T|!StatckEmpty(L) if(T) n+; if(n=k) printf(位于先序序列第K个结点的数据为：%cn,T-data); Push(L,T); T=T-lchild; else Pop(L,T); T=T-rchild; int main() struct BiTree* T; char temp; printf(请按先序序列输入二叉树（如：ab.表示a为根结点，b为左子树的二叉树）n); T=CreatBiTree(); while(T=NULL) printf(你输入的对叉树为空，请重新输入：n); temp=getchar(); T=CreatBiTree(); printf(请输入K的值：n); scanf(%d,&k); while(km) printf(你输入的K值不合理，请重新输入：n); scanf(%d,&k); Search(T); system(pause); return 0;实验名称：图的应用一目的与要求 熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二例题 问题描述给定一个图，设计一个程序，找出一条从某一顶点A到另一顶点B边数最少的一条路径。输入图的顶点个数N，图中顶点之间的关系及要找的路径的起点A和终点B。输出若A到B无路径，则输出“There is no path”，否则输出A到B路径上各顶点。存储结构图采用邻接矩阵的方式存储。 算法的基本思想采用广度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,.,VAK, 访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,.,VA1M，再访问与VA2邻接顶点.，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。参考源程序#includeint number;typedef struct int q20; int f,r;queue;int nodelist2020;queue Q;int z20;int a,b,n,i,j,x,y;int finished;void enq(queue *Q,int x) Q-qQ-r=x; if(Q-r=19) Q-r=0; else Q-r+; if(Q-r=Q-f) printf(Overflow!n);front(queue *Q) if(Q-r=Q-f) printf(Underflow!n); else return(Q-qQ-f);void deq(queue *Q) if(Q-r=Q-f) printf(Underflow!n); else if(Q-f=19) Q-f=0; else Q-f+; int qempty(queue Q) if(Q.f=Q.r) return 1; else return 0;void readgraph() printf(nPlease input n:); scanf(%d,&n); printf(Please input nodelistij:n); for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&nodelistij); printf(n); printf(Lis