开始 第 1 页

第二章

线性表

线性表是最简单又最常用的存储方法，这部分内容 和方法的掌握，有助于理解和掌握后续章节的内容，如 栈、队列、串是特殊的线性表，数组和广义表是线性表 的扩展；有助于理解和掌握树和图等复杂的数据结构的 存储结构操作算法，因为树和图的存储结构大多或是这 两种存储结构的扩充，或是它们的组合，因此这一章的 内容非常重要。

第 2 页

第二章

线性表

在本课程介绍的几种数据结构中，线性表是最 简单的，也是最常用的数据结构，线性表在实际应 用中大量使用，并不是一个陌生的概念。

第 3 页

第二章

线性表

2.1 线性表的概念及基本操作 2.2 线性表的顺序存储和实现(静态和动态) 2.3 线性表的链式存储和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表

第 4 页

2. 1

线性表的概念

第二章

线性表

一 、 线性表的逻辑结构 线性表是n 个类型相同数据元素的有限序列，通常记作(a1, a2, a3, …, an )。 在数

据结构中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有 且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构，也叫线性表。例1、数学中的数列(11,13,15,17,19,21) 例2、英文字母表(A, B, C, D, E Z )。 例3、某单位的电话号码簿。

姓名蔡颖 陈红 刘建平

电话号码63214444 63217777 63216666

王小林张力

6321888863215555

第 5 页

2.1

线性表的概念

第二章

线性表

一 、 线性表的逻辑结构 说明：设 A=(a1, a2, ... , ai -1, ai , ai+1, …, an )是一线性表，则 1) 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须 是同一类型的； 2) 在表中 ai-1 领先于ai ,ai 领先于ai+1 ,称ai-1 是ai 的直接前驱，ai+1 是 ai 的直接后继； 3) 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表； 4) ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在 线性表中的位置，仅取决于它的序号； 5)线性表的元素间有次序。

第 6 页

2.1

线性表的概念

第二章

线性表

二、线性表的基本操作 1、 线性表的建立：initlist(&L);

2、存取线性表中的第i个元素：getElem(L,i,&e); 3、线性表中查找满足条件元素 ：locatElem(L,e,compare());4、线性表的第i个元素之前插入 一个新元素 ：insert(&L,i,e); 5、 删除线性表的第i个元素:delete(&L,i); 6 、 将一个线性表拆分为多个线性表； 7、 将两个线性表进行合并: mer(&L,L1,L2); 8、 对线性表进行排序:sort(&L). 说明 1、上面列出的操作，只是线性表的一些常用的基本操作； 2、不同的应用，基本操作可能是不同的； 3、 线性表的复杂操

作可通过基本操作实现； 第 7 页

第二章

线性表

如何在计算机中存储线性表？ 如何在计算机中实现线性表的基本 操作？

存储线性表，至少要保存两类信息： 1、线性表中的数据元素； 2、线性表中数据元素的顺序关系；

第 8 页

2.2

顺序存储和实现

第二章

线性表

一、 线性表的顺序存储结构——顺序表(静态 和动态)

二、顺序表的基本操作算法三 、效率分析

第 9 页

2.2 顺序存储和实现

第二章

线性表线性表(a1,a2, a3, ... an ) 的顺序存储结构

一 、 线性表的顺序存储结构——顺序表 线性表的顺序存储结构，就是用一组连续的 内存单元依次存放线性表的数据元素。

a1 a2ai-1 ai ai+1

用顺序存储结构存储的线性表 ——称为顺序表

an

第 10 页

2.2 顺序存储和实现

第二章

线性表t个单元

一 、 线性表的顺序存储结构——顺序表 线性表的顺序存储结构，就是用一组连续的 内存单元依次存放线性表的数据元素。 说明： 在顺序存储结构下，线性表元素之间的 逻辑关系，通过元素的存储顺序反映(表 示)出来； 假设线性表中每个数据元素占用 t 个存 储单元，那么，在顺序存储结构中，线性 表的第i个元素的存储位置与第1个元素的 存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i – 1) t

Loc( a1 )

a1 a2ai-1 ai ai+1

Loc(ai )

an

第 11 页

2.2 顺序存储和实现

第二章

线性表

一 、 线性表的顺序存储结构——顺序表

怎样在计算机上实现 静态存储：用C语言中的一维数组来表示,但数组不 线性表的顺序存储结构？ 是线性表,数组存放的是线性表,数组的类型由线性表 中的数据元素的性质决定.如:

#define MAX 100 int a[MAX];

第 12 页

2.2 顺序存储和实现

第二章

线性表

一 、 线性表的顺序存储结构——顺序表

线性表初始分 配存储空间大 小 当前线性表 的实际长度

动态顺序表的类型定义#define ListinitSize 100#define listincrement 10 typedef int ElemType; typedef struct{ ElemType *elem; int length; int listsize;

数据元素 类型 扩充容量大小 存储空 间基址

当前线性 表空间大 小

}SqList;

结构体名 第 13 页

2.2 顺序存储和实现

第二章

线性表

一 、 线性表的顺序存储结构——顺序表 设 A = (a1,a2 , a3 , ... an )是一线性表，L是SqList 类型的结构 体变量，用于存放线性表A,则L在内存中的状态如图所示：

0 …… 此处隐藏：1075字，全部文档内容请下载后查看。喜欢就下载吧 ……