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

数据结构实验报告专业：软件工程班级：软件姓名： 2016年12月太原理工大学学生实验报告学院名称软件学院专业班级软件学号2实验成绩学生姓名实验题目线性表实验日期一目的与要求 本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。二例题 问题描述 用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。输入初始字符串，插入位置，插入字符，删除字符。输出已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。存储结构采用链式存储结构算法的基本思想建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。参考源程序#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三实习题用单链表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 #includestdafx.h#includestatic int n;static int m;static int max;struct Polynomialfloat 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; i data = 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; i next = 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)while (Pb != NULL)Pc-data = Pb-data;Pc = Pc-next;Pb = Pb-next;else if (Pb = NULL)while (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; i data, i);if (i = max)break;Hc = Hc-next;return 0;实验室名称致远楼指导教师姓名张月琴太原理工大学学生实验报告学院名称软件学院专业班级软件1学号实验成绩学生姓名实验题目树实验日期. 一目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。二例题问题描述任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。输入一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。对下图，其输入序列为ABD.EH.CF.I.G.。 A B C D E F G H I 输出若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。存储结构采用二叉链表存储。算法的基本思想采用递归方法建立和遍历二叉树。首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。参考源程序#include#include struct nodechar 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(); elsep=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);三实习题编写递归算法，计算二叉树中叶子结点的数目。#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; 实验室名称指导教师姓名太原理工大学学生实验报告学院名称软件学院专业班级软件学号实验成绩学生姓名实验题目图实验日期一目的与要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二例题问题描述给定一个图，设计一个程序，找出一条从某一顶点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 structint 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;elseQ-r+;if(Q-r=Q-f)printf(Overflow!n);front(queue *Q)if(Q-r=Q-f)printf(Underflow!n);elsereturn(Q-qQ-f);void deq(queue *Q)if(Q-r=Q-f)printf(Underflow!n);elseif(Q-f=19)Q-f=0;elseQ-f+; int qempty(queue Q)if(Q.f=Q.r)return 1;elsereturn 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(List-link is bulitn);for(i=1;i=n;i+)for(j=1;j=n;j+)printf(%3d,nodelistij);printf(n); void shortest(int a,int b)if(a=b)nodelistaa=2;elseenq(&Q,a);nodelistaa=2;finished=0;while(!qempty(Q)&!finished)a=front(&Q);deq(&Q);j=1;while(j=n)&!finished)if(nodelistaj=1)&(nodelistjj!=2)enq(&Q,j);nodelistjj=2;zj=a;if(j=b)/*&(nodelistaj=1)*/finished=1;if(!finished)j+; if (!finished) printf(There is no path.); void writepath(int a,int b)i=b;while(i!=a)printf(%d - ,i);i=zi; printf(%d,a);main()readgraph();printf(Please input a:);scanf(%d,&a);printf(Please input b:);scanf(%d,&b);Q.f=0; Q.r=0;shortest(a,b);if (finished)writepath(a,b);三实习题采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。#include#include#includeint n;struct VNode int position; struct VNode* next;struct ArcNode int mark; struct VNode* first;void DFS(struct ArcNode* v,struct ArcNode* w) struct VNode* L; w-mark=1; L=w-first; while(L!=NULL) if(v+(L-position)-mark=0) DFS(v,(v+L-position); L=L-next; int main() int i,j,k; int num=0; struct ArcNode* p; struct VNode* temp; struct VNode* flag; printf(该无向图有多少个顶点：n); scanf(%d,&n); while(n1) printf(你输入的值不合理，请重新输入：n); scanf(%d,&n); p=(struct ArcNode*)malloc(n*sizeof(struct ArcNode); for(i=0;iposition=k; temp-next=NULL; pi.first=temp; pi.mark=0; flag=temp; scanf(%d,&k); while(k!=-1) temp=(struct VNode*)malloc(sizeof(struct VNode); temp-position=k; temp-next=NULL; flag-next=temp; flag=temp; scanf(%d,&k); i=0; while(pi.mark=0) DFS(p,(p+i); num+; i=0; while(pi.mark!=0&in) i+; printf(此图的连通分量个数为：%dn,num); return 0; 实验室名称指导教师姓名太原理工大学学生实验报告学院名称软件学院专业班级软学号20实验成绩学生姓名实验题目查找实验日期一目的与要求通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。二例题问题描述将折半查找算法写成完整的程序，并上机通过。输入有序表（12,23,28,35,37,39,50,60,78,90）及待查找记录23,58。输出输入23，表中存在待查找记录，则显示该记录在表中位置2，输入58显示该记录不存在。存储结构有序表采用顺序方式存储。算法的基本思想首先用待查找记录与查找区间中间位置记录比较，若相等则查找成功，返回该记录在表中的位置数，若小于中间位置记录，则修改区间上界为中间位置减 1，若大于中间位置记录，则修改区间下界为中间位置加 1，在新的区间内继续查找。当查找区间下界大于上界，则该记录不存在。参考源程序#includestdio.htypedef structint a30;int length;sqtable;sqtable st;int b=0;void createst(int k)int i;printf(Please input data:); st.a0=-100;for (i=1;(!b&(i=k);i+)scanf(%d,&(st.ai);if (st.aist.ai-1) printf(Input data error.n); b=1; if (!b) st.length=k; printf(The table is builted.n); void stfind(sqtable st,int y) int f,l,h,m; l=1;h=st.length; f=1; while (l=h)&f) m=(l+h)/2; if (y=st.am) f=0; else if (yst.am) h=m-1; else l=m+1; if (!f) printf(Find %d in position %d.n,y,m); else printf(Not find %d.n,y); main()int n,x;printf(nPlease input n:);scanf(%d,&n);createst(n);if (b=0) printf(Please input you want find value:);scanf(%d,&x);stfind(st,x);三实习题试将折半查找的算法改写成递归算法#includestdafx.h#include#include#includeint Search(int* a, int k, int low, int hight)int mid;if (lowhight)return 0;mid = (low + hight) / 2;if (amid = k)return (mid + 1);else if (amidk)return Search(a, k, low, mid - 1);elsereturn Search(a, k, mid + 1, hight);int main()int *p;int i, n, key, position;printf(输入数据数量：n);scanf(%d, &n);p = (int*)malloc(n*sizeof(int);printf(请按非递减序列输入你的数据（整型），并用空格隔开：n);scanf(%d, &p0);for (i = 1; in; i+)scanf(%d, &pi);while (pipi - 1)printf(你输入的数据不合理，请重新输入：n);scanf(%d, &pi);printf(请输入你要查找的数据：n);scanf(%d, &key);position = Search(p, key, 0, n - 1);if (position = 0)printf(没有找到你要查找的数据！n);elseprintf(你所查找的数据位于原有序表的第%d个位置！n, position);return 0;实验室名称指导教师姓名太原理工大学学生实验报告学院名称软件学院专业班级软件学号20实验成绩学生姓名实验题目内排序实验日期一目的与要求通过本次实验，掌握线性表的排序方法，并分析时间复杂度。二例题问题描述将快速排序算法写成完整的程序上机通过，并统计递归深度。输入待排序记录个数n，各待排序记录值。输出n个记录由小到大排列的结果。存储结构待排序记录顺序存储。算法的基本思想快速排序算法每次任取一个记录的关键字为标准，将其余记录分为两组，将所有关键字小于或等于标准的记录都放在它的位置之前，将所有关键字大于标准的记录都放在它的位置之后。对这两组再进行快速排序，直到完全有序。每递归1次，递归深度加1。参考源程序#includetypedef int node;node afile20;node x;int d,dl,n;int l,r,i,j;void q(int l,int r)int p;d+;if(dld)dl=d;printf(dl=%d ,dl);printf(d=%dn,d);if(lx)&(ji)j-;if(ij)afilei+=afilej;while(afileii)i+;if(ij)afilej-=afilei; afilei=x;for(p=1;p=n;p+)printf(%d,afilep);printf(n);q(l,i-1);q(i+1,r);d-;printf( * *%d* *n,d);main() int p;printf(nPlease input n:n);scanf