• 线性表是典型的线性结构,最常用的一种数据结构。
• 线性表的抽象数据类型、
• 线性表的两种存储结构、
• 相关运算算法设计和线性表的应用。

2.1线性表的定义

• 先:线性表的定义
• 对线性表的抽象数据类型描述
• 后面几节用顺序存储方式和链表存储方式实现这些基本运算

2.1.1什么是线性表

• 线性表是具有相同特性的数据元素的一个有限序列。
• 数据元素的类型相同
• 有限个数据元素构成
• 线性表中的数据元素与位置有关,从1编号,每个数据元素有唯一的序号,这点表明线性表不同于集合
• 线性表中的数据元素可重复,集合中不重复出现

 

 

• 对至少含一个数据元素的线性表,除开始元素a1(也称为首元素)没
  有前趋元素外,其他每个元素a1(2≤i≤n)有且仅有一个前趋元素a1;
• 除终端元素an(也称为尾元素)没有后继元素外,
  • 其他元素a,(1≤にn-1)有且仅有一个后继元素a;1。
• 线性表中,每个元素至多只有一个前趋,至多只有一个后继,
  • 这就是线性表的逻辑特征

 

• 若干人排成一行或列就构成一个人线性表,如图2.2。
• 若干汽车排成行或一列就构成一个汽车线性表。

2.1.2线性表的抽象数据类型描述

2.2线性表的顺序存储结构

• 线性表的顺序存储是最常用的存储方式。
• 它直接将线性表的逻辑结构映射到存储结构上,既便于理解,又易实现。
• 本节讨论顺序存储结构及其基本运算的实现

2.2.1线性表的顺序存储结构–顺序表

• 线性表的顺序存储结构
  • 把线性表中的所有元素按照其逻辑顺序依次
  • 存储到从存储器中指定存储位置开始的一块连续的存储空间中。
• 线性表的顺序存储称顺序表

 

• C#中一维数组data实现顺序表,设数组长度为常量Maxsize
• 数组的长度是指存放线性表的存储空间的长度,
  • 存储分配后这个量一般不变
• 线性表的长度是指线性表中的数据元素个数,
  • 随着插人和删除操作,线性表长度变化,
  • 但任何时刻,线性表的长度应<=Maxsize
• 当长度小于data长时,数组有一部分空闲
• 设计变量length表示顺序表的长度,
  • data中实际数据元素个数

• 线性表中元素$a_i$ai​逻辑序号为i,
  • 在对应顺序表中该元素的物理序号为i-1
• 形参中的序号i通常指逻辑序号。

 

 

• 类的一个对象L称顺序表对象L,简称顺序表L
• 主要有data、 length和相关的运算方法
• L.data或L.length对字段操作
• 后面的顺序栈、顺序队和顺序串等都用相似的方式

2.2.2顺序表基本运算的实现

1.建立顺序表

• 将给定的含有若干个元素的数组split的每个元素依次放到顺序表中,并将其长度赋给顺序表的length。