Microsoft PowerPoint - ds_2.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - ds_2.ppt"

宝劳
6 years ago
Views:

1 第二章线性表 2.1 线性表的概念 2.2 顺序表示 2.3 链接表示 2.4 应用举例 -Josehus 问题另外介绍动态顺序表程序里常需要保存一批某种类型的元素, 这些元素的数目可能变化 ( 可以加入或删除元素 ) 有时需要把这组元素看成一个序列, 元素的顺序可能表示实际应用中的某种有意义的关系这样一组元素可以抽象为元素的一个线性表线性表是元素的集合, 同时记录了元素的顺序关系线性表是一种最基本的数据结构, 在各种程序里应用广泛, 还常作为实现更复杂的数据结构的基础本章讨论线性表的概念, 它的两种基本实现方式, 它们的一些变形, 以及若干应用实例线性表的概念元素 :{,,e N-1 是一个元素集合线性表 : 简称表, 元素的有穷序列, 可包含 0 个或多个元素, 表示为 (,,,e n-1 ),n 0 元素位置称为下标, 下标从 0 开始 ( 一种选择 ) 表中元素个数称为表的长度, 长度为 0 的表是空表关系 :<, >,<,e 2 >,,<e n-2, e n-1 > 是一种顺序关系 ( 线性关系 ) 例 : 整数的表, 字符串的表, 某种结构的表线性表是一种线性结构非空线性表中 : 1. 存在唯一的称为第一个的元素 ; 2. 存在唯一的称为最后一个的元素 ; 3. 除第一个元素之外, 表中的每个元素都有且只有一个前驱元素 ; 4. 除最后一个元素之外, 表中的每个元素都有且只有一个后继元素可以把线性表作为一种数学对象, 为它建立抽象模型 3 4 抽象模型元素集合 : 线性表集合 : 基本操作组合 : 取头部 : 取尾部 : 判空表 : 操作的基调 (Signature, 原型, 类型特征 ) 组合 : 取头部 : 取尾部 : 判空表 : 定义操作, 例如表的长度操作基调 : 定义 : 5 其他操作可类似定义 6

2 代数定律假设 : 定律 : 下面从更实际的角度考虑表的结构类型与变量说明 : 元素类型 DataTye 元素变量说明 DataTye x; 下标类型 Index 下标变量说明 Index ; 这样下去, 可以定义更多的表操作以及操作之间的关系, 做出一套表的理论 7 线性表类型 List 线性表变量说明 List list; 8 线性表的基本运算 ( 可根据需要扩充 ): 1. List createnulllist ( void ) 创建一个空线性表 2. int insert ( List list, Index, DataTye x ) 在线性表 list 中下标为的位置插入一个值为 x 的元素, 返回成功与否的标志操作把新元素插入序列中, 保持原有元素的前后顺序不变插入可能由于内部原因而失败, 此时原表结构不变 3. int delete (List list, Index ) 在线性表 list 中删除下标为的元素, 返回删除成功与否的标志操作保证表中剩余元素的顺序不变如果表里没有下标则删除操作失败 4. Index locate ( List list, DataTye x ) 在线性表 list 中查找值为 x 的元素的位置找到时返回元素在表中的位置, 找不到返回一个特殊值 5. int isnull ( List list ) 判别线性表 list 是否为空表如果 list 是空表就返回真 ( 在 C 里用非 0), 否则返回假还可以有其他操作, 例如 1. int deleteelem ( List list, DataTye x ) 在线性表 list 删除值为 x 的元素 2. void sortascend ( List list ) 将线性表 list 的元素按照值的上升顺序重新排列线性表与数组的比较 : 线性表线性结构是一种更抽象的结构少数语言内部提供了表类型, 在多数语言里需要自己实现数组线性结构是一种更具体的结构, 通常作为语言最基本的数据机制, 可直接使用 2.2 顺序表示线性表的一种可能实现方式是顺序存放其中元素把元素顺序存放在一片连续存储区中, 借助元素在内存的物理位置表示元素间的顺序逻辑关系 ( 隐式表示元素间的关系 ), 这样形成的结构称为顺序表操作集合包括插入删除等, 还可根据需要考虑许多操作表中元素个数可通过操作改变操作只有通过下标访问, 元素赋值或取元素值元素个数不变, 创建时确定完全可能用数组作为实现线性表的一种具体表示结构顺序表中任一元素的位置都可直接算出, 因此可以在 O(1) 时间直接存取元素 e i 的地址计算公式 : Locate(e i ) = Locate( ) + c * i 其中 c = sizeof(datatye), 一个元素占用的存储量 11 12

3 逻辑地址线性表的顺序存储结构示意图 0 1 i n-1 数据元素 e i e n-1 存储地址 Locate( ) Locate( )+c Locate( )+i*c Locate( )+ (n-1)*c 数据元素 e i e n-1 13 顺序表, 可看作以数组作为基础实现的线性表数组的元素个数固定, 线性表的元素个数可以随操作改变, 需要设法弥合两者之间的差异方式 : 创建一个大数组, 表元素存在数组前面一段表元素应密集地连续存放, 以便能用数组下标作为表元素索引 ( 效率 ) 需要记录表中元素个数必须维持元素个数记录和表中实际元素个数一致数组大小确定了顺序表的最大容量 ( 需根据实际确定 ), 也使插入操作有可能失败连续存放给删除操作的实现带来问题 n 表中当前存在的元素 14 顺序表的 C 实现 : 类型定义定义 1: DataTye elements[nmax]; int n; /* 元素个数 n < NMAX */ /* 没反映 elements 和 n 的内在联系 ; 应专门引进一个类型 */ 定义 2:( 用结构将相关数据成分包装起来 ) struct SeqList { int n; /* 元素个数 n < NMAX */ DataTye elements[nmax]; ; 最好是定义为类型 : tyedef struct SeqList { SeqList; 15 后一定义更清晰, 更符合数据抽象原则 ( 一个对象应是一个整体, 一种对象应定义为类型 ), 应该采用为了使用方便, 常定义指向顺序表类型的指针类型 : tyedef SeqList *PSeqList; 如果函数 f 的原型是 :... f (PSeqList l) 实际调用函数 f 应该采用的形式 : SeqList L1; /* 定义顺序表 L1 */... f(&l1); 在 f 里可以完成对 L1 的任何操作 ( 思考题 : 如果 f 的参数用 SeqList 类型, 情况有什么不同?) 16 顺序表基本运算的实现算法 2.1 创建空表 PSeqList createnulllist_seq( void ) 算法 2.2 插入 int insert_seq( PSeqList alist, int, DataTye x ) 算法 2.3 删除 int delete_seq( PSeqList alist, int ) 算法 2.4 求表中某元素的下标 int locate_seq( PSeqList alist, DataTye x ) 算法 2.5 求 alist 所指表中下标为的元素值 DataTye retrieve_seq( PSeqList alist, int ) 算法 2.6 判断表是否为空算法 2.1 创建空顺序表 PSeqList createnulllist_seq( void ) alist 需要 : 分配存储把 n 设置为 0, 保证表处于合法的初始状态 0 n elements int isnulllist_seq( PSeqList alist) 17 18

4 创建空顺序表 PSeqList createnulllist_seq( void ) { PSeqList alist = (PSeqList)malloc(sizeof(SeqList)); if (alist!= NULL) alist->n = 0; /* 分配成功, 空表长度为 0 */ else rintf("out of sace!\n"); /* 分配失败 */ return alist; 算法 2.2 顺序表的插入 int insert_seq seq( PSeqList alist, int, DataTye x ) e 2 e 3 e 4 e 5 e 2 e 3 e 4 e 2 x e 3 e 4 e 6 e 5 e 5 e 6 e 6 19 移动元素, 腾出空位后, 把新元素存入空位 20 /* 在 alist 所指顺序表中下标为的元素之前插入元素 x*/ int insert_seq(pseqlist alist, int, DataTye x) { int q; if ( alist->n == NMAX ) { /* 顺序表已满, 插入失败 */ rintf("seq-list overflow!\n"); return FALSE; if ( < 0 > alist->n ) { /* 不存在下标为的元素 */ rintf("index of seq-list is out of range! \n"); return FALSE; /* 插入失败 */ for (q = alist->n - 1; q >= ; --q) /* 元素逐一后移 */ alist->elements[q+1] = alist->elements[q]; alist->elements[] = x; /* 插入元素 x */ alist->n++; /* 元素个数加 1 */ return TRUE; 21 算法 2.3 顺序表的删除 int delete_seq seq( PSeqList alist, int ) e 2 e 3 e 4 e 5 e 6 e 2 e 4 e 5 e 6 元素逐个前移, 覆盖掉被删除的元素需要维护元素个数记录 22 /* 在 alist 所指顺序表中删除下标为的元素 */ int delete_seq( PSeqList alist, int ) { int q; if ( < 0 > alist->n - 1 ) { /* 不存在下标为的元素 */ rintf("index of seq-list is out of range!\n "); return FALSE; for (q = + 1; q < alist->n; ++ q) /* 元素逐个前移 */ alist->elements[q - 1] = alist->elements[q]; alist->n--; /* 元素个数减 1 */ return TRUE; 算法 2.4 求表中某元素的下标 int locate_seq( PSeqList alist, DataTye x ) int locate_seq(pseqlist alist, DataTye x) { int q; for ( q = 0; q<alist->n; ++q) if (alist->elements[q] == x) return q; return -1; 这里用 1 表示元素没有找到 -1 不是合法位置值, 因此适合用于表示特殊情况 23 24

5 算法 2.5 求 alist 所指表中下标为的元素值 DataTye retrieve_seq( PSeqList alist, int ) DataTye retrieve_seq( PSeqList alist, int ) { if ( >= 0 && < alist->n ) /* 存在下标为的元素 */ return alist->elements[]; rintf("index of seq-list is out of range.\n "); return SPECIAL; /* 返回一个表中没有的特殊值, 需定义 */ 参数出错是一类难处理的麻烦问题这里采用的方式是提供信息并返回一个特殊值这是一种处理方式, 也有缺点 25 使用表的程序片段 ( 假定 DataTye 是 int ): PSeqList l1 = createnulllist_seq( ); /* 创建空顺序表 */ insert_seq seq(l1, 0, 9); insert_seq seq(l1, 1, 5); insert_seq seq(l1, 1, 1); for (i = 3; i < 10; ++i) insert_seq(l1, i, i*3); 直接定义表变量 : SeqList L1; /* 注意, 这时表不在合法状态 */ set_emty_seq(&l1); /* 初始化, 把表的 n 成分置为 0 */ insert_seq(&l1, 0, 9); insert_seq(&l1, 1, 5); 直接写 L1.n = 0; 初始化好不好? 26 算法分析在 n 元素的顺序表里下标 i( 第 i+1 个 ) 的元素前插入元素需要移动 n - i 个元素 ; 删除下标为 i( 第 i+1 个 ) 的元素需要移动 n -i -1 个元素若在位置 i 插入和删除元素的概率分别是 i 和 i 则插入时的平均移动数是 : n m i = (n-i) i i=0 删除的平均移动数是 : n-1 m d = (n-i-1) i i=0 这里考虑的是平均复杂性, 问题较复杂, 因为这些操作的时间开销依赖于参数 ( 与插入删除位置有关 ) 和分布情况 27 顺序表插入和删除操作的平均时间代价为 O(n)( 最坏也是 O(n), 具体计算见书 ) 特殊情况 : 后端插入 / 删除的时间代价为 O(1), 可考虑独立实现 backinsert_seq(pseqlist,datatye) 和 backdelete_seq(pseqlist) 根据元素值的定位操作 locate_seq, 需顺序与表中元素比较定位各位置的概率平均分布时, 操作平均需做 n/2 次比较, 时间 O(n) 顺序实现 ( 顺序表 ) 的优点 :O(1) 时间 ( 随机直接, 按位置 ) 存取元素, 元素存储紧凑, 不需要附加空间缺点 : 需要连续的大片空间 ; 插入删除常要大量移动元素 ; 需事先确定空间大小, 有时事先难以做出估计存储区中可能有大量空闲单元 28 简单的阶段性总结 : 定义了线性表的概念 ( 还给出了一种抽象模型 ) 设计了线性表应的一组基本操作, 明确了操作的含义, 这样一组描述实际上定义了一个抽象数据类型还提出了另一些可能操作提出了一种实现模型顺序表, 讨论了顺序实现的问题在 C 语言里给出了顺序表的一个具体实现注意 : 表抽象数据类型的设计可以有许多变化 ( 操作集合的选择 ) 除顺序方式外, 还可能找到其他实现模型在 C 语言里实现, 完全可能采用其他方式和技术链接表示单链表循环链表双链表可通过在与元素相关的地方存放对其他元素的引用, 显式指明元素之间的关系这样建起的结构称为链接结构, 用这种方式实现的表称为链接表 ( 链表 ) 引用的最常见实现方式是借助语言中的指针链接结构的最常见实现方式是利用动态存储分配功能 30

6 2.3.1 单链表最简单的链表是单链表 : 为每个元素关联一个链接, 表示后继关系 ( 这时没有表示前驱关系的信息 ) 结点 : 元素的存储映象, 包括数据域和指针域数据域链接域单链表 : 与表中 n 个元素对应的 n 个结点通过指针链接成一个链表链表中每个结点只有一个指针域头指针 : 指示单链表第一个结点的存储位置的指针, 整个链表的存取必须从头指针开始一个链表的存储示例 head Zhao Qian Sun Zhou Wu Zheng Wang ^ Li 图 2.6 一个线性链表的逻辑结构实际中不需要关心结点的具体存储地址 ( 与链接表结构无关 ), 只需关心表的逻辑结构链接表的操作也可以在逻辑结构上考虑单链表的 C 实现 tyedef struct Node Node, *PNode; /* 结点 / 指针类型 */ struct Node { /* 单链表结点结构 */ DataTye info; PNode link; ; 为提高可读性, 可定义如下单链表类型 : tyedef struct Node *LinkList; 定义链表头指针 : LinkList llist; 另一种定义方式 ( 增加一层封装 ): tyedef struct { /* 单链表类型定义 */ PNode head; /* 指向单链表中的第一个结点 */ LinkList; 这种方式把链表的具体实现封装起来本书没采用这种方式 35 设 llist 是 LinkList 类型变量, 指向单链表的首结点, 如下图表为空时,llist 的值为 NULL llist. e n-1 (a) 不带头结点为方便运算实现, 可在链表首结点前增加一个称为头结点的辅助结点 ( 不属于表的内容 ) 头结点的 info 域可不存信息, 或存放与整个表相关的信息 ( 如元素个数 ), 头结点的 link 域指向表的第一个实际结点, 如下图 llist (b) 带头结点. e n-1 36

7 无头结点时, 在表头插入删除时需修改表头指针, 在其他位置插入删除时修改其前驱结点的 link, 两种操作需要分别处理有了头结点, 操作的实现可以统一处理因为表中每个有效结点都链接在另一结点的 link 域 llist llist. e n-1 (a) 不带头结点 (b) 带头结点下面算法实现的是带头结点的单链表. e n-1 37 单链表基本运算的实现算法 2.7 创建空单链表 LinkList createnulllist_link( void ) 算法 2.8 单链表的插入 int insert_link( LinkList llist, int i, DataTye x ) 算法 2.9 单链表的删除 int delete_link(linklist llist, DataTye x ) 算法 2.10 在单链表中求某元素的存储位置 PNode locate_link( LinkList llist, DataTye x ) 算法 2.11 求单链表中下标为 i 的元素的存储位置 PNode find_link( LinkList llist, int i ) 算法 2.12 判断单链表是否为空 int isnulllist_link( LinkList llist ) 向下 38 /* 创建一个带头结点的空链表 */ LinkList createnulllist_link( void ) { LinkList llist; /* 申请表头结点空间 */ llist = (LinkList) malloc( sizeof( Node ) ); if ( llist!= NULL ) llist->link = NULL; return llist; 可以增加对错误情况的处理操作正常完成后的状态 : 结点插入操作 : q->link = ->link; ->link = q; q q q llist 返回 39 注意 : 指针更新次序不能错 /* 在带头结点单链表 llist 中下标 i 的 ( 第 i+1 个 ) 结点前插入元素 x */ int insert_link(linklist llist, int i, DataTye x) { PNode = llist, q; int j; for (j = 0 ;!= NULL && j < i; j++) = ->link; if (j!= i) { /* i<1 或者大于表长 */ rintf("index %d is out of range.\n", i); return FALSE; q = (PNode)malloc( sizeof( Node ) ); /* 申请新结点 */ if ( q == NULL ) { rintf( "Out of sace!\n" ); return FALSE; /* 填充数据并插入链表中 */ q->info = x; q->link = ->link; ->link = q; return TRUE ; /* 在 llist 带有头结点的单链表中删除第一个值为 x 的结点 */ /* 这时要求 DataTye 可以用!= 比较 */ int delete_link( LinkList llist, DataTye x ) { PNode = llist, q; /* 找值为 x 的结点的前驱结点的存储位置 */ while( ->link!= NULL && ->link->info!= x ) = ->link; if( ->link == NULL ) { /* 没找到值为 x 的结点 */ rintf("datum does not exist!\n "); return FALSE; q = ->link; /* 找到值为 x 的结点 */ ->link = ->link->link; /* 删除该结点 */ free( q ); return TRUE; q 返回 41 返回 42

8 /* 在带头结点的单链表 llist 中找第一个值为 x 的结点 */ /* 找不到时返回空指针 */ PNode locate_link( LinkList llist, DataTye x ) { PNode ; if (llist == NULL) return NULL; for ( = llist->link;!= NULL && ->info!= x; ) = ->link; return ; /* 在带头结点单链表 llist 中找下标为 i 的 ( 第 i+1 个 ) 结点 */ /* 当表中无下标为 i 的 ( 第 i+1 个 ) 元素时, 返回值为 NULL */ PNode find_link( LinkList llist, int i ) { PNode ; int j; if (i < 0) { /* 检查 i 的值 */ rintf("index of llist is out of range.\n", i); return NULL; for ( = llist, j = 0;!= NULL && j <= i; j++) = ->link; if ( == NULL) rintf("index of llist is out of range.\n", i); 返回 43 return ; 返回 44 单链表与顺序表的比较存储密度 = 数据本身所占的存储量整个数据结构所占的存储量 (1) 单链表的 link 占用额外存储空间但整个表的空间安排方式灵活 ; 顺序表需要连续空间, 要按估计的最大空间需求分配, 所占存储里可能有大片闲置空间 (2) 顺序表支持对任一元素的 O(1) 按位置访问 ; 单链表中只能顺链接逐个查找, 按位置访问的时间为 O(n) (3) 在单链表里的插入删除运算不需要移动其它元素 ; 而对顺序表可能需要移动许多元素单链表适合于实现其中元素常常成批顺序地处理的线性表顺序表适合静态或大小可以估计的数据表示 45 单链表的前端插入和删除都是 O(1) 操作, 一般位置的插入和删除是 O(n) 操作修改设计, 增加表尾指针, 可使后端插入变成 O(1) 操作 : llist e. 0 e n-1 带表尾结点指针的链接表采用这种表示, 插入删除时需要考虑维护表尾指针, 创建表的操作也需要修改同样可以考虑有头结点和没有头结点的形式双链表其中的每个结点里设后继指针和前驱指针既可以直接找到后继, 也可以直接找到前驱 head rear ^ e 2 e n-1 ^ cdlist 带头尾指针的双链表带有头结点的循环双链表 e n-1 47 双链表的实现数据类型定义 : tyedef struct DNode DNode, *PNode; /* 类型 */ struct DNode { /* 双链表结点结构 */ DataTye data; PNode rev, next; ; tyedef DNode *DLinkList; /* 双链表类型 */ 48

9 双链表的一个特点 : 有了指向一结点的指针, 就可以把该结点从链表上取下 ( 并保持链表的正常状态 ) 完成这一操作的语句序列 ( 假定指向被删结点 ): if (->next!= NULL) ->next->rev = ->rev; if (->rev!= NULL) ->rev->next = ->next; 在一个结点的后面插入新结点假定 q 指向新结点, 指向表中结点 (q 所指结点插入其后 ) nx = ->next; q->next = nx; if (nx!= NULL) nx->rev = q; ->next = q; q->rev = ; 这里引进 nx 只是为了使代码更清晰一些在结点前插入新结点的操作与此类似写链接表操作, 需要特别注意指针赋值的顺序循环链表让单链表最后结点的指针指向头结点, 就得到循环链表优点 : 从表中任一结点出发都能访问所有结点 clist e. 1 e n-1 循环链接表插入第一个元素时需要特别处理 : clist 也可以考虑带头结点的循环链表操作中经常要访问修改首结点和末结点让表头指针指向循环链表末结点, 可以使对表头表尾的操作都方便 e. 1 e n-1 clist clist e. 1 e n 实现循环链表可以采用与单链表一样的数据类型定义创建链表的操作需要修改如有头结点的链表 : llist = (LinkList) malloc( sizeof( Node ) ); if ( llist!= NULL ) llist->link = llist; return llist; 无头结点的表插入第一个结点时, 也需建立循环链接判断空表的操作 ( 有头结点的表 ): return llist->link = llist; 其他操作基本上可以照搬单链表的操作根据所采用的设计, 可能需要做些小调整应用举例 Josehus 问题问题描述 : 设有 n 个人围坐在一个圆桌周围, 现从第 s 个人开始报数, 数到第 m 的人出列, 然后再从出列的下一人开始报数, 数到第 m 的人出列, 如此反复直到所有人全部出列 Josehus 问题 : 对于任意给定的 n, s 和 m, 求出按出列次序得到的 n 个人员的序列以 n=8,s=1,m=4 为例, 问题的求解过程如图 2-15 图中 s1 指向开始报数位置, 若初始的顺序为 n 1,n 2, n 3,n 4,n 5,n 6,n 7,n 8 则问题的解为 n 4,n 8,n 5, n 2,n 1,n 3,n 7,n 6 54

10 可用顺序表和循环单链表作为求解 Josehus 问题的程序的数据表示, 用表元素表示人的编号 ( 或名字 ) 求解过程概要 : 1) 首先用线性表基本运算, 如创建空线性表插入元素等, 构造出与具体 Josehus 问题实例对应的表 ; 2) 从 Josehus 表中的第 s 个结点开始寻找输出删除表中第 m 个结点然后从该结点后下一结点寻找输出和删除表中第 m 个结点, 重复此过程, 直到删除完 Josehus 表中所有元素程序见书虽然比较长, 但意义很容易理解顺序表实现中有如何形成循环计数的问题 ( 取模 ) 顺序表的实现方式前面讨论顺序表时采用的数据类型定义 #define NMAX 40 tyedef struct SeqList { int n; /* 元素个数 n < NMAX */ DataTye elements[nmax]; SeqList; /* SeqList 成为一个自定义类型名 */ 这样做优点 : 实现简单缺点 : 不灵活, 程序里通过 createnulllist_seq 创建的每个 SeqList 的元素个数都一样实际中常常需要几个表, 但可能需要大小不同的表可能希望下面这样的空表创建函数 : PSeqList createnulllist_seq( int size ); 用原类型就不行了, 因为其中结构成员的数组大小是固定的引进灵活性的方法是修改设计, 把保存元素的数组和表的基本部分分开, 动态分配保存表元素的数组由于表中元素数组的大小 ( 元素容量 ) 在创建时才确定, 不同的表可能不同, 必须记录容量修改的顺序表的基本布局图 : n nmax 当前元素个数当前容量动态分配的元素存储区 tyedef struct { int n, nmax; DataTye *elems; DSeqList, *PDSeqList; nmax 记录表容量,elems 是指针, 实际存储区动态分配注意 : 为了灵活性, 相关类型变复杂了操作也会变得复杂一些 : 创建操作需要重新写, 比原来的复杂还需要专门定义一个销毁表的函数其他函数都不需要修改 ( 还好 ) PDSeqList createnulllist_dseq( int size ) { PDSeqList l = (PDSeqList)malloc(sizeof(DSeqList)); if (l!= NULL) { l->elems = (DataTye*)malloc(sizeof(DataTye)*size); if (l->elems) { l->n = 0; l->nmax = size; /* 设置表容量 */ return l; /* 创建成功 */ else free(l); /* 存储分配失败, 释放已分配存储 */ rintf("out of sace!\n"); /* 存储分配失败 */ return NULL; 使用 PDSeqList list = createnulllist_dseq(100); 59 销毁动态顺序表 : void destroy_dseq( PDSeqList l) { free(l->elems); /* 首先释放元素存储区 */ free(l); /* 释放表结构 */ 由于表元素的存储空间时独立分配的, 必须专门删除如果直接用 ( 假定 dsl 指向一个动态顺序表 ) free(dsl); 顺序表基本部分的释放了, 元素存储区 ( 另一存储块 ) 就丢了注意 : 现在不能简单地定义 DSeqList 变量并使用, 因为没有元素存储区 ( 可以专门定义函数来处理 ) DSeqList list; /* 无元素存储区 */ 60

11 动态顺序表顺序表实现支持 O(1) 的元素访问, 但需要静态 ( 或创建时 ) 确定容量实际中容量有时很难确定可否实现能在使用中动态改变大小的顺序表? 利用动态分配的技术, 不难实现能动态变动大小的顺序表现在的问题 : 在插入元素时可能遇到存储区满了的情况解决办法 : 换一块更大的存储区由于存储区是动态分配的, 在运行中动态换一块并不困难 ( 显示了指针和动态存储管理的威力 ) 元素存储区设定初始大小, 插入时满则扩充从问题到程序讨论了扩充策略和相应时间代价类型定义与前面修改的顺序表类似 : enum { NBASE = 20 ; tyedef int DataTye; /* 根据需要确定 */ tyedef struct { int n, nmax; DataTye *elems; DSeqList, *PDSeqList; elems 指向动态分配的元素存储区,nmax 是当时容量表创建和前面动态分配存储区的顺序表类似, 元素插入操作必须重写表删除和其他操作可照搬创建新的动态顺序表 : PDSeqList createnulllist_dseq( void ) { PDSeqList l = (PDSeqList)malloc(sizeof(DSeqList)); if (l!= NULL) { l->elems = (DataTye*)malloc(sizeof(DataTye)*NBASE); if (l->elems) { l->n = 0; /* 空表长度为 0 */ l->nmax = NBASE; return l; /* 创建成功 */ else free(l); /* 存储分配失败, 释放已分配存储 */ rintf("out of sace!\n"); /* 存储分配失败 */ return NULL; 后端元素插入 : int backinsert_dseq(pdseqlist l, DataTye x) { if ( l->n == l->nmax ) { /* 存储区满, 扩大一倍 */ DataTye *d = (DataTye*)realloc(l->elems, l->nmax*2*sizeof(datatye)); if (d == NULL) { /* 空间耗尽, 已有元素还在原处 */ rintf("seq-list overflow!\n"); return FALSE; l->elems = d; l->nmax *= 2; l->elems[n] = x; l->n++; /* 插入, 个数加 1 */ return TRUE; int insert_dseq(pdseqlist l, int, DataTye x) { int q; if ( < 0 > l->n ) { /* 不存在下标为的元素 */ rintf("index out of range! \n"); return FALSE; if ( l->n == l->nmax ) { /* 存储区满, 扩大一倍 */ DataTye *d = (DataTye*)realloc(l->elems, l->nmax*2*sizeof(datatye)); if (d == NULL) { /* 空间耗尽, 已有元素还在原处 */ rintf("seq-list overflow!\n"); return FALSE; l->elems = d; l->nmax *= 2; for (q = l->n - 1; q >= ; -- q) /* 元素后移 */ l->elems[q+1] = l->elems[q]; l->elems[] = x; l->n++; /* 插入, 个数加 1 */ return TRUE; 65 复杂性分析 : 按位置访问元素,O(1) 操作 : dsl->elems[i] 后端元素插入操作的情况比较复杂 : 正常情况需要 O(1) 时间 ; 当存储区满时可能需要把现有的元素复制到新存储区, 因此是 O(n) 一次 O(n) 情况之后将有至少 n 次正常情况 ( 如果其间没有删除 ) 把该 O(n) 平均进去, 总时间对操作的平均仍是常量 ( 采用加倍的存储分配策略 ) 人们把这类情况称为分期付款式的 O(1) 复杂性动态顺序表使用很广泛, 被用在一些标准库的实现里 66

12 表结点空间的管理静态数据结构 : 顺序表 ( 用数组实现 ) 在程序运行期间, 数组大小不变化动态数据结构 : 链表 ( 通过许多小的结点实现 ) 在程序运行期间, 表大小 ( 结点数 ) 可自由变化链表结点使用的空间通常通过系统提供的动态存储管理功能获得 (C 语言库函数 malloc 和 free) 也可以自己管理, 用一个数组实现某个类型的链表建立一个数组 ( 定义, 或者动态分配 ) 数组元素是表结点结构, 其 link 成分是整数 link 成分里保存下一结点的数组下标作为 ( 结点 ) 链接 67 avail 整型变量 0 数组元素通过整数下标链接起来整型变量 avail 指向空闲单元形成的链接表, 称为自由表 ( 可用空间表 ) 遇到分配请求, 就从自由表里分配结点用数组实现链表 ( 初始状态 ) list2 list1 avail d c a e -1 7 b 用数组实现链表 ( 一个场景 ) 69 实现结点结构 : /* 根据需要定义类型, 这里从略 */ struct NNode { DataTye data; int link; ; 定义一个数组变量, 其元素为 NNode 结构 enum { MEMSIZE = 1000 ; /* 根据需要确定 */ NNode array[memsize]; int avail = 0; /* 把数组元素用 link 成分链接起来,-1 表示空链接 */ for (i = 0; i < MEMESIZE-1; ++i) array[i].link = i + 1; array[memsize-1].link = -1; 70 用 -1 表示空链接, 自然数表示正常链接 ( 数组下标 ) 分配结点 (link 是 int 类型的链接域 ), 分配完成后引用新分配的结点 : if (avail >= 0) { = avail; avail = array[avail].link; 释放结点 ( 假定是要释放结点的下标 ): array[].link = avail; avail = ; 基于上述语句可以定义自己的 mymalloc 和 myfree 表操作的实现与前面类似, 但需注意链接的表示 71 小结本章讨论了线性表的概念存储表示和基本运算的实现线性表是一种较简单的数据结构, 是 n 个数据元素的有限序列常用存储方式是顺序存储和链接存储在线性表的顺序存储实现中, 元素之间的逻辑关系通过存储位置直接反映其中只需存放数据元素自身信息, 因此存储密度大空间利用率高另外, 元素位置可以从下标出发通过简单算式算出, 因此可以随机存取这些是顺序存储结构的优点另一方面, 顺序表中元素的插入和删除运算可能需要移动许多其它元素, 长度变化较大的线性表必须按最大需要的空间分配存储, 这些是线性表顺序存储结构的缺点在链接实现 ( 链接表 ) 里, 元素间的关系通过显式链接表示, 因此表中元素可以任意存放, 灵活, 可以通过修改链接的方式修改表的结构但表中的链接占用存储空间, 而且只能顺着链接查找所需元素, 不能随机访问 72

2.3 链表

2.3 链表数据结构与算法 ( 二 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) https://pkumooc.coursera.org/bdsalgo-001/ 第二章线性表 2.1 线性表 2.2 顺序表 tail head a 0 a 1 a n-1 2.4 顺序表和链表的比较 2 链表 (linked list) 通过指针把它的一串存储结点链接成一个链