数据结构第2章1

线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 →可表示为：(a1 , a2 , ……, an) 特点① 只有一个首结点和尾结点； 特点② 除首尾结点外，其他结点只有一个直接前驱和一个 直接后继。 简言之，线性结构反映结点间的逻辑关系是 一对一 (1:1) 的。

线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是------ 线性表1

第2章 线性表2.1 线性表的基本概念 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例

2.1 线性表的基本概念1、线性表 它是一种最简单的线性结构。是一种可以在任 意位置进行插入和删除数据元素操作的，由n(n≥0) 个相同类型数据元素a0, a1, … , an-1组成的线性结 构。

线性表的逻辑结构：

(a0, a1, … ai-1,ai, ai+1 ,…, an-1)数据元素线性起点

ai的直接前趋 ai的直接后继

线性终点

下标，是元素的 序号，表示元素 在表中的位置

n=0时称为

空表

n为元素总个数，即表 长。n≥0

例1 分析26 个英文字母组成的英文表是什么结构。( A, B, C, D, …… , Z) 分析： 数据元素都是同类型(字母), 元素间关系是线性的。

例2 分析学生情况登记表是什么结构。学号 姓名 性别 年龄 班级

012003010622012003010704 012003010813 012003010906 012003011018 :

陈建武赵玉凤 王 泽 薛 荃 王 春 ：

男女 男 男 男 ：

1918 19 19 19 :

2003级电信0301班2003级电信0302班 2003级电信0303班 2003级电信0304班 2003级电信0305班 ：

分析：数据元素都是同类型(记录),元素间关系是线性的。 注意：同一线性表中的元素必定具有相同特性 ！5

2、线性表抽象数据类型它包括两个方面： 数据集合：{ a0, a1, … , an-1 } ai的数据类型为 DataType 操作集合：(1)ListInitiate(L) 初始化线性表 (2)ListInsert(L,i,x) 插入数据元素 (3)ListLength(L) 求当前数据元素个数 (4)ListDelete(L,i,x) 删除数据元素 (5)ListGet(L,i,x) 取数据元素 等6

3、线性表的存储结构(1)顺序存储结构:它是使用一片地址连续的有限内存单

元空间存储数据元素的一种计算机存储数据方法。 特点：(任意两个在逻辑上相邻的数据元素在物理位置 上也必然相邻)逻辑上相邻的元素，物理上也相邻。 (2)链式存储结构:它是把数据元素和指针定义成一个 存储体，使用指针把发生联系的数据元素链接起来 的一种计算机存储数据方法。 特点：任意两个在逻辑上相邻的数据元素在物理上不 一定相邻，数据元素的逻辑次序是通过链中的指针 链接实现的。

2.2 线性表的顺序表示和实现一

、顺序表的存储结构 二、 顺序表的实现

三、 顺序表的运算效率分析

一、 顺序表的存储结构表示 可以利用数组V[n]来实现

1、顺序表：用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性 表。它通常采用静态数组实现数据元素的存储。

注意：在C语言中数组的下标是从0开始，即： V[n]的有效范围是从 V[0]~V[n-1]9

2、线性表顺序存储特点：

(1) 逻辑上相邻的数据元素，其物理上也相邻； (2) 若已知表中首元素在存储器中的位置，则其他元 素存放位置亦可求出(利用数组V[n]的下标)。 设首元素a0的存放地址为LOC(a0)(称为首地址), 设每个元素占用存储空间(地址长度)为L字节， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a0 ) + L *i 对上述公式的解释如图所示10

3、线性表的顺序存储结构示意图地址 b=LOC(a0) 内容 a0 a1 …… ai ai+1 …… 元素在表中的位序

L

0 1 i i+1

b+ Lb +iL

b +(n-1)Lb +(MaxSize-1)L

an-1

n-1空闲区

LOC ( ai ) = LOC( a0 ) + L *i11

4、用C语言描述 typedef struct { DateType list[MaxSize]; int size; }SeqList;/* MaxSize表示数组的最大元素个数，list表示顺序表 的数组名，size表示顺序表中当前存储的数据元素个 数，它必须满足size≤ MaxSize,SeqList是该结构体 的名字。*/12

例1

设有一维数组M,下标的范围是0到9,

每个数组元素用相邻的5个字节存储。存储器

按字节编址，设存储数组元素M[0]的第一个字节的地址是98,则M[3]的第一个字节的

地址是多少？解：已知地址计算通式为： LOC(ai) = LOC(a0) + L *i LOC( M[3] ) = 98 + 5 ×3 =113

113

例2 用数组V来存放26个英文字母组成的线性表

(a,b,c,…,z),写出在顺序结构上生成和 显示该表的C语言程序。 char V[30]; void build() /*字母线性表的生成，即建表操作 */ { int i; 核心语句： V[0]='a'; 方法1 V[i]= V[i-1]+1; for( i=1; i<=n-1; i++ ) 方法2 V[i]=’a’+i; V[i]=V[i-1]+1; 方法3 V[i]=97+i; }14

void display( ) /*字母线性表的显示，即读表操作*/ { int i; for( i=0; i<=n-1; i++ ) printf( "%c", v[i] ); printf( "\n " ); } void main(void) /*主函数，字母线性表的生成和输出*/ { n=26; /* n是表长，是数据元素的个数，而不是V的实际下标*/

build( ); display( ); }执行结果： a b c d e f g h i j k l m n o p q r s t u v w x y z15

二、 顺序表的实现(或操作) 数据结构的基本运算： 修改、插入、删除、查找、排序 1) 修改 通过数组的下标便可访问某个特定元素并 修改之。 核心语句: V[i]=x;

显然，顺序表修改操作的时间效率是 O(1)

2)插入 在线性表(n个元素)的第i个位置前插入一个元素实现步骤：

将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满?

for (j=n-1; j>=i; j--) 核 // 元素后移一个位置 心 a[j+1]=a[ j ]; // 插入x 语 a[ i ]=x; 句： // 表长加1 n++;17

在线性表的第i个位置前插入一个元素的示意图如下：1 2 3 4 插入25 5 12 1

1213 21

1321 24 28 30 42 77

23 4 5 6 7 8

2425

67 8

2830 42 77

9

3)删除 删除线性表的第i个位置上的元素实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 核心语句： for ( j=i+1; j<=n-1; j++ )

a[j-1]=a[j];

// 元素前移一个位置 // 表长减1

n--;

删除顺序表中某个指定的元素的示意图如下：1 2 3 4 5 6 7 8 12 13 21 24 25 28 1 2 3 4 5 6 7 8 12 13 21 24 28 30 42 77

3042 77

9

例：建立一个线性表，先依次输入数据元素1,2, 3,4,…,10,然后删除5,最后依次显示当前 线性表中的数据元素。假设该线性的数据元素个 数最坏情况下不会超过100个。 实现方法： 1、采用直接编写一个主函数实现。 2、利用已设计实现的抽象数据类型模块。(存 放在头文件名为SeqList.h中，通过 #include “SeqList.h” )