北京邮电大学远程教育计算机科学与技术专业《数据结构》实验指导书
实验一线性表的插入和删除
一、实验目的
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 { printf(“data[%d]=”, i); scanf (“%d”, (*L).data[i]); (*L).last=n-1; printf(“\n”); } printout (L) sequenlist *L; { int i; for(i=0; i<(*L).last; i++) { printf(“data[%d]=”, i); printf(“%d”, (*L).data[i]); } } main( ) { sequenlist *L; char cmd; int i, t; clscr( ); printf(“i, I…..插入\n”); printf(“d,D…..删除\n”); printf(“q,Q……退出\n”); do { do { cmd =getchar( ); } while((cmd!=‘d’)‖(cmd!=‘D’) ‖(cmd!=‘q’) ‖ (cmd!=‘Q’) ‖(cmd!=‘i’) ‖(cmd!=‘I’)); switch (cmd) { case ‘i’,‘I’; scanf(&x); scanf(&i); insert(L, x, i); printout(L); break; case ‘d’,‘D’; scanf(&i); delete(L, i); printout(L); break; } } while ((cmd!=‘q’)&&( cmd!=‘Q’)); } 实验二二叉树的操作 一、实验目的 1、进一步掌握指针变量、动态变量的含义; 2、掌握二叉树的结构特征,以及各种存储结构的特点及适用范围; 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实验内容 已知以二叉链表作存储结构,试编写按层次顺序遍历二叉树的算法。 算法思想:本算法要采用一个队列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; float wgt; struct node *next; }edgenode; typedef struct { char vtx; edgenode *link; }vexnode; typedef vexnode Graph[n]; void Floyd(Graph G, float A[n][n], int p[n][n]) { int i, j, k;