最权威的网站推广公司,wordpress 微信导航菜单,wordpress实时聊天,专业seo站长工具目录 一、数组#xff08;Array#xff09;
二、链表#xff08;Linked List#xff09;
三、栈#xff08;Stack#xff09;
四、总结 数据结构是算法的基石#xff0c;是程序设计的核心基础。不同的数据结构适用于不同的场景和需求#xff0c;选择合适的数据结构能…目录 一、数组Array
二、链表Linked List
三、栈Stack
四、总结 数据结构是算法的基石是程序设计的核心基础。不同的数据结构适用于不同的场景和需求选择合适的数据结构能显著提升程序的效率和可读性。在众多的数据结构中数组、链表和栈是最基本、最常用的三种。它们各具特色不仅应用广泛也是更复杂数据结构的基础。
一、数组Array
1. 什么是数组
数组是一种用于存储一组具有相同数据类型元素的数据结构。这些元素在内存中按照顺序连续存储可以通过索引访问每个元素。
定义 int arr[5]; // 定义一个包含5个整数的数组 特点
连续存储所有元素占用的内存是连续的。
固定大小数组声明后其大小不能改变。
快速访问可以通过索引快速访问任意元素时间复杂度为 O(1)O(1)O(1)。
类型一致性数组中的元素必须是相同的数据类型。
2. 数组的内存布局
数组在内存中是连续分配的。假设一个数组存储在地址 0x1000 开始并且元素大小为 4 字节则
第一个元素的地址为 0x1000
第二个元素的地址为 0x1004
第 n 个元素的地址计算公式 元素地址基地址(索引×元素大小)
示例
int arr[3] {1, 2, 3};
// 内存布局:
// 0x1000: 1
// 0x1004: 2
// 0x1008: 33. 数组的基本操作
3.1 声明与初始化
静态声明
int arr[5]; // 声明大小为5的整型数组
int arr[5] {1, 2, 3}; // 部分初始化未赋值的元素默认为0
int arr[] {4, 5, 6}; // 根据初始化列表自动推断大小动态分配
int *arr (int *)malloc(sizeof(int) * 5); // 动态分配大小为5的整型数组3.2 访问与修改
数组元素通过索引访问索引从0开始
int arr[3] {10, 20, 30};
arr[1] 40; // 修改第二个元素
printf(%d, arr[1]); // 输出403.3 遍历数组
使用循环遍历
for (int i 0; i 5; i) {printf(%d , arr[i]);
}4. 数组的种类
4.1 一维数组
最简单的数组类型用来表示线性数据结构。
int arr[5] {1, 2, 3, 4, 5};4.2 多维数组
用于表示多维数据如矩阵。
int matrix[3][3] {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};
printf(%d, matrix[1][2]); // 输出64.3 动态数组
通过指针动态分配内存的数组。
int *arr (int *)malloc(sizeof(int) * 5);
// 使用完成后记得释放内存
free(arr);5. 数组的优缺点
优点
快速访问通过索引可以直接访问任意元素。存储效率高由于元素连续存储硬件可以高效缓存和访问。简单易用语法简单操作直观。
缺点
大小固定声明后无法动态扩展或收缩。插入与删除效率低需要移动大量元素。内存连续性要求高对于大数组可能会因内存碎片而分配失败。
6. 数组的应用场景与注意事项
数据存储与排序适合存储大小固定的数据并对其进行排序操作。快速索引场景如哈希表中的直接寻址。矩阵操作如图像处理中的像素存储。实现其他数据结构如栈、队列和字符串。
注意事项
数组越界访问索引超出范围会导致未定义行为。内存管理动态数组需要手动释放分配的内存。性能优化频繁的插入或删除操作不适合使用数组。 7. 数组与其他数据结构的对比 8.小结
数组是一种高效的、简单的数据结构适用于存储固定大小的数据并进行快速访问。然而其固定大小和插入删除效率低的限制在一些动态需求下需要其他数据结构如链表、动态数组替代。深入理解数组的特性和限制可以帮助我们更好地在实际开发中合理使用这一基本工具。
二、链表Linked List
1. 什么是链表
链表是一种动态数据结构由多个节点Node按线性顺序链接而成。每个节点包含两个部分
数据域Data存储节点的数据。指针域Next存储指向下一个节点的地址。
链表通过指针连接形成一个线性结构常用于需要频繁插入或删除操作的场景。
节点结构
struct Node {int data; // 数据域struct Node *next; // 指针域
};2. 链表的分类
2.1 单向链表Singly Linked List
每个节点只有一个指针指向下一个节点。
最后一个节点的指针为 NULL表示链表结束。
示例
Head - [Data | Next] - [Data | Next] - NULL2.2 双向链表Doubly Linked List
每个节点包含两个指针一个指向前驱节点一个指向后继节点。
可以从任意节点向前或向后遍历。
示例
NULL - [Prev | Data | Next] - [Prev | Data | Next] - NULL2.3 循环链表Circular Linked List
链表的最后一个节点指向头节点使链表形成一个环。可为单向或双向。
示例
[Data | Next] - [Data | Next] - [Data | Next] - ...↑----------------------------------------↑3. 链表的基本操作
3.1 创建链表
通过动态分配内存创建节点并将节点链接起来。
struct Node* createNode(int value) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node));newNode-data value;newNode-next NULL;return newNode;
}3.2 插入节点
头插法在链表头部插入节点。 void insertAtHead(struct Node** head, int value) {struct Node* newNode createNode(value);newNode-next *head;*head newNode;
}尾插法在链表尾部插入节点。 void insertAtTail(struct Node** head, int value) {struct Node* newNode createNode(value);if (*head NULL) {*head newNode;return;}struct Node* temp *head;while (temp-next ! NULL) {temp temp-next;}temp-next newNode;
}3.3 删除节点
按值删除 void deleteByValue(struct Node** head, int value) {struct Node* temp *head;struct Node* prev NULL;// 若删除头节点if (temp ! NULL temp-data value) {*head temp-next;free(temp);return;}// 查找要删除的节点while (temp ! NULL temp-data ! value) {prev temp;temp temp-next;}if (temp NULL) return; // 值不存在// 重新链接并释放内存prev-next temp-next;free(temp);
}3.4 遍历链表
void traverse(struct Node* head) {while (head ! NULL) {printf(%d - , head-data);head head-next;}printf(NULL\n);
}3.5 反转链表
struct Node* reverseList(struct Node* head) {struct Node* prev NULL;struct Node* current head;struct Node* next NULL;while (current ! NULL) {next current-next;current-next prev;prev current;current next;}return prev;
}4. 链表的优缺点
优点
动态大小不需要预先分配固定大小可以动态增减节点。高效插入与删除不需要移动其他元素时间复杂度为 O(1)O(1)。节省内存适合存储大小不确定的数据。
缺点
随机访问效率低无法通过索引直接访问元素需从头遍历时间复杂度为 O(n)O(n)。额外内存开销每个节点都需要存储指针。实现复杂性高操作链表需要处理指针容易引发错误如野指针、内存泄漏等。
5. 链表的使用场景
动态内存需求如实现队列、栈、哈希表等需要动态扩展的结构。频繁插入与删除如处理任务队列、缓冲区。内存碎片化环境连续存储难以满足时链表可以更好地利用内存。 6. 链表与数组的对比 7. 注意事项
内存管理动态分配的内存需要手动释放防止内存泄漏。指针处理链表操作需要谨慎处理指针避免野指针或空指针。遍历复杂度链表不适合需要频繁访问特定位置的场景。
8.小结
链表作为一种灵活且动态的数据结构在处理动态数据、内存碎片化环境中非常实用。通过理解其基本操作与优缺点开发者可以在合适的场景中高效地使用链表。同时链表的概念是进一步学习更复杂数据结构如树和图的基础非常重要。
三、栈Stack
1. 什么是栈
栈是一种抽象数据类型遵循后进先出LIFO, Last In First Out**的线性数据结构。栈中的数据只能通过一端进行插入和删除这一端被称为栈顶Top。
栈顶Top表示栈中最新加入的元素。
栈底Bottom表示栈中最早加入的元素。
关键操作
入栈Push将数据插入栈顶。
出栈Pop从栈顶删除数据。
查看栈顶元素Peek/Top访问栈顶数据但不删除。
2. 栈的实现
2.1 使用数组实现栈
栈可以通过数组来实现栈顶通过数组的索引表示。
示例代码
#include stdio.h
#include stdlib.h
#define MAX 100typedef struct Stack {int arr[MAX];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack-top -1;
}// 入栈
void push(Stack* stack, int value) {if (stack-top MAX - 1) {printf(Stack Overflow\n);return;}stack-arr[stack-top] value;
}// 出栈
int pop(Stack* stack) {if (stack-top -1) {printf(Stack Underflow\n);return -1;}return stack-arr[stack-top--];
}// 查看栈顶
int peek(Stack* stack) {if (stack-top -1) {printf(Stack is empty\n);return -1;}return stack-arr[stack-top];
}2.2 使用链表实现栈
链表实现栈可以动态调整大小不受固定容量限制。
示例代码
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node* next;
} Node;// 入栈
void push(Node** top, int value) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data value;newNode-next *top;*top newNode;
}// 出栈
int pop(Node** top) {if (*top NULL) {printf(Stack Underflow\n);return -1;}Node* temp *top;int popped temp-data;*top temp-next;free(temp);return popped;
}// 查看栈顶
int peek(Node* top) {if (top NULL) {printf(Stack is empty\n);return -1;}return top-data;
}3. 栈的应用场景
3.1 函数调用栈
编程语言运行时会使用栈存储函数的局部变量、返回地址等信息。
函数的调用和返回严格遵循后进先出原则。
3.2 表达式求值
栈用于处理中缀表达式到后缀表达式的转换以及后缀表达式的求值。
例如算术表达式计算。
3.3 括号匹配
检查字符串中的括号是否成对匹配常用于编译器和代码编辑器的语法检查。
3.4 深度优先搜索DFS
栈在实现深度优先搜索算法时用于存储路径信息。
3.5 撤销操作
栈记录用户操作的历史用于实现撤销Undo功能。
4. 栈的优缺点
优点
操作简单只需要维护栈顶插入和删除操作时间复杂度均为 O(1)O(1)。内存管理内存分配集中在栈顶易于管理。适用场景广泛特别适合递归和后进先出的场景。
缺点
容量有限基于数组的栈需要预先分配固定大小可能造成溢出。非灵活访问只能访问栈顶元素无法随机访问栈中其他元素。
5. 栈的实现方式对比
数组实现 使用一个数组来存储栈中的元素并使用一个变量来跟踪栈顶的位置。优点是访问速度快因为直接通过索引访问缺点是在预先定义的大小之外添加元素可能会导致问题。链表实现 使用链表来存储栈中的元素每个节点包含元素值和指向下一个节点的指针。优点是可以动态地增加或减少栈的大小缺点是访问速度相对较慢因为需要遍历链表。 6. 栈与队列的对比 7. 栈的注意事项
溢出问题基于数组的栈在容量满时会发生溢出需要提前处理。递归深度限制递归调用过深可能导致函数调用栈溢出。内存管理链表实现的栈需要手动释放节点内存防止内存泄漏。最小栈在栈中以常数时间获取当前栈的最小值。双栈模拟队列使用两个栈实现队列操作。多栈共享数组一个数组同时存储多个栈的数据。
8.小结
栈是一种重要的数据结构其后进先出的特性使得它在递归、表达式求值、括号匹配等场景中应用广泛。通过理解栈的基本操作和实现方式可以帮助开发者灵活应用栈并掌握其在算法和系统设计中的重要作用。
四、总结 数组、链表和栈是编程中最基础的数据结构它们各具特色适用于不同的场景
数组提供高效的随机访问但大小固定且不适合频繁增删。
链表适合动态存储和频繁插入删除但随机访问效率较低。
栈专注于后进先出的顺序操作应用场景广泛。
数组、链表和栈作为程序设计中最基础的数据结构各自有着独特的优势与应用场景。数组因其固定的内存分配和高效的随机访问能力适合用于数据规模确定的场景链表因其灵活的内存管理适用于频繁插入和删除的需求而栈则以其后进先出的特性在递归、表达式求值等领域扮演着不可或缺的角色。熟练掌握这三种数据结构是深入理解算法和设计更高效程序的必经之路。
