《湘潭大学-数据结构-课件.ppt》由会员分享，可在线阅读，更多相关《湘潭大学-数据结构-课件.ppt（33页珍藏版）》请在三一文库上搜索。
1、CHAPTER 3 表、栈和队列,1 抽象数据类型 (ADT),【定义】数据类型= 数据对象 操作 例 int = 0, 1, 2, , INT_MAX, INT_MIN , , , , , ,【定义】抽象数据类型 (ADT)：“抽象”的意思，是指我们描述数据类型的方法是不依赖于具体实现的，即数据对象集和操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。简而言之，抽象数据类型只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。,对于每种ADT并不存在什么法则来规定必须要有哪些操作； 错误处理和结构调整一般也取决于程序的设计者。,类型名
2、称：线性表（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
3、 )：已知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 DataM
4、AXSIZE; int Last; List;,List L, *PtrL;,访问下标为 i 的元素：L.Datai 或 PtrL-Datai,线性表的长度：L.Last+1 或 PtrL-Last+1,插入（第 i (1in+1)个位置上插入一个值为X的新元素),X,删除（删除表的第 i (1in)个位置上的元素), 必须首先估计MaxSize ., Find_Kth 仅需 O(1) 时间., Insertion 和 Deletion 在一般情况下需要移动大量元素，需花费O(N) 时间.,Find X需要多少时间？,不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间
5、的逻辑关系。因此对线性表的插入、删除不需要移动数据元素，只需要修改“链”。,2 表ADT,2. 链表,初始化: typedef struct list_node *list_ptr; typedef struct list_node char data 4 ; list_ptr next ; ; list_ptr ptr ;,NULL,连接ZHAO 和 QIAN两个结点: list_ptr N1, N2 ; N1 = (list_ptr)malloc(sizeof(struct list_node); N2 = (list_ptr)malloc(sizeof(struct list_node)
6、; N1-data = ZHAO ; N2-data = QIAN ; N1-next = N2 ; N2-next = NULL ; ptr = N1 ;,连接操作的次序不同， 结点的顺序也会发生变化,2 表ADT,插入, temp-next = node-next, node-next = temp,问题1: 如果这两个步骤的顺序更换，结果会如何？,问题2: 怎样插入一个新的首结点？, 花费 O(1) 时间.,2 表ADT,删除, pre-next = node-next, free ( node ),问题: 怎样从表中删除第一个结点？,解决方法: 在表中添加“哑”的头节点。, 花费 O(
7、1) 时间.,a1,.,然后假设你又需要找到 它的前驱结点m 1?,2 表ADT,双向循环链表,typedef struct node *node_ptr ; typedef struct node node_ptr llink; element item; node_ptr rlink; ;,ptr = ptr-llink-rlink = ptr-rlink-llink,呃 . 那么我将再次从第一个结点 出发但是，为什么我会想要 找到前驱结点呢？,一个带头节点的双向循环链表：,一个带头节点的 空双向循环链表:,有了前面的那些实现还不够吗? 为什么我们还需要双向链表？,你说呢？ 也许你想删除第
8、m个结点？,假设你有一个表 1-2-3-m. 现在，怎样找到其中 第m个结点?,从第一个结点出发， 顺着链接到第m个结点。,2 表ADT,例子, 多项式ADT,数据对象集 : P ( x ) = a1 x e1 + + an x en ; 可以表示成一个有序对的集合， 其中 ai 是系数，ei 是指数. ei 是非零整数.,操作集: Finding degree, 找到多项式中最大 ei . Addition ,两个多项式的加法. Subtraction ，两个多项式的减法. Multiplication ，两个多项式的乘法. Differentiation ，多项式求导.,2 表ADT,【实
9、现方法 1】 typedef struct int CoeffArray MaxDegree + 1 ; int HighPower; *Polynomial ;,我喜欢这种实现方法！这能很容易地 实现大多数操作，比如加法和乘法。,试着对多项式 P1(x) = 10x1000+5x14+1 和 P2(x) = 3x19902x1492+11x+5做乘法 -会发生什么?,真的吗？假设两个多项式分别具有最大指 数N1 和N2 ，那它们做乘法的时间复杂度是多少？,O( N1*N2 )，有什么问题吗?,2 表ADT,给定多项式:,Declaration: typedef struct poly_nod
10、e *poly_ptr; struct poly_node int Coefficient ; /* assume coefficients are integers */ int Exponent; poly_ptr Next ; ; typedef poly_ptr a ; /* nodes sorted by exponent */,【实现方法 2】,2 表ADT, 多重表,例 一所有40,000名学生和2,500门课程的大学需要生成两种类型的报告：列出每个班的注册者；列出每个学生注册的班级。,【实现方法 1】 int Array400002500;,2 表ADT,【实现方法 2】,2
11、表ADT,3. 链表的游标实现法 (不用指针), 一个链表必须具有这些特征：,数据元素存储在一个结构的集合里，每个结构包含数据和一个指向下一个结构的指针。 一个新结构可以通过调用malloc从系统全局内存中生成，以及通过调用free释放结构所占内存空间。,Note: 游标实现的接口（p43，图3-28）和指针实现的（p34，图3-6）是完全相同的。,2 表ADT,malloc:,p = CursorSpace 0 .Next ;,CursorSpace 0 .Next = CursorSpace p .Next ;,x,free(p):,2,CursorSpace p .Next = Curs
12、orSpace 0 .Next ;,CursorSpace 0 .Next = p ;,Note: 由于不需要内存管理线程，游标实现法通常明显地较快。,具体操作实现在 图 3.32-3.36给出,3 栈ADT,1. ADT,1,2,3,4,5,6,6,5,6,5,栈是一个后进先出的表，即插入和删除操作都只能在顶端(top)进行。,数据对象集: 一个有0个或多个元素的有穷线性表。,操作集: Int IsEmpty( Stack S ); Stack CreateStack( ); DisposeStack( Stack S ); MakeEmpty( Stack S ); Push( Eleme
13、ntType X, Stack S ); ElementType Top( Stack S ); Pop( Stack S );,Note: 在空栈上进行Pop (或 Top)操作是一个ADT错误。 在满栈中执行Push 操作是一个实现错误，而不是ADT错误。,3 栈ADT,2. 栈的实现, 栈的链表实现(带头结点), Push:, TmpCell-Next = S-Next, S-Next = TmpCell, Top:, FirstCell = S-Next, S-Next = S-Next-Next, free ( FirstCell ),return S-Next-Element, P
14、op:,Element,太简单了! 只要使用 另一个栈作为回收站即可。,但是，调用 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: 栈的模型必须很好地封装。也就是说，你的代码的任何
15、部分都没有存取被每个栈蕴含的数组（Array） 或 栈顶（TopOfStack）变量的可能 （除了一些栈例程）。 执行Push 或 Pop (Top)操作之前应进行错误检测.,相关栈操作的实现细节，请查看图3.38-3.52,3 栈ADT,3. 应用, 平衡符号,检查圆括号 ( ), 方括号 和花括号 是否成对出现（平衡）。,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) i
16、f (S is empty) ERROR; exit; else /* stack is okay */ if (Top(S) doesnt 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
17、 b c d e 一个后缀表达式： a b c d e ,操作数,操作符,具有最高优先级的操作符,例2 6 2 3 4 2 = ?,8,读取符号: 6 ( 操作数 ),6,读取符号: 2 ( 操作数 ),2,读取符号: ( 操作符 ),2,6,= 3,3,读取符号: 3 ( 操作数 ),3,读取符号: ( 操作符 ),3,3,= 0,0,读取符号: 4 ( 操作数 ),4,读取符号: 2 ( 操作数 ),2,读取符号: ( 操作符 ),2,4,= 8,8,读取符号: ( 操作符 ),8,0,= 8,8,Pop: 8,逆波兰表达式,T( N ) = O ( N ). 不需要知道任何运算优先级。,
18、3 栈ADT, 中缀到后缀的转换,例1 a b c d = ?,a b c d ,Note: 在中缀表达式和后缀表达式中，操作数的顺序是不变的。 具有较高优先级的操作符出现在较低优先级的操作符前面。,输出:,读取符号: a (操作数),a,读取符号: (加号),读取符号: b (操作数),b,读取符号: (乘号), ?,读取符号: c (操作数),c,读取符号: (减号), ?, ?,读取符号: d (操作数),d,别着急， 再看看下面的例子,噢！太简单了！,3 栈ADT,( ?,例2 a ( b c ) d = ?,a b c d ,输出:,读取符号: a (操作数),a,读取符号: (乘号
19、),读取符号: ( (左括号), ( ?,(,读取符号: b (操作数),b,读取符号: (加号),NO?!,+,读取符号: c (操作数),c,读取符号: ) (右括号),读取符号: (除号), ?,读取符号: d (操作数),d,T( N ) = O ( N ),3 栈ADT,解决方法: 当 ( 在栈里时，只有遇到 ) 才会弹出。 当 ( 没有进栈前，它的优先级是最高的；但进栈后，它的优先级被视为最低。我们可以定义符号的栈内优先级和栈外优先级， 比较时根据不同情况使用对应优先级。,Note: a b c 将转换成a b c 。但是, 223 ( ) 必须转换为2 2 3 , 而不是 2 2
20、 3 。 因为幂运算是从右向左结合的。,递归总能够被彻底除去。 非递归程序通常比等价的递归程序要快， 但是递归程序通常更简单而易于理解。,3 栈ADT, 函数调用,- 系统栈,Return Address,Stack Frame,Local Variables,Return Address,Old Frame Pointer,void PrintList ( List L ) if ( L != NULL ) PrintElement ( L-Element ); PrintList( L-next ); /* 一个递归的坏例子*/,如果L包含1,000,000 个 元素，会发生什么情况？,有
21、什么问题呢？,尾递归,void PrintList ( List L ) top: if ( L != NULL ) PrintElement ( L-Element ); L = L-next; goto top； /* 编译器可以自动去除尾递归 */,6/9,如果1,000,000个数据还不足 使程序崩溃，那么可用 更大的个数代替它。,4 队列ADT,1. ADT,队列是一个先进先出(First-In-First-Out，FIFO)表, 插入在一端进行而删除在另一端进行。,2,3,4,1,1,1,2,2,数据对象集: 一个有0个或多个元素的有穷线性表。,操作集: int IsEmpty(
22、Queue Q ); Queue CreateQueue( ); DisposeQueue( Queue Q ); MakeEmpty( Queue Q ); Enqueue( ElementType X, Queue Q ); ElementType Front( Queue Q ); Dequeue( Queue Q );,Job 3,2. 队列的数组实现 (链表实现是直接的，留作练习),struct QueueRecord int Capacity ; /* max size of queue */ int Front; /* the front pointer */ int Rear;
23、 /* the rear pointer */ int Size; /* Optional - the current size of queue */ ElementType *Array; /* array for queue elements */ ;,例 操作系统中的作业调度,Enqueue Job 1,Enqueue Job 2,Enqueue Job 3,Dequeue Job 1,Enqueue Job 4,Enqueue Job 5,Enqueue Job 6,Dequeue Job 2,Enqueue Job 7,Enqueue Job 8,Job 1,Job 2,Rear,
24、Rear,Front,Job 4,Job 5,Job 6,Job 7,4 队列ADT,你有更好的办法吗?,当然有！,4 队列ADT,Enqueue Job 1,Enqueue Job 2,Enqueue Job 3,Dequeue Job 1,Enqueue Job 4,Enqueue Job 5,Enqueue Job 6,Enqueue Job 7,Job 1,Job 2,Job 3,Job 4,Job 5,Job 6,队列已满,问题: 为何队列 中还剩一个 空位时， 就已报 “队列满”？,循环队列:,Rear,Rear,Front,Rear,Rear,Rear,Note: 添加一个 Size 域可以避免为了区分“队列空”和“队列满”状态而浪费一个空位置。 你还有其他想法吗？,Review,线性数据结构 线性表 数组实现 链表实现 受限的线性表 栈（LIFO） 实现 应用 队列（FIFO） 实现 应用,Preview,查找操作如何实现？ 线性结构上查找操作效率太低 非线性关系怎么表示？ 树,