Linux与数据结构 2019-3-10 上午

1.栈与队列

1.1 栈的实际应用

1.递归函数就有栈的使用，递归函数中调用自身函数的那一行代码下的所有代码将被压入栈中；

1.2 Fibonacci 数列的递归方式

#include<stdio.h>

int Fibonacci(int nNum)
{
	if(nNum == 1 || nNum == 2)return 1;

	if(nNum <= 0)return -1;

	return Fibonacci(nNum-1)+Fibonacci(nNum-2);
}


int main()
{
	printf("%d\n",Fibonacci1(50));
	return 0;
}

1.3 我们发现当我们给函数传入的参数大于45之后，程序的执行速度明显下降，因此我们对其进行优化

1.我们从头开始往后加，加的次数即为传入的参数；

int Fibonacci2(int n)
{
	if(n == 1||n ==2)return 1;
	if(n <= 0)return -1;

	int fn1;
	int fn2;
	int fn;
	fn1 = 1;
	fn2 = 1;
	int i;
	for(i= 3;i<=n;i++)
	{
		fn = fn1+fn2;

		fn2 = fn1;
		fn1 = fn;
	}

	return fn;
}

1.4 四则运算：栈的实际应用

1.说到四则运算与栈，就少不了前缀表达式、中缀表达式以及后缀表达式，这三种表达式是指计算机在处理时的方法；
2.对于 3+4 这样的简单加法，其前缀表达式为： + 3 4 ；
3.对于 3+4 这样的简单加法，其中缀表达式即为其本省： 3 + 4；
4.对于 3+4 这样的简单加法，其后缀表达式为： 3 4 + ；
5.中缀表达式转换为后缀表达式的口诀：
1).借助辅助栈，遇到数字或字符直接打印；
2).遇到符号将当前符号优先级与栈顶元素优先级进行比较，若当前符号优先级高则直接出栈；若当前符号优先级较低，则栈内元素依次出栈，直到出栈的符号比当前符号优先级低为止，再将当前元素压入栈内；遇到左括号，无条件入栈；遇到右括号，则将栈内元素依次输出，知道遇见左括号为止；
6.后缀表达式转换为中缀表达式的口诀：
借助辅助栈，遇到数字或字符直接入栈，遇到符号将栈顶元素的下一个与栈顶元素构成表达式；

1.5 队列

1.队列也成 FIFO ；
2.循环队列用连续结构(数组结构)；
3.我们本次只完成 init push pop isempty 这四个函数；

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
	int nValue;
	struct node *pNext;
}Node;

typedef struct queue
{
	int nCount;
	Node *pHead;
	Node *pTail;
}Queue;

void q_Init(Queue **pQueue)
{
	*pQueue = (Queue*)malloc(sizeof(Queue));
	(*pQueue)->nCount = 0;
	(*pQueue)->pHead = NULL;
	(*pQueue)->pTail = NULL;
}

void q_Push(Queue *pQueue,int nNum)
{
	if(pQueue == NULL)return;

	Node *pTemp = NULL;
	pTemp = (Node*)malloc(sizeof(Node));
	pTemp->nValue = nNum;
	pTemp->pNext = NULL;

	//尾添加
	if(pQueue->pHead == NULL)
	{
		pQueue->pHead = pTemp;
	}
	else
	{
		pQueue->pTail->pNext = pTemp;
	}
	pQueue->pTail = pTemp;
	pQueue->nCount++;
}

int q_Pop(Queue *pQueue)
{
	if(pQueue == NULL || pQueue->nCount == 0)return -1;

	int nNum;
	Node *pDel = NULL;
	pDel = pQueue->pHead;
	nNum = pDel->nValue;

	pQueue->pHead = pQueue->pHead->pNext;

	free(pDel);
	pDel = NULL;

	pQueue->nCount--;

	if(pQueue->nCount == 0)
	{
		pQueue->pTail = NULL;
	}

	return nNum;
}

int q_IsEmpty(Queue *pQueue)
{
	if(pQueue== NULL)exit(1);

	return pQueue->nCount == 0?1:0;
}


int main()
{
	Queue *pQueue = NULL;
	q_Init(&pQueue);

	q_Push(pQueue,1);
	q_Push(pQueue,2);
	q_Push(pQueue,3);
	q_Push(pQueue,4);

	printf("%d\n",q_Pop(pQueue));
	printf("%d\n",q_Pop(pQueue));
	printf("%d\n",q_Pop(pQueue));
	printf("%d\n",q_Pop(pQueue));
	return 0;
}