个人介绍及问题解决
系统按照最大数据类型对齐;
为什么同一结构,在不同平台大小不同?
因为:
- 不同平台上相同类型所占(内存)字节不同
- 不同平台对齐方式不一样
#pragma pack(1):系统按照一个字节对齐。
1
struct Node
{
int a;
short b;
char c;
short d;
}
小端存储:低字节写在低地址里
联合体内所有变量共用同一块地址空间
全局变量和静态变量默认初始化为0
数据结构有几种结构？
集合，一对一，一对多，多对多。四种！
OneByOne(一对一)
---------------------------------------------------------------------------------------------
元素同属一个集合,前后元素有关系并单向
例如:线性表:
一个表里面元素a1到aN,a1没有直接前驱有且仅有一个直接后继,ai作为中间元素,有且仅有一个直接前驱
和一个直接后继,aN作为表的尾元素,没有直接后继,有且仅有一个直接前驱直接前驱也叫直接前件
线性表的两种储存结构
- 顺序储存→数组
- 链式储存→链表
递归和循环的优缺点
递归:代码简单,逻辑简单(便于阅读),但是函数跳转浪费时间,函数参数占用空间
循环:相对于递归,节约资源,但是每层循环逻辑必须弄清
stack(栈)
特性:先进后出,且只能操作栈顶
本质:也许是数组,也许是链表
stack
常用栈:单向链表,头添加,头删除
八个基本操作
- Push 添加元素
- Pop 删除元素
- Init 初始化栈
- Clear 清空栈
- Deatroy 销毁栈
- GetCount 获得栈元素个数
- GetTop 得到栈顶
- IsEmpty 判断是否是空栈
#include<stdio.h>
#include<stdlib.h>
typedef struct node1
{
int nValue;
struct node1 *pNext;
}MyStack;
typedef struct node2
{
MyStack *pTop;
int nCount;
}Stack;
//初始化
void s_Init(Stack **pStack)
{
if(pStack == NULL)return;
*pStack = (Stack*)malloc(sizeof(Stack));
(*pStack)->pTop = NULL;
(*pStack)->nCount = 0;
}
//压栈
void s_Push(Stack *pStack,int nNum)
{
MyStack *pTemp = NULL;
if(pStack == NULL)
{
printf("栈没啦!!!\n");
return;
}
//开辟新节点装载值
pTemp = (MyStack*)malloc(sizeof(MyStack));
pTemp->nValue = nNum;
pTemp->pNext = pStack->pTop;
pStack->pTop = pTemp;
pStack->nCount++;
}
//出栈
int s_Pop(Stack *pStack)
{
MyStack *pDel = NULL;
int nNum;
if(pStack == NULL || pStack->pTop == NULL)return -1;
pDel = pStack->pTop;
nNum = pDel->nValue;
pStack->pTop = pStack->pTop->pNext;
free(pDel);
pDel = NULL;
pStack->nCount--;
return nNum;
}
//清空
void s_Clear(Stack *pStack)
{
if(pStack == NULL || pStack->pTop == NULL)return;
while(pStack->nCount)
{
s_Pop(pStack);
}
}
//销毁
void s_Destroy(Stack **pStack)
{
s_Clear(*pStack);
free(*pStack);
*pStack = NULL;
}
//获得栈内元素个数
int s_GetCount(Stack *pStack)
{
if(pStack == NULL)return -1;
return pStack->nCount;
}
//获得栈顶
MyStack *s_GetTop(Stack *pStack)
{
if(pStack == NULL)return NULL;
return pStack->pTop;
}
//是否为空栈
int s_IsEmpty(Stack *pStack)
{
if(pStack == NULL)return -1;
return (pStack->nCount)?0:1;
}
int main()
{
Stack *pStack = NULL;
s_Init(&pStack);
s_Push(pStack,1);
s_Push(pStack,2);
s_Push(pStack,3);
s_Push(pStack,4);
s_Push(pStack,5);
printf("%d\n",s_Pop(pStack));
printf("%d\n",s_Pop(pStack));
printf("-------------------------------------------------\n");
printf("%d\n",s_GetCount(pStack));
s_Destroy(&pStack);
s_Push(pStack,5);
return 0;
}
二级指针的使用:一般是参数无中生有,和从有到无
递归相当于栈的实际应用
因为:解决大问题的方式与其子问题方式一致(定义)
斐波那契数列FIBONACCI
也叫黄金分割数列
#include<stdio.h.>
#include<stdlib.h>
int Fibonacci_1(int n)//迭代法
{
if (n<=2)
{
return 1;
}
return Fibonacci_1(n-1)+Fibonacci_1(n-2);
}
int Fibonacci_2(int n)
{
int i = 3;
int a = 1;
int b = 1;
int c = 0;
if (n<=2)
{
return 1;
}
for ( ;i <=n; i++)
{
c = a+b;
a = b;
b = c;
}
return c;
}
int main()
{
printf("%d\n",Fibonacci_1(10));
printf("%d\n",Fibonacci_2(10));
return 0;
}
四则运算
后缀表达式(逆波兰表示法)。
中缀表示法:例如:19+41*5-7/6,也叫表达式
转换规则
中缀转后缀(官方版)
借助辅助栈,遇到数字或字符直接打印,遇到符号(+ - * /),拿当前符号与栈顶元素进行优先级比较。如果当前元素优先级高直接入栈,如果当前元素优先级低,则直接出栈直到比当前元素优先级比它低的,如果遇到左括号无条件入栈,如果遇到右括号,将栈内元素依次出栈直到左括号停下来,如果没有元素,就将栈内元素全部拿出。
非官方版
所以运算加括号,将运算符放到括号后面。
后缀转中缀
遇到数字或字符直接进栈,遇到符号将栈顶元素下一个和栈顶元素构成表达式。
Queue
实际应用:打印机
特性:先进先出
queue
#include<stdio.h>
#include<stdlib.h>
typedef struct node3
{
int nValue;
struct node3 *pNext;
}MyQueue;
typedef struct node4
{
int nCount;
MyQueue* pHead;
MyQueue *pTail;
}Queue;
void q_Init(Queue **pQueue)
{
if(pQueue == NULL)return;
*pQueue = (Queue*)malloc(sizeof(Queue));
(*pQueue)->nCount = 0;
(*pQueue)->pHead = NULL;
(*pQueue)->pTail = NULL;
}
void q_Push(Queue *pQueue,int nNum)
{
MyQueue *pTemp = NULL;
if(pQueue == NULL)return;
pTemp = (MyQueue*)malloc(sizeof(MyQueue));
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)
{
MyQueue *pDel = NULL;
int nNum;
if(pQueue == NULL || pQueue->pHead == NULL)return -1;
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 )return -1;
return pQueue->nCount ? 0:1;
}
Queue To Stack
用两个Queue(队列)实现Stack(栈)
#include<stdio.h>
#include<stdlib.h>
typedef struct node3
{
int nValue;
struct node3 *pNext;
}MyQueue;
typedef struct node4
{
int nCount;
MyQueue* pHead;
MyQueue *pTail;
}Queue;
typedef struct node
{
Queue *pQueue1;
Queue *pQueue2;
int nCount;
}Stack;
void q_Init(Queue **pQueue)
{
if(pQueue == NULL)return;
*pQueue = (Queue*)malloc(sizeof(Queue));
(*pQueue)->nCount = 0;
(*pQueue)->pHead = NULL;
(*pQueue)->pTail = NULL;
}
void q_Push(Queue *pQueue,int nNum)
{
MyQueue *pTemp = NULL;
if(pQueue == NULL)return;
pTemp = (MyQueue*)malloc(sizeof(MyQueue));
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)
{
MyQueue *pDel = NULL;
int nNum;
if(pQueue == NULL || pQueue->pHead == NULL)return -1;
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 )return -1;
return pQueue->nCount ? 0:1;
}
void s_Init(Stack **pStack)
{
if(pStack == NULL)return;
*pStack = (Stack*)malloc(sizeof(Stack));
(*pStack)->nCount = 0;
(*pStack)->pQueue1 = NULL;
(*pStack)->pQueue2 = NULL;
//初始化两个队列
q_Init(&((*pStack)->pQueue1));
q_Init(&((*pStack)->pQueue2));
}
void s_Push(Stack *pStack,int nNum)
{
MyQueue *pTemp = NULL;
if(pStack == NULL || pStack->pQueue1 == NULL || pStack->pQueue2 == NULL)return;
//将数值放入非空队列
if(!q_IsEmpty(pStack->pQueue1))
{
q_Push(pStack->pQueue1,nNum);
}
else
{
q_Push(pStack->pQueue2,nNum);
}
}
int s_Pop(Stack *pStack)
{
int nNum;
if(pStack == NULL || (pStack->pQueue1 == NULL && pStack->pQueue2 == NULL))return -1;
//检测非空队列
if(!q_IsEmpty(pStack->pQueue1))
{
//将队列元素依次放入空队列里 直到剩一个的时候停下来
while(pStack->pQueue1->nCount != 1)
{
q_Push(pStack->pQueue2, q_Pop(pStack->pQueue1) );
}
nNum = q_Pop(pStack->pQueue1);
}
else
{
//将队列元素依次放入空队列里 直到剩一个的时候停下来
while(pStack->pQueue2->nCount != 1)
{
q_Push(pStack->pQueue1, q_Pop(pStack->pQueue2) );
}
nNum = q_Pop(pStack->pQueue2);
}
return nNum;
}
Stack To Queue
用两个栈实现队列
#include<stdio.h>
#include<stdlib.h>
typedef struct node1
{
int nValue;
struct node1 *pNext;
}MyStack;
typedef struct node2
{
MyStack *pTop;
int nCount;
}Stack;
typedef struct node3
{
Stack *Mystack_1;
Stack *Mystack_2;
int nCount;
}MyQueue;
//初始化
void s_Init(Stack **pStack)
{
if(pStack == NULL)return;
*pStack = (Stack*)malloc(sizeof(Stack));
(*pStack)->pTop = NULL;
(*pStack)->nCount = 0;
}
//压栈
void s_Push(Stack *pStack,int nNum)
{
MyStack *pTemp = NULL;
if(pStack == NULL)
{
printf("栈没啦!!!\n");
return;
}
//开辟新节点装载值
pTemp = (MyStack*)malloc(sizeof(MyStack));
pTemp->nValue = nNum;
pTemp->pNext = pStack->pTop;
pStack->pTop = pTemp;
pStack->nCount++;
}
//出栈
int s_Pop(Stack *pStack)
{
MyStack *pDel = NULL;
int nNum;
if(pStack == NULL || pStack->pTop == NULL)return -1;
pDel = pStack->pTop;
nNum = pDel->nValue;
pStack->pTop = pStack->pTop->pNext;
free(pDel);
pDel = NULL;
pStack->nCount--;
return nNum;
}
//是否为空栈
int s_IsEmpty(Stack *pStack)
{
if(pStack == NULL)return -1;
return (pStack->nCount)?0:1;
}
void q_Init(MyQueue **queue)
{
if (queue == NULL )return;
(*queue) = (MyQueue*)malloc(sizeof(MyQueue));
(*queue)->Mystack_1 = NULL;
(*queue)->Mystack_2 = NULL;
s_Init(&(*queue)->Mystack_2);
s_Init(&(*queue)->Mystack_1);
(*queue)->nCount = 0;
}
void q_Push(MyQueue *queue,int nValue)
{
s_Push(queue->Mystack_2,nValue);
return;
}
int q_Pop(MyQueue *queue)
{
int num;
if (s_IsEmpty((queue)->Mystack_1))
{
while (queue->Mystack_2->nCount != 1)
{
s_Push((queue)->Mystack_1,s_Pop((queue)->Mystack_2));
}
num = s_Pop((queue)->Mystack_2);
while (queue->Mystack_1->nCount != 0)
{
s_Push((queue)->Mystack_2,s_Pop((queue)->Mystack_1));
}
}
return num;
}
