企业官网建设流程全解析

前面学完链表，继续学习栈、队列两种受限线性表，树与二叉树的理论、性质、四种遍历，以及哈希表基础原理与哈希冲突解决。这些是算法笔试、嵌入式开发的高频考点。数组、链表属于通用线性表，可以在任意位置增删查改。而栈、队列属于操作受限的线性表，只能在固定端点完成插入删除。树属于非线性层次结构，二叉树是重中之重；哈希表依靠哈希函数实现平均 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->top+1;//栈顶加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; }

三、树

树的递归定义

树是 n（n≥0）个结点的有限集合：

1. n=0：空树
2. n>0：有唯一根节点；其余节点拆分为 m 个互不相交的集合，每个集合又是子树。

基础术语

表格

存储两种方案：

1. 顺序存储：适合完全二叉树，数组存放
2. 链式存储：每个结点保存数据 + 子结点指针。

二叉树

二叉树：n≥0 结点集合，每个结点最多 2 棵子树，严格区分左子树、右子树，不能互换。

特殊二叉树

1. 斜树：全部只有左孩子（左斜树），或者全部只有右孩子（右斜树），退化成链表。
2. 满二叉树：深度 k，结点总数 2^k-1，每一层全部填满，叶子全部在最后一层。
3. 完全二叉树：除最后一层全部填满；最后一层结点全部靠左排列。堆就是基于完全二叉树实现。

二叉树重要数学性质（笔试常考）

1. 第 i 层，最多 2^（i-1）个结点
2. 深度 k，整棵树最多 2^k-1个结点
3. 叶子结点数量 n0，度为 2 结点数量 n2，恒有：n0=n2+1，总结点 N = n0+n1+n2
4. n 个结点完全二叉树深度： log2n+1，向下取整。

二叉树 C 语言结点结构

typedef struct BiTNode { int data; struct BiTNode *lchild; //左孩子指针 struct BiTNode *rchild; //右孩子指针 } BiTNode, *BiTree;

四种遍历（核心重点）

前、中、后序属于深度优先 DFS，递归实现；层序遍历 BFS 需要借助队列实现。

表格

考点：已知两种遍历序列，还原二叉树；树复制、释放销毁一般用后序遍历。

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，经过哈希函数算出同一个下标，就发生哈希冲突，冲突不可完全避免，需要专门的策略处理。

两大主流冲突解决方案：

1. 链地址法（拉链法，开散列）数组每个位置是链表头；发生冲突的数据挂载到同一个桶的链表上面。查找：先算哈希定位桶，再遍历链表比对 key。
2. 开放寻址法（闭散列）冲突就向后继续探测，依次找下一个空闲位置存放数据（线性探测、二次探测）。

全部元素存放在数组内部，不使用链表；容易出现数据堆积。

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; } p=p->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; } p=p->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; }

五、总结

1. 栈、队列是操作受限线性表栈 LIFO，多用于回溯、函数调用；队列 FIFO，多用于缓冲、BFS 层序遍历；底层数组 / 链表都可以实现。
2. 树与二叉树（非线性层次结构）记住递归定义，分清叶子、度、深度；掌握满二叉树、完全二叉树概念；熟记二叉树几条数学公式。

四种遍历：前 / 中 / 后序递归 DFS；层序 BFS 依赖队列，笔试高频。

1. 哈希表哈希函数映射 key 到下标；理解哈希冲突；两大解决方案：链地址法、开放寻址法，平均 O (1) 查找效率。

学习路线回顾：数组→链表→栈 & 队列→树 & 二叉树→哈希表，后面继续学习堆、排序查找算法。