网站首页搜索功能的id怎做,seo网站合作,wordpress主机免费,商标 做网站 是几类目录 一、线性表二、顺序表1. 静态顺序表2. 动态顺序表2.1 动态顺序表的实现分析2.2 动态顺序表的实现2.3 动态顺序表存在的问题 三、与数组有关的面试题1. 移除元素2. 删除有序数组中的重复项 一、线性表
线性表#xff08;linear list#xff09;是n个具有相同特性的数据元… 目录 一、线性表二、顺序表1. 静态顺序表2. 动态顺序表2.1 动态顺序表的实现分析2.2 动态顺序表的实现2.3 动态顺序表存在的问题 三、与数组有关的面试题1. 移除元素2. 删除有序数组中的重复项 一、线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。
二、顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表分为静态顺序表和动态顺序表静态顺序表是数组大小固定只能存储定量的数组超出了就不能存储动态顺序表使用一个指针管理动态数组当数组不够存储时可以使用 realloc() 函数进行动态增容。
而一般情况下我们都是使用动态顺序表因为静态顺序表大小固定多了不够用少了浪费空间。
1. 静态顺序表
这里这给出静态顺序表的大体框架并不实现。
// 静态顺序表// 容量
#define CAPACITY 100// 数据类型
typedef int SSL_DataType;// 静态顺序表结构声明
typedef struct Static_SeqList
{SSL_DataType datas[CAPACITY]; // 数据size_t size; // 当前数据个数
}SSeqList;// 操作// 初始化
void InitSSeqList(SSeqList* pssl);// 尾插
void SSeqListPushBack(SSeqList* pssl, SSL_DataType data);// 尾删
void SSeqListPopBack(SSeqList* pss1);// 头插
void SSeqListPushFront(SSeqList* pssl, SSL_DataType data);// 头删
void SSeqListPopFront(SSeqList* pssl, SSL_DataType data);// 查找
void SSeqListFind(SSeqList* pssl, SSL_DataType data);// 在 pos 位置插入
void SSeqListInsert(SSeqList* pssl, size_t pos, SSL_DataType data);// 删除 pos 位置的数据
void SSeqListErase(SSeqList* pssl, size_t pos, SSL_DataType data);// 打印
void SSeqListPrint(SSeqList* pssl);如果需要使用静态顺序表那么就在另一个 .c 文件中实现其操作功能然后在主函数中调用即可。
2. 动态顺序表
相比于静态顺序表动态顺序表增加了一个 capacity 成员表示容量因为需要比较判断是否增容。还增加了几个操作功能容量检查和销毁顺序表销毁顺序表也就是释放动态内存。
2.1 动态顺序表的实现分析
1成员动态申请数据 datas 的初始空间当前数据的个数 size容量的大小 capacity 2操作 a. 初始化申请数据空间当前数据个数 size 归零容量 capacity 设置为初始值 b. 检查容量当执行插入操作的时候需要检查当前顺序表是否需要增容 c. 头插在表头插入数据 d. 头删在表头删除数据 e. 尾插在表尾插入数据 f. 尾删在表尾删除数据 g. 查找在表中查找指定数据找到了返回下标没找到返回 -1 h. 插入在给定下标处插入数据下标范围 0-size i. 删除在给定下标处删除数据下标范围 0-size-1 j. 打印打印顺序表的所有数据 k. 销毁释放申请空间size 和 capacity 归零
2.2 动态顺序表的实现
下面是顺序表的三个文件
头文件SeqList.h
// 动态顺序表// 数据类型
typedef int SL_DataType;// 初始容量
#define INIT_CAPACITY 2// 动态顺序表结构声明
typedef struct SeqList
{SL_DataType* datas; // 数据size_t size; // 当前数据个数size_t capacity; // 当前容量
}SeqList;// 操作声明// 初始化
void SeqListInit(SeqList* psl);// 检查容量
void CheckCapacity(SeqList* psl);// 尾插
void SeqListPushBack(SeqList* psl, SL_DataType data);// 尾删
void SeqListPopBack(SeqList* psl);// 头插
void SeqListPushFront(SeqList* psl, SL_DataType data);// 头删
void SeqListPopFront(SeqList* psl);// 查找
int SeqListFind(SeqList* psl, SL_DataType data);// 在 pos 位置插入数据
void SeqListInsert(SeqList* psl, size_t pos, SL_DataType data);// 删除 pos 位置数据
void SeqListErase(SeqList* psl, size_t pos);// 打印顺序表
void SeqListPrint(SeqList* psl);// 销毁顺序表
void SeqListDestory(SeqList* psl);操作实现文件SeqList.c
// 头文件
#include SeqList.h
#include assert.h
#include stdlib.h// 操作定义// 初始化
void SeqListInit(SeqList* psl)
{// 检查空指针assert(psl);// 容量psl-capacity INIT_CAPACITY;// 申请空间psl-datas (SL_DataType*)malloc(sizeof(SL_DataType) * psl-capacity);// 判断是否申请成功if (NULL psl-datas){perror(SeqListInit::malloc: );return;}// 当前数据个数psl-size 0;
}// 检查容量
void CheckCapacity(SeqList* psl)
{assert(psl);// 判断是否需要增容if (psl-size psl-capacity){// 增容两倍SL_DataType* tmp (SL_DataType*)realloc(psl-datas, sizeof(SL_DataType) * psl-capacity * 2);// 判断是否增容成功if (NULL tmp){perror(CheckCapacity::realloc: );return;}// 成功psl-datas tmp;psl-capacity * 2;tmp NULL;}}// 尾插
void SeqListPushBack(SeqList* psl, SL_DataType data)
{assert(psl);// 检查增容CheckCapacity(psl);// 插入psl-datas[psl-size] data;
}// 尾删
void SeqListPopBack(SeqList* psl)
{assert(psl);// 检查当前表中是否有数据if (0 psl-size){printf(There is no data!\n);return;}// 删除--psl-size;
}// 头插
void SeqListPushFront(SeqList* psl, SL_DataType data)
{assert(psl);// 判断增容CheckCapacity(psl);// 把所有元素往后挪动int i;for (i (int)psl-size; i 0; --i)psl-datas[i] psl-datas[i - 1];// 插入psl-datas[0] data;psl-size;
}// 头删
void SeqListPopFront(SeqList* psl)
{assert(psl);// 检查当前表中是否有数据if (0 psl-size){printf(There is no data!\n);return;}// 把后面 sz-1 个元素往前移int i;for (i 1; i psl-size; i)psl-datas[i - 1] psl-datas[i];// 删除--psl-size;}// 查找
int SeqListFind(SeqList* psl, SL_DataType data)
{assert(psl);int i;for (i 0; i psl-size; i){// 找到了返回下标if (psl-datas[i] data){return i;}}// 没找到返回 -1return -1;
}// 在 pos 位置插入数据
void SeqListInsert(SeqList* psl, size_t pos, SL_DataType data)
{assert(psl);// 判断下标是否合法if (pos0 || pos psl-size){printf(Illegal subscript!\n);return;}// 判断增容CheckCapacity(psl);// 把从该下标开始的元素都往后移一位int i;for (i (int)psl-size; i pos; --i){psl-datas[i] psl-datas[i - 1];}// 插入psl-datas[pos] data;psl-size;
}// 删除 pos 位置数据
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl);// 判断坐标是否合法if (pos 0 || pos psl-size){printf(Illegal subscript!\n);return;}// 把从 pos1 开始的元素都往前移int i;for (i (int)pos 1; i psl-size; i)psl-datas[i - 1] psl-datas[i];// 删除--psl-size;
}// 打印顺序表
void SeqListPrint(SeqList* psl)
{assert(psl);// 判断表中是否有数据if (0 psl-size){printf(There is no data!\n);return;}// 打印int i;for (i 0; i psl-size; i)printf(%d , psl-datas[i]);printf(\n);
}// 销毁顺序表
void SeqListDestory(SeqList* psl)
{assert(psl);// 释放空间free(psl-datas);psl-datas NULL;psl-capacity 0;psl-size 0;
}测试文件test.c
// 头文件
#include SeqList.h// 头插头删测试
void test1(SeqList* PSL)
{// 头插加打印SeqListPushFront(PSL, 1);SeqListPrint(PSL);SeqListPushFront(PSL, 2);SeqListPrint(PSL);SeqListPushFront(PSL, 3);SeqListPrint(PSL);SeqListPushFront(PSL, 4);SeqListPrint(PSL);SeqListPushFront(PSL, 5);SeqListPrint(PSL);// 头删加打印SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);
}// 尾插尾删测试
void test2(SeqList* PSL)
{// 尾插加打印SeqListPushBack(PSL, 1);SeqListPrint(PSL);SeqListPushBack(PSL, 2);SeqListPrint(PSL);SeqListPushBack(PSL, 3);SeqListPrint(PSL);SeqListPushBack(PSL, 4);SeqListPrint(PSL);SeqListPushBack(PSL, 5);SeqListPrint(PSL);// 尾删加打印SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);
}// pos 位置插入删除测试
void test3(SeqList* PSL)
{// 在 pos 位置插入加打印SeqListInsert(PSL, 0, 1);SeqListPrint(PSL);SeqListInsert(PSL, 1, 9);SeqListPrint(PSL);SeqListInsert(PSL, 0, 8);SeqListPrint(PSL);SeqListInsert(PSL, 1, 3);SeqListPrint(PSL);SeqListInsert(PSL, 1, 7);SeqListPrint(PSL);SeqListInsert(PSL, 3, 6);SeqListPrint(PSL);// 在 pos 位置删除加打印SeqListErase(PSL, 0);SeqListPrint(PSL);SeqListErase(PSL, PSL-size - 1);SeqListPrint(PSL);SeqListErase(PSL, 1);SeqListPrint(PSL);SeqListErase(PSL, 1);SeqListPrint(PSL);SeqListErase(PSL, 0);SeqListPrint(PSL);SeqListErase(PSL, 0);SeqListPrint(PSL);
}// 查找功能测试
void test4(SeqList* PSL)
{// 插入数据SeqListPushBack(PSL, 1);SeqListPushBack(PSL, 3);SeqListPushBack(PSL, 5);SeqListPushBack(PSL, 7);SeqListPushBack(PSL, 9);SeqListPushBack(PSL, 10);SeqListPushBack(PSL, 8);SeqListPushBack(PSL, 6);SeqListPushBack(PSL, 4);SeqListPushBack(PSL, 2);// 打印SeqListPrint(PSL);// 查找int i;for (i 1; i 10; i){printf(元素 %d 的下标为: %d\n, i, SeqListFind(PSL, i));}}int main()
{// 测试顺序表// 创建顺序表SeqList SL;// 初始化顺序表SeqListInit(SL);// 头插头删测试printf(头插头删测试:\n);test1(SL);// 尾插尾删测试printf(\n\n尾插尾删测试:\n);test2(SL);// 在 pos 位置插入删除测试printf(\n\n在 pos 位置插入删除测试:\n);test3(SL);// 查找功能测试printf(\n\n查找功能测试:\n);test4(SL);// 销毁顺序表SeqListDestory(SL);return 0;
}该顺序表的每个功能作者都测试过基本上没有问题。但是在调试的时候发现了动态内存的越界访问问题经过调试发现是扩容之后的容量 capacity 没有乘以 2。总得来说顺序表的增删查改基本功能均已实现如果大家发现了上述代码的错误欢迎告知。
下面是在 x86 环境下程序测试的结果
2.3 动态顺序表存在的问题
通过对上述代码的学习发现动态顺序表存在以下问题 1当进行头插、头删、插入和删除这四个操作的时候需要挪动数组的数据时间复杂度为 O(n) 2当容量不够的时候需要增容每次增容后的容量是上一次的两倍但是这样肯定会有空间的浪费。且增容需要申请新空间拷贝数据释放旧空间这样会产生不小的时间消耗。
三、与数组有关的面试题
既然顺序表是在数组的基础上实现的那么现在来看几道与数组有关的面试题。
1. 移除元素
题目描述 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作 1更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 2返回 k。
示例 1 输入nums [3,2,2,3], val 3 输出2, nums [2,2,,] 解释你的函数函数应该返回 k 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。
示例 2 输入nums [0,1,2,2,3,0,4,2], val 2 输出5, nums [0,1,4,0,3,,,_] 解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。
提示 0 nums.length 100 0 nums[i] 50 0 val 100
题目OJ链接 链接: link
题目解析 这种在数组中原地删除数据的题目一般使用前后指针法前指针 front后指针 back。front 和 back 刚开始均指向数组首元素只要 back 指向的元素的值不为 val则 *front *back。要是后指针指向的元素的值为 val则 front 不动back。重复上述步骤直到 back 指向数组的尾后元素。最后返回 front 与数组首元素地址的差值。
图示过程
可以发现最后要删除的数不是被后面的数覆盖了就是跑到后面去了。而其他数都按照原来的顺序跑到前面去了。
代码如下
// 移除元素
void remove_element(int* arr, int sz, int val)
{// 前后指针int* front arr;int* back arr;// 移除while (back arr sz){if (*back val)back;else*front *back;}// 返回return front - arr;
}时间复杂度 O(n) 空间复杂度 O(1)
2. 删除有序数组中的重复项
题目描述 给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
1更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 2返回 k 。
示例 1 输入nums [1,1,2] 输出2, nums [1,2,_] 解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2 输入nums [0,0,1,1,1,2,2,3,3,4] 输出5, nums [0,1,2,3,4] 解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示 1 nums.length 3 * 104 -104 nums[i] 104 nums 已按 非严格递增 排列
题目OJ链接 link
题目思路 本题也是使用前后指针法前后指针刚开始都是指向数组首元素若来指针指向的数组元素的值相同那么 back 指针往后走直到两个指针指向的值不同然后先自增 front 指针然后把 back 指向元素的值赋给 front 指向元素的值。重复上述步骤直到 back 指向数组的尾后元素。最后返回 front 与数组首元素地址的差值。
图示过程
代码如下
// 删除有序数组中的重复项
int removeDuplicates(int* arr, int sz)
{// 前后指针int* front arr;int* back arr;// 开始删除while (back arr sz){if (*back *front)back;else*(front) *back;}// 返回return (int)(front - arr);
}时间复杂度 O(n) 空间复杂度 O(1)
