第3章栈和队列顺序栈.pptVIP

第3章 栈和队列 ;温故知新环节：回顾上次课内容 习题实践环节：检查上次课内容 新语新知环节：讲授第三章栈的概念 重点难点： 深刻理解栈是一种操作受限的线性表 理解栈指针的含义并熟练使用;线性表的顺序表示与链式表示: 从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的 从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1) 但是插入和删除时为O(n) 链式存储在数据的查找时时间复杂度为O(n) 但是插入和删除时为O(1) ;在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储 对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用链式存储 总之，两种情况各有优缺点，应看具体情况进行讨论。;1、带头结点的单链表为空的判定条件是 （哈尔滨工业大学） A.H=NULL B.H-next=NULL C.H-next=H D.H!=NULL ;2、将图中S结点加到P所指结点之后，其语句是：(浙江大学) A. s-next=p+1 p-next=s B.(*p).next=s (*s).next=(*p).next C.s-next=p-next p-next=s-next D.s-next=p-next p-next=s;3.下面关于线性表的叙述中，错误的是哪一个？（北方交通大学） 线性表采用顺序储存，必须占用一片连续的存储单元 线性表采用顺序储存，便于进行插入和删除操作 线性表采用链式储存，不必占用一片连续的储存单元 线性表采用链式储存，便于插入和删除操作 4.某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，这样采用（）储存方式最节省时间。（哈尔滨工业大学） A 顺序表 B 单链表;5.线性表的逻辑顺序和物理顺序总是一致的这种说法 A 正确 B 不正确 6.线性表若是采用链式存储，要求内存中可用存储单元的地址 A 必须连续 B 部分地址必须连续 C 一定是不连续的 D 连续不连续都可以 7.非空单链表L的尾结点P满足 A. p-next=NULL B. p=NULL C. p-next=L D. p=L ; (8) 插入数据元素ListInsert(L,i,e) 思路：先在单链表L中找到第i-1个结点*p,若存在这样的结点,将值为e的结点*s插入到其后。 若位序不合法：返回0，否则返回1表示插入 int ListInsert(LinkList *L,int i,ElemType e) { int j=0; LinkList *p=L-next,*s; while (ji-1 p!=NULL) /*查找第i-1个结点*/ { p=p-next; j++; }; if (p==NULL) return 0; /*未找到位序为i-1的结点*/ else /*找到位序为i-1的结点*p*/ { s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*s*/ s-data=e; s-next=p-next; /*将*s插入到*p之后*/ p-next=s; return 1; } };3.1 栈 3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本运算的实现 3.1.3 栈的链式存储结构及其基本运算的实现 ; 栈是一种操作受限的线性表。 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。 ;出栈; 例3.1 设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是 。（北京航天航空大学） (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C ;例3.2一个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学);明白为什么说栈是操作受限的线性表吗？ ;2个问题;新语新知环节--- 3.1.2 顺序栈的结构;假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack: ;顺序栈进栈和出栈示意图;初始化栈InitStack( ): 进栈Push(s,e): 求栈的长