C语言版的数据结构(6)

}

printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_c */ /* 进栈函数 */

void push(SqStack *s,ElemType e)

{ if(s->top==MAXSIZE-1)printf(“\\n Sstack is Overflow!”); else{ s->top++ ;

s->a[s->top]=e; }

}/* push */ /* 出栈函数 */

ElemType pop(SqStack *s) { ElemType x;

if(s->top==-1){ printf(“\\n Stack is Underflow!”); x=-1; }

else { x=s->a[s->top]; s->top--; } return(x); } /* pop */

2. 循环队列（即队列的顺序存储结构）实现。 #include #include

#define MAXSIZE 20 /* 数组最大界限 */ typedef int ElemType; /* 数据元素类型 */ typedef struct

{ ElemType a[MAXSIZE]; /* 一维数组子域 */ int front,rear; /* 头、尾指针子域 */ }SqQueue; /* 循环队列的结构体类型 */ SqQueue Q1; /* 函数声明 */

void init_Q(SqQueue *Q); void out_Q(SqQueue Q);

void EnQueue(SqQueue *Q,ElemType e); ElemType DeQueue(SqQueue *Q); /* 主函数 */ main()

{ int k; ElemType e,x; char ch;

init_Q( &Q1); /* 初始化一个空循环队列 */

26

do { printf(\

printf(\数据元素e进队列 \

printf(\出队一个元素，返回其值\； printf(\结束程序运行\

printf(\ printf(\请输入您的选择 (1,2,3)\ scanf(\ switch(k) { case 1:{ printf(\进队 e=?\ EnQueue(SqQueue &Q1,e); out_Q(Q1); } break; case 2:{ x= DeQueue(&Q1);

printf(\出队元素 : %d\ out_Q(Q1 ); } break; case 3: exit(0); } /* switch */ printf(\ }while(k>=1 && k<3);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */

/* 初始化空队列 * / void init_Q(SqQueue *Q)

4 3 5 { Q->front=0; Q->rear=0;

0 } /* init_Q */ 2 Q1.front 1 /* 输出队列的内容 */

Q1.rearr void out_Q(SqQueue Q)

空循环队列 { char ch; int i;

/* 不能修改队列头、尾指针 */

if (Q->front==Q->rear) printf(“\\n Queue is NULL. “); else{ i=(Q->front+1)% MAXSIZE;

while( i!=Q->rear){ printf(“\\n data=%d”, Q->a[i]);

i=(i+1)%MAXSIZE; }

printf(“\\n data=%d”, Q->a[i]); }

printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_Q */

27

/ * 进队函数 */

void EnQueue(SqQueue *Q,ElemType e)

{ if((Q->rear+1)%MAXSIZE==Q->front) printf(“\\n Queue is Overflow!”); else{ Q->rear=(Q->rear+1)% MAXSIZE ; Q->a[Q->rear]=e; }

}/* EnQueue */

3 4 5

12 2 1 0

Q1.rear 11 Q1.front 进队两个数据后

/* 出队函数 */

ElemType DeQueue(SqQueue *Q) { ElemType x;

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

{ printf(“\\n Queue is NULL!”); x=-1; }

else { Q->front=(Q->front+1)% MAXSIZE ;

x=Q->a[Q->front]; } return(x);

} /* DeQueue */

3. 队列的链表储结构及实现。 #include #include #include typedef int ElemType; typedef struct QNode

{ ElemType data; /* 数据子域 */ struct QNode *next; /* 指针子域 */ }QNode; /* 结点结构类型 */ typedef struct

{ Qnode *front, *rear; /* 头、尾指针子域

28

*/

}L_Queue; /* “头尾”结点结构类型 */ L_Queue Q1; /* 函数声明 */

void init_Q(L_Queue *Q); void out_Q(L_Queue Q);

void EnQueue(L_Queue Q,ElemType e); ElemType DeQueue(L_Queue Q); /* 主函数 */ main()

{ int k; ElemType e,x; char ch;

init_Q( &Q1); /* 初始化一个空循环队列 */ do { printf(\

printf(\数据元素e进队列 \

printf(\出队一个元素，返回其值\； printf(\结束程序运行\

printf(\ printf(\请输入您的选择 (1,2,3)\ scanf(\ switch(k) { case 1:{ printf(\进队 e=?\ EnQueue(SqQueue &Q1,e); out_Q(Q1); } break; case 2:{ x= DeQueue(&Q1);

printf(\出队元素 : %d\ out_Q(Q1 ); } break; case 3: exit(0); } /* switch */ printf(\ }while(k>=1 && k<3);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */

/* 初始化一个空队列 */ void init_Q(L_Queue *Q)

Q.front { QNode *p ;

Q.rear

p=(QNode *)malloc(sizeof(QNode)); p->next=NULL; 空链表队列 Q->fornt=p; Q->rear=p;

29

∧ } /* init_Q */

/* 输出队列的内容 */ void out_Q(L_Queue Q) { QNode *p; char ch; p=Q.front->next;

while(p!=NULL) { printf(“\\n %d”,p->data); p=p->next; }

printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_Q */ / * 进队函数 */

void EnQueue(L_Queue Q,ElemType e) { QNode p,s;

s=(QNode *)malloc(sizeof(QNode)); s->data=e; s->next=NULL; Q.rear->next=s; Q.rear=s; } /* EnQueue */ Q.front

11 ∧ Q.rear

有一个数据元素的链表队列

/* 出队函数 */

ElemType DeQueue(L_Queue Q) { ElemType x; QNode *p;

if(Q.front==Q.rear) { printf(“\\n Queue is NULL!”); x=-1; }

else { p=Q.front->next; x=p->data;

Q.front->next=p->next;

If(Q.rear= =p) Q.rear=Q.fornt; Free(p); } return(x); } /* DeQueue */

30