NYIST_数据结构实验指导书.doc

PAGE I . . . 南阳理工学院 数据结构上机实验指导书 （2011版） 软件学院·软件工程教研室 2011.3 . . . 目 录 TOC \o 1-1 \h \u 实验1 线性表应用 2 实验2 栈和队列的应用 2 实验3 线性表应用 3 实验4 图论及其应用 3 实验5 查找 4 实验6 排序 4 . . . 实验1 线性表应用 一、实验目的 了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。 能够利用线性表结构对实际问题进行分析建模，利用计算机求解。 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 二、实验内容及步骤 利用程序设计语言分别实现顺序表和链表的抽象数据类型。 掌握程序分文件（头文件和实现文件）书写的方式。 分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。P21 #includec1.h typedef int ElemType; #includec2-1.h #includebo2-1.c #includefunc2-3.c /* 包括equal()、comp()、print()、print2()和print1()函数 */ void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法2.2 */ { /* 已知线性表La和Lb中的数据元素按值非递减排列。 */ /* 归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列 */ int i=1,j=1,k=0; int La_len,Lb_len; ElemType ai,bj; InitList(Lc); /* 创建空表Lc */ La_len=ListLength(La); Lb_len=ListLength(Lb); while(i=La_lenj=Lb_len) /* 表La和表Lb均非空 */ { GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai=bj) { ListInsert(Lc,++k,ai); ++i; } else { ListInsert(Lc,++k,bj); ++j; } } /* 以下两个while循环只会有一个被执行 */ while(i=La_len) /* 表La非空且表Lb空 */ { GetElem(La,i++,ai); ListInsert(Lc,++k,ai); } while(j=Lb_len) /* 表Lb非空且表La空 */ { GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj); } } void main() { SqList La,Lb,Lc; int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20}; InitList(La); /* 创建空表La */ for(j=1;j=4;j++) /* 在表La中插入4个元素 */ ListInsert(La,j,a[j-1]); printf(La= ); /* 输出表La的内容 */ ListTraverse(La,print1); InitList(Lb); /* 创建空表Lb */ for(j=1;j=7;j++) /* 在表Lb中插入7个元素 */ ListInsert(Lb,j,b[j-1]); printf(Lb= ); /* 输出表Lb的内容 */ ListTraverse(Lb,print1); MergeList(La,Lb,Lc); printf(Lc= ); /* 输出表Lc的内容 */ ListTraverse(Lc,print1); } 实验2 栈和队列的应用 一、实验目的 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 熟练掌握栈类型的两种实现方法。 熟练掌握循环队列和链队列的基本操作实现算法。 二、实验内容及步骤 用程序设计语言实现栈和队列的抽象数据类型。 在第一题的基础上完成以下选择： 选择一： 设计并实