企业官网建设流程全解析

目录

一、数据结构基础概念

1. 逻辑结构（数据之间的逻辑关系）

2. 存储结构（数据在计算机中的存储方式）

3. 算法与复杂度

二、链表的核心概念

1. 链表相关术语

2. 链表 vs 数组

三、单链表的基本操作（C语言实现）

1. 节点结构定义

2. 创建空链表

3. 插入操作

4. 查找与修改

5. 删除操作

6. 遍历打印

三、单链表的进阶操作

1. 找到链表的中间节点（快慢指针）

2. 找到链表的倒数第k个节点（双指针）

3. 判断链表是否有环（快慢指针）

4. 链表的逆序（反转）

一、数据结构基础概念

数据结构主要研究数据与数据之间的关系。它分为两个层次：

1. 逻辑结构（数据之间的逻辑关系）

• 线性结构：一对一。如线性表、栈、队列。
• 树形结构：一对多。如树、二叉树。
• 图形结构：多对多。如网、图。
• 集合：无关系，仅仅属于同一个集合。

2. 存储结构（数据在计算机中的存储方式）

• 顺序存储：一段连续的空间，用数组实现。逻辑相邻，物理也相邻。
• 链式存储：空间不连续，通过指针（地址）链接。逻辑相邻，物理不一定相邻。
• 索引存储：建立附加的索引表。
• 散列存储：根据关键字计算存储地址（哈希表）。

3. 算法与复杂度

算法是对特定问题求解步骤的描述，有五个特性：有穷性、确定性、可行性、输入、输出。
衡量算法好坏的核心指标是时间复杂度和空间复杂度，常用大O表示法。例如：

• 顺序存储（数组）：随机访问 O(1) O(1)，插入/删除 O(n) O(n)。
• 链式存储（链表）：随机访问 O(n) O(n)，插入/删除 O(1) O(1)。

二、链表的核心概念

链表是一种动态地进行存储分配的结构。它不需要预先分配固定大小的空间，而是根据需要动态申请。

1. 链表相关术语

• 头指针（head）：指向链表中第一个结点的指针，是链表的入口。

• 头节点：第一个结点前附加的一个结点，数据域通常不存放有效数据（可放链表长度等），指针域指向首节点。引入头节点可以简化插入和删除第一个结点的操作。
• 首节点：链表中第一个有效结点。
• 尾节点：最后一个结点，其指针域为NULL。

2. 链表 vs 数组

三、单链表的基本操作（C语言实现）

我们以带头节点的单链表为例。

1. 节点结构定义

typedef struct node { int data; // 数据域 struct node *next; // 指针域 } node_t;

2. 创建空链表

node_t *linklist_creat(void){ node_t *head = malloc(sizeof(node_t)); if(head == NULL){ printf("linklist malloc failed"); return NULL; } head->next = NULL; return head; }

3. 插入操作

• 头插法：新节点插在头节点之后。常用于链表逆序。
• 尾插法：新节点插在尾部。常用于保持插入顺序。

//头插 void linklist_insert_head(node_t *phead,data_t data){ if(phead == NULL){ printf("head = NULL\n"); return ; } //创建新节点 node_t *pnew = malloc(sizeof(node_t)); if(pnew == NULL){ printf("new linklist malloc failed\n"); return ; } pnew ->data = data; //插入 pnew->next = phead->next; phead->next = pnew; } //尾插 void linklist_insert_rail(node_t *phead,data_t data){ if(phead == NULL){ return; } node_t *pnew = malloc(sizeof(node_t)); if(pnew == NULL){ printf("new linklist malloc failed\n"); return ; } node_t *p = phead->next; pnew->data = data; while(p->next!=NULL){ p = p->next; } p->next = pnew; pnew->next = NULL; }

4. 查找与修改

//查找 node_t *linklist_find_key(node_t *phead,data_t key){ if(phead == NULL||is_empty(phead) ){ printf("phead is empty\n"); return NULL; } node_t *p = phead->next; while(p!=NULL){ if(p->data == key){ return p; } p = p->next; } return NULL; } //修改（先找再改） node_t *linklist_update(node_t *phead,data_t old,data_t new){ if(phead == NULL||is_empty(phead) ){ printf("phead is empty\n"); return NULL; } node_t *p = linklist_find_key(phead,old); if(p == NULL){ printf("not found %d\n",old); return NULL; } p->data = new; return p; }

5. 删除操作

//从头开始删 void linklist_delete_head(node_t *phead){ if(phead == NULL){ printf("head = NULL\n"); return ; } if(is_empty(phead) == 1 ){ printf("phead is empty\n"); return ; } node_t *p=phead->next; phead->next = p->next; free(p); p = NULL; } //从结尾开始删 void linklist_delete_tail(node_t *phead){ if(phead == NULL){ printf("head = NULL\n"); return ; } if(is_empty(phead) == 1 ){ printf("phead is empty\n"); return ; } node_t *p=phead; //找尾节点的前一个节点 while(p->next->next!=NULL){ p = p->next; } free(p->next);//释放当前节点的下一个节点 p->next = NULL;//当前节点的地址域设为空 } //删除指定值 void linklist_delete_key(node_t *phead,data_t key){ node_t *q = linklist_find_key(phead,key); if(q == NULL){ printf("not found\n"); return ; } node_t *p = phead; while(p->next != q){ p = p->next; } p->next = q->next; free(q); q = NULL; }

6. 遍历打印

//遍历打印链表 void linklist_print(node_t *phead){ //判断phead是否为空 //判断是否为空链表； if(phead == NULL||is_empty(phead) ){ printf("phead is empty\n"); return; } //遍历 node_t *p = phead->next; while(p != NULL){ printf("%d ",p->data); p = p->next; } putchar('\n'); }

三、单链表的进阶操作

1. 找到链表的中间节点（快慢指针）

思路：快指针一次走两步，慢指针一次走一步。快指针走到尾时，慢指针正好在中间。

node_t *linklist_find_mid(node_t *phead){ if(phead == NULL || is_empty(phead) == 1){ printf("mid find fail\n"); return NULL; } node_t *p = phead; node_t *q = phead; while(p!=NULL && p->next!=NULL){ p = p->next->next; q = q->next; } return q; }

2. 找到链表的倒数第k个节点（双指针）

思路：先让快指针走k步，然后快慢指针同时走。快指针走到NULL时，慢指针正好在倒数第k个位置。

//找倒数第k个值的位置（双指针） node_t *linklist_find_behind_key(node_t *phead,int k){ if(phead==NULL||is_empty(phead)){ printf("find fail\n"); return NULL; } node_t *p = phead; node_t *q = phead; while(k){ if(p->next == NULL){ printf("have no enough node\n"); return NULL; } p = p->next; --k; } while(p!=NULL){ p = p->next; q = q->next; } return q; }

3. 判断链表是否有环（快慢指针）

思路：快指针一次走两步，慢指针一次走一步。如果链表有环，快慢指针必定相遇。

//是否含有环（快慢指针） int linklist_is_cirlc(node_t *phead){ if(phead == NULL ||is_empty(phead) == 1){ return -1; } node_t *p = phead; node_t *q = phead; while(p!=NULL && p->next !=NULL){ p = p->next->next; q = q->next; if(p==q){ return 1; } } return 0; }

4. 链表的逆序（反转）

思路1：使用头插法。遍历原链表，依次将每个节点插入到新链表的头部。

//链表逆序（双指针） void linklist_reverse(node_t *phead){ if(phead == NULL || is_empty(phead) == 1){ return ; } node_t *p = phead->next; node_t *q = p->next; if(q == NULL){ return ; } phead->next = NULL; while(p!=NULL){ q = p->next; p->next = phead->next; phead->next = p; p = q; } }

思路2：使用三个指针prev、curr、next，遍历链表，逐个将当前节点的next指针反转，最终让头节点指向新的首节点（原来的尾节点）。

//链表逆序（三指针） void linklist_reverse_plus(node_t *phead){ if(phead == NULL || is_empty(phead) == 1){ return ; } node_t *prev = NULL; node_t *curr = phead->next; if(curr->next == NULL){ return ; } while(curr!=NULL){ node_t *next = curr->next; curr->next = prev; prev = curr; curr = next; } phead->next = prev; }