PowerPoint Presentation

Transcription

1 数据结构与算法 ( 二 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五 国家级规划教材 )

2 第二章 线性表 第二章线性表 2.1 线性表 2.2 顺序表 2.3 链表 {a 0, a 1,, a n 1 } a 0 a 1 a 2 a n-1 tail head a 0 a 1 a n 顺序表和链表的比较 2

3 第二章 线性表 2.1 线性表 线性表的概念 线性表简称表, 是零个或多个元素的有穷序列, 通常可以表示成 k 0,k 1,,k n-1 (n 1) 表目 : 线性表中的元素 ( 可包含多个数据项, 记录 ) 索引 ( 下标 ):i 称为表目 k i 的 索引 或 下标 表的长度 : 线性表中所含元素的个数 n 空表 : 长度为零的线性表 ( n = 0 ) 线性表特点 : 操作灵活, 其长度可以增长 缩短 3

4 第二章 线性表 概念 线性结构 二元组 B = K, R K = {a 0, a 1,, a n 1 } R = {r} 开始结点终止结点 有一个唯一的, 它没有前驱, 有一个唯一的直接后继 一个唯一的, 它有一个唯一的直接前驱, 而没有后继 其它的结点皆称为内部结点, 每一个内部结点都有且仅有一个唯一的直接有前驱, 也有一个唯一的直接后继 < a i, a i+1 > a i 是 a i+1 的前驱,a i+1 是 a i 的后继 前驱 / 后继关系 r, 具有反对称性和传递性 表头 a 0 内部 a i a i+1 表尾 a n 1 4

5 第二章 线性表 特点 特点 线性结构 均匀性 : 虽然不同线性表的数据元素可以是各种各样的, 但对于同一线性表的各数据元素必定具有相同的数据类型和长度 有序性 : 各数据元素在线性表中都有自己的位置, 且数据元素之间的相对位置是线性的 5

6 第二章 线性表 分类 线性结构 按复杂程度划分 简单的 : 线性表 栈 队列 散列表 高级的 : 广义表 多维数组 文件 按访问方式划分 直接访问型 (direct access) 顺序访问型 (sequential access) 目录索引型 (directory access) 链表 6

7 第二章 线性表 分类 线性结构 按操作划分 ( 详见后 ) 线性表 所有表目都是同一类型结点的线性表 不限制操作形式 根据存储的不同分为 : 顺序表, 链表 栈 (LIFO, Last In First Out) 插入和删除操作都限制在表的同一端进行 队列 (FIFO, First In First Out) 插入操作在表的一端, 删除操作在另一端 7

8 第二章 线性表 2.1 线性表 三个方面 线性表的逻辑结构 线性表的存储结构 线性表运算 2.1 线性表 8

9 第二章 线性表 2.1 线性表 主要属性包括 线性表逻辑结构 线性表的长度 表头 (head) 表尾 (tail) 当前位置 (current position) 当前位置 表尾 表头 a 0 a i a i+1 a n 1 9

10 第二章 线性表 2.1 线性表 线性表 线性表分类 ( 按存储 ) 所有表目都是同一类型结点的线性表 不限制操作形式 根据存储的不同分为 : 顺序表, 链表 10

11 线性表 2.1 线性表 顺序表 线性表的存储结构 按索引值从小到大存放在一片相邻的连续区域 紧凑结构, 存储密度为 1 链表 第二章 单链表 双链表 循环链表 11

12 第二章 线性表 2.1 线性表 线性表 不限制操作 栈 线性表分类 ( 按操作 ) 在同一端操作 队列 在两端操作 12

13 第二章 线性表 2.1 线性表 线性表分类 ( 按操作 ) 栈 (LIFO, Last In First Out) 插入和删除操作都限制在表的同一端进行 出栈 进栈 栈顶 k i+1 k i... k 1 栈底 k 0 13

14 第二章 线性表 2.1 线性表 线性表分类 ( 按操作 ) 队列 (FIFO, First In First Out) 插入操作在表的一端, 删除操作在另一端 rear 实指 删除 插入 front front rear rear A B C B D C D 14

15 第二章 线性表 2.1 线性表 建立线性表 清除线性表 插入一个新元素 删除某个元素 修改某个元素 排序 检索 线性表的运算 15

16 第二章 线性表 2.1 线性表 线性表类模板 template <class T> class List { void clear(); // 置空线性表 bool isempty(); // 线性表为空时, 返回 true bool append(const T value); // 在表尾添加一个元素 value, 表的长度增 1 bool insert(const int p, const T value); // 在位置 p 上插入一个元素 value, 表的长度增 1 bool delete(const int p); // 删除位置 p 上的元素, 表的长度减 1 bool getpos(int& p, const T value); // 查找值为 value 的元素并返回其位置 bool getvalue(const int p, T& value); // 把位置 p 元素值返回到变量 value bool setvalue(const int p, const T value); // 用 value 修改位置 p 的元素值 }; 16

17 第二章 线性表 思考 线性表有哪些分类方式? 各种线性表名称中, 哪些跟存储结构相关? 哪些跟运算相关? 17

18 第二章线性表 2.1 线性表 2.2 顺序表 2.3 链表 tail head a 0 a 1 a n 顺序表和链表的比较 18

19 2.3 链表 链表 (linked list) 通过指针把它的一串存储结点链接成一个链 存储结点由两部分组成 : 数据域 + 指针域 ( 后继地址 ) data next 19

20 2.3 链表 分类 ( 根据链接方式和指针多寡 ) 单链 双链 head 2.3 链表 a 0 a 1 a n-1 tail tail head a 0 a n-1 循环链 tail head a 0 a 1 a n-1 20

21 2.3 链表 单链表 (singly linked list) 简单的单链表 整个单链表 : head 第一个结点 : head 空表判断 : head == NULL 当前结点 a 1 :curr curr tail head a 0 a 1 a n-1 21

22 2.3 链表 单链表 (singly linked list) 带头结点的单链表 整个单链表 : head 第一个结点 : head->next,head NULL 空表判断 : head->next == NULL 当前结点 a 1 :fence->next (curr 隐含 ) fence curr tail head a 0 a 1 a n-1 22

23 2.3 链表 单链表的结点类型 template <class T> class Link { public: T data; // 用于保存结点元素的内容 Link<T> * next; // 指向后继结点的指针 }; Link(const T info, const Link<T>* nextvalue =NULL) { data = info; next = nextvalue; } Link(const Link<T>* nextvalue) { next = nextvalue; } 23

24 2.3 链表 单链表类定义 template <class T> class lnklist : public List<T> { private: Link<T> * head, *tail; // 单链表的头 尾指针 Link<T> *setpos(const int p); // 第 p 个元素指针 public: lnklist(int s); // 构造函数 ~lnklist(); // 析构函数 bool isempty(); // 判断链表是否为空 void clear(); // 将链表存储的内容清除, 成为空表 int length(); // 返回此顺序表的当前实际长度 bool append(cosnt T value); // 表尾添加一个元素 value, 表长度增 1 bool insert(cosnt int p, cosnt T value); // 位置 p 上插入一个元素 bool delete(cosnt int p); // 删除位置 p 上的元素, 表的长度减 1 bool getvalue(cosnt int p, T& value); // 返回位置 p 的元素值 bool getpos(int &p, const T value); // 查找值为 value 的元素 } 24

25 2.3 链表 查找单链表中第 i 个结点 // 函数返回值是找到的结点指针 template <class T> // 线性表的元素类型为 T Link<T> * lnklist <T>:: setpos(int i) { int count = 0; if (i == -1) // i 为 -1 则定位到头结点 return head; // 循链定位, 若 i 为 0 则定位到第一个结点 Link<T> *p = head->next; while (p!= NULL && count < i) { p = p-> next; count++; }; // 指向第 i 结点,i=0,1,, 当链表中结点数小于 i 时返回 NULL return p; } 25

26 2.3 链表 单链表的插入 tail head 在 23 和 12 之间插入 10 tail head 创建新结点 新结点指向右边的结点 左边结点指向新结点 26

27 2.3 链表 单链表插入算法 // 插入数据内容为 value 的新结点作为第 i 个结点 template <class T> // 线性表的元素类型为 T bool lnklist<t> :: insert(const int i, const T value) { Link<T> *p, *q; } if ((p = setpos(i -1)) == NULL) { // p 是第 i 个结点的前驱 cout << " 非法插入点 "<< endl; return false; } q = new Link<T>(value, p->next); p->next = q; if (p == tail) // 插入点在链尾, 插入结点成为新的链尾 tail = q; return true; 27

28 2.3 链表 从链表中删除结点 x 单链表的删除 1. 用 p 指向元素 x 的结点的前驱结点 2. 删除元素为 x 的结点 3. 释放 x 占据的空间 28

29 第二章 线性表 2.3 链表 单链表删除示意 tail head x p p = head; while (p->next!=null && p->next->info!= x) p = p->next; 29

30 2.3 链表 删除值为 x 的结点 tail head x p q q = p->next; p->next = q->next; free(q); 30

31 2.3 链表 单链表删除算法 template <class T> // 线性表的元素类型为 T bool lnklist<t>:: delete((const int i) { Link<T> *p, *q; // 待删结点不存在, 即给定的 i 大于当前链中元素个数 if ((p = setpos(i-1)) == NULL p == tail) { cout << " 非法删除点 " << endl; return false; } q = p->next; // q 是真正待删结点 if (q == tail) { // 待删结点为尾结点, 则修改尾指针 tail = p; p->next = NULL: } else // 删除结点 q 并修改链指针 p->next = q->next; delete q; return true; } 31

32 2.3 链表 单链表上运算的分析 对一个结点操作, 必先找到它, 即用一个指针指向它 找单链表中任一结点, 都必须从第一个点开始 p = head; while ( 没有到达 ) p = p->next; 单链表的时间复杂度 O n 定位 :O n 插入 :O n + O 1 删除 :O n + O(1) 32

33 2.3 链表 双链表 (double linked list) 为弥补单链表的不足, 而产生双链表 单链表的 next 字段仅仅指向后继结点, 不能有效地找到前驱, 反之亦然 增加一个指向前驱的指针 tail head a 0 a n-1 33

34 2.3 链表 双链表及其结点类型的说明 template <class T> class Link { public: T data; // 用于保存结点元素的内容 Link<T> * next; // 指向后继结点的指针 Link<T> *prev; // 指向前驱结点的指针 Link(const T info, Link<T>* prevalue = NULL, Link<T>* nextvalue = NULL) { // 给定值和前后指针的构造函数 data = info; next = nextvalue; prev = prevalue; } Link(Link<T>* prevalue = NULL, Link<T>* nextvalue = NULL) { // 给定前后指针的构造函数 next = nextvalue; prev = prevalue; } } 34

35 2.3 链表 双链表插入过程 ( 注意顺序 ) 在 p 所指结点后面插入一个新结点 new q; q->next=p->next q->prev=p p->next=q q->next->prev=q p 2 3 q

36 1 2.3 链表 删除过程 36 p 删除 p 所指的结点 p->prev->next=p->next p->next->prev=p->prev p->next=null p->prev=null 2 如果马上删除 p 则可以不赋空

37 2.3 链表 循环链表 (circularly linked list) 将单链表或者双链表的头尾结点链接起来, 就是一个循环链表 不增加额外存储花销, 却给不少操作带来了方便 从循环表中任一结点出发, 都能访问到表中其他结点 tail head a 0 a 1 a n-1 37

38 2.3 链表 几个特殊点的处理 头指针处理 链表的边界条件 非循环链表尾结点的指针域保持为 NULL 循环链表尾结点的指针回指头结点 链表处理 空链表的特殊处理 插入或删除结点时指针勾链的顺序 指针移动的正确性 插入 查找或遍历 38

39 思考 带表头与不带表头的单链表? 处理链表需要注意的问题? 39

40 第二章 线性表 2.1 线性表 2.2 顺序表 2.3 链表 第二章线性表 2.4 顺序表和链表的比较 a 0 a 1 a 2 a n-1 40

41 2.2 顺序表 2.2 顺序表 也称向量, 采用定长的一维数组存储结构 主要特性 元素的类型相同 元素顺序地存储在连续存储空间中, 每一个元素有唯一的索引值 使用常数作为向量长度 数组存储 读写其元素很方便, 通过下标即可指定位置 只要确定了首地址, 线性表中任意数据元素都可以随机存取 41

42 2.2 顺序表 元素地址计算如下所示 : 2.2 顺序表 Loc k i = Loc k 0 + c i, c = sizeof(elem) 逻辑地址 ( 下标 ) 数据元素 存储地址数据元素 0 k 0 Loc(k 0 ) k 0 1 k 1 Loc(k 0 )+c k 1 i k i Loc(k 0 )+i*c k i n-1 k n-1 Loc(k 0 )+(n-1)*c k n-1 42

43 第二章 线性表 2.2 顺序表 顺序表类定义 class arrlist : public List<T> { // 顺序表, 向量 private: // 线性表的取值类型和取值空间 T * alist ; // 私有变量, 存储顺序表的实例 int maxsize; // 私有变量, 顺序表实例的最大长度 int curlen; // 私有变量, 顺序表实例的当前长度 int position; // 私有变量, 当前处理位置 public: arrlist(const int size) { // 创建新表, 设置表实例的最大长度 maxsize = size; alist = new T[maxSize]; curlen = position = 0; } ~arrlist() { // 析构函数, 用于消除该表实例 delete [] alist; } 43

44 第二章 线性表 2.2 顺序表 顺序表类定义 }; void clear() { // 将顺序表存储的内容清除, 成为空表 delete [] alist; curlen = position = 0; alist = new T[maxSize]; } int length(); // 返回当前实际长度 bool append(const T value); // 在表尾添加元素 v bool insert(const int p, const T value); // 插入元素 bool delete(const int p); // 删除位置 p 上元素 bool setvalue(const int p, const T value); // 设元素值 bool getvalue(const int p, T& value); // 返回元素 bool getpos(int &p, const T value); // 查找元素 44

45 2.2 顺序表 重点讨论 插入元素运算 顺序表上的运算 bool insert(const int p, const T value); 删除元素运算 bool delete(const int p); 其他运算请大家思考 45

46 第二章 线性表 2.2 顺序表 顺序表的插入图示 k 0 k 0 k 1 k 1 X curr k 2 k 3 X curr k 2 k 3 k 4 k 4 k 5 k 5 46

47 2.2 顺序表 顺序表的插入 // 设元素的类型为 T, alist 是存储顺序表的数组, maxsize 是其最大长度 ; // p 为新元素 value 的插入位置, 插入成功则返回 true, 否则返回 false template <class T> bool arrlist<t> :: insert (const int p, const T value) { int i; if (curlen >= maxsize) { // 检查顺序表是否溢出 cout << "The list is overflow"<< endl; return false; } if (p < 0 p > curlen) { // 检查插入位置是否合法 cout << "Insertion point is illegal"<< endl; return false; } for (i = curlen; i > p; i--) alist[i] = alist[i-1]; // 从表尾 curlen -1 起往右移动直到 p alist[p] = value; // 位置 p 处插入新元素 curlen++; // 表的实际长度增 1 return true; } 47

48 第二章 线性表 2.2 顺序表 顺序表的删除图示 k 0 k 0 k 1 k 1 curr k 2 k 3 curr k 2 k 3 k 4 k 4 k 5 k 5 k 6 k 6 48

49 2.2 顺序表 顺序表的删除 // 设元素的类型为 T;aList 是存储顺序表的数组 ; p 为即将删除元素的位置 // 删除成功则返回 true, 否则返回 false template <class T> // 顺序表的元素类型为 T bool arrlist<t> :: delete(const int p) { int i; if (curlen <= 0 ) { // 检查顺序表是否为空 cout << " No element to delete \n"<< endl; return false ; } if (p < 0 p > curlen-1) { // 检查删除位置是否合法 cout << "deletion is illegal\n"<< endl; return false ; } for (i = p; i < curlen-1; i++) alist[i] = alist[i+1]; // 从位置 p 开始每个元素左移直到 curlen curlen--; // 表的实际长度减 1 return true; } 49

50 顺序表插入删除运算的算法分析 表中元素的移动 插入 : 移动 n i 2.2 顺序表 删除 : 移动 n i 1 个 i 的位置上插入和删除的概率分别是 p i 和 p i 插入的平均移动次数为 n M i = i=0 删除的平均移动次数为 n 1 i=0 n i p i M d = n i 1 p i 50

51 51 算法分析 如果在顺序表中每个位置上插入和删除元素的概率相同, 即 p i = 1 n+1, p i = 1 n 2.2 顺序表线性表第二章 2 1) 2( 1) ( 1 1) ( ) ( 1 1 ) ( n n n n n n n i n n i n n M n i n i n i i ) ( ) ( 1 1) ( n n n n n i n n i n n M n i n i n i d 时间代价为 O(n)

52 思考 顺序表中, 插入删除操作需要考虑哪些问题? 顺序表有哪些优缺点? 52

53 第二章线性表 2.1 线性表 2.2 顺序表 2.3 链表 2.4 顺序表和链表的比较 53

54 2.4 线性表实现方法的比较 2.4 线性表实现方法的比较 顺序表的主要优点 没有使用指针, 不用花费额外开销 线性表元素的读访问非常简洁便利 链表的主要优点 无需事先了解线性表的长度 允许线性表的长度动态变化 能够适应经常插入删除内部元素的情况 总结 顺序表是存储静态数据的不二选择 链表是存储动态变化数据的良方 54

55 2.4 线性表实现方法的比较 顺序表 顺序表和链表的比较 插入 删除运算时间代价 O(n), 查找则可常数时间完成 预先申请固定长度的连续空间 如果整个数组元素很满, 则没有结构性存储开销 链表 插入 删除运算时间代价 O(1), 但找第 i 个元素运算时间代价 O(n) 存储利用指针, 动态地按照需要为表中新的元素分配存储空间 每个元素都有结构性存储开销 55

56 2.4 线性表实现方法的比较 顺序表和链表存储密度 n 表示线性表中当前元素的数目, P 表示指针的存储单元大小 ( 通常为 4 bytes) E 表示数据元素的存储单元大小 D 表示可以在数组中存储的线性表元素的最大数目 空间需求 顺序表的空间需求为 DE 链表的空间需求为 n(p + E) n 的临界值, 即 n > DE / (P+E) n 越大, 顺序表的空间效率就更高 如果 P = E, 则临界值为 n = D / 2 56

57 2.4 线性表实现方法的比较 顺序表不适用的场合 应用场合的选择 经常插入删除时, 不宜使用顺序表 线性表的最大长度也是一个重要因素 链表不适用的场合 当读操作比插入删除操作频率大时, 不应选择链表 当指针的存储开销, 和整个结点内容所占空间相比其比例较大时, 应该慎重选择 57

58 2.4 线性表实现方法的比较 顺序表 顺序表和链表的选择 结点总数目大概可以估计 线性表中结点比较稳定 ( 插入删除少 ) n > DE / (P + E) 链表 结点数目无法预知 线性表中结点动态变化 ( 插入删除多 ) n < DE / (P + E) 58

59 思考 顺序表和链表的选择? 结点变化的动态性 存储密度 59

60 2.4 线性表实现方法的比较 思考 : 一元多项式的表达 一元多项式 :P n (x) = p 0 +p 1 x+p 2 x 2 + +p n x n 线性表表示 :P = (p 0, p 1, p 2,, p n ) 顺序表表示 : 只存系数 ( 第 i 个元素存 x i 的系数 ) p 0 p 1 p 2 p n 数据稀疏的情况 :p(x) = 1+2x x 链表表示 : 结点结构 系数指数

61 数据结构与算法 谢谢聆听 国家精品课 数据结构与算法 张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五 国家级规划教材