数据结构课程内容.ppt

《数据结构课程内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程的内容1讨论：已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在P结点后插入S结点的核心语句序列。答：此题答案不唯一。法二：已知P结点，则不必“顺藤摸瓜”，直接链接即可。(4)  S->next=P->next;(1)P->next=S;法一：从头“摸”起：(7)Q=P;(11)P=L;(8)while(P->next!=Q)P=P->next;(10)P=Q;(4)S->next=P->next;(1)P->next=S;23.1栈（Stack）第三章栈和队列3

2、.2队列（Queue）1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式1.定义2.逻辑结构3.存储结构4.运算规则5.实现方式31.定义3.1栈与同线性表相同，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。3.存储结构4.运算规则5.实现方式2.逻辑结构限定只能在表的一端进行插入和

3、删除运算的线性表（只能在栈顶操作）4问：堆栈是什么？它与一般线性表有什么不同？3.1栈答：堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝压入=PUSH（x)“出”＝弹出=POP(y)5栈是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶top;表头(即a1端)称为栈底base例如：栈

4、s=(a1,a2,a3,……….,an-1,an)a1称为栈底元素an称为栈顶元素插入元素到栈顶（即表尾）的操作，称为入栈。从栈顶（即表尾）删除最后一个元素的操作，称为出栈。教材P44对栈有更详细定义：强调：插入和删除都只能在表的一端（栈顶）进行！6顺序栈示意图sa1a2a3dataa4(栈底)(栈顶)99...3210top7a1a2……an顺序栈Sai……表和栈的操作区别——对线性表s=(a1,a2,….,an-1,an)表头表尾栈底base栈顶top低地址高地址写入：v[i]=ai读出：x=v[

5、i]压入：PUSH(an+1)弹出：POP(x)前提：一定要预设栈顶指针top！低地址高地址v[i]a1a2aian……顺序表V[n]……an+18入栈操作——例如用堆栈存放（A，B，C，D）（注意要遵循“后进先出”原则）AACBABAtop核心语句：top=L;顺序栈中的PUSH函数statusPush(ElemTypex){if(top>M){上溢}elsev[top++]=x;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD9出栈操

6、作——例如从栈中取出‘B’（注意要遵循“后进先出”原则）DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop();Pop();Printf(Pop());顺序栈中的POP函数statusPop(){if(top=L){下溢}else{y=v[--top];return(y);}}10例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？43512不可能实现，主要是其中的12顺序不能实现；12345的输

7、出可以实现，只需压入一个立即弹出一个即可。435612中到了12顺序不能实现；135426可以实现。例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？答：答：11例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、

8、3入，3、2、1出，即321；合计有5种可能性。12例4：计算机系2001年考研题（程序设计基础）设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列i，j，k，能同时满足i