数据结构队列的特点和实现本解读.ppt

  1. 1、本文档共31页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
队列 定义 特点 基本操作 存储结构 取队头 入队 出队 队列的存储结构 循环队列 链队列 链队列的表示和实现 链队列的基本形态 链队列的基本操作 链队列的基本操作 链队列的基本操作 链队列的基本操作 链队列的基本操作 循环队列的表示和实现 队列的基本形态 假溢出的解决办法 如何判断队空和队满 循环队列的基本操作 循环队列的基本操作 循环队列的基本操作 双端队列 输出受限的双端队列 输入受限的双端队列 队列的应用 舞伴配对 舞伴配对 舞伴配对 舞伴配对 * 第三章 队列 限定在线性表的一端(表尾)进行插入,而在线性表的另一端(表头)进行删除。在队列中允许插入的一端叫队尾(rear),允许删除的一端叫队头(front)。 1.队列也是一种线性结构; 2.对队列的操作按照“先进先出”的原则进行。 与栈相比,队列的插入、删除分别在线性表的表尾和表头进行。 读取非空队列中的队头元素 a1 a2 an … … 向队列中插入一个新的元素,新插入的元素为队尾。 a1 a2 an e … … 非空队列中,删除队头元素,其直接后继为新队头。 a1 a2 an … … 用一组地址连续的存储单元依次存放自队头到队尾的数据元素。 利用链表存储队列中队头到队尾的数据元素。 需要设置队头和队尾位置标志 队头指针指向队头,队尾指针指向队尾。 定义 用链表表示的队列称为链队列。也就是用带头结点的单链表存储数据。设置头指针front指向头结点,设置尾指针rear指向尾结点。 C描述 typedef struct QNode{ ElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; 链队列结点类型 链队列类型 空队列 非空队列 通常链队列用单链表表示。为了操作方便,给链队列添加一个头结点,令头指针指向头结点。也就是说,带头结点的链队列中,非空队列中,队头指针指向头结点,队尾指针指向队尾结点。空队列中,队头指针和队尾指针均指向头结点。 Q.front Q.rear ∧ a1 ∧ an … Q.front Q.rear Q.front==Q.rear 链队列的基本操作即为单链表的插入和删除的特殊情况,只是需要进一步修改尾指针或头指针。 初始化队列 入队列 出队列 取队头 清空队列 销毁队列 Q.front = (QueuePtr)malloc(sizeof(QNode)); Q.rear = Q.front ; Q.front-next = NULL; 1.初始化为空队列 生成新结点为头结点,队头和队尾指针指向此结点。头结点的指针域为空。 while(Q.front){ Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; } 2.销毁队列 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; 3.入队 入队修改尾指针 链队列在入队前不需要判断队列是否满。入队元素动态分配内存,插入到队尾处,同时修改队尾指针。 if (Q.front == Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear == p) Q.rear = Q.front; free (p); 4.出队 出队修改头结点的链接 一般情况下,删除队列首元素时仅需修改头结点中的指针,但当队列中最后一个元素被删除后,需要对队尾指针重新赋值(指向头结点)。 定义 用一组地址连续的存储单元依次存放从队头到队尾的元素。还需要附设两个整型变量:front指示队头元素的位置,rear指示队尾元素的下一个位置。 C描述 const int MAXSIZE=128; typedef struct { Elemtype elem[MAXSIZE]; int front; int rear; }Squeue; 空队列 非空队列 6 5 4 3 2 1 0 Q.front=Q.rear=

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档