数据结构2第3章幻灯片.ppt

顺序队列判队空 int EMPTY(sequeue *sq) { if (sq-rear==sq-front) return(TRUE); else return(FALSE); } 顺序队列取队头元素 datatype FRONT(sequeue *sq) { if (EMPTY(sq)) { printf(“queue is empty\n”);return NULL;} else return (sq-front+1)%maxsize; } 顺序队列入队 int ENQUEUE(sequeue *sq,datatype x) { if (sq-front==(sq-rear+1)%maxsize) {printf(“sequeue is full\n”;return NULL);} else { sq-rear＝(sq-rear+1)%maxsize; sq-data[sq-rear]＝x; return(TRUE); } } 顺序队列出队 datetype DEQUEUE(sequeue *sq) { if (EMPTY(sq)) {printf(“queue is empty\n”);return NULL;} else { sq-front＝(sq-front+1)%maxsize; return(sq-data[sq-front]); } } 顺序队列存在问题 设数组维数为M，则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0; 0 M-1 1 front rear …... …... 实现：利用“模”运算 入队： rear=(rear+1)%M; sq[rear]=x; 出队： front=(front+1)%M; x=sq[front]; 队满、队空判定条件 存储队列的数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: front = (front + 1) % maxSize; 队尾指针进1: rear = (rear + 1) % maxSize; 队列初始化：front = rear = 0; 队空条件：front == rear; 队满条件：(rear + 1) % maxSize == front 循环队列 (Circular Queue) 0 1 2 3 4 5 rear front J4 J5 J6 0 1 2 3 4 5 rear front J9 J8 J7 J4 J5 J6 0 1 2 3 4 5 rear front 初始状态 J4,J5,J6出队 J7,J8,J9入队 队空：front==rear 队满：front==rear 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front==rear 队满：(rear+1)%M==front 循环队列的进队和出队 队列的链接表示 — 链式队列 队头在链头，队尾在链尾。 链式队列在进队时无队满问题，但有队空问题。 队空条件为 front == NULL 链队列结点类型定义 typedef struct { linklist *front,*rear; } linkqueue; 链队列置队空 SETNULL(linkqueue *q) { q-front＝malloc(sizeof(linklist)); q-front-next＝NULL; q-rear＝q-front; } 链队列判队空 int EMPTY(linkqueue *q) { if q-front==q-rear) return(TRUE); else return(FALSE); } 链队列取队头结点 datatype FRONT(linkqueue *q) { if (EMPTY(q)) {printf(“queue is empty\n”);return NULL;} else return(q-front-next-data); } 链队列入队 ENQUEUE(linkqueue *q,datatype x) { q-rear-next＝mallo