第二章线性表栈和队列.ppt
《第二章线性表栈和队列.ppt》由会员分享,可在线阅读,更多相关《第二章线性表栈和队列.ppt(131页珍藏版)》请在三一文库上搜索。
1、第二章 线性表、栈和队列,大纲,2.1 线性表(linear list) 2.1.1 线性表的抽象数据类型 2.1.2 线性表的存储结构 2.1.3 线性表运算分类 2.2 顺序表向量(sequential listvector ) 2.2.1 向量的类定义(type definition) 2.2.2 向量的运算,2.5 栈 2.5.1 顺序栈 2.5.2 链式栈 2.5.3 顺序栈与链式栈的比较 2.5.4 栈的应用后缀表达式求值 2.5.4 递归的实现 2.6 队列 2.6.1 顺序队列 2.6.2 链式队列 2.2.3 顺序队列与链式队列的比较,大纲(续),2.3 链表(linked
2、list) 2.3.1单 链 表(singly linked list) 2.3.2 双 链 表(double linked list) 2.3.3 循 环 链 表(circularly linked list) 2.4 线性表实现方法的比较,线性结构分类,直接访问型( direct access ) 顺序访问型(sequential access) 目录索引型(directory access),线性结构分类,2.1 线性表(linear list),2.1.1 线性表的抽象数据类型 2.1.2 线性表的存储结构 2.1.3 线性表运算分类,线性表的抽象数据类型,线性表定义: 由结点集N,以
3、及定义在结点集N上的线性关系r所组成的线性结构。这些结点称为线性表的元素。,线性表的性质,线性表(N , r): (a)结点集N中有一个唯一的开始结点,它没有前驱,但有一个唯一的后继; (b)对于有限集N, 它存在一个唯一的终止结点,该结点有一个唯一的前驱而没有后继; (c)其它的结点皆称为内部结点,每一个内部结点既有一个唯一的前驱,也有一个唯一的后继;,线性表的性质(续),线性表(N , r): (d)线性表所包含的结点个数称为线性表的长度,它是线性表的一个重要参数;长度为0的线性表称为空表; (e)线性表的关系r,简称前驱关系,应具有反对称性和传递性。,线性表的抽象数据类型,取值空间 运算
4、集,线性表类模板,template class list /线性表类模板list,模板参数ELEM /1. 线性表的取值类型: /元素的类型为ELEM,是本list类模板的模板 /参数ELEM。 /本线性表用的最大长度为Max_length;,/2. 名字空间,使用变量访问线性表的方法: /用curr +或 curr- /控制线性表游标curr的前后游走。 / 用公共变 /量curr_len指示线性表的尾部,并导出表的当 /前长度,等。 / 3. 运算集:请参看下面的成员函数,private: /私有变量,线性表的存储空间 /Max_length用于规定所存储线性表的最大长度 public:
5、int curr_len; /公共变量,该线性表的当前长度 int curr; /公共变量,该线性表的当前指针,游标 list(); / constructor算子,创建一个空的新线性表,/destructor算子, /从计算机存储空间删去整个线性表 list(); /将该线性表的全部元素清除,成为空表 void clear() ; / 尾附算子,在表的尾部添加一个新元素,参 /数value作为元素内容(数据类型为 /ELEM),表的长度加1 void append(ELEM value) ;,/插入算子,整数i指出第i号位置,参数value /作为元素内容(数据类型为T),该位置上 /插入一
6、个新结点,表的长度加1。第i号位置后 /的元素后移 void insert(int i, ELEM value) ; /删除算子,删去第i号元素,表的长度减1,其 /后元素前移 void remove(int i); /读取,返回第i个元素的值 ELEM fetch(int i); ,2.1.2 线性表的存储结构,定长的一维数组结构 又称向量型的顺序存储结构 变长的线性表存储结构 链接式存储结构 串结构、动态数组、以及顺序文件,2.1.3 线性表运算分类,创建线性表的一个实例list(-) 线性表消亡(即析构函数)list() 获取有关当前线性表的信息 访问线性表并改变线性表的内容或结构 线性
7、表的辅助性管理操作,2.2 顺序表向量(sequential listvector),采用定长的一维数组存储结构 主要特性: 元素的类型相同 元素顺序地存储在连续存储空间中,每一个元素唯一的索引值 使用常数作为向量长度,2.2.1 向量的类定义(type definition),数组存储 读写其元素很方便 ,通过下标即可指定位置,顺序表类定义,enum Boolean False,True; /假定最大长度为100 /并假定顺序表的元素类型T为ELEM const int Max_length = 100; class list /顺序表,向量 private : /私有变量,顺序表实例的最大
8、长度 int msize; / 私有变量,顺序表实例的当前长度 int curr_len;,/私有变量,存储顺序表实例的向量 ELEM* nodelist; public: /以下列出成员函数(顺序表的算子集) /当前下标,顺序表的公共变量 int curr; / constructor算子,创建一个新的顺序表, /其实参是表实例的最大长度。 list(const int size) ;,/destructor算子,用于将该表实例删去 list(); /将顺序表存储的内容清除,成为空表 void clear(); /将当前下标curr赋值为第一个元素的位置 void setFirst(); /
9、将当前下标curr下移一格,即curr+1 void next(); /若当前下标curr位置有值时,返回True Boolean isInList();,/在表尾增添一个新元素,顺序表的实际长度加1 void append(const ELEM item); /在当前下标curr位置插入元素新值。 void insert(const ELEM item); /当前下标curr位置的元素值作为返回值,并删去该元素 ELEM remove(); Boolean isEmpty(); /当线性表为空时,返回True ELEM currValue(); /返回当前curr位置的元素值。 int le
10、ngth(); /返回此顺序表的当前实际长度 void prev(); /将当前下标curr上移一格,即curr-1 ,2.2.2 向量的运算,插入元素运算 void insert( item) 删除元素运算 ELEM remove( ),插入算法,/*(设元素的类型为ELEM,nodelist是存储顺序表的向量,msize是此向量的最大长度,curr_len是此向量的当前长度,curr为此向量当前下标)*/ include viod insert(ELEM item) /需要检查当前长度不能等于msize,当前游标指针 /curr不能小于0,也不能大于当前长度,assert(curr_len
11、 = 0) ,算法执行时间,元素总个数为k,各个位置插入的概率相等为p1/k 平均移动元素次数为 总时间开销估计为O(k),删除算法,/*(设元素的类型为ELEM,nodelist是存储顺序表的向量,msize是此向量的最大长度,curr_len是此向量的当前长度,curr为此向量当前下标)*/ /返回curr所指的元素值,并从表中删去此元素 ELEM remove() /首先需要检验当前长度不能等于0, 当前指针 /curr不能小于0,不能等于curr_len,assert( (curr_len != 0) /返回值是进入时的旧值 ,算法时间代价,与插入操作相似,O(k) 顺序表存取元素方便
12、,时间代价为O(1) 但插入、删除操作则付出时间代价O(k),2.3 链表(linked list),单链表 双链表 循环链表,2.3.1 单链表,通过指针把它的一串存储结点链接成一个链 存储结点由两部分组成: data字段 link字段,单链表的存储结构,单链表的结点类型以及变量first说明,struct ListNode ELEM data; ListNode * link; ; typedef ListNode * ListPtr; ListPtr first;,查找单链表中第i个结点算法,/函数返回值是找到的结点指针 ListNode * FindIndex(const int i)
13、 / first表首变量,可能指向空表 if( i = -1) return first; *p=first-link; / p没有定义! int j=0;,while( p !=NULL ,单链表插入算法,/ 插入数据内容为value的新结点,为第i个结点。 ListNode * Insert(ELEM value, int i) ListNode *p,*q; q = new ListNode; p = FindIndex(i-1); if(p = NULL ) return NULL;,q-link = p-link; q-data = value; p-link = q; if(q-l
14、ink = NULL ) last=q; return q; ,插入过程,单链表删除算法,/删除由参数link所指定的结点 void RemoveAfter(ListNode * link) ListNode *newlink=link; if(link!=NULL) link=link-link; delete newlink; ,删除过程,求长度算法,int Length() ListNode *p=first-link; int count=0; while(p!=NULL) p=p-link; count+; return count; ,2.3.2 双链表 (double linke
15、d list),单链表的主要不足之处是: link字段仅仅指向后继结点,不能有效地找到前驱 双链表弥补了上述不足之处 增加一个指向前驱的指针,双链表示意图,双链表及其结点类型的说明,struct DblListNode ELEM data; DblListNode *rlink; DblListNode *llink; ; struct DoubleList DblListNode * first,*last; ;,双链表删除结点,如果要删除指针变量p所指的结点,只需修改该结点前驱的rlink字段和该结点后继的llink字段,即 p-llink-rlink=p-rlink; p-rlink-l
16、link=p-llink; 然后把变量p变空,再把p所指空间释放即可。 p-rlink=NULL; p-llink=NULL; delete p;,删除过程,双链表的插入,如果要在p所指结点后插入一个新结点,首先执行new q开辟结点空间。然后,让该新结点的rlink填入p所指的后继地址,新结点的llink填入p所指结点的后继的llink字段,即 new q; q-rlink=p-rlink; q-llink=p-rlink-llink; 此外,要把新结点的地址填入原p所指结点的rlink字段,而且新结点后继的llink字段也应该回指新结点。 p-rlink=q; q-rlink-llink=
17、q;,插入过程,2.3.3 循环链表 (circularly linked list),将单链表或者双链表的头尾结点链接起来,就是一个循环链表。 不增加额外存储花销,却给不少操作带来了方便 从循环表中任一结点出发,都能访问到表中其他结点。,几种主要链表比较,2.4 线性表实现方法的比较,顺序表的主要优点 没用使用指针,不用花费附加开销 线性表元素的读访问非常简洁便利 链表的主要优点 无需事先了解线性表的长度 允许线性表的长度有很大变化 能够适应经常插入删除内部元素的情况,应用场合的选择,不要使用顺序表的场合 经常插入删除时,不宜使用顺序表 线性表的最大长度也是一个重要因素 不要使用链表的场合
18、当读操作比插入删除操作频率大时,不应选择链表 当指针的存储开销,和整个结点内容所占空间相比其比例较大时,应该慎重选择,2.5 栈(stack),一种限制访问端口的线性表,后进先出表(LIFO表,Least-In First-Out)。也称为“下推表”。 元素插入称为栈的压入,push,删除称为栈的弹出,pop 表首被称为栈顶,而栈的另一端则叫做栈底 每次取出(并被删除)的总是刚压进的元素,而最先压入的元素则被放在栈的底部,栈的抽象数据类型,enum Boolean True,False template class Stack / 栈的元素类型为ELEM /栈的存储:可以用顺序表或单链表存储,
19、长 /度为定长 /栈的运算集为: stack(int s); /创建栈的实例 stack(); /该实例消亡,void Push(ELEM item); /item压入栈顶 ELEM Pop(); /返回栈顶内容,并从栈顶弹出 ELEM GetTop(); /返回栈顶内容,但不弹出 void MakeEmpty(); /变为空栈 Boolean IsEmpty(); /返回真,若栈已空 Boolean IsFull(); /返回真,若栈已满 ;,栈的实现,顺序栈 使用向量实现 链式栈 用单链表方式存储,其中指针的方向是从栈顶向下链接,2.5.1 顺序栈,/设栈的类定义为stack,栈元素类型为
20、浮点float类型 enum Boolean True,False #include /引入逻辑断言语句 class Stack public: float *ElmList; /存放数据元素的指针变量,int top;/该变量指示栈顶在该向量的位置,下标值 /当新元素压入或栈内容弹出,top值随之增减 int maxsize; /栈的最大长度 /构建函数,创建栈的实例,向量空间长度为size Stack(int size); ;,顺序栈,按压入先后次序,最先压入的元素编号为1,然后依次为2,3,4,顺序栈的创建,/栈实例的创建,指定最大长度10 Stack:Stack(int size=10
21、) maxsize=size; /开辟向量存储空间 ElmList=new floatmaxsize; /判断new命令成功否,否则断言程序异常 assert(ElmList!=NULL); top=-1; / 表示栈空 ,压入栈顶,void Stack:Push(float item) /判非栈满,否则栈溢出,退出运行 assert(!IsFull(); top+; /栈顶 ElmListtop=item; ,从栈顶弹出,float Stack:Pop() /判栈非空,否则断言栈空异常,退/出运行 assert(!IsEmpty(); return ElmListtop-; ,从栈顶读取,但
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 线性 队列
链接地址:https://www.31doc.com/p-3119963.html