数据结构第2章 线性表

数据结构

第 1 页

数据结构

学习的意义： 学习的意义：线性表是最简单、 线性表是最简单、也是最基本的一种线性数据结 其存储表示法主要有两种：顺序存储结构和 构。其存储表示法主要有两种：顺序存储结构和链 式存储结构。这一部分内容和方法掌握了， 式存储结构。这一部分内容和方法掌握了，有助于 理解和掌握后续章节的内容， 理解和掌握后续章节的内容，如栈队列串是特殊的 线性表，数组和广义表是线性表的扩展； 线性表，数组和广义表是线性表的扩展；有助于理 解和掌握树和图等复杂的数据结构 存储结构和图等 复杂结构的操作算法， 复杂结构的操作算法，因为树和图的存储结构大多 或是这两种存储结构的扩充，或是它们的组合， 或是这两种存储结构的扩充，或是它们的组合，因 此这一章的内容非常重要， 此这一章的内容非常重要，同学们要很好地学习理 解和掌握。 解和掌握。第 2 页

数据结构

主要内容： 主要内容：2.1 线性表的类型定义2.1.1 线性表的定义 2.1.2 线性表的基本操作

2.4 有序表 2.5 顺序表和链表的综合比较

2.2 线性表的顺序表示和实现2.2.1 顺序表——线性表的顺序存储表示 顺序表——线性表的顺序存储表示 2.2.2 顺序表中基本操作的实现 2.2.3 顺序表其他算法举例

2.3 线性表的链式表示和实现2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 单链表和指针 单链表的基本操作 单链表的其他基本操作 循环链表 双向链表

第 3 页

数据结构

2. 12.1.1 线性表的定义

线性表的类型定义

线性表是n 个类型相同数据元素的有限序列， 线性表是n 个类型相同数据元素的有限序列，表中相邻的数据元 素之间存在“序偶”关系。通常记作( 素之间存在“序偶”关系。通常记作(a1, a2, a3, …, an )。 例1、数学中的数列(11,13,15,17,19,21) 数学中的数列(11,13,15,17,19,21) 英文字母表( E… 例2、英文字母表(A, B, C, D, E… Z )。 某单位的电话号码簿。 例3、某单位的电话号码簿。

姓名蔡颖 陈红

电话号码63214444 63217777 63216666 63218888 63215555

刘建平 王小林 张力 ...

第 4 页

数据结构

2.1.1 2.1.1

线性表的定义ai , ai+1, …, an )是一线性表

特性： A=( 特性：设 A=(a1, a2, ... , ai -1,类型的； 类型的；

线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一 线性表的数据元素可以是各种各样的， 在表中 ai-1 领先于ai ,ai 领先于ai+1 ,称ai-1 是ai 的直接前驱，ai+1 是ai 的 领先于a 领先于a 的直接前驱， 直 接后继； 接后继； 在线性表中，除第一个元素和最后一个元素之外， 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有 一个直接前驱，有且仅

有一个直接后继， 一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构 称为线性结构。线性表是一种线性数据结构； 称为线性结构。线性表是一种线性数据结构； 线性表中元素的个数n 称为线性表的长度 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表； 线性表的长度， 时称为空表 空表； ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表 是线性表的第i 个元素， 为数据元素a 序号， 中的位置，仅取决于它的序号； 中的位置，仅取决于它的序号； 第 5 页

数据结构

2.1.1 2.1.1

线性表的定义

线性表的其他表示方式: 线性表的其他表示方式:1、 二元组表示 L = < D,S >,其中：D = { a1,a2,a3,, ..., an} >,其中： ..., S = {R} R = {< a1, a2 > , <a2,a3 >, < a 3,a4 > … < an-1, an> } 2、图形表示 a1 a2 ai - 1 ai ai+1 an

顶点：表示数据 顶点： 边：表示是数据间的顺序结构关系 第 6 页

数据结构

2.1.2 线性表的基本操作 2.1.21. 初始化线性表L InitList(&L) 初始化线性表L 2. 销毁线性表L DestoryList(&L) 销毁线性表L 3. 清空线性表L ClearList(&L) 清空线性表L 4. 求线性表L的长度 ListLength(L) 求线性表L 5. 判断线性表L是否为空 ListEmpty(L) 判断线性表L 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,&e) 获取线性表L 7. 检索值为e的数据元素 LocateELem(L,e) 检索值为e 8. 返回线性表L中cur_e的直接前驱元素 PriorElem(L,cur_e,&pre_e) 返回线性表L cur_e的直接前驱元素 9. 返回线性表L中cur_e的直接后继元素 NextElem(L,cur_e,&next_e) 返回线性表L cur_e的直接后继元素 10. 在线性表L中插入一个数据元素 ListInsert(&L,i,e) 在线性表L (1≦ (1≦i≦ ListLength(L)+1) 11. 删除线性表L中第i个数据元素 ListDelete(&L,i,&e) 删除线性表L中第i (1≦ (1≦i≦ ListLength(L)) 12. 输出线性表L中的每个数据元素 ListTraverse(L) 输出线性表L第 7 页

数据结构

2.1.2 2.1.2

线性表的基本操作

说明: 说明:1、上面列出的操作，只是线性表的一些常用 上面列出的操作， 的基本操作； 的基本操作； 2、不同的应用，基本操作可能是不同的； 不同的应用，基本操作可能是不同的； 3、线性表的复杂操作可通过基本操作实现； 线性表的复杂操作可通过基本操作实现；

第 8 页

数据结构

2.1.2 2.1.2

线性表的基本操作

【例2-1 】假设线性表L=(23,56,89,76,18),i=3,x=56,y=88, 假设线性表L=(23,56,89,76,18 …… 此处隐藏：6311字，全部文档内容请下载后查看。喜欢就下载吧 ……