《吉林大学数据结构课件 第二章 线性表、堆栈和队列》由会员分享，可在线阅读，更多相关《吉林大学数据结构课件 第二章 线性表、堆栈和队列（109页珍藏版）》请在金锄头文库上搜索。
1、第二章线性表、堆栈和队列线线性表、堆栈栈和队队列v2.1 线性表的定义和基本操作v2.2 线线性表的顺顺序存储结储结 构v2.3 线线性表的链链接存储结储结 构例1 英文字母表( A,B,C,Z )例2 某班学生健康情况登记表。学号 姓名 性别 年龄 健康情况01 张军 男 18 一般 02 陈红 女 17 良好03 陈军 男 19 健康 v线线性表定义义：一个线性表是由零个或多个具有相 同类型的结点组成的有序集合。通常用（a0，a1 ，an-1）来表示一个线性表，n为自然数。当 时， a0称为线性表的表头（head），an-1称为线 性表的表尾（tail），ai称为ai+1的前驱结点， ai
2、+1称为ai的后继结点；当 时，表中没有结点（ 包含零个结点），这样的线性表被称为空表。线性表记为(a0, a1, , an-1) n0( ) n = 0线性表的操作1. 创创建一个线线性表；2. 确定线线性表的长长度；3. 确定线线性表是否为为空；4. 存取表中第k个结结点的字段值值；5. 查查找指定字段值值在表中的位置；6. 删删除表中第k个结结点；7. 在表中第k个结结点后插入一个新结结点 ；线线性表、堆栈栈和队队列v2.1 线线性表的定义义和基本操作v2.2 线性表的顺序存储结构v2.3 线线性表的链链接存储结储结 构在线性表（a0，a1，an-1）中，对于表 中的相邻结点ai与ai-
3、1（这里的“相邻”是 指二者逻辑相邻）它们在计算机存储器中的物理存储地址 Loc(ai)与Loc (ai-1 )的关系？顺序存储结构 顺顺序存储储：用一组组连续连续 的存储储空间间依次 存储线储线 性表的元素。 特点：其逻辑顺逻辑顺 序与物理顺顺序相同。 实现顺实现顺 序存储储的最有效方法是使用一维维数 组组 。例 ：线线性表(a0，a1 ，a2 , a3)。顺序存储结构实现顺实现顺 序存储储的最有效方法是使用一维维数 组组 。图图4.1是包含4个结结点的线线性表A4在内存中 的表示，其中每个结结点占2个连续连续 的字节节， 第一个结结点A0的首地址为为302 图图4.1 线线性表的顺顺序存储
4、储线性表 A2 308306304302A0A1A3Loc(ak)= Loc (a0) + k*ca0a1an-1akb+cb+k*cbb+(n-1)*c01n-1k空闲区起始存储位置：起始存储位置：b b 每个元素大小：每个元素大小：c c 求第求第k k个元素的开始位个元素的开始位 置？置？线性表上实现的基本运算1、插入例 在线性表(12,13,21,24,28,30,42,77) 中下标为3的结点后，插入元素 25。序号 元素2 304167512 13 21 24 28 3042 77插入25序号 元素2 304167512132521 242830 42 778在下标为标为 k的结结
5、点后插入一个新结结点 /ADL描述算法 Insert(A,k,x)IF (kn) THEN PRINT(“overflow”).ELSE ( FOR i= n TO k1 STEP -1 DO Ai+1 Ai. Ak1 x. n n+1.) 2、删除例 在线性表(12,13,21,24,28,30,42,77) 中删除下标为3的元素 。序号 元素2 30416751213 21 24 28 3042 77删除24序号 元素2 3041651213 21 28 30 4277删删除下标为标为 k的结结点 /ADL描述算法 Delete(A,k)IF (kn)THEN PRINT(“error”)
6、ELSE ( FOR i=k+1 TO n DOAi-1 Ai.n n-1.) 结论：优点：线性表的顺序存储结构简单、易于实现，可以随机访 问表中任一元素。缺点：线性表的容量不容易扩充；插入、删除麻烦， 需移动元素。线线性表、堆栈栈和队队列v2.1 线线性表的定义义和基本操作v2.2 线线性表的顺顺序存储结储结 构v2.3 线性表的链接存储结构1、单链表的定义 链式存储：用一组任意存储单元存储线性 表的数据元素。单链表的结点结构：链表的第一个结点被称为头结点，指向头结点 的指针被称为头指针。链表的最后一个结点被称为尾结点。 单链表的定义：每个结点只含有一个指针域的 链表叫单链表。datanex
7、ta5a3a4 特点：逻辑顺序与物理顺序可以相同也可以不同。 优点： 插入、删除方便。 合理利用空间。例 将线性表(a3，a4，a5 ) 以链表的形式存储在内存中。(a3，a4，a5 )a5500a3100002a4002500 删除当前节点的后继节点： 算法Delete ( this . tempptr ) /* 删除当前结点的后继结点，并令指针tempptr指 向被删除结点 */ IF next（this）= NULL THEN tempptr NULL ELSE（ tempptr next（this）. next（this） next（tempptr） ）. FATHATthisGATt
8、empptr在当前结点之后插入结点 p /ADL描述算法InsertAfter(this ，p) IA1 将当前结点的next域值赋给P的next域 next(p) next(this). IA2 将P赋给当前结点的next域 next(this) p FATHATthisGATp在头指针为 head 的链表中，插入一个data 域为 item 的新结点作为该链表的表头结点。算法InsertFront(head ， item) IF1 调用函数GetNode GetNode(item,head. newNode). IF2 head指向新结点 head newNode. HATGATitemn
9、ewNode head head所谓遍历一个结构，是指按一定的次序访 问结构中的所有结点，且每个结点恰被访 问一次。遍历链表，就是按一定次序访问 链表的所有结点。 要想遍历整个链表，必须从头指针开始。 遍历链表 遍历链表演示 算法 PrintList(head) /输出头指针为head的链表,每输出5个元素换行 PL 1 取表头，计数器初始化 currptr head . count 0 .acbhead currptrPL 2 遍历并输出链表结点的data值 WHILE(currptr NULL) DO (PRINT( data(currptr). count count + 1. if (
10、count mod 5)=0 PRINT( ENTER). currptr next(currptr).) acbheadcurrptrabc操作:遍历插入InsertFrontInsertRearInsertAtInsertAfeter删除从一个结点出发，只能访问到链接在它后 面的结点，而无法访问位于它前面的结点 。链接结构“循环化”，即令表尾结点的next域 存放指向表头结点的指针，而不是存放空 指针NULL，这样的链表被称为循环链表。acbhead 循环链表1 循环链环链 表的定义义和结结构定义义：在单链单链 表中，使其最后一个结结点的指针针又 指回到第一个结结点，则这样则这样 的链链表
11、叫循环环链链表 循环链环链 表表头头：哨位节节点（数据为为空，指向第一 个数据项项）xnx1L 注意：判断表尾的条件：第一个节点判断空表的条件：xnx1p HeaderHeaderp - next = = NULLp - next = = NULL p p - - next = = headernext = = headerHead=NULLHead=NULL Header - next Header - next HeaderHeader双向循环链表1 问题的提出：找一个结点的前趋结点 2 双向循环链表的结构链表的结构leftdata right。L结点结构：Headerleft =Head
12、er right =Headerp - right - left = p - left - right = p 循环双链表判空的条件：双链表的对称性：Header在当前结点(this)之后插入结点 p 算法InsertRight(this ，P) / 在当前结结点Node(this)的右边边插入结结点Node(P) IR1 令当前结结点的右结结点的左指针针指向Node(P)left(right(this) P . IR2 令Node(P)的右指针针指向当前结结点的右结结点right(P) right(this). IR3 令Node(P)的左指针针指向当前结结点left(P) this. IR
13、4 令当前结结点的右指针针指向Node(P)right(this) P left(right(this) P . right(P) right(this). left(P) this. right(this) Pp4321this在当前结点(this)之后插入结点 p 算法InsertRight(this ，P) / 在当前结结点Node(this)的右边边插入结结点Node(P) IR1 令当前结结点的右结结点的左指针针指向Node(P)left(right(this) P . IR2 令Node(P)的右指针针指向当前结结点的右结结点right(P) right(this). IR3 令N
14、ode(P)的左指针针指向当前结结点left(P) this. IR4 令当前结结点的右指针针指向Node(P)right(this) P 在当前结点(this)之前插入结点 p 算法InsertLeft(this ，P) / InsertLeft用IL简记简记 IL1 令Node(P)的左指针针指向当前结结点的左结结点left(P) left(this). IL2 令当前结结点之左结结点的右指针针指向Node(P)right(left(this) P. IL3 令Node(P)的右指针针指向当前结结点right(P) this . IL4 令当前结结点的左指针针指向Node(P)left(t
15、his)P 左插入演示p2134left(P) left(this)thisright(left(this) P.right(P) this .left(this)P算法DeleteNode（this ） /* 删除当前结点 */ DN1. 令当前结点的左结点的右指针指向当前 结点的右结点 right（left（this） right（this）. DN2. 令当前结点的右结点的左指针指向当前 结点的左结点 left（right（this） left（this）right（left（this） right（this）. left（right（this） left（this）this顺序表当表中的元素较少时，顺序表中的很多空间处 于闲置状态，造成了空间的浪费；链表所占用的
