資料結構(3)

第四章 Queues and Lists

A queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end(called the rear of the queue).

FIFO(first-in, first-out)

The primitive operations can be applied to queue.

The operation insert (q,x) insert items at the rear of the queue q.

The operation x=remove(q) delete the front element from the queue q and set x to its contents.

The third operation, empty(q), returns false or true depending on whether or not the queue contains any elements.

Abstract typedef <<eltype>> QUEUE(eltype);

abstract empty(q)

QUEUE(eltype) q;

postcondition empty == (len(q) == 0);

abstract eltype remove(q)

QUEUE(eltype) q;

precondition empty(q)==FALSE

postcondition remove == first(q');

q=sub(q',1,len(q')-1);

abstract insert(q, elt)

QUEUE(eltype) q;

eltype elt;

postcondition q==q'+<elt>;

#define MAXQUEUE 100

struct queue{

int items[MAXQUEUE];

int front, rear;

};

Initially, q.rear is set to -1, and q.front is set to 0. The queue is empty whenever q.rear < q.front.

int empty(struct queue *pq)

{

return ((pq->front ==pq->rear) ? TRUE : FALSE);

}

int remove(struct queue *pq)

{

if(empty(pq)

{

printf(“queue underflow”);

exit(1);

}

if(pq->front == MAXQUEUE-1)

pq->front=0;

else

(pq->front)++;

return (pq->items[pq->front]);

}

void insert(struct queue *pq, int x)

{

/*make room for new element*/

if(pq->rear == MAXQUEUE-1)

pq->rear=0;

else

(pq->rear)++;

/*check for overflow*/

if(pq->rear == pq->front)

{

printf(“queue overflow”);

exit(1);

}

pq->items[pq->rear] = x;

return;

}

The priority queue is a data structure in which the intrinsic ordering of the elements does determine the results of its basic operations.

What are the drawbacks of using sequential storage to represent stacks and queues? One major drawback is that a fixed amount of storage remains allocated to the stack or queue when the structure is actually using smaller amount or possibly no storage at all. Further, no more than that fixed amount of storage may be allocated, thus introducing the possibility of overflow.

A data structure pictured in Figure. 4.1 which is known as a linear linked list. Each item in the list is called a node and contains two fields, an information field and a next address field.

node(p) refers to the node pointed by p.

info(p) refers to the information portion of the node.

next(p) referss to the next address portion and is therefore a pointer.

#define NUMNODES 500

struct nodetype{

int info, next;

};

struct nodetype node[NUMNODES];

int getnode(void)

{

int p;

if(avail==-1)

{

printf(“overflow\n”);

exits(1);

}

p = avail;

avail = node[avail].next;

return p;

}

void feenode(int p)

{

node[p].next=avail;

avail=p;

return;

}

void insafter(int p, int x)

{

int q;

if(p==-1)

{

printf(“void insertion\n”);

return;

}

q = getnode();

node[q].info=x;

node[q].next=node[p].next;

node[p].next=q;

return;

}

void delafter(int p, int *px)

{

int q;

if((p==-1) || (node[p].next==-1))

{

printf(“void deletion\n”);

return;

}

q = node[p].next;

*px = node[q].info;

node[p].next=node[q].next;

freenode(q);

return;

}

Linked lists Using Dynamic Variables

struct node{

int info;

struct node *next;

};

typedef struct node *NODEPTR;

NODEPTR getnode(void)

{

NODEPTR p;

p=(NODEPTR)malloc(sizeof(struct node));

return p;

}

void freenode(NODEPTR p)

{

free(p);

}

void insafter(NODEPTR p, int x)

{

NODEPTR q;

if(p==NULL)

{

printf(“void insertion\n”);

return;

}

q = getnode();

q->info=x;

q->next=p->next;

p->next=q;

return;

}

void delafter(NODEPTR p,int *px)

{

NODEPTR q;

if((p==NULL || p->next==NULL))

{

printf(“void deletion\n”);

return;

}

q =p->next;

*px = q->info;

p->next=q->next;

freenode(q);

return;

}

Page 216 search and rmvx

page 232 concat

Doubly Linked List

Page 237 238 239