的 华中科技大学 计算机学院(5) 2001-3-26
2001-3-26 华中科技大学 数据结构 计算机学院(5)
3.4队列(排队, queue) 3.4.2链式队列:用带表头结点的单链表表示队列 般形式 (1)空队列: Q front data next Q. rear ///∧ 表头结点 (2)非空队列: data next Q. front an Q rear 表头结点队头结点 队尾结点 其中:Q. front队头(首)指针,指向表头结点 rear一 队尾指针,指向队尾结点 Q. front->data不放元素。 Q. front->next指向队首结点a1
3.4 队列（排队,queue) 3.4.2 链式队列: 用带表头结点的单链表表示队列 1.一般形式 (1)空队列: (2) 非空队列: 其中： Q.front----队头(首)指针,指向表头结点。 Q.rear----队尾指针，指向队尾结点。 Q.front->data 不放元素。 Q.front->next 指向队首结点a1。 /// ∧ data next 表头结点 /// data next 表头结点 a1 队头结点 an ∧ 队尾结点 ... Q.front Q.rear Q Q.front Q.rear Q
2.定义结点类型 (1)存放元素的结点类型 typedef struct Qnode i Elem Type data; //data为抽象元素类型 struct Qnode*next;//next为指针类型 } Qnode,* QueuePtr;/结点类型,指针类型 其中: Qnode-结点类型 data next QueuePtr-指向 Qnode的指针类型 (2)由头、尾指针组成的结点类型 typedef struct Qnode* front;/头指针 front Qnode*rear;/尾指针 rear } LinkQueue;//链式队列类型
2.定义结点类型 (1)存放元素的结点类型 typedef struct Qnode { ElemType data； //data为抽象元素类型 struct Qnode *next； //next为指针类型 }Qnode，*QueuePtr； //结点类型, 指针类型 其中：Qnode----结点类型 QueuePtr----指向Qnode的指针类型 (2)由头、尾指针组成的结点类型 typedef struct { Qnode *front； //头指针 Qnode *rear； //尾指针 }LinkQueue； //链式队列类型 data next front rear
3生成空队列算法 # define leng sizeof( Qnode)/求结点所占的单元数 LinkQueue InitQueue() //生成仅带表头结点的空队列Q i LinkQueue Q: //说明变量Q Q. front=Q.rear=( Queueptr)ma1loc(LENG);//生成表头结点 Q. front->next=NUI //表头结点的next为空指针 return Q; //返回Q的值 main LinkQueue que /*定义一个队列* que=InitQueueo
3.生成空队列算法 #define LENG sizeof(Qnode) //求结点所占的单元数 LinkQueue InitQueue( ) //生成仅带表头结点的空队列Q { LinkQueue Q； //说明变量Q Q.front=Q.rear=(QueuePtr)malloc(LENG)；//生成表头结点 Q.front->next=NULL； //表头结点的next为空指针 return Q； //返回Q的值 } main() { LinkQueue que; /*定义一个队列*/ que=InitQueue(); ……… }
4.(空队列时)插入新元素x data next Q. front 新结点X ///∧ rear 表头结点 Q front /// ∧ rear 表头结点 队头(尾)结点 (非空队列时)插入新元素y data next Q. front x|∧ y Q. rear 表头结点↑队头(尾) ---新结点 Q. front ∧ Q rear 表头结点队头结点′队尾结点
/// ∧ data next 表头结点 Q.front Q.rear Q x 新结点X /// 表头结点 Q.front Q.rear x ∧ X 队头(尾）结点 P 4.（空队列时）插入新元素x P /// 表头结点 Q.front Q.rear x ∧ 队头(尾） y data next /// 表头结点 Q.front Q.rear x 队头结点 y ∧ 新结点y 队尾结点 X （非空队列时）插入新元素y