企业官网建设流程全解析

目录

一、线性表基本概念

1. 定义

2. 线性表抽象数据类型 ADT（操作）

二、两种存储实现

三、C++ 引用

1. 引用是什么

2. 引用三大特性

3. 函数传参三种方式对比

四、顺序表

4.1 静态顺序表和动态顺序表

4.1.1 静态顺序表

4.1.2 动态顺序表

4.1.3 核心对比表

4.1.4 关键概念区分

4.1.5 易混淆点

4.2 动态顺序表实现

4.2.1 接口函数定义

4.2.2 初始化

4.2.3 销毁

4.2.4 插入

4.2.5 删除

4.2.6 查找

4.2.7 测试代码

4.2.8 复杂度分析

插入的时间复杂度

删除的时间复杂度

下标查找的时间复杂度

按值查找的时间复杂度

4.3 题1

4.4 题2

一、线性表基本概念

1. 定义

线性表，是相同类型数据元素的有限序列

• n：表长；n=0→空表
• a_i的位序从 1 开始；C 语言数组下标从 0 开始，做题一定要区分「位序」和「数组下标」
• 逻辑关系：
  • a_1 表头，无前驱
  • a_n表尾，无后继
  • 中间元素：唯一前驱、唯一后继

一句话：线性表是逻辑结构；

物理存储分两种：

✅ 顺序存储 →顺序表

✅ 链式存储 →链表

2. 线性表抽象数据类型 ADT（操作）

表格

注意：带&是 C++ 引用，作用：直接修改原表，不用拷贝整个表。

二、两种存储实现

1. 顺序存储（顺序表）逻辑相邻，物理内存地址也连续；元素之间的逻辑关系靠内存位置体现。 优点：随机访问速度快；缺点：插入 / 删除需要大量移动元素，扩容麻烦。
2. 链式存储（链表）逻辑相邻，物理地址可以任意分散；逻辑关系靠指针记录。 优点：插入删除只改指针，不用移动元素；缺点：不能随机访问，找元素必须从头遍历。

三、C++ 引用

1. 引用是什么

引用 = 给已经存在的变量起别名，不新开内存；引用和原变量共用同一块内存空间。 语法：类型 & 别名 = 原变量;

int a = 0; int& b = a; // b是a的别名，a、b是同一个变量

修改别名，等价修改原变量，两者地址完全相同。

2. 引用三大特性

1. 定义时必须初始化，不能单独声明引用

int& ra; // ❌ 编译报错，没有绑定变量

1. 一个变量可以有多个引用（多个别名）
2. 引用一旦绑定某个变量，不能再绑定别的变量

int a=10, c=20; int &b = a; b = c; // ⚠️ 这不是让b引用c！只是赋值：把c的值拷贝给a

3. 函数传参三种方式对比

// 1. 值传递：拷贝一份，函数内修改不影响外面实参 void Swap1(int rx, int ry) // 2. 指针传递：传地址，通过*解引用修改外面变量 void Swap2(int* rx, int* ry) // 3. 引用传递：形参是实参别名，直接操作原变量 void Swap3(int& rx, int& ry)

• 值传参：不改变实参；会拷贝数据，大对象开销大
• 指针 / 引用传参：都能修改外部实参；大对象传参减少拷贝，提升效率
• 区别：引用是别名，语法更简洁；C 语言没有引用，只能用指针。

教材里ListInsert(&L,i,e)里的&L就是引用，目的：函数内部直接修改原来的线性表 L，不用拷贝。

注意：

1. 线性表的位序从1开始，数组下标从 0 开始；
2. 线性表是逻辑结构，顺序表、链表是存储结构（物理实现）；
3. 引用不是新变量，不分配独立内存；&在定义引用时是引用符号，在表达式里&a是取地址，符号复用，场景不同含义不同；
4. b=c对引用来说，只是赋值，不能改变引用绑定的对象。

四、顺序表

4.1 静态顺序表和动态顺序表

4.1.1 静态顺序表

typedef int SqDataType; #define Sq_MAX_SIZE 10 typedef struct SequenceList{ SqDataType arr[Sq_MAX_SIZE]; // 固定大小的静态数组，在栈上分配 int size; // 当前已经存放的数据个数 }SqList;

存储载体：固定长度的静态数组，编译期就确定最大容量，容量不可更改。

内存位置：结构体里面的数组是在栈内存分配。

• ✅ 优点：实现简单，直接访问，不需要手动开辟 / 释放堆内存。
• ❌ 缺点：
  1. 容量写死，一旦定义无法扩容；
  2. 预估容量大了浪费空间，预估小了存不下数据；
  3. 适合提前知道最多存多少数据的场景。

示例：容量 10，存入{10,20,30,40,50}，size=5，数组下标 0~4 存有效数据，下标 5~9 闲置。

4.1.2 动态顺序表

typedef int SqDataType; typedef struct SequenceList{ SqDataType* arr; // 指向堆上动态开辟数组的指针 int size; // 当前有效数据个数 int capacity; // 当前数组总容量 }SqList;

存储载体：指针arr，运行时在堆内存申请数组空间；满了可以重新开辟更大空间，拷贝旧数据，完成扩容。

• ✅ 优点：容量动态可变，按需扩容，空间利用率更高，是实际开发常用版本。
• ❌ 缺点：实现稍复杂，需要手动malloc/realloc/free管理堆内存，扩容会有数据拷贝开销。

示例：初始容量 10，size=5；数据填满（size==capacity）后，可以扩容（比如扩到 20），重新申请更大堆空间。

4.1.3 核心对比表

4.1.4 关键概念区分

1. size：当前有效元素个数，代表顺序表里真实存了多少数据。
2. capacity / Sq_MAX_SIZE：最大容量，代表数组一共能存放多少元素。
3. 静态顺序表：capacity=Sq_MAX_SIZE，固定不变。
4. 动态顺序表：capacity是变量，扩容时会变大。

4.1.5 易混淆点

• 静态顺序表的数组arr是结构体成员，不是指针；
• 动态顺序表的arr只是一个指针变量（结构体成员），真正存放数据的数组单独在堆区；结构体本身可以在栈上。

4.2 动态顺序表实现

4.2.1 接口函数定义

#pragma once // SqList.h 一般这些接口函数声明放到.h中 // 下面的接口函数的实现放到SqList.cpp中 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> // typedef是为了方便类型替换 typedef int SqDataType; // 数据元素类型 typedef struct { SqDataType* arr; // 存储数据的动态数组的指针 int size; // 记录顺序表中已经存入的数据个数 int capacity; // 动态数组的容量空间的大小 }SqList; // 初始化顺序表 void SqListInit(SqList* ps); // 有些书本上的用法 // void SqListInit(SqList s); // 销毁顺序表 void SqListDestroy(SqList* ps); // 返回顺序表中第i个下标位置元素的值 SqDataType GetElem(SqList* ps, int i); // 返回第一个等于x的数据元素的下标，若不存在返回-1 int LocateElem(SqList* ps, SqDataType x); // 书本中的i通常是位序，位序是从1开始 // 我们实现的时候，i用的是下标 // 在顺序表的第i个位置插入元素x void SqListInsert(SqList* ps, int i, SqDataType x); // 删除顺序表中第i个元素，并返回删除的值 SqDataType SqListDelete(SqList* ps, int i); // 打印顺序表中的元素 void SqListPrint(SqList* ps); // 检测顺序表是否为空，空返回true，否则返回false bool EmptySqList(SqList* ps); // 获取顺序表中有效元素个数 int SqListSize(SqList* ps); // 以下接口复用上面的Insert和Delete即可完成 // 头插尾插 void SqListPushBack(SqList* ps, SqDataType x); void SqListPushFront(SqList* ps, SqDataType x); // 头删尾删 void SqListPopBack(SqList* ps); void SqListPopFront(SqList* ps);

4.2.2 初始化

顺序表的结构体变量创建好后，系统会以随机值对其进行填充，所以在使用前须先进行初始化，步骤如下：

a. 使用 malloc 申请一个默认大小动态数组空间，比如默认大小为 4，这个空间一般不要太大，因

为太大了，用不了就浪费了，反正如果不够，后续可以扩容；

b. 申请成功后，将有效元素个数初始化为 0，因为初始化阶段，顺序表中还未存放任何有效元素；

c. 将 capacity 设置为所申请空间的实际大小。

// 初始化顺序表 void SqListInit(SqList* ps) { assert(ps); ps->arr = (SqDataType*)malloc(sizeof(SqDataType) * 4); if (ps->arr == NULL) { //申请失败，请退出 printf("InitSqList:内申请空间失败\n"); //exit(-1); return; } ps->size = 0; ps->capacity = 4; } // 有些书本上的用法 // void SqListInit(SqList& s);

4.2.3 销毁

由于顺序表中的空间是用 malloc 从堆上动态申请的，使用完后必须释放，否则会内存泄漏。具体

步骤如下：

a. 检测顺序表 s 的空间是否被销毁；

b. 如果未销毁，使用 free 将其释放掉，并将 arr 设置

NULL，size 和 capacity 设置为 0；

c. 其次要注意的 free 本质并不是真的把空间销毁掉，free 的本质是把这段空间的使用权还给操作

系统，操作系统后续还可以把这段空间分配给别人。

// 销毁顺序表 void SqListDestroy(SqList* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->size = ps->capacity = 0; }

4.2.4 插入

顺序表经过初始化之后，才可以进行元素插入操作。插入函数原型为

void SqListInsert(SqList* ps, int i, SqDataType x)，即在顺序表的第 i 个位置插入新元素

x，如果 i 的位置非法，则不进行插入；插入具体步骤如下：

a. 参数检测。主要检测位序 i 是否满足0 <= i <= s.size，满足则插入，否则无法插入

b. 检测是否需要扩容，如果顺序表中存满了则需要先扩容之后才能插入。

c. 插入元素 x。将 i 及其之后的所有元素整体往后移动一个位置，然后将 x 填充到待插入位置。

d. 插入成功后，给有效元素个数加 1

① 当 i 的值为s.size时，即尾插

示例：SqListInsert(s, 4, 50)，数组 size=4，capacity=8，在下标 4 位置放入 50，size 变为

5，不需要挪动原有元素。

② 当 i 的值小于s.size时，比如SqListInsert(s, 1, 15)，即在第 1 个位置之前插入新元素。此

时需要将第 1 个位序及其后面所有元素整体往后搬移一个位置。

当顺序表中元素存满时，就需要进行扩容，否则无法继续插入。扩容时是一个前瞻思维，不仅仅考

虑插入当前数据没有空间了，还要考虑后面数据插入也要空间，所以索性一次多扩展一些，一般的

做法是2 倍左右扩容，当然有些书上是按固定大小扩容，比如每次扩容 4 个变量空间。

我们这里扩容使用 C 的库函数void* realloc (void* ptr, size_t size)实现，ptr 是旧空间的

指针，size 是需要的新空间的字节数，realloc 函数有以下几种情况：

a. 原地扩容：如果当前数组后面有足够的空间没有分配给别人，realloc 则会将后面空间分配给我

们，返回的地址跟 ptr 一样。

b. 异地扩容：如果当前数组后面没有足够的空间 (这些空间已经分配给别人了)，realloc 则会尝试

找一块 size 大小的新空间，如果没有找到则代表扩容失败了，返回 NULL；找到了则会把 ptr 空间

的数据拷贝到新空间，然后释放 ptr 指向的旧空间，然后返回新空间的地址。

异地扩容：

①开辟新空间

②拷贝元素

③释放旧空间

④结构体 arr 指针指向新空间

// 我们实现的时候，i用的是下标 // 在顺序表的第i个位置插入元素x void SqListInsert(SqList* ps, int i, SqDataType x) { assert(ps); assert(i <= ps->size); //满了就扩容 if (ps->size == ps->capacity) { SqDataType* tmp = (SqDataType*)realloc(ps->arr, sizeof(SqDataType) * ps->capacity * 2); if (tmp == NULL) { printf("SqListInsert:内存申请空间失败！\n"); return; } ps->arr = tmp; ps->capacity *= 2; } //挪动数据 int j = ps->size - 1; while (j >= i) { ps->arr[j + 1] = ps->arr[j]; --j; } ps->arr[i] = x; ++ps->size; }

4.2.5 删除

删除函数原型：SqDataType SqListDelete(SqList* ps, int i)

删除函数的功能是删除顺序表中第 i 个位置上的元素，删除的元素通过返回值带出，注意 i 必须在0 ≤ i < s.size，否则无法删除。具体操作如下:

a. 参数检测，主要检测位序 i 是否满足0 <= i < s.size，满足则删除，否则无法删除；

b. 将 i 位置之后所有元素整体往前搬移一个位置；

c. 删除成功，将有效元素个数减 1。

// 删除顺序表中第i个元素, 并返回删除的值 SqDataType SqListDelete(SqList* ps, int i) { assert(ps); assert(i < ps->size && i >= 0); SqDataType del = ps->arr[i]; for (int j = i + 1; j < ps->size; j++) { ps->arr[j - 1] = ps->arr[j]; } --ps->size; return del; }

4.2.6 查找

顺序表有两种查找操作，位序查找和按值查找。

位序查找函数原型：SqDataType GetElem(SqList* ps, int i)第 i 个位置元素随机访问，在 i 满

足0 <= i < s.size时 (不满足则报错)，直接返回顺序表第 i 个元素即可。

// 返回顺序表中第i个下标位置元素的值 SqDataType GetElem(SqList* ps, int i) { assert(ps); assert(i < ps->size); return ps->arr[i]; }

按值查找函数原型：int LocateElem(SqList* ps, SqDataType x)从前往后逐个查找，找到第一

个相等的就返回其下标，否则返回 - 1。

// 返回第一个等于x的数据元素的下标, 若不存在返回-1 int LocateElem(SqList* ps, SqDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) { return i; } } return -1; }

4.2.7 测试代码

// main.cpp #include "SqList.h" void TestSqList1() { SqList L; SqListInit(&L); SqListInsert(&L, 0, 9); SqListInsert(&L, 1, 10); SqListInsert(&L, 2, 20); SqListInsert(&L, 3, 30); SqListInsert(&L, 4, 40); SqListInsert(&L, 5, 50); // 扩容 SqListPrint(&L); // 头插 SqListInsert(&L, 0, 0); SqListPrint(&L); // 尾插 SqListInsert(&L, SqListSize(&L), 60); SqListPrint(&L); // 中间插入 SqListInsert(&L, 2, 2); SqListPrint(&L); } void TestSqList2() { SqList L; SqListInit(&L); SqListInsert(&L, 0, 9); SqListInsert(&L, 1, 10); SqListInsert(&L, 2, 20); SqListInsert(&L, 3, 30); SqListInsert(&L, 4, 40); SqListInsert(&L, 5, 50); // 扩容 SqListPrint(&L); // 删除顺序表第1个位置上的元素 printf("顺序表中有效元素个数为: %d \n", SqListSize(&L)); // 删除第一个数据 printf("删除的元素是:%d \n", SqListDelete(&L, 0)); // 删除末尾的数据 printf("删除的元素是:%d \n", SqListDelete(&L, SqListSize(&L) - 1)); // 删除中间的数据 printf("删除的元素是:%d \n", SqListDelete(&L, 2)); SqListPrint(&L); printf("顺序表中第%d个元素是: %d\n", 1, GetElem(&L, 1)); printf("40 的下标是%d\n", LocateElem(&L, 40)); SqListDestroy(&L); } int main() { //TestSqList1(); TestSqList2(); return 0; }

4.2.8 复杂度分析

插入的时间复杂度

a. 最好情况：位序i = n+1在表尾插入，插入时无需扩容，无需移动元素，时间复杂度为O(1)

b. 最坏情况：位序i = 1在表头插入，此时需要将所有元素整体往后移动 1 步，即移动语句要执行

n 次，再叠加需要扩容，异地扩容的最大的消耗是要拷贝 n 个元素，那么时间复杂度为O(n)

c. 平均情况：假设在任意位置前插入元素的概率p_i相等，则，则在长度为 n 的线性表中

插入一个元素时所需移动元素的平均次数为：

那么时间复杂度为O(n)

删除的时间复杂度

a. 最好情况：位序i = n在表尾删除，删除时无需移动元素，时间复杂度为O(1)

b. 最坏情况：位序i = 1在表头删除，此时需要将 i 位置后面的元素依次往前挪动覆盖，即挪动 n-

1 个数据，时间复杂度为O(n)

c. 平均情况：假设在任意位置删除元素的概率p_i相等，则，则在长度为 n 的线性表中删除

一个元素时所需移动元素的平均次数为：

那么时间复杂度为O(n)

下标查找的时间复杂度

a. 因为顺序表中的数组物理存储上是连续的，通过首地址常数次就是可以算出任意 i 位置的地址，

所以时间复杂度均是O(1)

按值查找的时间复杂度

a. 最好情况：查找的元素就在表头，此时比较 1 次即可找到，时间复杂度为O(1)

b. 最坏情况：查找的元素在表尾或不存在时，则需要比较 n 次，时间复杂度为O(n)

c. 平均情况：假设查找任意位置元素的概率p_i相等，则，则在长度为 n 的线性表中查找一

个值的比较平均比较次数为：

那么时间复杂度为O(n)

4.3 题1

题目：

分析：

解答：

int removeElement(int* nums, int numsSize, int val) { int src=0; int det=0; while(src<numsSize) { if(nums[src]!=val) { nums[det]=nums[src]; src++; det++; } else { src++; } } return det; }

4.4 题2

题目：

分析：

解答：

int removeDuplicates(int* nums, int numsSize) { int src=0; int dst=1; while(dst<numsSize) { if(nums[src]!=nums[dst]) { src++; nums[src]=nums[dst]; dst++; } else { dst++; } } return src+1; }