2009级数据结构实验指导书

数据结构实验指导书

教案

2010～2011学年 第1学期

《数据结构》实验教案

教学院（部） 计算机学院

教 研 室 基础教研室

授 课 班 级 09应用

授 课 教 师 杨 慧

职 称 职 务 讲 师

教 材 名 称 《数据结构》 朱战立 主编

2010年 8 月30 日

- 1 -

数据结构实验指导书

实 验 安 排 表

周次 4 5-6 7 8 9 14 15 16 日期 9.20-9.24 9.27-10.8 10.8-10.15 实验课题 实验一 线性表 （一） 实验一 线性表（二） 实验一 线性表 （三） 学时 2 2 2 2 2 2 2 2 实验报告次 数 0 0 1 1 1 1 0 1 10.18-10.22 实验二 栈、队列的实现及应用 10.25-10.29 实验三 串及数组的实验 11.29-12.3 12.6-12.10 实验四 二叉树的基本操作 实验五 查找和排序（一） 12.13-12.17 实验五 查找和排序（二） 检查日期 检查人 一式三份: 一份交教务处,一份存教学系部,一份由本人保存.

- 2 -

数据结构实验指导书

实验一 线性表

一、实验目的

1、掌握用TC环境上机调试线形表的基本方法

2、掌握顺序表、链表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现

二、实验内容

1、顺序表基本操作的实现

[问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

[基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。 [实现提示] 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。 [程序实现]

#include #include typedef int DataType ; # define maxnum 20 typedef struct {int data[maxnum]; int length; }SeqList; /*插入函数*/

int insert(SeqList *L , int i , DataType x) /* 将新结点x插入到顺序表L第i个位置 */ { int j ;

if( i<0 || i>(*L).length +1) { printf(\值不合法 ! \ return 0; }

if((* L).length >=maxnum-1) { printf(\表满不能插入!\ return 0; }

for(j=(*L).length;j>=i;j--) (*L).data[j+1]=(*L).data[j]; (*L).data[i] = x; (*L).length++; return 1; }

/*删除函数*/

int delete( SeqList *L ,int i) /*从顺序L中删除第i个结点*/ { int j ;

if( i<0|| i>(*L).length )

{ printf(\删除位置错误 ! \return 0; }

for(j=i+1;j<=(*L).length;j++) (*L).data[j-1] =(*L).data[j];

- 3 -

数据结构实验指导书

(*L).length--; return 1; }

/*生成顺序表*/

void creatlist(SeqList * L) { int n , i;

printf(\请输入顺序表 L 的数据个数：\\n\scanf(\for(i=0 ; i

{ printf(\ scanf(\}

(*L).length=n-1; printf(\}/*creatlist */

/*输出顺序表 L*/

printout(SeqList * L) { int i ;

for (i=0 ; i<=(* L).length ; i++) { printf(\ printf(\}/*printout */ printf(\}

main()

{ SeqList *L ; char cmd ; int i, x; clrscr() ; creatlist(L); do {

printf(\插入\\n\printf(\删除\\n\printf(\退出\\n\do

{cmd=getchar() ;

}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q')); switch(cmd) { case 'i': case 'I': printf(\ scanf(\ printf(\ scanf(\ insert(L,i,x) ;

- 4 -

数据结构实验指导书

printout(L); break ; case 'd': case 'D' : printf(\ scanf(\ delete(L,i);

printout(L); break ;

}

}while((cmd!='q')&&(cmd!='Q')); }

2、有序顺序表的合并

[问题描述] 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc

[基本要求] lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表 [程序实现]

# include # define maxnum 20 typedef int DataType ; typedef struct

{ DataType data[maxnum] ; int length ; }SeqList ;

int MergeQL(SeqList la , SeqList lb , SeqList *lc) { int i , j , k ;

if (la.length+1 + lb.length+1>maxnum) { printf(\return 0; }

i=j=k=0;

while(i<=la.length && j<=lb.length) { if (la.data[i]<=lb.data[j])

lc->data[k++]=la.data[i++] ; else

lc->data[k++]=lb.data[j++]; }

/* 处理剩余部分 */

while (i<=la.length) lc->data[k++]=la.data[i++]; while (j<=lb.length) lc->data[k++]=lb.data[j++]; lc->length=k-1; return 1; }

main()

{ SeqList la={{3,4,7,12,15},4} ; SeqList lb={{2,5,7,15,18,19},5} ; SeqList lc ;

- 5 -