当前位置：首页 > backend >正文

数据结构--栈和队列

backend 2025/6/19 11:42:27

链栈

头文件

#ifndef __LINKS_H__
#define __LINKS_H__
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{int data;struct node *next;
}node,*node_p;
//1、创建结点
node_p create_node(int value);
//2、判空
int empty_stack(node_p S);
//3、入栈
void push_stack(node_p *S,int value);
//4、出栈
int pop_stack(node_p *S);#endif

主函数文件

#include "links.h"
int main()
{//申请栈顶指针初始值为NULL//刚申请栈顶指针时，栈中没有元素node_p S = NULL;push_stack(&S,12);push_stack(&S,90);printf("%d\n",pop_stack(&S));push_stack(&S,26);printf("%d\n",pop_stack(&S));printf("%d\n",pop_stack(&S));return 0;
}

功能函数文件

#include "links.h"
//1、创建结点
node_p create_node(int value)
{node_p new = (node_p)malloc(sizeof(node));if(new==NULL){return NULL;}new->next = NULL;new->data = value;return new;
}
//2、判空
int empty_stack(node_p S)
{return S==NULL;
}
//3、入栈
//入栈操作需要修改主函数中栈顶指针的指向
void push_stack(node_p *S,int value)
{//S是一个二级指针，保存主函数内栈顶指针的地址if(S==NULL){return;}//不用判断*S,因为如果*S==NULL说明栈中没有元素node_p new = create_node(value);new->next = *S;  //新结点指向原来的栈顶元素*S = new;   //让主函数中的栈顶指针S指向新的栈顶结点
}
//4、出栈
int pop_stack(node_p *S)
{if(*S==NULL){return -1;}if(empty_stack(*S)){return -2;}int ret = (*S)->data;node_p del = *S;   //先保存栈顶结点*S = (*S)->next;     //让栈顶指针向后指一个结点free(del);   //释放栈顶元素return ret;
}

makefile文件

EXE=link_stack
Objs=$(patsubst %.c,%.o,$(wildcard *.c))
CC=gcc
CFlags=-c -oall:$(EXE)
$(EXE):$(Objs)                                 $(CC) $^ -o $@
%.o:%.c$(CC) $^ $(CFlags) $@
.PHONY:clean
clean:rm *.o $(Objs)

1.什么是计算机的大小端存储：

大端存储（Big Endian）
定义：将数据的高位字节存于低地址，低位字节存于高地址，即 “高字节在前”。
类比：类似人类阅读习惯（从左到右读高位），如数字 “1234” 写作 “12 34”。

小端存储（Little Endian）
定义：将数据的低位字节存于低地址，高位字节存于高地址，即 “低字节在前”。
类比：类似逆序存储，如数字 “1234” 写作 “34 12”。如何判断大小端存

维度大端存储（Big Endian）小端存储（Little Endian）
存储顺序 高位字节→低位字节（从低地址到高地址）低位字节→高位字节（从低地址到高地址）
逻辑顺序 与数据的二进制表示顺序一致与数据的二进制表示顺序相反
典型场景 网络协议、PowerPC/MIPS 架构、BMP 文件 x86/AMD64 架构、ARM（默认）、PE 文件
访问效率 需按字节顺序读取，可能增加处理开销低地址优先访问，符合 CPU 缓存预取策略

维度	大端存储（Big Endian）	小端存储（Little Endian）
存储顺序	高位字节→低位字节（从低地址到高地址）	低位字节→高位字节（从低地址到高地址）
逻辑顺序	与数据的二进制表示顺序一致	与数据的二进制表示顺序相反
典型场景	网络协议、PowerPC/MIPS 架构、BMP 文件	x86/AMD64 架构、ARM（默认）、PE 文件
访问效率	需按字节顺序读取，可能增加处理开销	低地址优先访问，符合 CPU 缓存预取策略

2.如何判断大小端存储
#include <stdio.h>int isLittleEndian() {unsigned int num = 1;  // 0x00000001 (32位整数)unsigned char* ptr = (unsigned char*)&num;  // 指向最低地址字节// 小端：低字节在前 -> 第一个字节是0x01// 大端：高字节在前 -> 第一个字节是0x00return (*ptr == 1);
}int main() {if (isLittleEndian()) {printf("小端存储（低字节在前）\n");} else {printf("大端存储（高字节在前）\n");}return 0;
}
通过将整数的地址强制转换为字符指针，访问第一个字节的值：
原理：

小端存储（如 x86）中，0x00000001 的内存布局为 0x01 0x00 0x00 0x00，最低地址字节是 0x01。
大端存储中，内存布局为 0x00 0x00 0x00 0x01，最低地址字节是 0x00。

3.arr和&arr的区别

arr：数组首元素的地址，指向第一个元素 arr[0]。
&arr: 整个数组的地址，指向包含 N 个元素的数组。

4.解释数组指针、指针数组、函数指针和指针函数的区别

一、数组指针（指向数组的指针）
定义
指向整个数组的指针，类型为 type (*)[N]，其中 N 是数组长度。
二、指针数组（元素为指针的数组）
定义
数组的每个元素都是指针，类型为 type* arr[N]，其中 N 是数组长度。
三、函数指针（指向函数的指针）
定义
指向函数的指针，可用于动态调用函数。类型为 return_type (*)(parameter_types)。
四、指针函数（返回指针的函数）
定义
返回值为指针的函数，本质是函数，类型为 type* func(params)。