C语言——线性表及其应用（栈和队列）

梦里梦外; 2023-06-21 07:26 36阅读 0赞

## 程序需求 ##

1.初始化顺序栈  
2. 插入元素  
3. 删除栈顶元素  
4. 取栈顶元素  
5. 遍历顺序栈  
6. 置空顺序栈  
7. 初始化并建立链队列  
8. 入链队列  
9. 出链队列  
10. 遍历链队列  
11. 算法的基本思想  
**使用栈和队列的表示方式**  
1.栈作为一种限定性线性表，将线性表的插入与删除操作限制为只在表的一端进行；使用顺序存储结构，利用一组地址连续的存储单元，设置栈顶指针Top来动态的指示栈顶元素在顺序栈中的位置，Top=-1表示空栈；  
2.队列只允许在表的一端插入元素，而在另一端进行删除元素，具有先进先出的特性；用链表表示的队列叫做链队列，设置队头指针front，队尾指针rear；

## 1.栈 ##

**栈流程：**  
1.初始化顺序栈  
2.输入元素进行入栈  
3.删除栈顶元素  
4.得到此时栈顶元素  
5.遍历顺序栈  
6.置空顺序栈  
7.此时再次遍历顺序栈判断是否置空成功

#include<stdio.h>
    #include<stdlib.h>
    
    
    //顺序栈存储结构
    #define StackSize 50
    typedef struct
    {
        
    	int elem[StackSize]; //用来存放栈元素的一堆数组
    	int top;//栈顶元素的下标，top=-1表示空栈
    }SeqStack;
    
    
    //初始化顺序栈（清空）
    void InitStack(SeqStack * S)
    {
        
    	S->top=-1;//构造一个空栈
    }
     
    
    //顺序进栈
    int Push(SeqStack * S,int x)
    {
        
    	if(S->top == StackSize-1) return 0;//栈已满
    	S->top++;//修改栈顶指针
    	S->elem[S->top]=x;//x进栈
    	return 1;
    }
    
    //读栈
    void PrintStack(SeqStack *S)
    {
        
    	if(S->top == -1)
    		printf("栈为空！\n");
    	while(S->top!=-1)
    	{
        
    		printf("%d  ",S->elem[S->top]);
    		S->top--;
    	}
    }
    
    //出栈
    int Pop(SeqStack * S,int * x) 
    {
        
    	if(S->top == -1)
    		printf("栈为空！\n");//栈为空
    	else
    	{
        
    		* x =S->elem[S->top];//栈顶元素赋值给x
    		S->top--;//修改栈顶指针
    		return 1;
    	}
    }
    
    
    //读栈顶
    int GetTop(SeqStack * S,int * x )
    {
        
    
    	if(S->top == -1)
    		printf("栈为空！\n");//栈为空
    	else
    	{
        
    		
    		* x = S->elem[S->top];//栈顶元素赋值给x
    		return *x;
    	}
    }
    
    
    //主函数
    int main()
    {
        
    	SeqStack S;
        InitStack(&S);//初始化顺序栈
    	printf("请输入需要入栈的数据元素：\n");
    	int i,x,y;
    	for(i=0;i<StackSize;i++)
    	{
        
    		scanf("%d",&x);
    		y=Push(&S,x);//入栈
    		if(getchar() == ' ')
    			continue;
    		else 
    			break;
    	}
    		if(y == 0)
    		printf("栈已满，插入失败!\n");
    	else
    		printf("入栈成功!\n");
    		
    	    Pop(&S,&x);//出栈
            printf("栈顶元素删除成功！\n");
    		printf("此时栈顶元素为：%d\n",GetTop(&S,&x));//读栈顶
    		printf("这个栈为：\n");
            PrintStack(&S);
    	    printf("\n");
    		InitStack(&S);//置空栈
         	printf("置空完成！\n");
    		printf("再次进行读栈:\n");
    		PrintStack(&S);//再次进行读栈确定是否置空成功
    	    return 0;
    }

**输入和输出的格式**  
1.输入需要入栈的数据元素  
2.自动删除栈顶元素  
3.输出栈顶元素  
4.输出栈遍历  
5.进行栈的置空，判断是否置空成功  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]

## 2.队列 ##

**队列流程：**  
1.初始化并建立链队列  
2.输入元素进行入队  
3.出队队头元素  
4.进行遍历队列

#include<stdio.h>
    #include<stdlib.h>
    
     typedef struct Node
    {
        
    	 
    	int data; //数据域
    	struct Node * next;//指针域
    }LinkQueueNode;
    
     typedef struct 
    {
        
    	LinkQueueNode *front;
    	LinkQueueNode *rear;
    
    }LinkQueue;
    
    
    //链队列初始化如下
    int InitQueue(LinkQueue * Q)
    {
        
    	Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));//初始化空队列
    	if(Q->front != NULL)
    	{
        Q->rear=Q->front;
    	Q->front->next=NULL;
    	return 1;
    	}
    	else
    		printf("溢出!\n");
    }
    
    
    //链队列入队如下
    int EnterQueue(LinkQueue *Q,int 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 1;
    	}
    	else 
    		printf("溢出!\n");
    
    }
    
    
    //链队列出队如下
    int DeleteQueue(LinkQueue * Q,int * x)
    {
        //将队列Q队列头出队，并且存放到x所指的存储空间中
    	LinkQueueNode *p;
    	if(Q->front==Q->rear)
    		printf("链队列为空!\n");
    	p=Q->front->next;
    	Q->front->next=p->next;//队列头元素出队
    
    	if(Q->rear== p)
    	{
        
            Q->front=Q->rear;
            printf("链队列为空!\n");//如果队列中只有一个元素，出队之后队列为空
    	}
    	* x = p->data;
    	free(p);//释放存储空间
    	return 1;
    }
    
    
    //遍历队列如下
    void TraverseQueue(LinkQueue * Q)
    {
        
    	LinkQueueNode *p;//建立结点p的目的是为了保护链式队列的结构，通过结点p来完成队列的遍历
    	p = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    	p = Q->front;
    	while(p != Q->rear)
    	{
        
    		printf("%d  ",p->next->data);
    		p = p->next;
    	}
    	printf("\n遍历成功!\n");
    	free(p);
    }
    
    
    //主函数如下
    int main()
    {
        
    	LinkQueue S;
    	InitQueue(&S);//初始化并建立链队列
    	printf("请输入需要入队的元素:\n");
    int i,x;
    for(i=0;i<100;i++)
    {
        
    	scanf("%d",&x);
    	EnterQueue(&S,x);//入链队列
    	if(getchar() == ' ')
    			continue;
    		else 
    			break;
    }
    printf("入队成功!\n");
    DeleteQueue(&S,&x);//出链队列
    printf("出队元素为:%d\n",x);//出队的队顶元素
    printf("出队成功!\n");
    printf("此时这个队列为:\n");//遍历队列
    TraverseQueue(&S);
    return 0;
    }

**输入和输出的格式**  
1.输入需要入队的数据元素  
2.自动进行出队，队头元素出队  
3.输出出队元素  
4.输出队列遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191211183413707.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191211183606705.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70