选课时间段： 周四6、7、8、9 序 号：

实验报告

课程名称： 数据结构

实验名称： 顺序表的实现

指导教师：

学生姓名：

学生学号：

实验日期： 20xx年4月11日

1

一、实验目的

1、 熟悉实验环境

2、 理解顺序表的基本操作

3、 了解顺序表的建立和输出

4、 掌握顺序表的插入、删除、合并和归并等实现方法

二、实验内容

三、实验步骤

1．需求分析

本演示程序用C语言编写，完成顺序表的生成，任意位置的插入、删除，以及确定某一元素在顺序表中的位置。

① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。

② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后顺序表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。

③ 程序所能达到的功能：完成顺序表的生成（通过插入操作）、插入、删除、查找操作。

④ 测试数据：

A． 插入操作中依次输入11，12，13，14，15，16，生成一个顺序表

B． 查找操作中依次输入12，15，22返回这3个元素在顺序表中的位置

C． 删除操作中依次输入2，5，删除位于2和5的元素

2．概要设计

1）为了实现上述程序功能，需要定义顺序表的抽象数据类型： ADT LinkList { 数据对象：D={ai|ai∈IntegerSet,i=0,1,2,?,n,n≥0} 数据关系：R={<ai,ai+1>|ai,ai+1 ∈D} 基本操作： InitLinkList(&L) 操作结果：构造一个空的顺序表L. InsLinkList(&L,pos,e) 初始条件：顺序表L已存在 2

} 操作结果：将元素e插入到顺序表L的pos位置 DelLinkList(&L,pos,&e) 初始条件：顺序表L已存在 操作结果：将顺序表L中pos位置的元素删除，元素值置入e中返回 LocLinkList(L,e) 初始条件：顺序表L依存在 操作结果：顺序表L中查找是否元素e，若存在，返回元素在表中的位置；若不存 在，返回-1. Menu() 操作结果：在屏幕上显示操作菜单 2）本程序包含7个函数： ① 主函数main() ② 初始化顺序表函数InitLinkList() ③ 显示操作菜单函数menu() ④ 显示顺序表内容函数dispLinkList() ⑤ 插入元素函数InsLinkList() ⑥ 删除元素函数DelLinkList() ⑦ 查找元素函数LocLinkList()

3．详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出C代码算法。对主程序和其他模块也都需要写出C代码算法。

1) 结点类型和指针类型

？？？？？？？？？？？？

2) 顺序表的基本操作

bool InitLinkList(LinkList &L) （C代码算法） void DispLinkList(LinkList L) （C代码算法） void menu() （C代码算法） bool InsLinkList(LinkList &L,int pos,int e) （C代码算法） bool DelLinkList(LinkList &L,int pos,int &e) （C代码算法） int LocLinkList(LinkList L,int e) （C代码算法）

3) 其他模块C代码算法

3

4．使用说明

程序名为？？？？？？？？.exe，运行环境为DOS。程序执行后显示 ======================== 0----EXIT 1----INSERT 2----DELETE 3----LOCATE ======================= SELECT:

在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后顺序表的内容。

选择0：退出程序 选择1：显示“INSERT pos,e =” ， 要求输入要插入的位置和元素的值（都是整数）。 选择2：显示“DELETE pos =” ， 要求输入要删除元素的位置，执行成功后返回元素的值。 选择3：显示“LOCATE e = ” ， 要求输入要查找元素的值，执行成功后返回元素在表中的位置

6．测试结果

1） 建立顺序表：

? 选择1，分别输入（0，11），（0，12），（0，13），（0，14）（0，15）。得到顺序表（15，14，13，12，11）

2） 插入：

? 选择1输入（1，100），得到顺序表（15，100，14，13，12，11）

? 选择1输入（-1，2），显示输入错误

? 选择1输入（7，2），显示输入错误

? 选择1输入（6，2），得到顺序表（15，100，14，13，12，11，2）

3） 删除：

? 选择2，输入1。返回e=100，得到顺序表（15，14，13，12，11，2） ? 选择2，输入0。返回e=15，得到顺序表（14，13，12，11，2）

? 选择2，输入4。返回e=2，得到顺序表（14，13，12，11）

? 选择2，输入5。返回输入错误

4） 查找

? 选择3，输入14。返回pos=0

? 选择3，输入100。返回输入错误

四、实验总结（结果分析和体会）

4

 

第二篇：数据结构实验报告线性表

实验一 集合的交与并

1、 顺序表 (Sequential List) 顺序表的定义和特点

定义：n（ ? 0）个表项的有限序列（a1, a2, ?, an）ai是表项，n是表长度。

特点：顺序存取遍历 逐项访问 从前向后 从后向前 从两端向中间

2、 顺序表的应用

（1）集合的“并”运算：是指两个集合的所有元素，最后放在一个集合的过程（若有相等的则取一个即可）。具体步骤是：先从一个集合A中取一个数，然后和另一个集合的首个元素比较，若不相等则保存A的这个元素，然后B中的第一个元素在和A中的第二个元素比较，一次类推。若A中的第一个元素和B中的第一个元素相等，则删除B中的第一个元素，然后A中第一个元素和B中的第二个元素比较，直到不相等才转到B中的元素和A中的元素比较。

主要用到的函数有：获取元素LB.Get()，搜素元素LA.Find ()，插入元素LA.Insert（），而这些函数的定义都放在seqlist.h这个文件中，具体的实现放在seqlist.cpp这个工程文件中。 主要程序有：

【Seqlist.h】

#ifndef SEQLIST_H

#define SEQLIST_H

#include <iostream>

using namespace std;

const int defaultSize = 30;

class SeqList {

int *data; //顺序表存储数组

int MaxSize; //最大允许长度

int last; //当前最后元素下标

public:

SeqList ( int sz = defaultSize );

~SeqList ( ) { delete [ ] data; }

int Length ( ) const { return last+1; }

int Find ( int& x ) const; //查找

int Locate ( int i ) const; //定位

int Insert ( int & x, int i ); //插入

int Remove ( int & x ); //删除

int Show ();

int Next ( int & x ) ; //后继

int Prior ( int & x ) ; //前驱

int IsEmpty ( ) { return last ==-1; }

int IsFull ( ) { return last == MaxSize-1; }

int Get ( int i ) { //提取

return i < 0 || i > last?NULL : data[i];

}

} ;

#endif

【Seqlist.cpp】

#include "SeqList.h"

SeqList :: SeqList (int sz)

{

if (sz>0)

{

MaxSize = sz;

last = -1;

data = new int[MaxSize]; if ( data == NULL)

{

MaxSize=0;

last = -1;

return;

}

}

}

int SeqList :: Find (int& x) const //搜索函数 {

int i = 0;

while ( i <= last && data[i] != x )

i++;

if ( i > last ) return -1;

else return i;

}

int SeqList :: Insert (int& x, int i )

{

//在表中第 i 个位置插入新元素 x

if ( i < 0 || i > last+1 || last == MaxSize-1 )

return 0; //插入不成功 else

{

last++;

for ( int j = last; j > i; j-- )

data[j] = data[j -1];

data[i] = x; return 1; //插入成功 }

}

//template <class Type>

int SeqList :: Remove ( int& x )

{

//在表中删除已有元素 x

int i = Find (x); //在表中搜索 x

if ( i >= 0 )

{

last-- ;

for ( int j = i; j <= last; j++ )

data[j] = data[j+1];

return 1; //成功删除 }

return 0; //表中没有 x }

//template <class Type>

int SeqList ::Show()

{

if(last < 0 )

{

cout<< "the Seqlist is empty" << endl;

return 0; //没有可输出内容 }

else

{

for(int i=0 ; i<=last ; i++)

cout<< data[i] <<" ";

return 1; //输出成功

}

cout << endl;

}

集合的并运算函数程如下：

template <class Type>

void Union ( SeqList<Type> & LA,

SeqList<Type> & LB ) { int n = LA.Length ( );

int m = LB.Length ( );

for ( int i = 1; i <= m; i++ ) {

Type x = LB.Get(i); //在LB中取一元素 int k = LA.Find (x); //在LA中搜索它

if ( k == -1 ) //若未找到插入它

{ LA.Insert (n+1, x); n++; }

}

}：

综上所述，要完成集合的并运算，需要这样几步分程序，首先所用函数的定义（头文件），放在.h文件当中，其次各个函数的算法，例如查找，插入，取数（这些都是用来给集合的并作铺垫的）等放在一个工程当中，然后直接调用就行了。

（2）集合的“交”运算：是指两个集合的所有元素，若有相同的元素最后放在一个集合的过程。具体步骤是：先从一个集合A中取一个数，然后和另一个集合的首个元素比较，若相等则保存A的这个元素，然后B中的第二个元素在和A中的第二个元素比较，一次类推。若A中的第一个元素和B中的第一个元素不相等，则B中第一个元素和A中的第二个元素比较，直到相等才转到A中的元素和B中的元素比较。

主要用到的函数和集合的“并”相同，不同点只是交采用的函数是元素的删除，而“并”采用的是元素的插入，区别主要就在LA.Insert（）和LA.Remove ()。

int SeqList :: Remove ( int& x ) //元素的删除

{

//在表中删除已有元素 x

int i = Find (x); //在表中搜索 x

if ( i >= 0 )

{

last-- ;

for ( int j = i; j <= last; j++ )

data[j] = data[j+1];

return 1; //成功删除

}

return 0; //表中没有 x

}

3、顺序表的结构定义：

#define maxlen 50 //定义顺序表中元素个数最多有几个

typedef struct

{

elementtype data[maxlen]; //elementtype是元素的类型 依具体情况而定

int listlen; //便于时刻了解顺序表里元素的个数

}seqlist; //顺序表的名称 不妨为seqlist

声明顺序表类型变量：

seqlist L,L1;

如顺序表的每个结点占用len个内存单元，用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +len

location (ki) = location(k1) + (i-1)len

存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。

4、实验总结：

（1）求两个集合的并集

该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。 首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。

（2）求两集合的交集

此的算法首先把存放结果的集合s变成一个空集，然后依次从s2集合中取出每一个元素，利用它去查找s1集合，看是否存在，若存在则把它写入交集s中，这样写入s中的元素既属于s1又属于s2。此算法中，从s1中查找一个元素的时间复杂度为O（n）,所以整个算法的时间复杂度为O（n*m）。