文档介绍：Data Structures and Algorithms
主讲教师 : 黄襄念
西华大学数学与计算机学院
图像处理与模式识别实验室
课程QQ群：101600501
数据结构与算法
本章授课内容
线性表的定义
线性表的特性
线性表举例
线性表顺序存储结构
顺序表操作（4 种）
顺序表插入时间效率
顺序表的优缺点
线性表链式存储结构
链表分类与运算
单链表的存储结构
单链表运算（13 种）
单链表时间效率分析
循环链表概述
循环链表运算（2 种）
双链表类型与逻辑结构
双链表运算（4 种）
静态链表
线性表应用：多项式存储
本章授课学时：5 学时
11:46
2／51
线性表(Linear List)
线性表 —— n 个同类型元素组成的有限序列。
理解：C++ 数组元素
记为：
元素ai ：同一表中类型相同。例如：
字母表，元素：字母
数字表，元素：数字
成绩表
一个元素即一条记录，一人信息
线性表长度：n , n=0 为空表，记作 L=（）
线性表的定义
001
张三
数学
85
英语
92
…
002
李四
数学
96
英语
87
…
003
王五
数学
78
英语
90
…
11:46
3／51
线性表：
a1 —— 表中第一个元素，无前驱元素
an —— 表中最后一个元素，无后继元素
其他元素（非头非尾）：
有且仅有一个直接前驱
ai-1 是 ai 的直接前驱
有且仅有一个直接后继
ai +1 是 ai 的直接后继
线性表的特性
11:46
4／51
ADT List
{
数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n>0 }
数据关系：R = { <ai-1, ai> | ai-1 , ai∈D, i = 2 , …, n }
数据操作：
InitList(L) // 构造一个空线性表 L
DestroyList(L) // 销毁 L
ClearList(L) // 清空 L
ListEmpty(L) // L为空：true ; 非空：flase
ListLength(L) // 返回 L 的元素个数
GetElem(L, i) // 返回 L 中第 i 个元素
LocateElem(L, e) // 返回L中第一个与e相等的元素
// 的位序，没找到返回 0
抽象数据类型定义
11:46
5／51
PriorElem(L, e) // 返回e 元素的直接前驱
NextElem(L, e) // 返回e 元素的直接后继
ListInsert(L, i, e) // 在 i 位置之前插入元素e
ListDelete(L, i) // 删除第 i 个元素
ListTraverse(L, visit()) // 遍历 L, visit() 访问结点
} ADT List
例1：线性表遍历
ListTraverse(L, visit()) // 类C++语言
{
if ( !ListEmpty(L) )
for( i=1; i<=ListLength(L); i++ )
visit(GetElem(L, i)) ;
}
抽象数据类型定义(续)
时间效率O(n)
11:46
6／51
例2
两个线性表 La 和 Lb 的元素属于同一数据对象，试将Lb 合并到 La，要求：相同元素不再合并。
ListMerge(La , Lb)
{
La_len = ListLength(La) ;
Lb_len = ListLenght(Lb) ;
for ( i=1; i<=Lb_len; i++ ) {
e = GetElem(Lb, i) ; // 待插元素e
if ( !LocateElem(La, e) )
ListInsert(La, ++La_len, e) ; } //插到La的后面
}
线性表举例
请思考：算法设计？
思考：为什么不插到 La 的前面？
验证：T(n) = O(La_len×Lb_len)
11:46
7／51
定义
用一片地址连续内存单元依次存放线性表的各元素
—— 逻辑上相邻的元素，存储位置也相邻
实现手段
可用高级编程语言(如C++) 的数组来简单实现
线性表的顺序存储结构（顺序表）