做英德红茶的网站,装修公司 网站模板,wordpress文章自动发布,上城区商城网站建设本章重点 线性表 顺序表 顺序表OJ题 1.线性表 线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结…本章重点 线性表 顺序表 顺序表OJ题 1.线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 2.顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表中的元素在内存中是相邻存储的每个元素都有一个对应的索引来标识其在顺序表中的位置。顺序表支持随机访问可以通过索引直接访问任意位置的元素。 顺序表一般可以分为 1. 静态顺序表使用定长数组存储元素。 静态顺序表的缺点 固定大小 静态顺序表的大小在创建时被固定下来无法动态地扩展或缩小。这意味着一旦初始化了静态顺序表其容量就无法改变。如果需要存储的元素数量超过初始分配的容量可能需要重新分配更大的空间并手动进行数据迁移。 内存浪费 如果静态顺序表的容量设置过大但实际存储的元素数量较少会导致内存浪费。因为未使用的部分空间也会被保留占用了额外的内存。 不灵活 由于容量固定静态顺序表可能无法适应动态变化的数据需求。当需要的容量超过初始设置时可能需要重新设计或重写代码。 初始化成本 静态顺序表在初始化时需要分配固定大小的内存空间而如果无法预估元素的最终数量就需要进行适当的空间规划这可能增加设计和开发的成本。 2. 动态顺序表使用动态开辟的数组存储。 3.顺序表接口实现
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{SLDataType* a; // 指向动态开辟的数组int size; // 有效数据个数int capicity; // 容量空间的大小
}SeqList;// 基本增删查改接口
//
// 顺序表初始化
void SeqListInit(SeqList * s);
// 检查空间如果满了进行增容
void CheckCapacity(SeqList* s);
// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* s);
// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* s);
// 顺序表查找
int SeqListFind(SeqList* s, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* s);
// 顺序表打印
void SeqListPrint(SeqList* s); 顺序表初始化void SeqListInit(SeqList * s); 代码中存在一些问题主要是关于C语言中函数参数传递方式的错误理解。C语言中的参数传递是值传递意味着函数接收的是参数的副本而不是原始的数据。因此当你在 SeqListInit 函数中修改 s 的值时实际上只是修改了传递进来的副本而不会影响原始的 s。为了解决这个问题需要通过指针传递来修改原始数据。 // 顺序表初始化
void SeqListInit(SeqList* s)
{s-a NULL;s-size 0;s-capicity 0;
} 但是我们需要在初始的时候就开辟一些空间这样更方便数据存储不用一上来就扩容。
// 顺序表初始化
void SeqListInit(SeqList* s)
{s-a (SeqList*)malloc(sizeof(SLDataType) * 4);if (s-a NULL){perror(malloc);//return;只是该函数退出程序依然运行exit(-1);//程序退出为-1}s-size 0;s-capicity 4;
} malloc函数malloc函数的返回值是void *使用malloc函数要在返回的时候转化为我们需要的类型。malloc(sizeof(SLDataType) * 4)这代表的是申请了4个SLDataType类型大小的空间。 malloc函数的使用要引头文件#includestdlib.h。 分配成功则返回指向被分配内存的指针分配失败则返回空指针NULL。 检查空间如果满了进行增容void CheckCapacity(SeqList* s);
// 检查空间如果满了进行增容
void CheckCapacity(SeqList* s)
{//满了需要扩容if (s-size s-capicity){//realloc,第二个参数是新空间的大小不是要扩多少SLDataType* temp (SLDataType*)realloc(s-a, s-capicity * 2 * sizeof(SLDataType));//扩容2倍if (temp NULL){perror(realloc);exit(-1);}s-a temp;s-capicity * 2;}
} realloc函数realloc函数的返回值是void *使用realloc函数要在返回的时候转化为我们需要的类型。realloc(s-a, s-capicity * 2 * sizeof(SLDataType))这代表的是申请了s-capicity * 2 个SLDataTypet型大小的空间。 我这里是扩充2倍空间。同时realloc函数,第二个参数是新空间的大小不是要扩多少 。 realloc函数的使用要引头文件#includestdlib.h。 分配成功则返回指向被分配内存的指针分配失败则返回空指针NULL。 顺序表尾插void SeqListPushBack(SeqList* s, SLDataType x);
// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x)
{CheckCapacity(s);s-a[s-size] x;//尾插数字s-size;//尾插后有效数字1
} 顺序表尾删void SeqListPopBack(SeqList* s);
// 顺序表尾删
void SeqListPopBack(SeqList* s)
{s-a[s-size - 1] 0;s-size--;
} 这样写有一个问题万一要删除的数字就是0你还把size-1的位置设置为0就没有意义了我们发现只用将size--就行有效数字就会少一个打印数据自然会少一个下次再尾插原本的数据就会被覆盖原数字也自然就被删除了。
// 顺序表尾删
void SeqListPopBack(SeqList* s)
{//s-a[s-size - 1] 0;s-size--;
} 这样写是不是还有问题假设删掉的数字比原本数字多怎么办程序直接崩了这样会出现越界访问的问题 // 顺序表尾删
void SeqListPopBack(SeqList* s)
{//方法一if(s-size 0)//保证不会被越界{return;}//s-a[s-size - 1] 0;s-size--;//方法二assert(s-size 0);//s-a[s-size - 1] 0;s-size--;
}
顺序表头插void SeqListPushFront(SeqList* s, SLDataType x);
// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x)
{CheckCapacity(s);//挪动数据int end s-size - 1;//最后一个数据while (end 0){s-a[end 1] s-a[end];end--;}s-a[0] x;s-size;
} 顺序表头删void SeqListPopFront(SeqList* s);
// 顺序表头删
void SeqListPopFront(SeqList* s)
{assert(s-size 0);//防止越界int begin 0;while (begin s-size - 1){s-a[begin] s-a[begin 1];begin;}s-size--;
} 顺序表查找int SeqListFind(SeqList* s, SLDataType x); 顺序表有顺序存取的功能因此按位查找元素可以直接通过数组下标定位取得。 // 顺序表查找
int SeqListFind(SeqList* s, SLDataType x)
{for (int i 0; i s-size; i){if (s-a[i] x)return i;}return -1;
} 顺序表在pos位置插入xvoid SeqListInsert(SeqList* s, size_t pos, SLDataType x); 顺序表的元素插入和插队是一个意思的。想象一下有一个人要插队他要插到第3个位置去那么他前面的两个人不用动而他后面的人都得动。具体步骤是最后面的那个人后退一个位置倒数第二个人后退到原来最后一个人的位置这样子后面的每个人依次后退最后就空出来了一个位置这个人就插队进去了。顺序表也是这么插入的。在插入操作完成后表长1多了一个人。 元素插入有一些要求 元素下标是否越界有没有插队到奇怪的位置顺序表存储空间是否满了有没有位置让你插队 // 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x)
{//检查pos是否合法assert(pos 0 pos s-size);//检查是否需要扩容CheckCapacity(s);int end s-size - 1;while (end pos){s-a[end 1] s-a[end];end--;}s-a[pos] x;s-size;
} 顺序表删除pos位置的值void SeqListErase(SeqList* s, size_t pos); 删除和插入的操作类型这里借用插队的例子说明。一群人在排队有一个人有事临时走了那么这个人的位置就空出来了后面的人就一个个往前一步补上这个空位。在删除操作完成后表长-1少了一个人。 元素删除有一些要求 元素下标是否越界走的人是不是这个排队里面的人顺序表存储空间是否为空有没有人可以走 // 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos)
{//检查pos是否合法assert(pos 0 pos s-size);int begin pos;while (begin s-size - 1){s-a[begin] s-a[begin 1];begin;}s-size--;
} 顺序表销毁void SeqListDestory(SeqList* s); 顺序表初始化的时候是用malloc函数向系统申请的空间malloc函数申请的空间是在内存的堆区堆区的空间不会被系统自动回收还需要用free函数释放空间。与malloc一样要引头文件#includestdlib.h。 // 顺序表销毁
void SeqListDestory(SeqList* s)
{free(s-a);//释放开辟的空间s-a NULL;s-size 0;s-capicity 0;
}
顺序表打印void SeqListPrint(SeqList* s);
// 顺序表打印
void SeqListPrint(SeqList* s)
{for (int i 0; i s-size; i){printf(%d , s-a[i]);}printf(\n);
}
修改顺序表pos位置的值
// 修改顺序表pos位置的值
void SeqListModify(SeqList* s, size_t pos, SLDataType x)
{assert(pos 0 pos s-size);//修改pos位置的值s-a[pos] x;
}
3.顺序表OJ题
1. 原地移除数组中所有的元素valOJ链接
https://leetcode.cn/problems/remove-element/
思路一暴力解法
这个题目暴力的解法就是两层for循环一个for循环遍历数组元素 第二个for循环更新数组。
删除过程如下 int removeElement(int* nums, int numsSize, int val)
{int size numsSize;for (int i 0; i size; i) {if (nums[i] val) { // 发现需要移除的元素就将数组集体向前移动一位for (int j i 1; j size; j) {nums[j - 1] nums[j];}i--; // 因为下标i以后的数值都向前移动了一位所以i也向前移动一位size--; // 此时数组的大小-1}}return size;
} 时间复杂度O(n^2)空间复杂度O(1) 思路二双指针法快慢指针法 通过一个快指针和慢指针在一个whiler循环下完成工作。
定义快慢指针
快指针寻找新数组的元素 新数组就是不含有目标元素的数组慢指针指向更新 新数组下标的位置
删除过程如下 int removeElement(int* nums, int numsSize, int val)
{int fastindex 0;int slowindex 0;while (fastindex numsSize){if (nums[fastindex] ! val){nums[slowindex] nums[fastindex];//赋值}else{fastindex;//发现需要移除的元素就将指针向后移动一位}}return slowindex;
} 时间复杂度O(n)空间复杂度O(1) 2. 删除排序数组中的重复项OJ链接https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 3. 合并两个有序数组OJ链接https://leetcode.cn/problems/merge-sorted-array/
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1 m;int end2 n;int end m n;while (end1 0 end2 0){if (nums1[end1] nums2[end2])nums1[end--] nums2[end2--];elsenums1[end--] nums1[end1--];}while (end2 0)nums1[end--] nums2[end2--];
} 本节结束啦
