《数据结构》期中作业.doc

精品文档】如有侵权，请联系网站删除，仅供学习与交流《数据结构》期中作业.....精品文档......北京邮电大学远程教育计算机科学与技术专业《数据结构》实验指导书实验一 线性表的插入和删除一、 实验目的1、 掌握用Turbo C上机调试线性表的基本方法；2、 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算二、 实验内容线性表基本操作的实现当我们要性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置程序实现： typedef Null 0; typedef int datatype; #define maxsize 1024; typedef struct { datatype data[maxsize]; int last; }sequenlist; int insert(L, x, i) sequenlist *L; int i; { int j; if ((*L).last= =maxsize-1) { printf(“overflow”); return Null; else if ((i<1)‖(i>(*L).last+1) { printf(“error”); return Null; else { for(j=(*L).last; j>=i-1; j--) (*L).data[j+1]=(*L).data[j]; (*L).data[i-1]=x; (*L).last=(*L).last+1; return(1); int delete(L,i) sequenlist *L; int i; { int j; if ((i<1)‖(i>(*L).last+1)) {printf (“error”); return Null; else { for(j=i, j<=(*L).last; j++) (*L).data[j-1]=(*L).data[j]; (*L).data - -; return(1); void creatlist( ) { sequenlist *L; int n, i, j; printf(“请输入n个数据\n”); scanf(“%d”,&n); for(i=0; i

二、 实验内容已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法算法思想：本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的程序实现： #define M 100 #define Null 0 typedef struct node { int data; stuuct node *lchild, *rchild;} bitree; bitree *que[M]; int front=0, rear=0;bitree *creat( ){ bitree *t;int x;scanf (“%d”, &x);if (x= =0) t=Null;else t=malloc(sizeof(bitree)); t→data=x; t→lchild=creat( ); t→rchild=creat( );return t;void inorder( t )bitree *t;{ if (t!=Null) { inorder (t→lchild); printf(“%4d”, t→data); inorder (t→rchild);void enqueue(t)bitree *t;{ if(front!=(rear+1) % M) {rear = (rear+1) % M;que[rear]=t; bitree *delqueue( ) if (front= =rear) return Null; front=(front+1) % M; return (que[front]);void levorder ( t ) bitree *t;{ bitree *p; if(t!=Null) {enqueue( t );while(front!=rear){ p=delqueue( ); printf(“%4d”, p→data); if(p→lchild!=Null) enqueue(p→lchild); if(p→rchild!=Null) enqueue(p→rchild);}main ( ) { bitree *root; printf(“\n”); root=creat ( ); inorder(root); printf(“\n”); levorder(root);实验三 图的操作一、 实验目的1、 掌握图的基本存储方法；2、 掌握有关图的操作算法并用高级语言实现；3、 熟练掌握图的两种搜索路径的遍历方法。

二、 实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所算法思想：下面是R、W、Floyd求每对顶点之间最短路径算法的C语言程序，程序中矩阵A用来进行n次迭代，矩阵P用来记录路径，P[i][j]为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点算法实现：typedef struct node{ int no; floa。