全部栏目

首页 热点资讯 义务教育 高等教育 出国留学 考研考公
您的当前位置：首页数据结构之一对一（完结）

数据结构之一对一（完结）

2024-12-14 来源：哗拓教育

为什么同一结构,在不同平台大小不同?
因为:

  • 不同平台上相同类型所占(内存)字节不同
  • 不同平台对齐方式不一样

#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;

}
显示全文