第12章_线性结构.ppt

数据结构概述 数据结构包含内容之一：数据的逻辑结构 数据结构包含内容之一：数据的逻辑结构 数据结构包含内容之一：数据的逻辑结构 数据结构包含内容之二：数据的存储结构 数据结构包含内容之三：数据的运算 算法 算法 线性表 线性表的顺序存储结构（顺序表） 顺序表模板类的定义 顺序表类的构造函数 顺序表类的Find()函数 顺序表类的Search()函数 顺序表类的Insert()函数 顺序表类的Delete()函数 顺序表类的output()函数 顺序表类的友元函数 线性表的链接存储结构（链表） 带头结点的单链表 单链表模板类的定义 单链表类的构造函数 单链表类的析构函数 单链表类的Find()函数 单链表类的Search()函数 顺序表类的Insert()函数 单链表类的Delete()函数 单链表类的ClearList()函数 单链表类的output()函数 单链表类的友元函数 其他形式的链表（1） 其他形式的链表（2） template typename T ChainT::Chain(){ head=new NodeT; head-next=NULL; length=0; } 12.2 线性表 函数的功能是：建立一个空表。 template typename T ChainT::~Chain(){ ClearList(); delete head; } 12.2 线性表 函数的功能是：释放链表空间。 函数的功能是：把下标为i的元素取至x。 12.2 线性表 函数的功能是：返回x在表中的下标 。 12.2 线性表 函数的功能是：在下标i处插入元素x 。 12.2 线性表 ai-1 ai ① p ② q ③ x ④ ⑤ ? 点击鼠标演示 函数的功能是：返回下标为i的元素至x，并删除之 。 12.2 线性表 ? 点击鼠标演示 ai-1 ai ai+1 ① p ② q ③ ④ 函数的功能是：把表清空，即将单链表置为初始状态 。 12.2 线性表 函数的功能是：输出表中所有元素的值 。 12.2 线性表 template typename T void ChainT::output(ostream out)const{ NodeT *p=head-next; while(p!=NULL){ outp-data ; p=p-next; } } 函数的功能是：为方便输出，重载“” 。 12.2 线性表 template typename T ostream operator(ostream out,const ChainT x){ x.output(out); return out; } 例：将一字符存入单链表，删除其中所有的数字字符。 12.2 线性表 程序的输出结果是： 1C++ 2FORTRAN 3PASCAL 4BASIC C++ FORTRAN PASCAL BASIC 单循环链表 12.2 线性表 设置尾指针的单循环链表 双链表 12.2 线性表 双循环链表 栈的概念（1） 1.栈的定义 2. 栈的特点 栈中元素的变化是按后进先出原则进行，因此又称栈为后进先出（Last In First Out，简称LIFO）表 。 栈是限定只能在表的一端进行插入和删除运算的线性表。 12.3 栈 3.栈的术语 4. 栈的基本运算 ? 栈顶：允许进行插入和删除的一端。 ? 栈底：与栈顶相对的一端。 ? 入栈：向栈顶插入一个元素。 ? 出栈：从栈顶插入一个元素。 入栈、出栈、判栈空、取栈顶元素、置栈空 栈的概念（2） 12.3 栈 讨论： 栈的入栈和出栈操作可以穿插进行，所以对应于相同的入栈序列其出栈序列可以有多种。 c、a、b 、e 、f 、d 和 e、f、d、c 、b、a 等均为不可能出现的出栈序列。 栈的概念（3） 12.3 栈 以顺序方式存储的栈称为顺序栈。 顺序栈可以用一维数组实现。 需要一个整型变量top指示当前栈顶位置 。 顺序栈（1） 12.3 栈 顺序栈（2） 12.3 栈 顺序栈模板类的定义与实现： 12.3 栈 例：编写将十进制整数转换为B（2≤B≤9)进制整数的程序。 (设已将顺序栈类的定义和实现放在文件seqstack.h中） ? 当使用两个栈时，可让它们共享一个一维数组空间，以达到节省存储空间和降低上溢发生频率的目的。 顺序栈（3） 12.3 栈 以链接方式存储的栈称为链式栈。 可以用不带头结点的单链表实现链式栈。 用头指针top指示当前栈顶位置 。 链式栈（1） 12.3 栈 例