数据结构（栈与队列）——栈的顺序表示和实现、队列的链式表示和实现

客官°小女子只卖身不卖艺 2022-12-24 11:50 122阅读 0赞

**实验内容：**

1.  编写一个程序实现顺序栈的各种基本运算。
2.  实现队列的链式表示和实现。  
    **实验步骤：**  
    1．初始化顺序栈
3.  插入元素
4.  删除栈顶元素
5.  取栈顶元素
6.  遍历顺序栈
7.  置空顺序栈
8.  初始化并建立链队列
9.  入链队列
10. 出链队列
11. 遍历链队列

1、栈的顺序表示和实现

#include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    
    #define TRUE       1
    #define FALSE      0
    #define OK         1
    #define ERROR      0
    #define INFEASIBLE -1
    #define OVERFLOW   -2
    typedef int StackElementType;
    
    //----- 栈的顺序存储表示 -----
    #define  Stack_Size  100
    #define  STACKINCREMENT   10
    
    typedef struct
    {
        
    	StackElementType elem[Stack_Size]; //用来存放栈中元素的一维数组
    	int top;          /*用来存放栈顶元素的下标，top为-1表示空栈*/
    }SeqStack;
    
    /*初始化顺序栈函数*/
    void InitStack(SeqStack *S)
    {
        
    	/*构造一个空栈S*/
      	S->top = -1;
    }
    
    /*判栈空*/
    int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
    {
        
    	return(S->top==-1?TRUE:FALSE);
    }
    
    /*入栈函数*/
    int Push(SeqStack *S,StackElementType x)
    {
        
    	//请完成本函数的功能
    	if(S->top==Stack_Size-1) return (FALSE);/*栈已满*/
    	S->top++;
    	S->elem[S->top] = x;
    	return (TRUE);
    }
    /*出栈函数*/
    int Pop(SeqStack *S,StackElementType *x)
    {
          
    	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
    	//请完成本函数的功能
    	if(S->top==-1)
    		return (FALSE);
    	else
    	{
        
    		*x = S->elem[S->top];
    		S->top--;
    		return (TRUE);
    	}
    }
    /*获取栈顶元素函数*/
    int GetTop(SeqStack *S,StackElementType *x)
    {
          
    /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
    //请完成本函数的功能
    	if(S->top == -1)
    		return (FALSE);
    	else
    	{
        
    		*x = S->elem[S->top];
    		return (TRUE); 
    	}
    }
    
    int StackDisplay(SeqStack *S){
        //显示栈S
    	int i = 0;
    	if(IsEmpty(S)){
        
    	  printf("堆栈已空!\n");
    	  return OK;
    	}
    	while( i<=S->top)
    		printf("[%d:%d]",++i,S->elem[i]);
    	printf("\n");
    	return OK;
    }//StackDisplay
    
    void main(){
        
    	SeqStack St;
    	int temp;
    	int flag=1,ch;
    	int e;
    	printf("本程序实现顺序结构的堆栈的操作。\n");
    	printf("可以进行入栈，出栈，取栈顶元素等操作。\n");
    	InitStack(&St);       //初始化堆栈St
    	while(flag){
        
    		printf("请选择:\n");
    		printf("1.显示栈中所有元素     \n");
    		printf("2.入栈                 \n");
    		printf("3.出栈                 \n");
    		printf("4.取栈顶元素           \n");
    		printf("5.退出程序             \n");
    		scanf("%d",&ch);
    		switch(ch){
        
    		case 1:
    			StackDisplay(&St);
    			break;
    		case 2:
    			printf("请输入要入栈的元素(一个整数):");
    			scanf("%d",&e);      //输入要入栈的元素
    			temp=Push(&St,e);      //入栈
    			if(temp!=TRUE) printf("堆栈已满!入栈失败!\n");
    			else {
        
    				printf("成功入栈!\n");  //成功入栈
    				StackDisplay(&St);
    			}
    			break;
    		case 3:
    			temp=Pop(&St,&e);  //出栈
    			if(temp==FALSE) printf("堆栈已空!\n"); 
    			else {
        
    				printf("成功出栈一个元素:%d\n",e); //成功出栈
    				StackDisplay(&St);
    			}
    			break;
    		case 4:
    			temp=GetTop(&St,&e); //取得栈顶元素
    			if(temp==FALSE) printf("堆栈已空!\n");
    			else printf("栈顶元素是:%d\n",e); //显示栈顶元素
    			break;
    		default:
    			flag=0;
    			printf("程序结束，按任意键退出!\n");
    			getchar();
    		}
    	}
    }

2、队列的链式表示和实现

#include <conio.h>
    #include <stdio.h>
    #include <stdlib.h>
    #define TRUE       1
    #define FALSE      0
    #define OK         1
    #define ERROR      0
    
    typedef int QueueElementType;
    
    typedef struct Node
    {
        
    	QueueElementType data;     /*数据域*/
    	struct Node *next;     /*指针域*/
    }LinkQueueNode;
    
    typedef struct 
    {
        
    	LinkQueueNode *front;
    	LinkQueueNode *rear;
    }LinkQueue;
    
    /*初始化操作。*/
    int InitQueue(LinkQueue *Q)
    {
         
    	/* 将Q初始化为一个空的链队列 */
    	Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    	if(Q->front!=NULL)
    	{
        
    		Q->rear=Q->front;
    		Q->front->next=NULL;
     		return(TRUE);
    	}
    	else return(FALSE);    /* 溢出！*/
    }
    
    /*入队操作。*/
    int EnterQueue(LinkQueue *Q,QueueElementType x)
    {
          
    	/* 将数据元素x插入到队列Q中 */
    	//请完成本函数的功能
    	LinkQueueNode *NewNode;
    	NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    	if(NewNode != NULL)
    	{
        
    		NewNode->data = x;
    		NewNode->next = NULL;
    		Q->rear->next = NewNode;
    		Q->rear = NewNode;
    		return(TRUE);
    	}
    	else return(FALSE);
    }
    
    /*出队操作。*/
    int DeleteQueue(LinkQueue *Q,QueueElementType *x)
    {
          
    	/* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */
    	//请完成本函数的功能
    	LinkQueueNode *p;
    	if(Q->front == Q->rear)
    		return(FALSE);
    	p = Q->front->next;
    	Q->front->next = p->next;
    	if(Q->rear == p)
    		Q->rear = Q->front;
    	*x = p->data;
    	free(p);
    	return (TRUE);
    }
    
    int GetHead(LinkQueue *Q, QueueElementType *x)
    {
         
    	/*提取队列的队头元素，用x返回其值*/
    	//请完成本函数的功能/
    	if(Q->rear == Q->front)
    		return(FALSE);
    	else
    	{
        
    		*x = Q->front->data;
    		return(TRUE);
    	}
    }
    
    
    int DestroyLinkQueue(LinkQueue *Q)
    {
        //销毁一个队列
    	QueueElementType e;
    	while(Q->front!=Q->rear)
    		DeleteQueue(Q,&e);
    	free(Q->front);
    	Q->front=Q->rear=NULL;
    	return OK;
    }
    
    int LinkQueueLength(LinkQueue *Q)
    {
        //队列的长度
    	int i=0;
    	LinkQueueNode * p=Q->front;
    	while(p!=Q->rear){
        
    		++i;
    		p=p->next;
    	}
    	return i;
    }
    
    int DisplayLinkQueue(LinkQueue *Q)
    {
        //显示队列中所有元素
    	LinkQueueNode * p;
    	int i=0;
    	p=Q->front->next;
    	if(p==NULL) printf("队列为空!\n");//队列为空
    	else{
        
    		while(p){
               //否则显示队列中所有元素
    			printf("[%d:%d]",++i,p->data);
    			p=p->next;
    		}
    		printf("\n");
    	}
    	return OK;
    }
    
    void main(){
        
    	LinkQueue LQ;
    	QueueElementType e;
    	int flag=1,ch,len;
    	int temp;
    	printf("本程序实现链式结构队列的操作。\n");
    	printf("可以进行入队列、出队列等操作。\n");
    	InitQueue(&LQ);       //初始化队列
    	while(flag){
        
    		printf("请选择:\n");
    		printf("1.显示队列所有元素\n");
    		printf("2.入队列\n");
    		printf("3.出队列\n");
    		printf("4.求队列的长度\n");
    		printf("5.退出程序\n");
    		scanf("%d",&ch);
    		switch(ch){
        
    		case 1:DisplayLinkQueue(&LQ);   //显示队列中所有元素
    			break;
    		case 2:printf("请输入要人队的元素(一个整数):");
    			scanf("%d",&e);   //输入要入队列的字符
    			EnterQueue(&LQ,e);//入队列
    			DisplayLinkQueue(&LQ);
    			break;
    		case 3:temp=DeleteQueue(&LQ,&e);  //出队列
    			if(temp==TRUE){
        
    				printf("出队一个元素:%d\n",e);
    				DisplayLinkQueue(&LQ);
    			}
    			else printf("队列为空!\n");
    			break;
    		case 4:len=LinkQueueLength(&LQ);
    			printf("队列的长度为:%d\n",len);
    			break;
    		default:flag=0;
    			printf("程序运行结束，按任意键退出!\n");
    			getchar();
    		}
    	}
    	DestroyLinkQueue(&LQ);
    }