C++程序设计与数据结构基础 第9章_线性结构.ppt

单链表类的Insert()函数 函数的功能是：在下标i处插入元素x 。 9.2 线性表 ai-1 ai ① p ② q ③ x ④ ⑤ ? 点击鼠标演示 单链表类的Delete()函数 函数的功能是：返回下标为i的元素至x，并删除之 。 9.2 线性表 ? 点击鼠标演示 ai-1 ai ai+1 ① p ② q ③ ④ 单链表类的ClearList()函数 函数的功能是：把表清空，即将单链表置为初始状态 。 9.2 线性表 单链表类的output()函数 函数的功能是：输出表中所有元素的值 。 9.2 线性表 void Chain::output(ostream out)const{ Node *p=head-next; while(p!=0){ outp-data ; p=p-next; } } 单链表类的友元函数 函数的功能是：为方便输出，重载“” 。 9.2 线性表 ostream operator(ostream out,const Chain x){ x.output(out); return out; } 例：将一字符串存入单链表，删除其中所有的数字字符。 9.2 线性表 程序的输出结果是： 1C++ 2FORTRAN 3PASCAL 4BASIC C++ FORTRAN PASCAL BASIC 其他形式的链表（1） 单循环链表 9.2 线性表 设置尾指针的单循环链表 其他形式的链表（2） 双链表 9.2 线性表 双循环链表 9.2 线性表 ? 优点： 1）插入和删除运算的实现效率比较高。 2）在存储长度变化比较大的线性表时适应性较好。 讨论： 以链接方式存储线性表的优缺点 ? 缺点： 1）需要增加额外的空间表示元素之间的逻辑关系。 2）不能实现对线性表中元素的随机存取。 栈的概念（1） 1.栈的定义 2. 栈的特点 栈中元素的变化是按后进先出原则进行，因此又称栈为后进先出（Last In First Out，简称LIFO）表 。 栈是限定只能在表的一端进行插入和删除运算的线性表。 9.3 栈 3.栈的术语 4. 栈的基本运算 ? 栈顶：允许进行插入和删除的一端。 ? 栈底：与栈顶相对的一端。 ? 入栈：向栈顶插入一个元素。 ? 出栈：从栈顶删除一个元素。 入栈、出栈、判栈空、取栈顶元素、置栈空 栈的概念（2） 9.3 栈 讨论： 栈的入栈和出栈操作可以穿插进行，所以对应于相同的入栈序列其出栈序列可以有多种。 例：设A , B , C 三个元素依次进栈，则可能的出栈序列有： 栈的概念（3） 12.3 栈 C , B , A B , C , A B , A , C A , C , B A , B , C 不可能的出栈序列： C , A , B 以顺序方式存储的栈称为顺序栈。 顺序栈可以用一维数组实现。 需要一个整型变量top指示当前栈顶位置 。 顺序栈（1） 12.3 栈 A B C D E 0 1 2 3 4 5 6 7 top 栈底元素 当前值为4 顺序栈（2） 9.3 栈 字符顺序栈类的定义： 9.3 栈 例：将一个非负的十进制整数转换为Ｂ（２≤Ｂ≤16）进制数输出。(设已将顺序栈类的定义和实现放在文件seqstack.h中） 以链接方式存储的栈称为链式栈。 可以用不带头结点的单链表实现链式栈。 用头指针top指示当前栈顶位置 。 链式栈（1） 9.3 栈 例：链式栈示意图（设栈中有依次进入的A、B、C 三个元素）。 C B A top 栈底元素 队列的概念（1） 1.队列的定义 2. 队列的特点 队中列元素的变化是按先进先出原则进行，因此又称队为先进先出（First In First Out，简称FIFO）表 。 队列是限定只能在表的一端进行插入，而在另一端进行删除的线性表。 9.4 队列 3.队列的术语 4. 队列的基本运算 ? 队头：允许进行删除的一端。 ? 队尾：允许进行插入的一端。 ? 入队：向队尾插入一个元素。 ? 出队：从队头删除一个元素。 入队、出队、判队空、取队头元素、置队空 队列的概念（2） 9.4 队列 以顺序方式存储的队称为顺序队。可以用一维数组实现。 设置整型变量 front（队头指示器）指示当前队头，设置整 型变量 rear（队尾指示器）指示将要入队元素所在