数据结构与算法实验指导书
}while(q!=p); head=p;
printf(\ return (head); }/* select */
main( )
{ int n,m;
linklist *head;
printf(\ scanf(\
printf(\ scanf(\ head=creat(head,n); head=select(head,m);
printf(\ }/* main */
思考题：编程实现两个循环单链表的合并。
实验四 栈、队列的实现及应用
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。
二、实验内容
1、实现栈的顺序存储
# define MAXSIZE 100 typedef int ElemType; typedef struct
{ ElemType data[MAXSIZE]; int top; }SeqStack;
void InitStack(SeqStack *s) {s->top=0; return 1; }
int StackEmpty(SeqStack *s) { if(s->top==0) return 1; else return 0; }
int StackFull(SeqStack *s)
{ if(s->top==MAXSIZE-1) return 1; else return 0; }
- 11 -
数据结构与算法实验指导书
void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf(\ return 0; }
else { s->data[s->top]=x;
s->top++; }
}
void Display(SeqStack *s) {if(s->top==0)
printf(\ else{ while(s->top!=0)
{ printf(\ s->top=s->top-1;
}
} }
ElemType Pop(SeqStack *s)
{ if(StackEmpty(s)) return 0; else return s->data[--s->top]; }
ElemType StackTop(SeqStack *s) { int i;
if(StackEmpty(s)) return 0; else { i=s->top-1;
return s->data[i];} /*返回栈顶元素的值，但不改变栈顶指针*/
}
main(SeqStack *p)
{int n,i,k,h,x1,x2,select;
printf(\ InitStack(p);
printf(\ scanf(\ for(i=0;i { printf(\ scanf(\ Push(p,k); } printf(\ printf(\ printf(\ printf(\ printf(\ scanf(\ switch(select) - 12 - 数据结构与算法实验指导书 {case 1:{ display(p); break;} case 2:{ printf(\ scanf(\ Push(p,h); display(p); break;} case 3:{ x1=Pop(p); printf(\ display(p); break; } case 4:{ x2=StackTop(p); printf(\ break; } } 2、利用栈实现数制转换 # define MAXSIZE 100 typedef int ElemType； /*将顺序栈的元素定义为整型*/ typedef struct { ElemType data[MAXSIZE]; int top; }SeqStack; void InitStack(SeqStack *s) {s->top=0; return 1; } int StackEmpty(SeqStack *s) { if(s->top==0) return 1; else return 0; } int StackFull(SeqStack *s) { if(s->top==m-1) return 1; else return 0; } void Push(SeqStack *s,int x) { if (StackFull(s)){ printf(\ return 0; } else { s->data[s->top]=x; s->top++; } } - 13 - } 数据结构与算法实验指导书 ElemType Pop(SeqStack *s) { ElemType y; if(StackEmpty(s)){ printf(\ return 0; } else { y=s->data[s->top]; s->top=s->top-1; return y; } } ElemType StackTop(SeqStack *s) { if(StackEmpty(s)) return 0; else return s->data[s->top]; } void Dec_to_Ocx (int N) /* n是非负的十进制整数，输出等值的八进制数*/ { SeqStack *S； /*定义一个顺序栈*/ ElemType x； Init_SeqStack(S)； /*初始化栈*/ if(N<0) { printf(\。\； return； } if(!N) Push(S,0)； while(N) /*自右向左产生八进制的各位数字，并将其进栈*/ { Push(S，N%8)； /*余数入栈 */ N=N/8； /*商作为被除数*/ } printf(\ while(StackEmpty(S)) /*栈非空时退栈输出*/ { x=Pop(S)； printf(“%d”,x)； } printf(\} main( ) { int n; printf(\scanf(\Dec_to_Ocx (n); } 3、实现循环队列的顺序存储 #define maxsize 100 typedef struct {int data[maxsize]; int front; - 14 - 数据结构与算法实验指导书 int rear; }seqqueue; int sqinit(seqqueue *p) { p->front=0;p->rear=0; return 1;} int enqueue(seqqueue *q, int e) {if((q->rear+1)%maxsize==q->front) return 0; else q->data[q->rear]=e; q->rear=(q->rear+1)%maxsize; return 1; } int dequeue(seqqueue *q) {int e; if (q->front==q->rear) return 0; e=q->data[q->front]; q->front=(q->front+1)%maxsize; return e; } int empty(seqqueue *q) {int v; if (q->front==q->rear) v=1; else v=0; return v; } int gethead(seqqueue *q) {int e; if (q->front==q->rear) e=-1; else e=q->data[q->front]; return e; } void display(seqqueue *q) {int s; s=q->front; printf(\ if (q->front==q->rear) printf(\ else {while(s - 15 -
