手机版

主页 > 文库下载 > 实用文档 > 内容

东华大学数据结构上机实验报告

时间：2025-07-07 来源：未知

小中大

字号：

东华大学信息科学与技术学院

实验报告

实验名称：线性表的基本操作指导教师：

学生姓名：学生学号：实验日期： 2012/11

一、实验目的

１、熟悉Ｃ或VC++语言上机环境。

２、会定义线性表的顺序存储结构和链式存储结构。３、熟悉顺序表和单链表的一些基本操作和应用。

４、加深对线性表的理解，逐步培养解决实际问题的编程能力。二、实验环境

运行Ｃ或VC++的微机。

三、实验内容：分别使用顺序表和单链表存储结构实现以下操作： 1. 建立线性表L＝｛12,13,21,24,28,31,42,77｝； 2. 在第5个元素之前插入26； 3. 删除第5个元素28；

4.

查找28。

四、实验设计思路及算法流程

(一) 使用顺序表实现操作:

建立顺序表，完成顺序表的基本操作：初始化、插入、删除、输出、查找元素、判线

性表是否为空；

问题分析：利用顺序表,设计一组输入数据，能够对顺序表进行如下操作：创建一个新的顺序表，实现动态空间分配的初始化；

已给定的值插入到指定位置和删除指定位置的值，形成有序顺序表；

按值查找，根据给定数据元素的值，查找该元素的位置，对查找结果进行返回；

实现顺序表的各个元素的输出；

“初始化算法”的操作结果：构造一个空的顺序线性表，对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；

“位置插入算法” 的初始条件：顺序线性表L已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；其操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1；

“位置删除算法”的初始条件：顺序线性表L已存在，1≤i≤ListLength(L) ；其操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ；

“输出算法”的初始条件：顺序线性表L已存在；其操作结果：依次对L的每个数据元素进行输出；

“按值查找算法”初始条件：顺序线性表L已存在，元素值为e；其操作结果：返回L中数据元素值为e的元素位置；

线性表的顺序存储结构的定义及其基本操作的参考程序（顺序表）

文件一：pubuse. h 是公共使用的常量定义和系统函数调用声明。 /* 公共使用的常量定义和系统函数调用声明*/ /* (程序名) */ #include<iostream>

using namespace std;

/* 函数结果状态代码 */

#define TRUE 1 //宏定义

#define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int ElemType; //类型定义

文件二：seqlistdef.h 进行线性表的动态分配顺序存储结构的表示。 /* 线性表的动态分配顺序存储结构 */

#define LISTINCREMENT 20 /* 线性表存储空间的分配增量 */ #define LIST_INIT_SIZE 30 /* 线性表存储空间的初始分配量 */ typedef struct { ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */

int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */

}SqList;

文件三：seqlistalgo. h 进行线性表顺序存储结构的基本实验算法定义。 /* 顺序表示的线性表的基本操作 */

Status InitList_Sq(SqList &L) /* 思路类似于算法2.3 */ { /* 操作结果：构造一个空的顺序线性表 */ L.elem=new ElemType[LIST_INIT_SIZE]; // if(!L.elem)

exit(OVERFLOW); /* 存储分配失败 */

L.length =0; /* 空表长度为0 */

L.listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK;

}

Status ListInsert(SqList &L,int i,ElemType e) /* 思路类似于算法2.4 */ { /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 */

/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ int *q,*p;ElemType *newbase; //?

if(i<1 || i>L.length+1) return ERROR; /* i值不合法 */ if(L.length>=L.listsize) /* 当前存储空间已满,增加分配 */ { newbase=new ElemType[L.listsize+LISTINCREMENT]; if(!newbase)

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;

}

Status Look(SqList &L,ElemType e) /* 思路类似于算法2.4 */ {/* 初始条件：顺序线性表L已存在 */

/* 操作结果：返回L中第1个与e满足相等关系的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0*/

int *p=L.elem,*q=L.elem+L.length-1; /* p的初值为第1个元素的存储位置 */

int i=1; /* i的初值为第1个元素的位序 */ //记录此时元素在线性表中的次序