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

[计算机科学#14]:数据结构

news 来源：原创 2025/7/17 8:37:03

[LOGO]:CoreKSets

【核知坊】：释放青春想象，码动全新视野。

我们希望使用精简的信息传达知识的骨架，启发创造者开启创造之路！！！

内容摘要：数据结构是计算机科学中的核心概念，用于组织和管理数据。通过选择合适的数据结构，可以有效地表示和抽象现实世界中的复杂对象，提升程序的运行效率和可维护性。常见的数据结构包括数组、链表、栈、队列、树、图等，它们在不同的应用场景中扮演着关键角色。

关键词：数据结构

其他相关文章：

[计算机科学#13]:算法-CSDN博客

https://blog.csdn.net/weixin_64094522/article/details/147838154

https://blog.csdn.net/weixin_64094522/article/details/147806265

数字（Number）

数字在编程中通常表示整数、浮点数或其他数值类型。编译器通常会进行一些内存优化，减少占用。常量折叠，编译阶段直接计算常量表达式的结果，减少运行时开销。寄存器分配，将频繁使用的数值保存在寄存器中，减少内存访问。位运算优化，如果是二进制数字（如 0b11001），编译器可将加减乘除转换为更高效的位操作。

 a = 1         # 整数 intb = 3.14      # 浮点数 floatc = 0b11001   # 二进制整数（十进制等于25）# 内存优化a,b = 122222,122222id(a)#50728928id(b)#50728928

字符（Char）

字符是一个占一个字节（8位）的基本数据类型，通常表示一个符号或数字的ASCII编码（或Unicode编码的最小单位）。每个字符实质是一个整数（ASCII/Unicode编码），例如 'a' 是97，'1' 是49。编译器通常会进行一些内存优化，减少占用。字符常量内联，直接用 ASCII 值替换字符，提升运算效率。字符串池，相同字符或短字符串常量在内存中只保留一份引用。紧凑内存布局，在结构体或数组中，编译器可通过内存对齐规则将 char 类型数据高效打包，避免浪费空间。

 a = 'a'    # 字符 'a'，ASCII值为97b = '1'    # 字符 '1'，ASCII值为49# 内存优化a = 'a'b = 'a'id(a) == id(b)#Trueord('a')97ord('1')49ord('!')33chr(97)'a'chr(49)'1'chr(33)#'!'

数组（Array）

一组按顺序排列、类型相同的元素集合，支持下标访问。大多数的编程语言数组下标都是以 0 开始的，最后一个下标是数组长度-1。

python中的数组类似列表：

 num_array = [12,13,56,78,546,3]len(num_array)#6num_array[2]#56num_array[0]#12num_array[6-1]#3num_array[1]=111num_array#[12, 111, 56, 78, 546, 3]print(id(num_array[0]),id(num_array[1]),id(num_array[2]))# 170507390_2160 170507390_5328 170507390_3568char_array = ['1','b','b','1']print(id(char_array[0]),id(char_array[1]),id(char_array[2]),id(char_array[3]))# 1705075244592 1705075067568 1705075067568 1705075244592char_array = [11,'ppb',"dd",11]print(id(char_array[0]),id(char_array[1]),id(char_array[2]),id(char_array[3]))# 1705073902128 1705075545008 1705075545072 1705073902128

字符串（String）

字符数组的封装，用于表示文本，通常支持拼接、查找、切片等操作。

 char_str = "apple!"char_array = ['a','p','p','l','e','!']char_array[0]#'a'char_str[0]#'a'char_array[0:4]#['a', 'p', 'p', 'l']char_str[0:4]#'appl'len(char_array)#6len(char_str)#6

矩阵（Matrix）

本质上就是二维数组的扩展，用于数学计算、图像处理等。

 num_matrix=[[12,13,56],[34,344,23],[7,4,234]]num_matrix[1][1]#344num_matrix[1][2]#23len(num_matrix)#3len(num_matrix[0])#3num_matrix[0]#[12, 13, 56]

结构体（Struct）

一种复合数据类型，用于将多个不同类型的数据组合在一起。常见的形式在C语言，Python里没有这个结构体关键词，一般用类代替。

 struct Person {char name[5];int age;};// 初始化一个p1struct Person p1;  // 或者 typedef 简化：typedef struct Person {char name[50];int age;} Person;Person p2;  // 现在可以省略 struct 关键字Person p = {"Alice", 25};//嵌套结构体struct Date {int year, month, day;};struct Student {char name[20];struct Date birth;};

指针（Pointer）

指针是存储变量“地址”的变量，它本身并不存储具体的值，而是指向内存中另一个变量的位置。是 C/C++ 中实现动态数据结构（如链表、树、图）和内存操作的基础。

 int a = 10;int *p = &a;  // 定义一个整型指针 p，指向变量 a 的地址

类型	示例	描述
整型指针	`int *p`	指向整型变量的地址
字符型指针	`char *str`	字符串（C 风格）或字符的地址
指针数组	`int *arr[5]`	数组中每个元素是一个指针
指向指针的指针	`int **pp`	存放另一个指针变量的地址
结构体指针	`struct Node *n`	用于链表、树等结构

在 Python 中没有传统意义上的“指针”（像 C/C++ 的 int*、&a 那样的语法），但 Python 一切皆对象，所有变量本质上都是对象的引用（reference），这就起到了“类似指针”的作用。

 a = [1, 2, 3]b=a  # 将a的引用赋值给bb[0] = 33 # 相当于a[0] = 33a# [33, 2, 3]

链表（Linked List）

链表是一种动态数据结构，由一系列节点（Node）通过“指针”连接起来。不同于数组，链表的内存不是连续的。

节点（Node）

数据结构中的基本单位，通常包含数据域和指针域。每个节点包含两个部分：数据域，存储数据；指针域，指向下一个节点的地址。

C/C++中使用结构体表示：

 struct Node {int data;struct Node* next;};

python中使用类表示：

 class Node:def __init__(self, data):self.data = dataself.next = None

单向链表

每个节点只指向下一个节点，插入删除效率高，不需整体移动元素，不能反向访问。

  struct Node {int data;struct Node* next;};// 创建节点struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));node1->data = 10; node1->next = node2;node2->data = 20; node2->next = node3;node3->data = 30; node3->next = NULL;

双向链表

每个节点有两个指针，分别指向前一个和后一个节点，双向遍历更灵活，占用更多空间

 struct DNode {int data;struct DNode* prev;struct DNode* next;};// 创建节点struct DNode* node1 = (struct DNode*)malloc(sizeof(struct DNode));struct DNode* node2 = (struct DNode*)malloc(sizeof(struct DNode));struct DNode* node3 = (struct DNode*)malloc(sizeof(struct DNode));node1->data = 10; node1->prev = NULL; node1->next = node2;node2->data = 20; node2->prev = node1; node2->next = node3;node3->data = 30; node3->prev = node2; node3->next = NULL;

环形链表

单项链表，最后一个节点指向第一个节点，形成一个闭环结构。

 struct CNode {int data;struct CNode* next;};// 创建节点struct CNode* node1 = (struct CNode*)malloc(sizeof(struct CNode));struct CNode* node2 = (struct CNode*)malloc(sizeof(struct CNode));struct CNode* node3 = (struct CNode*)malloc(sizeof(struct CNode));node1->data = 10; node1->next = node2;node2->data = 20; node2->next = node3;node3->data = 30; node3->next = node1;  // 最后一个节点指向第一个，形成环

队列（Queue）

在 C语言中，队列（Queue）是一种先进先出（FIFO）*的数据结构，常用于*任务调度、缓冲区管理、广度优先搜索（BFS）等场景。

struct Queue {int data[SIZE];int front;int rear;};// 初始化队列void initQueue(struct Queue *q) {q->front = 0;q->rear = 0;}// 判断队列是否为空int isEmpty(struct Queue *q) {return q->front == q->rear;}// 判断队列是否满int isFull(struct Queue *q) {return (q->rear + 1) % SIZE == q->front;}// 入队void enqueue(struct Queue *q, int value) {if (isFull(q)) {printf("Queue is full!\n");return;}q->data[q->rear] = value;q->rear = (q->rear + 1) % SIZE;}// 出队int dequeue(struct Queue *q) {if (isEmpty(q)) {printf("Queue is empty!\n");return -1;}int val = q->data[q->front];q->front = (q->front + 1) % SIZE;return val;}struct Queue q;initQueue(&q);enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);

栈（Stack）

在 C语言中，栈（Stack）是一种 后进先出（LIFO） 的数据结构。常用于函数调用、括号匹配、表达式求值、撤销操作等场景。

 struct Stack {int data[SIZE];int top;};// 初始化栈void initStack(struct Stack *s) {s->top = -1;}// 判断是否为空int isEmpty(struct Stack *s) {return s->top == -1;}// 判断是否满int isFull(struct Stack *s) {return s->top == SIZE - 1;}// 入栈void push(struct Stack *s, int value) {if (isFull(s)) {printf("Stack overflow!\n");return;}s->data[++(s->top)] = value;}// 出栈int pop(struct Stack *s) {if (isEmpty(s)) {printf("Stack underflow!\n");return -1;}return s->data[(s->top)--];}// 查看栈顶元素int peek(struct Stack *s) {if (isEmpty(s)) {printf("Stack is empty!\n");return -1;}return s->data[s->top];}struct Stack s;initStack(&s);push(&s, 10);push(&s, 20);push(&s, 30);