想找做海报的超清图片去哪个网站找网站建设行业动态

想找做海报的超清图片去哪个网站找,网站建设行业动态,广州可以做票务商城的网站公司,啪啪男女禁做视频网站在编程世界中#xff0c;数据结构是构建高效程序的基石。无论是日常开发中的数据存储#xff0c;还是算法题中的逻辑实现#xff0c;掌握核心数据结构及其 C 语言实现都至关重要。本文将从线性表#xff08;顺序表、链表#xff09;入手#xff0c;逐步深入栈、队列…在编程世界中数据结构是构建高效程序的基石。无论是日常开发中的数据存储还是算法题中的逻辑实现掌握核心数据结构及其 C 语言实现都至关重要。本文将从线性表顺序表、链表入手逐步深入栈、队列最终聚焦二叉树与堆结合完整代码实现与实战场景带大家从零到一掌握这些核心数据结构。一、线性表数据结构的基础线性表是 n 个具有相同特性的数据元素的有限序列逻辑上呈线性结构物理存储分为连续数组和非连续链式两种形式是栈、队列等复杂结构的基础。1.1 顺序表数组的封装与优化1.1.1 核心概念顺序表是用物理地址连续的存储单元存储数据的线性结构底层基于数组实现封装了增删改查等常用接口解决了原生数组灵活性不足的问题。类比来看数组就像 炒西蓝花而顺序表则是 绿野仙踪—— 在基础食材上增加了规范化的处理流程。1.1.2 分类与缺陷静态顺序表使用定长数组存储缺陷明显空间给少了不够用给多了造成浪费。// 静态顺序表 typedef int SLDataType; #define N 7 typedef struct SeqList { SLDataType a[N]; // 定长数组 int size; // 有效数据个数 } SL;动态顺序表按需申请空间通过capacity记录容量size记录有效数据个数支持动态扩容。// 动态顺序表 typedef int SLDataType; #define INIT_CAPACITY 4 typedef struct SeqList { SLDataType* a; // 动态数组指针 int size; // 有效数据个数 int capacity; // 空间容量 } SL;1.1.3 核心接口实现动态顺序表的关键在于扩容机制和高效的增删改查以下是核心接口的完整实现// SeqList.h 头文件声明 #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int SLDataType; #define INIT_CAPACITY 4 typedef struct SeqList { SLDataType* a; int size; int capacity; } SL; // 初始化和销毁 void SLInit(SL* ps); void SLDestroy(SL* ps); void SLPrint(SL* ps); // 扩容 void SLCheckCapacity(SL* ps); // 头部/尾部插入删除 void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); void SLPushFront(SL* ps, SLDataType x); void SLPopFront(SL* ps); // 指定位置插入/删除 void SLInsert(SL* ps, int pos, SLDataType x); void SLErase(SL* ps, int pos); int SLFind(SL* ps, SLDataType x); // SeqList.c 实现 void SLInit(SL* ps) { assert(ps); ps-a (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); if (ps-a NULL) { perror(malloc fail); exit(EXIT_FAILURE); } ps-size 0; ps-capacity INIT_CAPACITY; } void SLDestroy(SL* ps) { assert(ps); free(ps-a); ps-a NULL; ps-size ps-capacity 0; } void SLPrint(SL* ps) { assert(ps); for (int i 0; i ps-size; i) { printf(%d , ps-a[i]); } printf(\n); } void SLCheckCapacity(SL* ps) { assert(ps); if (ps-size ps-capacity) { // 扩容为原来的2倍 SLDataType* tmp (SLDataType*)realloc(ps-a, sizeof(SLDataType) * ps-capacity * 2); if (tmp NULL) { perror(realloc fail); exit(EXIT_FAILURE); } ps-a tmp; ps-capacity * 2; } } // 尾插 void SLPushBack(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); ps-a[ps-size] x; } // 尾删 void SLPopBack(SL* ps) { assert(ps ps-size 0); ps-size--; } // 头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); // 数据后移 for (int i ps-size; i 0; i--) { ps-a[i] ps-a[i - 1]; } ps-a[0] x; ps-size; } // 头删 void SLPopFront(SL* ps) { assert(ps ps-size 0); // 数据前移 for (int i 0; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-size--; } // 按位置插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos 0 pos ps-size); SLCheckCapacity(ps); // 从pos位置开始后移 for (int i ps-size; i pos; i--) { ps-a[i] ps-a[i - 1]; } ps-a[pos] x; ps-size; } // 按位置删除 void SLErase(SL* ps, int pos) { assert(ps ps-size 0); assert(pos 0 pos ps-size); // 从pos1位置开始前移 for (int i pos; i ps-size - 1; i) { ps-a[i] ps-a[i 1]; } ps-size--; } // 查找元素 int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i 0; i ps-size; i) { if (ps-a[i] x) { return i; } } return -1; // 未找到 }1.1.4 优缺点分析优点支持随机访问O (1) 时间复杂度尾插尾删效率高。缺点中间 / 头部插入删除需移动元素O (N) 时间复杂度扩容存在空间浪费和拷贝开销。1.2 链表非连续存储的灵活选择1.2.1 核心概念链表是物理存储非连续、逻辑连续的线性结构通过指针链接结点实现数据访问。每个结点包含数据域和指针域类比火车车厢 —— 每节车厢独立存在通过挂钩连接。1.2.2 单链表结构与实现单链表是最基础的链表结构每个结点仅存储下一个结点的地址以下是完整实现// SList.h 头文件声明 #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int SLTDataType; // 单链表结点结构 typedef struct SListNode { SLTDataType data; // 数据域 struct SListNode* next; // 指针域指向next结点 } SLTNode; // 打印链表 void SLTPrint(SLTNode* phead); // 头部/尾部插入删除 void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopFront(SLTNode** pphead); // 查找结点 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); // 指定位置插入/删除 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); void SLTErase(SLTNode** pphead, SLTNode* pos); // 销毁链表 void SListDestroy(SLTNode** pphead); // SList.c 实现 // 创建新结点 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); if (newnode NULL) { perror(malloc fail); exit(EXIT_FAILURE); } newnode-data x; newnode-next NULL; return newnode; } // 打印链表 void SLTPrint(SLTNode* phead) { SLTNode* pcur phead; while (pcur) { printf(%d , pcur-data); pcur pcur-next; } printf(\n); } // 尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode BuySLTNode(x); if (*pphead NULL) { // 空链表 *pphead newnode; return; } // 找到尾结点 SLTNode* ptail *pphead; while (ptail-next) { ptail ptail-next; } ptail-next newnode; } // 尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead *pphead); // 只有一个结点 if ((*pphead)-next NULL) { free(*pphead); *pphead NULL; return; } // 找到倒数第二个结点 SLTNode* prev NULL; SLTNode* ptail *pphead; while (ptail-next) { prev ptail; ptail ptail-next; } free(ptail); prev-next NULL; } // 头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode BuySLTNode(x); newnode-next *pphead; *pphead newnode; } // 头删 void SLTPopFront(SLTNode** pphead) { assert(pphead *pphead); SLTNode* tmp *pphead; *pphead (*pphead)-next; free(tmp); tmp NULL; } // 查找结点 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur phead; while (pcur) { if (pcur-data x) { return pcur; } pcur pcur-next; } return NULL; // 未找到 } // 销毁链表 void SListDestroy(SLTNode** pphead) { assert(pphead); SLTNode* pcur *pphead; while (pcur) { SLTNode* tmp pcur; pcur pcur-next; free(tmp); } *pphead NULL; }1.2.3 链表 vs 顺序表核心对比对比维度顺序表链表单链表存储空间物理连续逻辑连续物理非连续随机访问支持O (1)不支持O (N)插入删除中间 / 头部 O (N)仅需修改指针O (1)空间效率可能存在扩容浪费按需申请无浪费应用场景频繁访问少量增删频繁增删少量访问二、栈与队列受限的线性表栈和队列是特殊的线性表其操作受到限制分别遵循 后进先出 和 先进先出 原则广泛应用于算法优化、数据缓冲等场景。2.1 栈后进先出LIFO2.1.1 核心概念栈仅允许在栈顶进行插入压栈和删除出栈操作类比叠盘子 —— 最后放的盘子最先被拿走。栈的实现优先选择数组因为数组尾插尾删效率高。2.1.2 完整实现// stack.h 头文件声明 #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int STDataType; typedef struct Stack { STDataType* a; // 数组存储 int top; // 栈顶指针指向栈顶元素下一个位置 int capacity; // 容量 } ST; // 初始化栈 void STInit(ST* ps); // 销毁栈 void STDestroy(ST* ps); // 入栈 void STPush(ST* ps, STDataType x); // 出栈 void STPop(ST* ps); // 取栈顶元素 STDataType STTop(ST* ps); // 获取栈大小 int STSize(ST* ps); // 判断栈是否为空 bool STEmpty(ST* ps); // stack.c 实现 void STInit(ST* ps) { assert(ps); ps-a (STDataType*)malloc(sizeof(STDataType) * 4); if (ps-a NULL) { perror(malloc fail); exit(EXIT_FAILURE); } ps-top 0; ps-capacity 4; } void STDestroy(ST* ps) { assert(ps); free(ps-a); ps-a NULL; ps-top ps-capacity 0; } void STPush(ST* ps, STDataType x) { assert(ps); // 扩容 if (ps-top ps-capacity) { STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * ps-capacity * 2); if (tmp NULL) { perror(realloc fail); exit(EXIT_FAILURE); } ps-a tmp; ps-capacity * 2; } ps-a[ps-top] x; } void STPop(ST* ps) { assert(ps !STEmpty(ps)); ps-top--; } STDataType STTop(ST* ps) { assert(ps !STEmpty(ps)); return ps-a[ps-top - 1]; } int STSize(ST* ps) { assert(ps); return ps-top; } bool STEmpty(ST* ps) { assert(ps); return ps-top 0; }2.2 队列先进先出FIFO2.2.1 核心概念队列允许在队尾插入入队、队头删除出队类比排队买票 —— 先到的人先买票。队列优先选择链表实现避免数组头删时的数据移动。2.2.2 完整实现// Queue.h 头文件声明 #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int QDataType; // 队列结点 typedef struct QueueNode { QDataType val; struct QueueNode* next; } QNode; // 队列结构管理队头和队尾 typedef struct Queue { QNode* phead; QNode* ptail; int size; } Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 入队 void QueuePush(Queue* pq, QDataType x); // 出队 void QueuePop(Queue* pq); // 取队头元素 QDataType QueueFront(Queue* pq); // 取队尾元素 QDataType QueueBack(Queue* pq); // 判断队列是否为空 bool QueueEmpty(Queue* pq); // 获取队列大小 int QueueSize(Queue* pq); // Queue.c 实现 void QueueInit(Queue* pq) { assert(pq); pq-phead pq-ptail NULL; pq-size 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur pq-phead; while (pcur) { QNode* tmp pcur; pcur pcur-next; free(tmp); } pq-phead pq-ptail NULL; pq-size 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc fail); exit(EXIT_FAILURE); } newnode-val x; newnode-next NULL; if (pq-ptail NULL) { // 空队列 pq-phead pq-ptail newnode; } else { pq-ptail-next newnode; pq-ptail newnode; } pq-size; } void QueuePop(Queue* pq) { assert(pq !QueueEmpty(pq)); if (pq-phead-next NULL) { // 只有一个结点 free(pq-phead); pq-phead pq-ptail NULL; } else { QNode* tmp pq-phead; pq-phead pq-phead-next; free(tmp); } pq-size--; } QDataType QueueFront(Queue* pq) { assert(pq !QueueEmpty(pq)); return pq-phead-val; } QDataType QueueBack(Queue* pq) { assert(pq !QueueEmpty(pq)); return pq-ptail-val; } bool QueueEmpty(Queue* pq) { assert(pq); return pq-size 0; } int QueueSize(Queue* pq) { assert(pq); return pq-size; }三、二叉树非线性数据结构的核心二叉树是树形结构的核心每个结点最多有两个子树左子树、右子树是非线性数据结构广泛应用于搜索、排序、文件系统等场景。3.1 核心概念与结构满二叉树每一层结点数达到最大值层数为 k 时结点总数为 2ᵏ-1。完全二叉树除最后一层外每一层结点数均满最后一层结点从左到右连续排列。链式存储每个结点包含数据域、左指针指向左子树、右指针指向右子树。// 二叉树结点结构 typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType val; struct BinaryTreeNode* left; // 左子树指针 struct BinaryTreeNode* right; // 右子树指针 } BTNode;3.2 二叉树的遍历遍历是二叉树操作的基础分为前序、中序、后序递归实现和层序队列实现四种方式。3.2.1 递归遍历实现// 创建新结点 BTNode* BuyBTNode(BTDataType x) { BTNode* newnode (BTNode*)malloc(sizeof(BTNode)); if (newnode NULL) { perror(malloc fail); exit(EXIT_FAILURE); } newnode-val x; newnode-left newnode-right NULL; return newnode; } // 前序遍历根 - 左 - 右 void PreOrder(BTNode* root) { if (root NULL) { printf(N ); // 用N表示空结点 return; } printf(%d , root-val); PreOrder(root-left); PreOrder(root-right); } // 中序遍历左 - 根 - 右 void InOrder(BTNode* root) { if (root NULL) { printf(N ); return; } InOrder(root-left); printf(%d , root-val); InOrder(root-right); } // 后序遍历左 - 右 - 根 void PostOrder(BTNode* root) { if (root NULL) { printf(N ); return; } PostOrder(root-left); PostOrder(root-right); printf(%d , root-val); }3.2.2 层序遍历实现借助队列// 层序遍历自上而下、自左至右 void LevelOrder(BTNode* root) { if (root NULL) return; Queue q; QueueInit(q); QueuePush(q, root); // 根结点入队 while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); printf(%d , front-val); // 左孩子入队 if (front-left) { QueuePush(q, front-left); } // 右孩子入队 if (front-right) { QueuePush(q, front-right); } } QueueDestroy(q); printf(\n); }3.3 堆特殊的完全二叉树堆是满足 双亲结点值大于等于大堆或小于等于小堆子结点值 的完全二叉树常用于堆排序和 Top-K 问题。3.3.1 堆的实现大堆// Heap.h 头文件声明 #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; } HP; // 初始化堆 void HPInit(HP* php); // 销毁堆 void HPDestroy(HP* php); // 插入元素 void HPPush(HP* php, HPDataType x); // 删除堆顶元素 void HPPop(HP* php); // 取堆顶元素 HPDataType HPTop(HP* php); // 判断堆是否为空 bool HPEmpty(HP* php); // 获取堆大小 int HPSize(HP* php); // Heap.c 实现 // 交换两个元素 void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp *a; *a *b; *b tmp; } // 向上调整插入元素后维护堆结构 void AdjustUp(HPDataType* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { // 大堆孩子父亲则交换 Swap(a[child], a[parent]); child parent; parent (parent - 1) / 2; } else { break; } } } // 向下调整删除堆顶后维护堆结构 void AdjustDown(HPDataType* a, int n, int parent) { int child parent * 2 1; // 左孩子 while (child n) { // 选择左右孩子中较大的一个 if (child 1 n a[child 1] a[child]) { child; } // 孩子父亲则交换 if (a[child] a[parent]) { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } } void HPInit(HP* php) { assert(php); php-a NULL; php-size php-capacity 0; } void HPDestroy(HP* php) { assert(php); free(php-a); php-a NULL; php-size php-capacity 0; } void HPPush(HP* php, HPDataType x) { assert(php); // 扩容 if (php-size php-capacity) { int newCapacity php-capacity 0 ? 4 : php-capacity * 2; HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity); if (tmp NULL) { perror(realloc fail); exit(EXIT_FAILURE); } php-a tmp; php-capacity newCapacity; } // 插入到末尾并向上调整 php-a[php-size] x; AdjustUp(php-a, php-size - 1); } void HPPop(HP* php) { assert(php !HPEmpty(php)); // 交换堆顶和最后一个元素 Swap(php-a[0], php-a[php-size - 1]); php-size--; // 向下调整堆顶 AdjustDown(php-a, php-size, 0); } HPDataType HPTop(HP* php) { assert(php !HPEmpty(php)); return php-a[0]; } bool HPEmpty(HP* php) { assert(php); return php-size 0; } int HPSize(HP* php) { assert(php); return php-size; }3.3.2 堆的应用Top-K 问题Top-K 问题是求海量数据中前 K 个最大 / 最小元素用堆实现效率极高时间复杂度 O(nlogk)。// 求前K个最大元素用小堆实现 void TopK(int* a, int n, int k) { assert(a n 0 k 0 k n); HP hp; HPInit(hp); // 用前k个元素建小堆 for (int i 0; i k; i) { HPPush(hp, a[i]); } // 剩余元素与堆顶比较大于堆顶则替换并调整 for (int i k; i n; i) { if (a[i] HPTop(hp)) { hp.a[0] a[i]; AdjustDown(hp.a, hp.size, 0); } } // 输出结果 printf(前K个最大元素); while (!HPEmpty(hp)) { printf(%d , HPTop(hp)); HPPop(hp); } printf(\n); HPDestroy(hp); }四、实战演练经典算法题4.1 顺序表算法题移除元素LeetCode 27int removeElement(int* nums, int numsSize, int val) { int dest 0; for (int src 0; src numsSize; src) { if (nums[src] ! val) { nums[dest] nums[src]; } } return dest; }4.2 链表算法题反转链表LeetCode 206BTNode* reverseList(BTNode* head) { BTNode* prev NULL; BTNode* cur head; while (cur) { BTNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; }4.3 栈算法题有效的括号LeetCode 20bool isValid(char* s) { ST st; STInit(st); while (*s ! \0) { if (*s ( || *s [ || *s {) { STPush(st, *s); } else { if (STEmpty(st)) { STDestroy(st); return false; } char top STTop(st); STPop(st); if ((*s ) top ! () || (*s ] top ! [) || (*s } top ! {)) { STDestroy(st); return false; } } s; } bool ret STEmpty(st); STDestroy(st); return ret; }