第2章线性表 2.1线性表的定义 211什么是线性表 线性表是具有相同特性的数据元素的一个有限序列。其特 征如下 ●所有数据元素类型相同; ●线性表是有限个数据元素构成的; ●线性表中数据元素是与位置有关的,通常从1开始 编号,每个数据元素有唯一的序号,这一点表明线 性表不同于集合
第2章 线性表 2.1 线性表的定义 2.1.1 什么是线性表 线性表是具有相同特性的数据元素的一个有限序列。其特 征如下： 所有数据元素类型相同； 线性表是有限个数据元素构成的； 线性表中数据元素是与位置有关的，通常从1开始 编号，每个数据元素有唯一的序号，这一点表明线 性表不同于集合
线性表的逻辑结构一般表示为:(a1a2,,n1,.an) 用图形表示的逻辑结构如下图所示 首元素 尾元素 a1)(a2 a)→ 其中,用n(m≥0)表示线性表的长度(即线性表中数据 元素的个数)。当n=0时,表示线性表是一个空表。 在线性表中,每个元素至多只有一个前趋元素并且 至多只有一个后继元素。这是线性表的逻辑特征
线性表的逻辑结构一般表示为：(a1 ,a2 ,…,ai ,ai+1,…an )。 用图形表示的逻辑结构如下图所示。 a1 a2 ai ai+1 an a … … 1 a2 ai ai+1 an … … 首元素 尾元素 其中，用n（n≥0）表示线性表的长度（即线性表中数据 元素的个数）。当n=0时，表示线性表是一个空表。 在线性表中，每个元素至多只有一个前趋元素并且 至多只有一个后继元素。这是线性表的逻辑特征
212线性表的抽象数据类型描述 ADT List 数据对象 D={a11≤i≤n,n≥0,a为 Elemtype类型 ElemType是自定义类型,本章中假设 ElemType为 Istring 数据关系: r={<a,a1+1-|aa+1∈D=1,…,n-1 基本运算 void create list( (stringl split):由spli数组中的元素建立存储结构。 string Displisto:将线性表中的所有元素构成一个字符串返回。 int ListLengtho:求线性表的长度 bool getelem(inti, restring e):求线性表中序号为的元素值e int Locate elem( string e):按元素值e查找其序号。 bool ListInsert(int i, stringe):插入数据元素e作为线性表的第个元素。 bool listDelete(int i; ref string e):在线性表中删除第个数据元素e
2.1.2 线性表的抽象数据类型描述 ADT List { 数据对象： D={ai | 1≤i≤n,n≥0,ai为ElemType类型} //ElemType是自定义类型，本章中假设ElemType为string 数据关系： r={<ai ,ai+1> | ai ,ai+1∈D,i=1,…,n-1} 基本运算： void CreateList(string[] split)：由split数组中的元素建立存储结构。 string DispList()：将线性表中的所有元素构成一个字符串返回。 int ListLength()：求线性表的长度。 bool GetElem(int i,ref string e)：求线性表中序号为i的元素值e int LocateElem(string e)：按元素值e查找其序号。 bool ListInsert(int i,string e)：插入数据元素e作为线性表的第i个元素。 bool ListDelete(int i,ref string e)：在线性表中删除第i个数据元素e。 }
2.2线性表的顺序存储结构 221线性表的顺序存储结构一顺序表 class sqlistclass 顺序表类 const int MaxSize=100;/数组的长度 public stringl data; /1放顺序表中元素 public int length /1放顺序表的长度 public sqlistclasso /构造函数,实现data和 ength的初始化 i data=new string MaxSize; length=0 线性表的基本运算算法 数组下标01… i-2 Max Size-I data数组a1a2 arl a+1 空闲
2.2 线性表的顺序存储结构 2.2.1 线性表的顺序存储结构—顺序表 class SqListClass //顺序表类 { const int MaxSize=100; //数组的长度 public string[] data; //存放顺序表中元素 public int length; //存放顺序表的长度 public SqListClass() //构造函数，实现data和length的初始化 { data=new string[MaxSize]; length=0; } //线性表的基本运算算法 } data 数组 a1 数组下标 0 a2 1 …… … ai -1 i-2 ai i-1 ai+1 i …… … an n-1 空闲 MaxSize-1
说明: Sqlistclass类的一个对象L称为顺序表对象L,也 简称为顺序表L,其中主要有data、 length字段和相关的运算 方法,通过 L data或 Llength对字段进行操作,后面的顺序栈 顺序队、顺序串等都采用相似的方式。 SqlistClass l= new sqlistClasso; data length 其他方法等
说明：SqListClass类的一个对象L称为顺序表对象L，也 简称为顺序表L，其中主要有data、length字段和相关的运算 方法，通过L.data或L.length对字段进行操作，后面的顺序栈、 顺序队、顺序串等都采用相似的方式。 data length 其他方法等 L SqListClass L＝new SqListClass();