数据结构3队详解.ppt

第3章堆栈和队列 链队列的入队示意 12EF front *p 130A p NULL 130A *p 1475 p x NULL x NULL 1475 12EF rear 130A rear 1475 rear int addq (LQueue *q,DataType x) {LQnode *p; if ((p=(LQnode* ) malloc(sizeof(LQnode)))==NULL) {printf (“\n申请空间失败!”); return (FALSE);} p-data=x; p-next=NULL; q-rear-next=p; q-rear=p; return (TRUE); } a1 front a2 ∧ rear rear 链队列的入队算法 p X ∧ 链队列的出队 y 1475 p 12EF front a2 NULL 1475 a1 130A 130A a1 1475 rear int delqueue (LQueue *q, DataType *x) { LQnode *p; if (q-front-next==NULL) return (FALSE); p=q-front-next; y=p-data; q-front-next=p-next; free(p); return (TRUE); } 链队列的出队算法 a1 front a2 ∧ rear p a1 y 回文判断 问题描述：编程序判断一个字符序列是否是回文 例：ABCDEDCBA ABCDEDBAC 基本要求： 1 字符序列个数 n可由用户自定义，且0n80. 2 可连续测试任意多个字符序列，由用户决定退出 3 字符序列由用户从键盘输入 测试数据： 1 abcdcba 2 abcdefg 3.4 队列的应用——1 1.回文判断 字符序列分别入队和进栈，再逐个出队和退栈进行比较 模块划分： 1 Palindrome(char str[],int n) 判断回文 2 EnterStr(char str[],int *n)输入字符序列 3 main() 数据结构： 1 顺序堆栈抽象数据类型 2 顺序队列抽象数据类型 算法思想： #includestdio.h #includestring.h #define MAXNUM 80 typedef char elemtype; typedef struct { elemtype stack[MAXNUM]; int top; } qstype; typedef struct { elemtype queue[MAXNUM]; int front,rear; } qqtype; 源程序： main() { char ch, str [MAXNUM]; int n; while(1) { EnterStr(str,n); Palindrome(str,n); printf(\n 是否继续? (y/n): ); scanf(%s,ch); if(ch==Y||ch==y) continue; else break; } } * * 3.3 队列 ( Queue ) 3.3.1 队列的概念 3.3.2 队列抽象数据类型 3.3.3 顺序队列及操作 3.3.4 链式队列及操作 1. 定义 队列:是只允许在一端删除，在另一端插入的线性表. 队头(front):允许删除的一端. 队尾(rear):允许插入的一端。 a2 … an-1 a1 a0 出队 入队 front rear 3.3.1.队列的概念 特性 先进先出(FIFO, First In First Out) 3.3.2.队列抽象数据类型 数据集合: 队列的数据集合可表示为a0,a1…an-1,每个元素的类型:DataType 关系:线性关系 操作集合: 1、初始化:设置一个空队列. 2、判队是否空:判空操作。 若队列为空， 则返回TRUE， 否则返回FALSE。 3、进队:在队列Q的队尾插入x。 操作成功，返回值为TRUE， 否则返回值为FALSE。  4、出队:使队列Q的队头元素出队， 并用x带回其值。 操作成功，返回值为TRUE， 否则返回值为FALSE。  5、取队头元素:用x取得队元素的值。操作成功，返回值为TRUE，否则返回值为FALS