数据结构 C语言 2.1 线性表抽象数据类型 2.2 小议顺序表

一、线性表抽象数据类型

线性表的定义

定义：零个或多个数据元素的有限序列

线性表的特点：

1.它是一个序列

数据元素之间是有序的

数据元素之间是一对一的关系

2.有限性

线性表的数据元素个数是有限的

注意：零个数据元素的有限序列又被称为空表

线性表常见的操作

1.创建和初始化、2.查找、3.删除、4.插入、5.清空

抽象数据类型定义：

ADT SequenceList

Data

   1.线性表数据元素是一个集合{a_1,a_2,a_3,...,a_n};//数据元素的类型是DataType

   2.除了第一个元素外，每个元素有且只有一个直接的前驱元素

   3.除了最后一个元素外，每个元素有且只有一个直接地后继元素

   4.每个数据元素之间的关系是一对一的关系

Operation

       1.初始化线性表：InitList(*List,int data)        创建一个空的线性表

       2.插入：InsertElement(*List,index,elem)        在线性表List的index下标处插入元素elem

       3.删除：DeleteElement(*List,index,*elem)        删除线性表List中第i个元素，并返回删除元素的指针e

       4.查找：GetElem(*List,index,*elem)        返回线性表中第i个位置的数据元素给e

       5.求长度：GetLength(*List)        返回线性表中的元素个数

       6.判空：IsEmpty(*List)        若线性表为空，返回TRUE，否则返回FALSE

endADT

       7.清空：ClearList(*List)        将线性表清空

二、小议顺序表

线性表的顺序存储示意图如下：

线性表的顺序存储结构，值得是用一段地址连续的存储单元依次存储线性表的数据元素

线性表的定义

position 元素的位置 从1开始        index 元素的下标 从0开始

1.我们需要定义线性表的最大存储空间

#define MAX_SIZE 255

2.线性表里需要有统一类型的元素集合

typedef ElemType;
typedef struct{
    int id;
    char name;
}ElenmType;

3.定义顺序表的结构

typedef struct{
    ElementType datas[MAX_SIZE];
    int length;
};

4.描述线性表的顺序存储结构：

       存储空间的起始位置：数组datas的存储位置

       线性表的最大存储容量：数组长度MAX_SIZE

       线性表的当前长度：length

线性表中顺序表地址的计算方式

地址从0到n-1

*(datas + 0);
*(datas + 1);
......
*(*datas+n-1);