计算机软件基础(自考本科)(1.9).pptVIP

桂林电子科技大学 GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY 桂林电子科技大学 GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY 计算机 软件基础 第二篇　数据结构基础 第九章　栈、队列和数组 一、栈（stack） （一）栈的概念 1. 栈：是一种后进先出的线性表，简称为LIFO表（Last In First Out）。 2. 栈顶（Top）：栈中进行插入、删除操作的一端（即：变化端）。 3. 栈低（Bottom）：栈中固定不变的一端。 4. 栈的存储结构：顺序存储和链式存储。 一、栈（stack） （二）顺序栈 -1 0 1 2 3 4 bottom top 栈空（top=-1） -1 0 1 2 3 4 top bottom 1. 形态 进栈（top=0） A top 一、栈（stack） -1 0 1 2 3 4 bottom top 栈满（top=m-1） A B C D E top top top top top bottom 出栈 -1 0 1 2 3 4 A B C D E top top top 栈的体积：一个栈所能容纳元素个数 一、栈（stack） 3. 顺序栈的类型 #define m 100 //定义栈的最大容量为100 struct seqstack { datatype data[m]; //栈内最多存放m个元素 int top; //指向栈顶的指针 }s; 一、栈（stack） 4. 顺序栈的基本运算----进栈 void push( s, x) { if(s.top==m-1) 上溢； else { s.top++; s.data[s.top]=x; } } step1:判断栈是否已满，若满，则上溢，否则进行下一步； step2:栈顶指针上移一个节点； Step3: 将x加入到top指定的位置。 一、栈（stack） 5. 顺序栈的基本运算----退栈 void pop(s) { if(s.top==-1) 下溢； else { x=s.data[s.top]; s.top--; } } step1:判断栈是否为空，若空，则下溢，否则进行下一步； Step2: 保留被删除元素到变量x中； step3:栈顶指针下移一个节点； 一、栈（stack） （三）链栈 1. 形态 Ls a b x 非空栈 栈顶元素 栈低元素 Ls 空栈 链栈：是一个不带表头节点的单链表（栈顶指针直接 指向栈顶元素）。 一、栈（stack） （三）链栈 2. 类型定义 struct node { datatype data; struct node *next; }*Ls; 一、栈（stack） （三）链栈 3. 进栈运算 void insert(Ls, x) { s=(struct node)malloc(sizeof(struct node)); s-data=x; s-next=Ls; Ls=s; } step1:申请一个新节点，并让s指向该节点； step2:将x赋给新节点的data域； step3:将原栈点链入新节点的next域； step4:新节点作为新的栈顶节点。 一、栈（stack） （三）链栈 4. 退栈运算 void del(Ls) { if(Ls==NULL) return; else { p=Ls; Ls=Ls-next; free(p); } } step1:判断栈是否为空，如为空，则直接返回，否则进行第二步； step2:让p指栈顶元素； step3:栈顶指针向下移一位； step4:删除原栈顶元素。 二、队列（queue） （一）队列的概念 1. 队列：是一种先进先出的线性表，简称为FIFO表（ First In First Out）。 2. 队头（front）：队列中进行删除操作的一端。 3. 队尾（rear）：队列中进行插入操作的一端。 4. 队列的存储结构：顺序存储和链式存储。 二、队列（queue） （二）顺序队列 1. 形态： -1 1 0 2 3 4 5 f=r=-1 队列空 -1 1 0 2 3 4 5 f 入队列 a r b c r r 注意：入队时， 头指针保持不 动，尾指针往 后移。 二、队列（queue） （二）顺序队列 1. 形态： -1 1 0 2 3 4 5 f 队列满 -1 1 0 2 3 4 5 f 出队列 r