前面学完链表继续学习栈、队列两种受限线性表树与二叉树的理论、性质、四种遍历以及哈希表基础原理与哈希冲突解决。这些是算法笔试、嵌入式开发的高频考点。数组、链表属于通用线性表可以在任意位置增删查改。而栈、队列属于操作受限的线性表只能在固定端点完成插入删除。树属于非线性层次结构二叉树是重中之重哈希表依靠哈希函数实现平均 O (1) 的查找效率。一、队列顺序队列1.创建队列queue_t *seqqueue_create(void) { queue_t *pq malloc(sizeof(queue_t)); if (pq NULL) { printf(queue fail to create\n); return NULL; } pq-que malloc(sizeof(queue_t)*MAX_SIZE); if (pq-que NULL) { printf(malloc que fail\n); return NULL; } pq-head 0; pq-tail 0; pq- tlen 0; return pq; }2.入队int enqueue(queue_t *p, data_t data) { if (p NULL) { return -1; } if (queue_is_full(p) 1) { return 0; } p-que[p-tail] data; p-tail (p-tail 1)%MAX_SIZE;//取模循环 return 0; }3.出队int dequeue(queue_t *p, data_t *data) { if (p NULL ) { return -1; } if (queue_is_empty(p) 1) { return 0; } //出队的数 *data p-que[p-head]; p-head (p-head 1)%MAX_SIZE; }4.销毁int queue_destroy(queue_t **ppq) { if (ppq NULL) { return -1; } queue_t *p *ppq; free(p-que); p-que NULL; free(p); *ppq NULL; return 0; }链式队列1.创建队列node_t *linkque_create(void) { node_t *head malloc(sizeof(node_t)); if (head NULL) { printf(linklist_create malloc fail\n); return NULL; } head-next NULL; return head; }2.入队尾插int linkque_enqueue(node_t *phead, data_t data) { if (phead NULL) { return -1; } node_t *pNew malloc(sizeof(node_t)); if (pNew NULL) { return -1; } pNew-data data; node_t *p phead; while (p-next ! NULL) { p p-next; } p-next pNew; pNew-next NULL; return 0; }3.出队头删int linkque_dequeue(node_t *phead, data_t *data) { if (phead NULL) { return -1; } node_t *p phead-next; *data p-data; phead-next p-next; free(p); p NULL; return 0; }4.打印int linkque_print(node_t *phead) { if (phead NULL || is_empty(phead) 1) { return -1; } node_t *p phead-next; while (p!NULL) { printf(%d ,p-data); p p-next; } putchar(\n); return 0; }5.销毁int linkque_destroy(node_t **pphead) { if (*pphead NULL) { return -1; } node_t *p *pphead; node_t *q p; while (q ! NULL) { q p-next; free(p); p q; } *pphead NULL; return 0; }二、栈顺序栈1.创建栈stack_t *seqstack_create(int len) { stack_t *ps malloc(sizeof(stack_t)); if (ps NULL) { printf(seqstack_create fail\n); return NULL; } ps-stack malloc(sizeof(stack_t) * len); if (ps-stack NULL) { printf(seqstack_create stack fail\n); return NULL; } ps-top -1; ps-len len; return ps; }2.入栈int push(stack_t *s, data_t data) { if (s NULL) { return -1; } if (is_full(s) 1) { return 0; } s-top; s-stack[s-top] data; return 0; }3.出栈int pop(stack_t *s, data_t *data) { if (s NULL) { return -1; } if (is_empty(s) 1) { return 0; } *data s-stack[s-top]; s-top--; return 0; }4.栈的长度int get_stack_size(stack_t *s) { if (s NULL) { return -1; } return s-top1;//栈顶加1等于长度 }5.获取栈顶元素int get_top_data(stack_t *s) { if (s NULL || is_empty(s) 1) { return -1; } return s-top; }6.销毁int seqstack_destroy(stack_t **pps) { if (pps NULL) { return -1; } stack_t *p *pps; free(p-stack); free(*pps); *pps NULL; return 0; }链式栈1.创建栈node_t *linkstack_create(void) { node_t *head malloc(sizeof(node_t)); if (head NULL) { printf(linkstack_create malloc fail\n); return NULL; } head-next NULL; return head; }2.入栈头插int push(node_t *phead, data_t data) { if (phead NULL) { return -1; } node_t *pNew malloc(sizeof(node_t)); if (pNew NULL) { return -1; } pNew-data data; pNew-next phead-next; phead-next pNew; return 0; }3.出栈头删int pop(node_t *phead, data_t *data) { if (phead NULL) { return -1; } node_t *p phead-next; phead-next p-next; *data p-data; free(p); p NULL; return 0; }4.获取栈顶元素int get_top_data(node_t *phead) { if (phead NULL) { return -1; } return phead-next-data; }5.销毁int linkstack_destroy(node_t **pphead) { if (*pphead NULL) { return -1; } node_t *p *pphead; node_t *q p; while (q ! NULL) { q p-next; free(p); p q; } *pphead NULL; return 0; }三、树树的递归定义树是 nn≥0个结点的有限集合n0空树n0有唯一根节点其余节点拆分为 m 个互不相交的集合每个集合又是子树。基础术语表格术语说明结点的度结点拥有子树的个数叶子结点 leaf度为 0没有孩子分支结点度不为 0拥有子结点树的度整棵树所有结点度的最大值层次根为第 1 层向下逐层递增树的高度 / 深度结点最大层次数存储两种方案顺序存储适合完全二叉树数组存放链式存储每个结点保存数据 子结点指针。二叉树二叉树n≥0 结点集合每个结点最多 2 棵子树严格区分左子树、右子树不能互换。特殊二叉树斜树全部只有左孩子左斜树或者全部只有右孩子右斜树退化成链表。满二叉树深度 k结点总数 2^k-1每一层全部填满叶子全部在最后一层。完全二叉树除最后一层全部填满最后一层结点全部靠左排列。堆就是基于完全二叉树实现。二叉树重要数学性质笔试常考第 i 层最多 2^i-1个结点深度 k整棵树最多 2^k-1个结点叶子结点数量 n0度为 2 结点数量 n2恒有n0n21总结点 N n0n1n2n 个结点完全二叉树深度 log2n1向下取整。二叉树 C 语言结点结构typedef struct BiTNode { int data; struct BiTNode *lchild; //左孩子指针 struct BiTNode *rchild; //右孩子指针 } BiTNode, *BiTree;四种遍历核心重点前、中、后序属于深度优先 DFS递归实现层序遍历 BFS 需要借助队列实现。表格遍历方式访问顺序记忆口诀前序遍历 PreOrder根 → 左 → 右先访问根再递归左子树再递归右子树中序遍历 InOrder左 → 根 → 右先左子树访问根再右子树后序遍历 PostOrder左 → 右 → 根先左右子树最后访问根结点层序遍历 LevelOrder从上向下同一层从左到右借助队列完成广度优先遍历考点已知两种遍历序列还原二叉树树复制、释放销毁一般用后序遍历。1.创建btree_t *btree_create(void) { data_t data tree[idx]; if(data #) { return NULL; } btree_t *root malloc(sizeof(btree_t)); root-data data; root-pl btree_create();//左结点 root-pr btree_create();//右结点 return root;//返回根 }2.前序遍历根 → 左 → 右int pre_order(btree_t *root) { if (root NULL) { return -1; } printf(%c, root-data); pre_order(root-pl);//左继续递归 pre_order(root-pr);//右 return 0; }3.中序遍历左 → 根 → 右int in_order(btree_t *root) { if (root NULL) { return -1; } in_order(root-pl);//左继续递归 printf(%c, root-data); in_order(root-pr);//右 return 0; }4.后序遍历左 → 右 → 根int post_order(btree_t *root) { if (root NULL) { return -1; } post_order(root-pl);//左继续递归 post_order(root-pr);//右 printf(%c, root-data); return 0; }5.层次遍历从上向下同一层从左到右借助队列int layer_order(btree_t *root) { if (root NULL) { return -1; } //创建队列 node_t *pq linkque_create(); //循环拿节点入队 linkque_enqueue(pq, *root); while (is_empty(pq) ! 1) { //出队 //打印 btree_t d; linkque_dequeue(pq, d); printf(%c\n, d.data); //判断出队结点的左边和右边 if (d.pl ! NULL) { //左边有则入队 linkque_enqueue(pq, *(d.pl)); }else if (d.pr ! NULL) { //右边有则入队 linkque_enqueue(pq, *(d.pr)); } } linkque_destroy(pq); return 0; }四、哈希表数组按下标访问链表需要遍历查找。哈希表可以做到平均 O (1) 查找、插入、删除。核心原理通过哈希函数把 key 映射成数组下标直接定位存储位置。通俗类比查字典通过拼音直接找到对应页码不需要一页一页翻。哈希冲突不同 key经过哈希函数算出同一个下标就发生哈希冲突冲突不可完全避免需要专门的策略处理。两大主流冲突解决方案链地址法拉链法开散列数组每个位置是链表头发生冲突的数据挂载到同一个桶的链表上面。查找先算哈希定位桶再遍历链表比对 key。开放寻址法闭散列冲突就向后继续探测依次找下一个空闲位置存放数据线性探测、二次探测。全部元素存放在数组内部不使用链表容易出现数据堆积。1.创建int hash_create(data_t *a, int len, node_t **hash_table) { if (a NULL || hash_table NULL) { return -1; } int i 0; for (i 0; i len; i) { //除留取余 int addr a[i]%10; node_t *pnew malloc(sizeof(node_t)); if (pnew NULL) { printf(hash_create fail\n); return -1; } pnew-data a[i]; //addr对应位置地址为空直接填充数据 if(hash_table[addr] NULL) { pnew-next NULL; hash_table[addr] pnew; }else//对应位置不为空完成尾插 { pnew-next hash_table[addr]; hash_table[addr] pnew; } } return 0; }2.遍历int hash_show(node_t **hash_table, int len) { if (hash_table NULL) { return -1; } int i 0; for (i 0; i len; i) { if (hash_table[i] NULL) { printf(%d|NULL|\n, i); }else { printf(%d|%p|, i, hash_table[i]); node_t *p hash_table[i]; while (p ! NULL) { printf (-|%d|, p-data); p p-next; } printf(NULL|\n); } } }3.找数据node_t *hash_find(data_t data, node_t **hash_table) { int addr data % 10; node_t *p hash_table[addr]; while (p ! NULL) { if (p-data data) { return p; } pp-next; } return NULL; }4.更新数据node_t *hash_update(data_t old, data_t new, node_t **hash_table) { int addr old % 10; node_t *p hash_table[addr]; while (p ! NULL) { if (p-data old) { p-data new; return p; } pp-next; } return NULL; }5.删除指定数据int hash_delete_key(data_t key, node_t **hash_table) { int addr key % 10; //头结点 node_t *p hash_table[addr]; node_t *q p-next; //判断头结点是否是待删除的数据 if (p-data key) { hash_table[addr] p-next; free(p); p NULL; return 1; } //头结点不是待删除数据继续往后遍历 while (p ! NULL) { if (p-next-data key) { q p-next; p-next q-next; free(q); q NULL; return 1; } p p-next; } return 0; }6.销毁int hash_destroy(node_t **hash_table) { int i 0; for (i 0; i 10; i) { node_t *p hash_table[i]; node_t *q NULL; //结点不为空说明有数据,从头逐个删除 while (p ! NULL) { q p-next; free(p); p q; } //所有数据删除将头置为空 hash_table[i] NULL; } return 0; }五、总结栈、队列是操作受限线性表栈 LIFO多用于回溯、函数调用队列 FIFO多用于缓冲、BFS 层序遍历底层数组 / 链表都可以实现。树与二叉树非线性层次结构记住递归定义分清叶子、度、深度掌握满二叉树、完全二叉树概念熟记二叉树几条数学公式。四种遍历前 / 中 / 后序递归 DFS层序 BFS 依赖队列笔试高频。哈希表哈希函数映射 key 到下标理解哈希冲突两大解决方案链地址法、开放寻址法平均 O (1) 查找效率。学习路线回顾数组→链表→栈 队列→树 二叉树→哈希表后面继续学习堆、排序查找算法。