第三章栈和队列栈.ppt

文档介绍：1、=->next=->next=!=NULL2、将图中S结点加到P所指结点之后,其语句是:(浙江大学)->next=p+1p->next=sB.(*p).next=s(*s).next=(*p).->next=p->nextp->next=s->->next=p->nextp->next=,错误的是哪一个?(北方交通大学)线性表采用顺序储存,必须占用一片连续的存储单元线性表采用顺序储存,便于进行插入和删除操作线性表采用链式储存,不必占用一片连续的储存单元线性表采用链式储存,,这样采用()储存方式最节省时间。(哈尔滨工业大学),->next==->next==L本章小结线性表的顺序表示与链式表示:从空间方面看:顺序存储空间是静态分配的,程序运行之前必须明确规定存储元素得多少,过大造成空间的浪费,过小会溢出。链式存储的空间是动态分配的,利用率高,但是链表中每个结点都要由指针域,因此从存储密度来说是不经济的从时间方面看:顺序表是一种随机存储的结构,在数据的查找时时间复杂度为O(1)但是插入和删除时为O(n)链式存储在数据的查找时时间复杂度为O(n)但是插入和删除时为O(1)结论在线性表长度变化较大或难以估计其储存规模时采用动态链表,否则采用顺序存储对线性表的操作主要是查找而很少做插入和删除操作时,采用顺序存储,否则采用链式存储总之,两种情况各有优缺点,应看具体情况进行讨论。,。栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。数据的插入操作通常称为进栈或入栈,数据的删除操作通常称为退栈或出栈。栈顶top栈底botton出栈进栈栈示意图A1A2A3A4A5A6A7栈是一种限制存取点的线性结构,即只允许在栈顶进行出栈和入栈的操作。所以,栈还叫做“后进先出”表