数据结构大话《数据结构》PPT课件

1、数据结构大话数据结构崔 基 哲2 0 1 6 年算法和数据结构1算法和数据结构2第一章 绪论第二章 算法第三章 线性表第四章 栈和队列第五章 串第六章 树第七章 图第八章 查找第九章 排序栈栈是限定于只在表尾进行插入和删除操作的线性表栈是限定于只在表尾进行插入和删除操作的线性表后进先出（后进先出（Last in first out,LIFOLast in first out,LIFO）相关概念相关概念栈顶（表尾）栈底（表头）算法和数据结构3第四章：栈和队列举例：IE浏览器中的“前，后”常常是件很令人恼火的事情尤其是在我们这样的人口大国w 电话亭1978年在北京15%的电话要在1小时后才能接通。

2、在电报大楼打电话的人还要带着午饭去排队 w 银行窗口，ATMw 医院、理发、火车售票w 游乐场的游乐项目算法和数据结构5w 在游乐园中的频频排队会极为扫兴算法和数据结构6算法和数据结构7怎样缩短排队的等待时间？算法和数据结构8w 银行的排队叫号机 只是有序的组织了顾客，并没有减少等待时间w 如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？w 排队排队( (队列队列) )到底有什么学问？到底有什么学问？队列队列的特点队列的特点 先进先出，First in first out(FIFO)相关概念相关概念 队头：删除 队尾：插入算法和数据结构9A1 A2 A3 A4 A5 An

3、入队出队队头（front）队尾（rear）第三章：栈和队列队列的操作初始化：初始化：InitQueueInitQueue判断是否为空：判断是否为空：IsEmptyIsEmpty入队列：入队列：EnQueueEnQueue出队列：出队列：DlQueueDlQueue取队列头：取队列头：GetHeadGetHead清空队列：清空队列：ClearClear得到队列长度：得到队列长度：GetSizeGetSize算法和数据结构10第三章：栈和队列队列顺序存储的不足队列顺序存储的不足排队打饭，头名打完后面所有元素都要往前移动，O(n) 不必要的浪费？引入两个指针：假溢出 算法和数据结构11算法和数据结构

4、12012345678910(3)(4)(5)(6)(7)Q(8)tailhead012345678910(4)(5)(6)(7)Q(8)tailhead循环队列算法和数据结构13假溢出 当队头与队尾元素重合时候，队满溢出算法和数据结构14循环队列演示J1Q.frontQ.rearJ2J3J1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ4J5J6J3J5J6J4Q.frontQ.rearJ5J6Q.frontQ.rearJ7J8还存在问题不是循环存储，算法的时间性能不高不是循环存储，算法的时间性能不高是循环队列，也要面临着数组可能会溢出的问题是循环队列，也要面临着数组可能

5、会溢出的问题需要队列的链式存储结构需要队列的链式存储结构 链队列算法和数据结构21第三章：栈和队列队列的链式存储算法和数据结构22NULLpFrontpRear入队只对 pRear操作，出队对pFront操作 链队列 结点定义3.3.3队列队列 的存储实现及运算实现的存储实现及运算实现typedef struct LQNode int data; struct LQNode *next;LQueueNode;typedef struct LQueueNode *front,*rear; LinkQueue;LinkQueue *q;头结点 .q-front队头队尾q-rear头结点q-fron

6、tq-rearv链队列基本运算实现（1）创建一个带头结点的空队头结点q-frontq-rear（2）判队空（3）入队q-frontq-rearx入队xq-frontq-reary入队xyLQueue *Init_LQueue() LinkQueue *q; LQueueNode *p; q=(LinkQueue *)malloc(sizeof(LinkQueue); p=(LQueueNode *)malloc(sizeof(LQueueNode); p-next=NULL; q-front=q-rear=p; return q; int Empty_LQueue( LinkQueue *q)

7、 if (q-front=q-rear) return 1; else return 0; void In_LQueue(LinkQueue *q , ElemType x) LQueueNode *p; p =(LQueueNode *)malloc(sizeof(LQueueNode); p-data=x; p-next=NULL; q-rear-next=p; q-rear=p;frontrearx出队xyfront reary出队（4）出队int Out_LQueue(LinkQueue *q , ElemType *x) LQueueNode *p; if (Empty_LQueue

8、(q) ) printf (队空)； return 0; else p=q-front-next; q-front-next=p-next; *x=p-data; free(p); if (q-front-next=NULL) q-rear=q-front; return 1; 队列的应用算法和数据结构26模拟打印机缓冲区： 在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区算法和数据结构27需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。算法和数据结构28CPU分时系统 在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请