《数据结构》期中作业

1、北京邮电大学远程教育计算机科学与技术专业数据结构实验指导书 实验一线性表的插入和删除 一、实验目的1、掌握用Turbo C上机调试线性表的基本方法;2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、实验内容 线性表基本操作的实现当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须 先将线性 表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到 该位置。若要删除第i个元素时，也必须把第i个元素之 后的所有元素前移一个位置。程序实现:typedefNullO;typ edefintdat ype;#d

2、efinemaxsize1024;typ edefstruct datyp edataiTiaxsize;intlast;sequenlist;intinsert(L, x, i) sequenlist*L;inti;1 / 13if (*L)Jast= =maxsize-1)9/13 pnnH("overflow ");returnNullJelse if (i<1) II (i>(*L).last+1) pnntf(“ error");return Null;else for(j=rL)Jast;j>=h1；H (*L).dataj+1=(*

3、L).dataj； (*L).datai-1=x;(*L),last=(*L),last+1; return sequenlist*L;inti;if (i<1)I(i>(*L).last+1) printf ( “error");return Null;elsefor(j=i, j<=(*L).last; j+)(*L).dataj-1=(*L).dataj； (*L).data - -Jreturn (1);voidcreatlist() sequenlist*L;intnJJ;printf（请“输入n个数据n ）;scanf( “ %d" ，&

4、;n);for(i=0; ivn; i+) printf( “ data%d= * , i););printout(L)scant (“ %d, (*L).datai);(*L)Ja-1 s;t=n printf( n " sequenlist*L;inti;for(i=0; i<(*L)Jast; i+) printf( “ data%d= ” , i);printf( “ %d , (*L).datai); main() sequenlist*L;charcmd;clscr();printf(“ i插入-“ d fflprintf(除printf(“q,QH 出5"

5、;dodocmd=getchar( );while(cmd!=;switch (cmd)scanf(&i);insert(L, x, i);prin tout(L);break;D* ;scanf(&i);'cP ) II (cmd!- ，D ) II (cmd!二'q，) II (cmd!二CTI ' ;scanf(&x);delete(L, i);prin tout(L);break;while (cmd!=、实验目的q )&&(cmd实验二二叉树的操作1、进一步掌握指针变量、动态变量的含义;掌握二叉树的结构特征，以及各种存储

6、结构的特点及适用范围；3、掌握用指针类型描述、访问和处理二叉树的运算。、实验内容已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。算法思想:本算法要采用一个队列q,先将二叉树根结点入队列，然后退队列，输出该结点；若它 有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列 空为止。因为队列的特点是先进先出，从而达到按层 次顺序遍历二叉树的目的。程序实现:#defineM 100 #defineNullO typ edefstruct node in tdata;stuuctnode*lchild, *rchild;bitree;bitree*queM;int

7、fro nt=0,rear=0;bitree *creat() bitree *t;intx;scant ( " %d" , &x);if (x= =0) t=Null;elset=malloc(sizeof(bitree);t data 二 X；t Ichild 二 creat();trchild=creat( );returnt;voidinorder( t) bitree*t;if (t!=Null) inorder (t Ichild);printf( ”4cr； t data);inorder (t rchild); voidenque(t) bitree

8、*t;if(front!=(rear+1) % M) rear = (rear+1) % M;querear=t; bitree*delque( )if (front= =rear) returnNull;front=(front+1) % M;return (quefront);voidlevorder (t) bitree*t; bitree *p;enque( t);while(front!=rear) p=delque();printf( “ 4cr , p /data);if(p flchild!二 Null) enque(p flchild);if(p frchild!=Null)

9、enque(p frchild); main () bitree *root;printf( n root=creat () ino rder(root);printf( n levorder(root);实验三图的操作一、实验目的1、掌握图的基本存储方法;2、掌握有关图的操作算法并用高级语言实现;3、熟练掌握图的两种搜索路径的遍历方法。二、实验内容 假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区算法思想:下面是R、W、Floyd求每对顶点之间最短路径算法的C语言程序，程序中矩阵A用 来进行n次迭代，矩阵P用来记录路径，Pij为迭代过程中当前已经求得的从顶点i到顶 点j的最短

10、路径上最后被插入的那个顶点。算法实现:typ edefstruct node intno;floatwgt;struct no de* next;edgenode;typ edefstruct charvtx;edgenode*li nk;vexnode;typ edefvexnodeGra phn;voidFloyd(Graph G, float Ann, int pnn)intij,k;for(i=0; i<n; i+) for(j=0;j<n;j+)Aij=Gij；Pijh1；for(k=0;kvn;k+) for (i=0; ivn;i+) for (j=0; j<n

11、; j+) if(Aik +Akj<AiD)PiD=k;Aij=Aik+Akj;实验四排序 一、实验目的1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法;2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用;3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验内容统计成绩问题描述给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算 法：(1)按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名 次；(2) 按名次列出每个学生的姓名与分数。基本要求学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出

12、进行格式 控制。算法实现下面给出的是用直接选择排序算法实现的C语言程序。#definen30 typ edefstructstudent char name8;intscore;studentRn;main () intnumJJ,max,temp;phntf( n请输入学生成绩: for(i=0;i vn;i+) printf (姓名“: scant ( “ %s ，&stui,name);scant ( “4cr，&stui.score);num=1;for (i=0;ivn;i+) max=i;for (j=i+1;jvn ;j+) if (Rj.score>Rma

13、x,score) max=j;tern p = Rmax;Rmax=Ri;Ri= temp;if (i>0)&&(Ri,score<Ri-1 ,score) num=num+1;printf( “ %4d%s%4 d , num, Ri,name, Ri,score);实验五查找、实验目的1、掌握查找的不同方法，并能用高级语言实现查找算法;2、熟练掌握二叉树的构造和查找方法。二、实验内容 设计一个读入一串整数构成一棵二叉排序树的算法。实现提示二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建 立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是

14、二叉排序树插入运 算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。算法实现typedefstruct nodeintkey;in tother;struct no de*lchild, *rchild; bstnode;voidinorder (t) bstno de*t;ino rder(t Ichild);printf( “ %4d', t key);ino rder(t rcdh);il bstnode*insertbst(t, s) bstno de*s,*t; bstnode*f,*p;P=t;while(p!=Null) f=P； if (s key 二=卩一key)returnt;if (s keyvp key)p=p Ichild;else p=prchild;if(t= =Null)returns;if (s key<f key)f lchild=s; elsef rchild=s;returntjbst no de*creatord() bstnode*t, * s;intkey;t=Null;scanf( “cr,&key);while