数据结构_顺序表

用户10551528

发布于 2023-05-09 13:32:01

3680

发布于 2023-05-09 13:32:01

文章被收录于专栏：浴巾的学习分享贴

数据结构_SeqList顺序表

前言：此类笔记仅用于个人复习，内容主要在于记录和体现个人理解，详细还请结合bite课件、录播、板书和代码。

[toc]

线性表

线性表（linear list）是n个具有相同特性的元素的有限序列，是一种数据结构，包括：顺序表，列表，栈，队列，字符串等逻辑结构上：是线性结构，连续的一条直线物理结构上：不一定是连续的，通常是以数组或链表的形式存储

顺序表

用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。顺序表分为：

静态顺序表：用定长数组存储元素
动态顺序表：使用动态开辟的数组存储元素

静态顺序表由于容量是有限的，所以在实际应用的时候不如动态顺序表更灵活，动态顺序表在实际应用中更广泛

动态顺序表的实现

动态顺序表的接口：实现动态顺序表的增删查改 #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> // 要求：存储的数据从0开始，依次连续存储 // 静态的顺序表 // 问题：开小了，不够用。开大了，存在浪费。 //#define N 10000 //struct SeqList //{ // int a[N]; // int size; // 记录存储了多少个数据 //}; typedef int SLDataType;//给顺序表存储的数据类型int取别名，便于在后期见到之后就知道是定义的顺序表存储的类型 // 动态的顺序表 typedef struct SeqList { SLDataType* a; int size; // 存储数据个数 int capacity; // 存储空间大小 }SL, SeqList; void SeqListPrint(SeqList* psl);//顺序表打印函数 //void SLInit(SeqList* psl); void SeqListInit(SeqList* psl);//初始化顺序表 void SeqListDestroy(SeqList* psl);//销毁顺序表 void SeqListCheckCapacity(SeqList* psl);//检查顺序表容量，如果不够的话就进行扩容 // 时间复杂度是O(1) void SeqListPushBack(SeqList* psl, SLDataType x);//尾插 void SeqListPopBack(SeqList* psl);//尾插 // 时间复杂度是O(N) void SeqListPushFront(SeqList* psl, SLDataType x);//头插 void SeqListPopFront(SeqList* psl);//头删 // 在pos位置插入x void SeqListInsert(SeqList* psl, size_t pos, SLDataType x); // 删除pos位置的数据 void SeqListErase(SeqList* psl, size_t pos); // 顺序表查找 int SeqListFind(SeqList* psl, SLDataType x);各个函数具体的实现以及注意事项 顺序表数据打印函数 void SeqListPrint(SeqList* psl) { assert(psl); for (int i = 0; i < psl->size; ++i) { printf("%d ", psl->a[i]); } printf("\n"); }有一个断言，如果没有顺序表（没有顺序表的地址），那么就是一个错误断言当指针一定不能为空时，才能用断言，“指针一定不能为空”一般指的是其逻辑意义上比如这里，如果顺序表不存在，那么根本就不能进行打印，所以指针一定不能为空，要断言顺序表初始化函数 void SeqListInit(SeqList* psl)//涉及到实参的改变，一定要传地址 { assert(psl); psl->a = NULL; psl->size = 0; psl->capacity = 0; }

断言
注意参数！

形参是实参的拷贝，形参的改变不影响实参要想改变实参，应把实参的地址作为形参，然后通过访问地址存储的数据（解引用）改变实参顺序表销毁函数 void SeqListDestroy(SeqList* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->capacity = psl->size = 0; }

断言
先free掉malloc出来的空间（动态开辟的内存，在最后不使用的情况下一定要free掉，有始有终，防止内存泄漏）
指针指向空，数据清为零（也可以是别的值比如-1）

顺序表容量检查函数 void SeqListCheckCapacity(SeqList* psl) { assert(psl); // 如果满了，我们要扩容 if (psl->size == psl->capacity) { size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; //这里进行一个判断，如果原来的顺序表是刚创建的，还没有数据，那么先分配四个数据的大小 SLDataType* tmp = realloc(psl->a, sizeof(SLDataType)*newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); //内存中找不到这么大的空间了，扩容失败（一般不会出现这种情况） } else { psl->a = tmp; psl->capacity = newCapacity; //把新开辟的空间地址赋值给顺序表，增大容量 } } }

断言
relloc
1. 用法，第一个参数是需要扩容的空间的地址，第二个是大小，单位为字节，返回的是开辟好的空间的地址
2. 如果第一个参数是NULL，那么作用相当于malloc
3. 扩容
4. 原地扩容
如果原来的空间后面的空间的足够大，够开辟所需要的新空间的大小，那么就会进行原地扩容，返回的还是原来的需要扩容的空间的地址

尾插（优化前） void SeqListPushBack(SeqList* psl, SLDataType x) { assert(psl); SeqListCheckCapacity(psl);//尾插前先检查一下容量（包括扩容） psl->a[psl->size] = x; psl->size++;//数据个数++ }尾删（优化前） void SeqListPopBack(SeqList* psl) { assert(psl); if (psl->size > 0)//防止数据在没有数据的时候把数据个数减为负的，产生错误 { psl->size--; } }这里如果进行尾删的话，直接减小size的大小就可以，容量、数据之类的都没有必要修改 size的大小就标定着数据的多少，顺序表不会进行超过size大小的操作被“删除”的数据没有必要进行内容覆盖，因为覆盖无非就是用别的数字覆盖掉原有的数字，size都改变了，不会读取之前被“删除”的数据的内容，没必要多此一举啊头插（优化前） void SeqListPushFront(SeqList* psl, SLDataType x) { assert(psl); SeqListCheckCapacity(psl);//增加数据前必须检查容量，防止越界 // 挪动数据，腾出头部空间//从后往前挪 int end = psl->size - 1; while (end >= 0) { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x; psl->size++; }头删（优化前） void SeqListPopFront(SeqList* psl) { assert(psl); // 挪动数据覆盖删除，从前往后进行 if (psl->size > 0)//防止没有数据时还头删 { int begin = 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; ++begin; } --psl->size; } }在尾删的时候，直接通过减小size就实现了“尾删” 那是不是在头删的时候，直接让数组的指针往后移一位就可以了呢不行因为数组是通过动态开辟的，地址必须是动态开辟的完整的空间的首地址在进行动态空间释放free的时候，必须free开头的位置（完整释放）在指定位置插入指定数据 // 在pos位置插入x //void SeqListInsert(SeqList* psl, int pos, SLDataType x) void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) { // 暴力检查（是否为空指针） assert(psl); // 温和检查（检查想要插入的位置是否超过数组本身范围） if (pos > psl->size) { printf("pos 越界：%d\n", pos); return; //exit(-1); } // 暴力检查 //assert(pos <= psl->size); SeqListCheckCapacity(psl);//进行增加前必须检查容量，防止越界 size_t end = psl->size; while (end > pos)//从pos位置往后转移数据 { psl->a[end] = psl->a[end-1]; --end; } psl->a[pos] = x; psl->size++; }删除指定位置的数据 void SeqListErase(SeqList* psl, size_t pos) { assert(psl);//断言是否为空指针 assert(pos < psl->size);//断言是否越界 size_t begin = pos + 1; while (begin < psl->size)//将数据前移 { psl->a[begin - 1] = psl->a[begin]; ++begin; } psl->size--; }查找指定数据 int SeqListFind(SeqList* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; ++i)//直接进行遍历 { if (psl->a[i] == x) { return i;//返回下标 } } return -1; }顺序表的优化！由于有“在指定位置插入指定数据”以及“删除指定位置的数据”功能比较具有通用性（因为指定位置当然包括头部和尾部）因此可以对于尾插、头插、尾删、头删进行优化 如果存在复用的代码段，可以写一个函数来复用，避免冗杂，还能提升代码效率（有时还能相互复用） 尾插（被注释掉的是优化前的代码） void SeqListPushBack(SeqList* psl, SLDataType x) { assert(psl); /*SeqListCheckCapacity(psl); psl->a[psl->size] = x; psl->size++;*/ SeqListInsert(psl, psl->size, x); }这里直接指定要插入的位置下标为数组中最后一个位置往后的地方头插（被注释掉的是优化前的代码） void SeqListPushFront(SeqList* psl, SLDataType x) { assert(psl); //SeqListCheckCapacity(psl); //// 挪动数据，腾出头部空间 //int end = psl->size - 1; //while (end >= 0) //{ // psl->a[end + 1] = psl->a[end]; // --end; //} //psl->a[0] = x; //psl->size++; SeqListInsert(psl, 0, x); }尾删（被注释掉的是优化前的代码） void SeqListPopBack(SeqList* psl) { assert(psl); //psl->a[psl->size - 1] = 0; /*if (psl->size > 0) { psl->size--; }*/ SeqListErase(psl, psl->size-1); }被删除的位置指向数组的最后一个元素头删（被注释掉的是优化前的代码） void SeqListPopFront(SeqList* psl) { assert(psl); // 挪动数据覆盖删除 /*if (psl->size > 0) { int begin = 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; ++begin; } --psl->size; }*/ SeqListErase(psl, 0); }

关于顺序表的OJ题

移除元素 OJ链接<要求时间复杂的为O(N)，空间复杂复为O(1)>

要求时间复杂度为O(N) 思路一：遍历数组，遍历过程中，没找到一个val，就往前挪动元素覆盖val <img src="https://map--depot.oss-cn-hangzhou.aliyuncs.com/image/image-20220723074154705.png" alt="image-20220723074154705" style="zoom: 50%;" /> 遍历一次时间复杂度是N，在遍历中还要进行元素前移，元素前移的时间复杂度最坏为N（比如数组内全是val或大多是val），此算法时间复杂度总共是O(N^2) 空间复杂度O(1) 思路二：双指针（初步思想）重新开辟一个大小相等的新数组new，一个指针src指向原数组nums，一个指针dst指向new，src指向元素不为val时，赋值给新数组，src和dst后移；src指向val，src直接后移。src遍历完原数组后返回dst <img src="https://map--depot.oss-cn-hangzhou.aliyuncs.com/image/image-20220723081143132.png" alt="image-20220723081143132" style="zoom: 67%;" /> 时间复杂度：O(N) 空间复杂度：O(N) “双指针”是一种定位思想，数组下标也可以充当双指针（本题就是）思路三：双指针（进阶）不用额外开辟数组，在原数组上进行双指针，src和dst都指向原数组，src遍历原数组，遇到非val就把元素赋值给dst的位置上，dst和src再双双后移；遇到val，src直接后移一位。src遍历完数组之后返回dst。

删除排序数组中的重复项OJ链接

思路一：双指针（下标充当指针）设置一个src，一个dst指针，src从数组的第二位开始，dst从数组的第一位开始（或者都从第一位开始，这里都是可以的，只是具体细节方面有些不同） src前面的元素如果和src的元素不同，就赋值给dst，然后两个指针在向后移一位，继续判断下面的；否则不赋值，只src往后移。直到src=numsSize为止然后把数组的最后一位元素直接赋值给dst位置，dst向后移动一个位，直接返回dst（这样dst的值就是元素个数）无论最后一个元素跟前面的是否重复，“非重复元素”（赋给dst的那些值）里面都没有最后一个元素如果最后一个元素跟前面的重复，那么一直都没有被赋值给dst 如果不重复，因为结束了循环，也没法赋值所以最后一个元素直接赋值给dst就可以

思路二：

相当于将数组进行了细分，dur指向元素，next先指向cur的下一个元素，来判断元素是不是重复的，如果元素是不重复的，那么就赋值给dst，cur和next后移；如果cur的值和next的值一样，则说明存在重复元素的区间，next在里面遍历，直到遍历出重复区间，把cur的值赋给dst，再让cur指向下一个区间，next再遍历，直到next=numsSize（遍历完整个数组）

合并两个有序数组OJ链接

解析：原题中的m就是需要nums1中要合并的元素的个数，n是nums2中要合并的元素的个数，也就是说，把nums2中的前n个元素赋值到nums1中后n个元素就可以还要求返回的数组是非递减的（也就是升序和重复的）思路一：用memmove+sort（可以是bubble sort，可以是qsort等） bubble sort时间复杂度是O(N^2)，qsort是O(N*logN)，太大，不优先考虑这种思路思路二：归并重新开一个数组长度为m+n的数组new，dst指向数组第一个元素 i指向nums1第一个元素，j指向nums2第一个元素 i的元素和j的元素进行比较，小的元素放在new里，并且指针后移相等的话，随便哪一个放在new里，然后指针后移直到任何一方走完（i=m-1或j=n-1）把另一方剩余的元素都放到new里（m、n是限制的数组实际数据个数，应以这个为标准，而不是数组大小）

思路三：如果要求不能额外开数组 i指向nums1第m个元素（i=m-1），j指向num2第n个元素，dst指向nums1最后一个元素（第n+m个元素，dst=n+m-1） i的元素和j的进行比较，大的赋值给dst i<0的时候，说明nums1已经没有比nums2小的了，把nums2里剩余的元素赋值给dst就行 j<0的时候，直接结束就可以，因为nums1中剩下的元素直接保留下来即可