《数据结构实验》讲义.doc

实验1 线性表的基本操作 实验编号 JX020101-01 所属院系 计算机科学与技术 所属年级 2012-03 所属课程 数据结构试验 实验目的 1．掌握线性表的特点及其存储结构 2．掌握线性表的基本操作 实验要求 1．线性表可以用顺序表也可以用单链表实现，鼓励大家用两种方式实现； 2．创建线性表时，数据从键盘输入整形数据； 3．线性表类型定义和或各种操作的实现，可以用教材给出的方法，也可以自己设计。 实验环境 硬件平台：计算机CPU 主频2.0G以上；内存128兆以上； 软件平台：Windows2003或以上版本，Visual C++6.0。 实验内容 1．用结构体描述一个线性表； 2．创建线性表，在线性表中实现插入、删除、按位置查找、按元素值查找和求表长等操作； 3．设计选择式菜单，以选择菜单方式进行操作。 实验步骤 实验指导 定义顺序表 #define LIST_INIT_SIZE 100 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ struct SqList { ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ };Status InitList(SqList L) /* 算法2.3 */ { /* 操作结果：构造一个空的顺序线性表 */ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); /* 存储分配失败 */ L.length=0; /* 空表长度为0 */ L.listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK; } ElemType *newbase, *q, *p; if(i1||iL.length+1) /* i值不合法 */ return ERROR; if(L.length=L.listsize) {/* 当前存储空间已满,增加分配 */ if(!(newbase=(ElemType *)realloc( L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)))) exit(OVERFLOW); /* 存储分配失败 */ L.elem=newbase; /* 新基址 */ L.listsize+=LISTINCREMENT; // 增加存储容量 } q=L.elem+i-1; /* q为插入位置 */ for(p=L.elem+L.length-1; p=q; --p) /* 插入位置及之后的元素右移 */ *(p+1)=*p; *q=e; // 插入e ++L.length; /* 表长增1 */ return OK; } 主函数样例 void main() { SqList L; Status i; int j; i=InitList(L); printf(初始化L后：L.elem=%u L.length=%d L.listsize=%d\n,L.elem,L.length,L.listsize); for(j=1;j=5;j++) i=ListInsert(L,1,j); printf(在L的表头依次插入1～5后：*L.elem=); for(j=1;j=5;j++) cout*(L.elem+j-1) ; coutendl; printf(L.elem=%u L.length=%d L.listsize=%d\n,L.elem,L.length,L.listsize); } 思考题 1、编写一个算法实现两个有序（从小到大）表合并成为一个有序表。 2、设有一个线性表A，包含n个元素，要求写出一个将该表逆置的算法。 实验2 栈的应用 实验编号 JX020101-02 所属院系 计算机科学与技术 所属年级 2012-03 所属课程 数据结构试验 实验目的 （1）学会栈基础知识、结构特点、存贮结构； （2）练习使用栈的结构特点和基本操作； （3）学会使用栈处理应用问题的方法。 实验要求 1．栈结构可以用顺序栈实现。 2．测试数据从键盘输入。 3．栈类型