数据结构(四)

小灰灰 2022-08-20 10:09 148阅读 0赞

\--接着栈。

栈的算法：出栈

压栈

不管怎么操作，栈都遵循先进后出，出栈是后进来的先出，压栈是先进来的放最底下。

下面是栈的一些算法实现代码：

# include <stdio.h>
    # include <malloc.h>
    # include <stdlib.h>
    
    typedef struct Node
    {
    	int data;
    	struct Node * pNext;
    }NODE,* PNODE;
    
    typedef struct Stack
    {
    	PNODE pTop;
    	PNODE pBottom;
    }STACK,* PSTACK;
    
    //函数声明
    void init(PSTACK pS);//初始化
    void push(PSTACK pS,int val);//压栈
    void traverse(PSTACK pS);//遍历
    bool pop(PSTACK pS,int * pVal);//出栈
    bool clear(PSTACK pS);//清空
    
    int main(void)
    {
    	int val;
    	STACK S;
    	printf("*******压栈******");
    	init(&S);
    	push(&S,1);
    	push(&S,2);
    	push(&S,3);
    	push(&S,4);
    	push(&S,5);
    	push(&S,6);
    	traverse(&S);
    	printf("*******出栈******");
        pop(&S,&val);
        traverse(&S);
    	printf("*******清空******");
    	clear(&S);
    	traverse(&S);
    	return 0;
    }
    
    void init(PSTACK pS)
    {
    	pS->pTop=(PNODE)malloc(sizeof(NODE));
    	if(NULL == pS->pTop)
    	{
    		printf("动态内存分配失败!\n");
    	}
    	else
    	{
    		pS->pBottom = pS->pTop;
    	}
    }
    
    void push(PSTACK pS,int val)
    {
    	PNODE pNew = (PNODE)malloc(sizeof(NODE));
    	pNew->data=val;
    	pNew->pNext=pS->pTop;
    	pS->pTop=pNew;
    	return;
    }
    
    void traverse(PSTACK pS)
    {
    	PNODE p=pS->pTop;
    	printf("\n******遍历*******\n");
    	while(p!=pS->pBottom)
    	{
    		printf("%d   ",p->data);
    		p=p->pNext;
    	}
    	printf("\n");
    	return;
    }
    
    bool empty(PSTACK pS)
    {
    	if(pS->pTop == pS->pBottom)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    
    bool pop(PSTACK pS,int * pVal)
    {
    	if(empty(pS))
    	{
    		return false;
    	}
    	else
    	{
    		PNODE r=pS->pTop;
    		*pVal=r->data;
    		pS->pTop=r->pNext;
    		free(r);
    		r=NULL;
    		return true;
    	}
    }
    
    bool clear(PSTACK pS)
    {
    	if(empty(pS))
    	{
    		return false;
    	}
    	else
    	{
    		PNODE p=pS->pTop;
    		PNODE q=NULL;
    		while(p!=pS->pBottom)
    		{
    			q=p->pNext;
    			free(p);
    			p=q;
    		}
    		pS->pTop=pS->pBottom;
    		return true;
    	}
    }

![Center][]

栈的实际应用：函数调用

中断

表达式求值

内存分配

缓冲处理

迷宫

...

队列：与栈不同，队列是”先进先出“类型的存储结构，而且是从不同口进出。类似火车站，从一个入口进去，从另外一个出口出来。

类型：链式队列

静态队列：通常是循环队列

队列的算法：出队

入队

循环队列的讲解：1.静态队列为什么必须是循环队列

由于队列是“先进先出”，当增加一个元素时，是在rear前添加，删除              一个元素时，是删除front后面的元素。如果队列不循环，在添加和删除时，front和rear的index值都是往上增加的，会造成内存泄漏，所以静态队列必须采用循环队列。比如，一个队列现有6个元素，front是1，rear是6，（第6个是无效的，只是方便操作），增加一个元素7，那么rear就变成7了，删除1，front就变成2，原先front和rear是1和6，现在是2和7，而内存中1和6并没有被释放。

2.循环队列需要几个参数来确定

front

rear

3. 循环队列各个参数的含义

2个参数在不同场合有不同意义:

1.)队列初始化

front 和 rear 的值都是零

2.)队列非空

front代表队列第一个元素

Rear代表队列最后一个有效元素的下一个元素

3.)队列空

front和rear的值相等，但不一定是零（下面简称f和r）