201560140140--袁若飞--实验1:线性表的基本操作及其应用 下载本文

数据结构

实验1:线性表的基本操作及其应用

班级:RB软工移151 学号:201560140140 姓名:袁若飞

第 1 页

学号:201560140140 姓名:袁若飞

实验一 线性表

一、实验目的

1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现,其中以熟悉链表的操作为侧重点。

二、实验内容

本次实验提供4个题目,每个题目都标有难度系数,*越多难度越大,题目一、二是必做题。题目三、题目四选作。

三、实验准备知识

1、请简述线性表的基本特性和线性表的几种基本操作的机制

①答:线性表的基本特性是:对线性表中某个元素ai来说,称其前面的元素ai-1为ai的直接前驱,称其后前面的元素ai+1为ai的直接后继。显然,线性表中每个元素最多有一个直接前驱和一个直接后继。

②答:线性表的几种基本操作的机制有六个:

(1)初始化线性表 initial_List(L)——建立线性表的初始结构,即建空表。这也是各种结构都可能要用的运算。

(2)求表长度 List_length(L)——即求表中的元素个数。

(3)按序号取元素 get_element(L,i)——取出表中序号为i的元素 。 (4)按值查询 List_locate(L,x)——取出指定值为x的元素,若存在该元素,则返回其地址;否则,返回一个能指示其不存在的地址值或标记。

(5)插入元素 List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然,若表中的元素个数为n,则插入序号i应满足1<=i<=n+1。 (6)删除元素 List_delete(L,i)——删除表L中序号为i的元素,显然,待删除元素的序号应满足1<=i<=n。

2、掌握线性表的逻辑结构。 3、掌握线性表的链式存储结构。 4、熟练掌握线性表的插入、删除等操作。

第 2 页

学号:201560140140 姓名:袁若飞

四、实验内容

题目一:顺序表的基本操作 [问题描述]

实现顺序表的建立、求长度,取元素、修改元素、插入、删除等基本操作。 [基本要求]

(1)依次从键盘读入数据,建立顺序表; (2)输出顺序表中的数据元素;

(3)求顺序表的长度;

(4)根据指定条件能够取元素和修改元素; (5)实现在指定位置插入和删除元素的功能。 [测试数据]

由学生任意指定。

运行结果如下图: 1)实现删除功能

2)实现取元素功能

第 3 页

学号:201560140140 姓名:袁若飞

3)实现查找功能

4)实现插入功能

[源代码](加注释)

#include #include #include

#define maxlen 100 //设元素个数最大为100 typedef struct //声明一个结构体来存放顺序表 { int data[maxlen]; //定义存储表中元素的数组 int listlen; //定义表长度分量 }seqlist;

void get_element(seqlist *L,int I,int *x); //按序号求元素运算的子函数 int List_locate(seqlist L,int I,int x); //声明按值查询元素的子函数 bool List_insert(seqlist *L,int I,int x); //声明插入元素的子函数 bool List_delete(seqlist *L,int I); //声明删除元素的子函数 void main() {

seqlist *L; //表结构变量的定义 L=(seqlist *)malloc(sizeof(seqlist)); //为表分配空间 int i; //定义整型变量 for(i=1;i<=20;i++) //赋值给表中的元素 { }

L->listlen=20; //定义表的长度 cout<<\删除前的顺序表:\\n\

L->data[i-1]=i; //填入删除内容

第 4 页