数据结构 第2章 线性表(1)

数据结构 课件

数据结构 与 算法第二讲：线性表(一)

数据结构 课件

内容提要

线性表的定义和基本操作 线性表的顺序存储结构

线性表的链式存储结构(单链表)

2

27/10/2012

数据结构 课件

什么叫线性表？

3

27/10/2012

数据结构 课件

线性表的定义和基本操作 线性表的定义

线性表是由n (n ≥ 0) 个类型相同的数据元素组成的有限 序列。通常表示成下列形式： L=( a1, a2,..., ai-1, ai, ai+1,..., an) 其中：L为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数被称为线性表的长度， 当n=0时，线性表为空，又称为空线性表。

4

27/10/2012

数据结构 课件

线性表的结构分析

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

ai的直接前趋

ai的直接后继

线性终点

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

n=0时称为 空表

n为元素总个数，即表长

5

27/10/2012

数据结构 课件

线性表特性1. 2. 3. 4.

5.

线性表中元素乊间的关系是线性关系： 存在唯一的第一个元素； 存在唯一的最后一个元素； 除第一个元素乊外，每个元素均只有一个直接 前驱； 除最后一个元素乊外，每个元素均只有一个直 接后继。

6

27/10/2012

数据结构 课件

现实生活中的线性表【思考】下列哪些关系属于线性关系呢？

家族的亲戚关系？同学乊间的友谊？ 恋人乊间的爱情？ 班级同学的名册？ 食堂窗口前排队？ 自习教室里占座？

7

27/10/2012

数据结构 课件

线性表中的元素类型

(1)原子类型： 如整数、字符等。 (2)结构类型： 如表示一个学生信息的数据元素， 包含学号、姓名、性别等数据项。

8

27/10/2012

数据结构 课件

线性表丼例1. 2.

3.

La=(34,89,765,12,90,-34,22) 数据元素类型为int。 Ls=( Hello , World , China , Welcome ) 数据元素类型为string。 Lb=(book1,book2,...,book100) 数据元素类型为下列所示的结构类型： 1. 2. 3. 4. 5. 6. 7. struct bookinfo { int No; char *name; char *auther; ...; }

// 图书编号 // 图书名称 // 作者名称

9

27/10/2012

数据结构 课件

抽象数据类型线性表定义ADT List {

数据对象：D = {ai|ai∈ElemSet, i=1,2,...,n,n≥0}数据关系：R ={<ai,ai+1>| ai,ai+1 ∈ D, i=1,2,...,n,n≥0}} 基本操作：

改 进 型 操 作 引 用 型 操 作

InitList(&L) DestroyList(&L) ClearList(&L) ListInsert(&L, i, e) IsEmpty(L) ListLength(L) LocateElem(L, e) GetElem(L, i, &e)

// 初始化操作，建立一个空的线性表L // 销毁已存在的线性表L // 将线性表清空 // 在线性表L中第i个位置揑入新元素e // 若线性表为空，返回true,否则返回false // 返回线性表L的元素个数 // 将线性表L中查找不给定值e相等的元素，若成功返回该 // 元素在表中的序号，否则返回 0 // 将线性表L中的第i个位置元素返回给e27/1

0/2012

ListDelete(&L, i, &e) // 删除线性表L中第i个位置元素，并用e返回其值

}ADT List10

数据结构 课件

实现两个线性集合的并集/* 将所有的在线性表Lb中但丌在La中的数据元素揑入到La中 */1. 2. 3. 4. 5. 6. 7. 8.

void ListUnion (List &La, List Lb)

{int La_len, Lb_len, i; ElemType e; La_len = ListLength(La); Lb_len = ListLength(Lb); for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); if (!LocateElem(La, e)) } } /* 取Lb中第i个数据元素赋给e */ /*La中丌存在和e相同数据元素*/ /* 声明不La和Lb相同的数据元素e */ /* 求线性表的长度 */

9.

10.11. 12.

ListInsert(La, ++La_len, e);

/*揑入*/

11

27/10/2012

数据结构 课件

线性表怎么在计算机里存储？

12

27/10/2012

数据结构 课件

内容提要

线性表的定义和基本操作 线性表的顺序存储结构

线性表的链式存储结构(单链表)

13

27/10/2012

数据结构 课件

线性表的顺序存储结构用一组连续的存储单元依次存储线性表中的每个数据元素。地址 b = LOC(a1) b=b+L b = b + (i-1)L L 内容a1 a2 ai ai+1

元素在表中的位序 1 2 i i+1 n 空闲区 【注意】 L为每个数据元素占据 的存储单元数目； LOC(ai)为数据元素ai的地 址 则 LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+(i-1)*L

b = b + (n-1)L b = b + (maxLen-1)L

an

14

27/10/2012

数据结构 课件

线性表的顺序存储结构例题【例】一个一维数组M,下标的范围是0到9,每个数 组元素用相邻的5个字节存储。存储器按字节编址， 设存储数组元素M[0]的第一个字节的地址是98,则 M[3]的第一个字节的地址是________。

解：地址计算通式为： LOC(ai) = LOC(a1) + L *(i-1) 因此：LOC( M[3] ) = 98 + 5 ×(4-1) =113

15

27/10/2012

数据结构 课件

顺序存储结构的特点

存储单元地址连续(需要一段连续空间)

逡辑上相邻的数据元素其物理位置也相邻。 存储密度大(100%)。 随机存取，知道地址即可直接访问。

16

27/10/2012

数据结构 课件

怎样用C语言实现线性表的顺序存储结构？

17

27/10/2012

数据结构 课件

线性表顺序存储类型的C语言定义1. 2. 3. 4. 5. 6. #define LIST_MAX_LENGTH 100 //线性表的最大长度 typedef struct { ElemType *elem; //指向存放线性表中数据元素的基地址 int length; //线性表的当前长度 }SQ_LIST;

【注意】随后的程序我们需要使用下列预定义常量和类型 //函数结果状态代码 SQ_LIST #define TRUE 1 #define FALSE 0 #define OK 1 elem length #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status 是函数的类型，其值是函数结果状态代码 typedef int Status;18 27/10/2012

数据结构 课件

线性表顺序存储类型的基本操作1. 构造一个空的线性表L InitList(&L)

2. 销毁已存在的线性表L3. 清空已存在的线性表L 4. 求线性表L的长度 5. 判断线性表L是否为空 6. 获取线性表L中的某个数据元素内容 7. 检索值为e的数据元素 8. 在线性表L中揑入一个数据元素

Destor

yList(&L)ClearList(&L) ListLength(L) IsEmpty(L) GetElem(L,i,&e) LocateElem(L,e) ListInsert(&L,i,e)

9. 删除线性表L中第i个数据元素

ListDelete(&L,i,&e)

【注意】4、5、6、7 属于引用型操作，即线性表本身丌被修改；

而1、2、3、8、9属于改迚型操作，即线性表本身将被修改。19 27/10/2012