湘潭大学数据结构课件.ppt

CHAPTER 3表、栈和队列表、栈和队列§1 抽象数据类型抽象数据类型 (ADT)【【定义定义】】数据类型数据类型= { 数据对象数据对象 }   { 操作操作 }〖〖例例〗〗 int = { 0,  1,  2,      , INT_MAX, INT_MIN }   {  ,  ,  ,  , ,       }【【定义定义】】抽象数据类型抽象数据类型 (ADT)：：“抽象抽象”的意思，是指我们的意思，是指我们描述数据类型的方法是不依赖于具体实现的，即数据对象描述数据类型的方法是不依赖于具体实现的，即数据对象集和操作集的描述集和操作集的描述与存放数据的机器无关、与数据存储的与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关物理结构无关、与实现操作的算法和编程语言均无关简简而言之，抽象数据类型只描述数据对象集和相关操作集而言之，抽象数据类型只描述数据对象集和相关操作集“是什么是什么”，并不涉及，并不涉及“如何做到如何做到”的问题。

的问题•对于每种对于每种ADT并不存在什么法则来规定必须要有哪些操作；并不存在什么法则来规定必须要有哪些操作；•错误处理和结构调整一般也取决于程序的设计者错误处理和结构调整一般也取决于程序的设计者类型名称：类型名称：线性表（线性表（List））数据对象集：数据对象集：线性表是线性表是 n (≥0)个元素构成的有序序列个元素构成的有序序列( a1, a2, ,an ) ；； ai+1称为称为 ai的直接后继，的直接后继， ai-1为为 ai的直接前驱；直接前驱和直接后继反的直接前驱；直接前驱和直接后继反映了元素之间一对一的邻接逻辑关系映了元素之间一对一的邻接逻辑关系操作集：操作集：对于一个具体的线性表对于一个具体的线性表L   List，一个表示位置的整数，一个表示位置的整数i，一个，一个元素元素X   ElementType，线性表的基本操作主要有：，线性表的基本操作主要有：1、、List MakeEmpty()：：初始化一个新的空线性表初始化一个新的空线性表L；；2、、ElementType FindKth( int K, List L )：根据指定的位序：根据指定的位序K，返回相应，返回相应元素元素 ；；3、、int Find( ElementType X, List L )：已知：已知X，返回线性表，返回线性表L中与中与X相同相同的第一个元素的相应位序的第一个元素的相应位序i；若不存在则返回空；；若不存在则返回空；4、、void Insert( ElementType X, int i, List L)：指定位序：指定位序i前插入一个新元前插入一个新元素素X；；5、、void Delete( int i, List L )：删除指定位序：删除指定位序i的元素；的元素；6、、int Length( List L )：返回线性表：返回线性表L的长度的长度n。

§2 表表ADT ADT:1. 表的简单数组实现表的简单数组实现§2 表表ADT在内存中用在内存中用地址连续的一块存储空间顺序存放地址连续的一块存储空间顺序存放线性表的各元线性表的各元素一维数组一维数组在内存中占用的存储空间就是一组连续的存储区域在内存中占用的存储空间就是一组连续的存储区域typedef struct { ElementType Data[MAXSIZE]; int Last;} List; List L, *PtrL;下标下标i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last访问下标为访问下标为 i 的元素：的元素：L.Data[i] 或或 PtrL->Data[i]线性表的长度：线性表的长度：L.Last+1 或或 PtrL->Last+1下标下标i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下标下标i01…i-1ii+1…n…SIZE-1Dataa1a2…aiai+1…an…-Last插入插入（第（第 i (1≤i≤n+1)个位置上插入一个值为个位置上插入一个值为X的新元素的新元素)先移动，再插入先移动，再插入X下标下标i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下标下标i01…i-1…n-2n-1…MAXSIZE-1Dataa1a2…ai+1…anan…-Last删除删除（删除表的第（删除表的第 i (1≤i≤n)个位置上的元素个位置上的元素)后面的元素依次前移后面的元素依次前移  必须首先估计必须首先估计MaxSize .  Find_Kth 仅需仅需 O(1) 时间时间.  Insertion 和和 Deletion 在一般在一般情况下需要移动大量元素，需花费情况下需要移动大量元素，需花费O(N) 时间时间.Find X需要需要多少时间？多少时间？不要求逻辑上相邻的两个数据元素物理上也相邻不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过，它是通过“链链”建立起数据元素之间的逻辑关系。

建立起数据元素之间的逻辑关系因此对线性表的插入、因此对线性表的插入、删除删除不需要移动数据元素不需要移动数据元素，只需要修改，只需要修改“链链”§2 表表ADT2. 链表链表地址地址数据数据指针指针r0010001101101011SUNQIANZHAOLI101100100011NULLHead pointer ptr = 0110初始化初始化:typedef struct list_node *list_ptr;typedef struct list_node { char data [ 4 ] ; list_ptr next ;} ;list_ptr ptr ;ZHAOQIANSUNLIptrNULL连接连接‘ZHAO’ 和和 ‘QIAN’两个结点两个结点:list_ptr N1, N2 ;N1 = (list_ptr)malloc(sizeof(struct list_node));N2 = (list_ptr)malloc(sizeof(struct list_node));N1->data = ‘ZHAO’ ;N2->data = ‘QIAN’ ;N1->next = N2 ;N2->next = NULL ;ptr = N1 ;ZHAOQIANptrNULL连接操作的次序不同，连接操作的次序不同，结点的顺序也会发生变化结点的顺序也会发生变化§2 表表ADTa1ptrNULLaiai+1an......插入插入插入插入nodebtemp temp->next = node->next node->next = temp问题问题1: 如果这两个步骤的顺序更换，结果会如何？如果这两个步骤的顺序更换，结果会如何？问题问题2: 怎样插入一个新的首结点？怎样插入一个新的首结点？  花费花费 O(1) 时间时间.§2 表表ADT删除删除删除删除a1ptrNULLaiai+1an......bprenode pre->next = node->next free ( node )bnode问题问题: 怎样从表中删除第一个结点？怎样从表中删除第一个结点？解决方法解决方法: 在表中添加在表中添加“哑哑”的头节点。

的头节点  花费花费 O(1) 时间时间.HNULLaian...a1... 然后假设你又需要找到然后假设你又需要找到它的它的前驱前驱结点结点m   1?§2 表表ADT双向循环链表双向循环链表typedef struct node *node_ptr ;typedef struct node { node_ptr llink; element item; node_ptr rlink;} ;item   llinkrlinkptr = ptr->llink->rlink = ptr->rlink->llink 呃呃 ... 那么我将再次从第一个结点那么我将再次从第一个结点出发出发…但是，为什么我会想要但是，为什么我会想要找到前驱结点呢？找到前驱结点呢？一个带头节点的双向循环链表：一个带头节点的双向循环链表：item1    item2  item3  H一个带头节点的一个带头节点的空双向循环链表空双向循环链表:  H 有了前面的那些实现还不够吗有了前面的那些实现还不够吗?为什么我们还需要双向链表？为什么我们还需要双向链表？ 你说呢？你说呢？也许你想删除第也许你想删除第m个结点？个结点？ 假设你有一个表假设你有一个表 1->2->3->…->m.现在，怎样找到其中现在，怎样找到其中第第m个结点个结点? 从第一个结点出发，从第一个结点出发，顺着链接到第顺着链接到第m个结点。

个结点§2 表表ADT例子例子 多项式多项式ADT数据对象集数据对象集 : P ( x ) = a1 x e1 +   + an x en ; 可以表示成一可以表示成一个有序对个有序对< ei , ai >的集合，的集合， 其中其中 ai 是系数，是系数，ei 是指数是指数. ei 是非零整数是非零整数.操作集操作集: Finding degree, 找到多项式中找到多项式中最大最大 { ei }. Addition ,两个多项式的加法两个多项式的加法. Subtraction ，，两个多项式的减法两个多项式的减法. Multiplication ，，两个多项式的乘法两个多项式的乘法. Differentiation ，多项式求导，多项式求导.§2 表表ADT【【实现方法实现方法 1】】 typedef struct {int CoeffArray [ MaxDegree + 1 ] ;int HighPower; } *Polynomial ; 我喜欢这种实现方法！这能很容易地我喜欢这种实现方法！这能很容易地实现大多数操作，比如加法和乘法。

实现大多数操作，比如加法和乘法试着对多项式试着对多项式 P1(x) = 10x1000+5x14+1 和和P2(x) = 3x1990 2x1492+11x+5做乘法做乘法--会发生什么会发生什么? 真的吗？假设两个多项式分别具有最大指真的吗？假设两个多项式分别具有最大指数数N1 和和N2 ，，那它们做乘法的时间复杂度是多少？那它们做乘法的时间复杂度是多少？O( N1*N2 )，有什么问题吗，有什么问题吗?§2 表表ADT给定多项式给定多项式:把每一项用一个结点表示：把每一项用一个结点表示：ExponentCoefficientNext  Declaration:typedef struct poly_node *poly_ptr;struct poly_node { int Coefficient ; /* assume coefficients are integers */ int Exponent; poly_ptr Next ;} ;typedef poly_ptr a ; /* nodes sorted by exponent */am 1em 1 a0e0NULL……a【【实现方法实现方法 2】】§2 表表ADT 多重表多重表〖〖例例〗〗 一所有一所有40,000名学生和名学生和2,500门课程的大学需要生成两门课程的大学需要生成两种类型的报告：列出每个班的注册者；列出每个学生注册的班种类型的报告：列出每个班的注册者；列出每个学生注册的班级。

级实现方法实现方法 1】】int Array[40000][2500];§2 表表ADT【【实现方法实现方法 2】】S1S2S3S4S5C1C2C3C4§2 表表ADT3. 链表的游标实现法链表的游标实现法 (不用指针不用指针) 一个链表必须具有这些特征：一个链表必须具有这些特征：a)数据元素存储在一个结构的集合里，每个结构包含数据元素存储在一个结构的集合里，每个结构包含数据数据和和一个指向下一个结构的一个指向下一个结构的指针指针b)一个新结构可以通过调用一个新结构可以通过调用malloc从系统全局内存中生成，以从系统全局内存中生成，以及通过调用及通过调用free释放结构所占内存空间释放结构所占内存空间CursorSpaceElementNext012S-1… …123S-10Note: 游标实现的接口（游标实现的接口（p43，图，图3-28）和指针实现的（）和指针实现的（p34，图，图3-6）是完全相同的是完全相同的§2 表表ADTElementNext25S-20012S-1… …malloc:pp = CursorSpace[ 0 ].Next ;CursorSpace[ 0 ].Next = CursorSpace[ p ].Next ;xElementNext25S-20012S-1… …pfree(p):2CursorSpace[ p ].Next = CursorSpace[ 0 ].Next ;pCursorSpace[ 0 ].Next = p ;Note: 由于不需要内存管理线程，由于不需要内存管理线程，游标实现法通常明显地较快。

游标实现法通常明显地较快具体操作实现在具体操作实现在图图 3.32-3.36给出给出§3 栈栈ADT1. ADT1234566 565 栈栈是一个是一个后进先出后进先出的表，即插入和删的表，即插入和删除操作都只能在除操作都只能在顶端顶端(top)进行数据对象集数据对象集: 一个有一个有0个或多个元素的有个或多个元素的有穷线性表穷线性表操作集操作集: Int IsEmpty( Stack S ); Stack CreateStack( );  DisposeStack( Stack S );  MakeEmpty( Stack S );  Push( ElementType X, Stack S );  ElementType Top( Stack S );  Pop( Stack S ); Note: 在在空栈空栈上进行上进行Pop (或或 Top)操作是一个操作是一个ADT错错误 在在满栈满栈中执行中执行Push 操操作是一个实现错误，而不作是一个实现错误，而不是是ADT错误§3 栈栈ADT2. 栈的实现栈的实现  栈的链表实现栈的链表实现(带头结点带头结点)NULLElement Element Element  Push: TmpCell->Next = S->Next S->Next = TmpCell Top: FirstCell = S->Next S->Next = S->Next->Next free ( FirstCell )return S->Next->Element S ElementTmpCell S  Pop:ElementFirstCell S 太简单了太简单了! 只要使用只要使用另一个栈作为另一个栈作为回收站回收站即可。

即可 但是，调用但是，调用 malloc 和和free 的代价很大的代价很大§3 栈栈ADT  栈的数组实现栈的数组实现struct StackRecord {int Capacity ; /* size of stack */int TopOfStack; /* the top pointer *//* ++ for push, -- for pop, -1 for empty stack */ElementType *Array; /* array for stack elements */ } ; Note:  栈的模型必须很好地栈的模型必须很好地封装封装也就是说，你的代码的也就是说，你的代码的任何部分都没有存取被每个栈蕴含的数组（任何部分都没有存取被每个栈蕴含的数组（Array）） 或或 栈顶（栈顶（TopOfStack）变量的可能）变量的可能 （除了一些栈例（除了一些栈例程）  执行执行Push 或或 Pop (Top)操作之前应进行错误检测操作之前应进行错误检测.相关栈操作的实现细节，请查看图相关栈操作的实现细节，请查看图3.38-3.52§3 栈栈ADT3. 应用应用 平衡符号平衡符号检查圆括号检查圆括号 ( ), 方括号方括号 [ ] 和花括号和花括号 { }是否成对出现（平衡）。

是否成对出现（平衡）Algorithm { Make an empty stack S; while (read in a character c) { if (c is an opening symbol) Push(c, S); else if (c is a closing symbol) { if (S is empty) { ERROR; exit; } else { /* stack is okay */ if (Top(S) doesn’t match c) { ERROR, exit; } else Pop(S); } /* end else-stack is okay */ } /* end else-if-closing symbol */ } /* end while-loop */ if (S is not empty) ERROR;}T( N ) = O ( N ) N 是表达式的长度。

是表达式的长度这是一个这是一个算法§3 栈栈ADT 后缀表达式后缀表达式〖〖例例1〗〗一个一个中缀中缀表达式表达式: a   b   c   d   e 一个一个前缀前缀表达式表达式:     a   b c   d e 一个一个后缀后缀表达式：表达式： a b c     d e    操作数操作数操作符操作符具有最高优先级具有最高优先级的操作符的操作符〖〖例例2〗〗 6 2   3   4 2     = ?8top读取符号读取符号: 6 ( 操作数操作数 )top6读取符号读取符号: 2 ( 操作数操作数 )top2读取符号读取符号:   ( 操作符操作符 )2 6= 3toptop3top读取符号读取符号: 3 ( 操作数操作数 )3top读取符号读取符号:   ( 操作符操作符 )3toptop3 = 00top读取符号读取符号: 4 ( 操作数操作数 )top4读取符号读取符号: 2 ( 操作数操作数 )top2读取符号读取符号:   ( 操作符操作符 )top2top4  = 88top读取符号读取符号:   ( 操作符操作符 )top8top0 = 88top Pop: 8top逆波兰表达式逆波兰表达式T( N ) = O ( N ). 不需要知道任何运算优先级。

不需要知道任何运算优先级§3 栈栈ADT 中缀到后缀的转换中缀到后缀的转换〖〖例例1〗〗 a   b   c   d = ? a b c     d  Note:  在中缀表达式和后缀表达式中，操作数的顺序是在中缀表达式和后缀表达式中，操作数的顺序是不变不变的  具有具有较高较高优先级的操作符出现在优先级的操作符出现在较低较低优先级的操作符前面优先级的操作符前面输出输出:top读取符号读取符号: a (操作数操作数)a 读取符号读取符号:   (加号加号) top读取符号读取符号: b (操作数操作数)b 读取符号读取符号:   (乘号乘号)      ?top 读取符号读取符号: c (操作数操作数)c 读取符号读取符号:   (减号减号)      ?top       ?top top 读取符号读取符号: d (操作数操作数)dtop 别着急，别着急，再看看下面的例子再看看下面的例子…噢！太简单了！噢！太简单了！§3 栈栈ADT(     ?〖〖例例2〗〗 a   ( b   c )   d = ? a b c     d  top输出输出: 读取符号读取符号: a (操作数操作数)a 读取符号读取符号:   (乘号乘号) top 读取符号读取符号: ( (左括号左括号)    ( ?top( 读取符号读取符号: b (操作数操作数)b 读取符号读取符号:   (加号加号)NO?!top+ 读取符号读取符号: c (操作数操作数)c 读取符号读取符号: ) (右括号右括号)top top 读取符号读取符号:   (除号除号)      ?top top  读取符号读取符号: d (操作数操作数)dtop T( N ) = O ( N ) §3 栈栈ADT解决方法解决方法:  当当 ( 在栈里时，只有遇到在栈里时，只有遇到 ) 才会弹出。

才会弹出 当当 ( 没有进栈前，它的优先级是没有进栈前，它的优先级是最高最高的；但进栈后，的；但进栈后，它的优先级被视为它的优先级被视为最低最低我们可以定义符号的我们可以定义符号的栈内栈内优先级优先级和和栈外优先级栈外优先级，， 比较时根据不同情况使用对比较时根据不同情况使用对应优先级应优先级Note: a – b – c 将转换成将转换成a b – c –但是, 2^2^3 ( ) 必须转换为必须转换为2 2 3 ^ ^, 而不是而不是 2 2 ^ 3 ^ 因为幂因为幂运算是运算是从右向左从右向左结合的递归总能够被彻底除去递归总能够被彻底除去非递归程序通常比等价的递归程序要非递归程序通常比等价的递归程序要快快，，但是递归程序通常更但是递归程序通常更简单而易于理解简单而易于理解§3 栈栈ADT 函数调用函数调用-- 系统栈系统栈Return AddressStack Frames pLocal VariablesReturn Addresss ps pOld Frame Pointers pf pf ps pf pvoid PrintList ( List L ){ if ( L != NULL ) { PrintElement ( L->Element ); PrintList( L->next ); }} /* 一个递归的坏例子一个递归的坏例子*/ 如果如果L包含包含1,000,000 个个元素，会发生什么情况？元素，会发生什么情况？ 有什么问题呢？有什么问题呢？尾递归尾递归void PrintList ( List L ){top: if ( L != NULL ) { PrintElement ( L->Element ); L = L->next; goto top；； }} /* 编译器可以自动去除尾递归编译器可以自动去除尾递归 */6/9 如果如果1,000,000个数据还不足个数据还不足使程序崩溃，那么可用使程序崩溃，那么可用更大的个数代替它。

更大的个数代替它§4 队列队列ADT1. ADT队列队列是一个先进先出是一个先进先出(First-In-First-Out，，FIFO)表表, 插入在一端进行而删除在另一端进行插入在一端进行而删除在另一端进行23411122数据对象集数据对象集: 一个有一个有0个或多个元素的有个或多个元素的有穷线性表穷线性表操作集操作集: int IsEmpty( Queue Q ); Queue CreateQueue( );  DisposeQueue( Queue Q );  MakeEmpty( Queue Q );  Enqueue( ElementType X, Queue Q );  ElementType Front( Queue Q );  Dequeue( Queue Q ); Job 32. 队列的数组实现队列的数组实现 (链表实现是直接的，留作练习链表实现是直接的，留作练习)struct QueueRecord {int Capacity ; /* max size of queue */int Front; /* the front pointer */int Rear; /* the rear pointer */int Size; /* Optional - the current size of queue */ElementType *Array; /* array for queue elements */ } ; 〖〖例例〗〗 操作系统中的作业调度操作系统中的作业调度RearFrontEnqueue Job 1Enqueue Job 2Enqueue Job 3Dequeue Job 1Enqueue Job 4Enqueue Job 5Enqueue Job 6Dequeue Job 2Enqueue Job 7Enqueue Job 8Job 1Job 2RearRearRearFrontRearJob 4RearJob 5RearJob 6FrontRearJob 70123456§4 队列队列ADT你有更好的办法吗你有更好的办法吗?当然有！当然有！§4 队列队列ADT[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ]Enqueue Job 1Enqueue Job 2Enqueue Job 3Dequeue Job 1Enqueue Job 4Enqueue Job 5Enqueue Job 6Enqueue Job 7Job1Job2Job3Job4Job5Job6队列已满队列已满问题问题:为何队列为何队列中还剩一个中还剩一个空位时，空位时，就已报就已报“队列满队列满”？？循环队列循环队列循环队列循环队列: :RearFrontRearRearFrontRearFrontRearRearRearNote: 添加一个添加一个 Size 域可以避免为了区分域可以避免为了区分“队列空队列空”和和“队队列满列满”状态而浪费一个空位置。

状态而浪费一个空位置你还有其他想法吗？你还有其他想法吗？§线性数据结构线性数据结构§线性表线性表§数组实现数组实现§链表实现链表实现§受限的线性表受限的线性表§栈（栈（LIFO））§实现实现§应用应用§队列（队列（FIFO））§实现实现§应用应用§查找操作如何实现？查找操作如何实现？§线性结构上查找操作效率太低线性结构上查找操作效率太低§非线性关系怎么表示？非线性关系怎么表示？§树树。