厦门市思明区建设局网站高端网站开发成本

当前位置： 首页 > news >正文

厦门市思明区建设局网站,高端网站开发成本,建网站找哪家,网站需要怎么做的目录 一、线性表 二、顺序表 1.顺序表的概念以及结构 2.顺序表的接口实现 3.顺序表完整代码 三、顺序表的经典题目 1.移除元素 2.删除有序数组中的重复项 3.合并两个有序数组 一、线性表 在了解顺序表前#xff0c;我们得先了解线性表的概念 线性表#xff08;linear…目录 一、线性表 二、顺序表 1.顺序表的概念以及结构 2.顺序表的接口实现 3.顺序表完整代码 三、顺序表的经典题目 1.移除元素 2.删除有序数组中的重复项 3.合并两个有序数组 一、线性表 在了解顺序表前我们得先了解线性表的概念 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储   二、顺序表 1.顺序表的概念以及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改 顺序表一般可以分为静态顺序表和动态顺序表 静态顺序表 typedef int SLDateType;#define N 10typedef struct SeqList {SLDateType a[N];int size; }SL; 如上代码所示就是静态顺序表的定义。但是静态顺序表很不好用因为开多了内存浪费开少了不够用 动态顺序表 //动态顺序表 typedef int SLDateType;typedef struct SeqList {SLDateType* a;//指向数据的指针int size;int capacity; //容量 }SL; 如上代码所示动态的顺序表就是通过一个指针来指向数据。为了动态管理所以要添加一个容量的变量 2.顺序表的接口实现 我们使用顺序表的目的就是为了增删查改一些数据。为此接口主要围绕增删查改。 1.顺序表接口声明 //顺序表的初始化 void SeqListInit(SL* ps); //顺序表的销毁 void SeqListDestroy(SL* ps); //顺序表的打印 void SeqListPrint(SL ps); //顺序表的尾插 void SeqListPushBack(SL* ps,SLDateType x); //顺序表的头插 void SeqListPushFront(SL* ps, SLDateType x); //顺序表的尾删 void SeqListPopBack(SL* ps); //顺序表的头删 void SeqListPopFront(SL* ps); //顺序表的查找 int SeqListFind(SL* ps, SLDateType x); //顺序表在pos位置的插入 void SeqListInsert(SL* ps, int pos, SLDateType x); //顺序表在pos位置的删除 void SeqListErase(SL* ps, int pos); 如上代码所示对于顺序表我们主要的目的就是增删查改因此我们所需要实现的接口就又初始化、销毁、打印、尾插、头插、尾删、头删、查找、在某位置插入、在某位置删除等 2.顺序表的初始化 //顺序表的初始化 void SeqListInit(SL* ps) {assert(ps);ps-a (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);if (ps-a NULL){perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY; } 如上代码所示我们的函数参数是顺序表的指针返回类型是void。 首先肯定ps是不可能为空的因为ps是顺序表的地址。 然后我们让顺序表的数据指针指向的数组初始容量设置为INIT_CAPACITY这个容量由宏来自定义。然后判断是否开辟内存成功。 如果成功则将size置为0size代表的是当前顺序表内已经存放的数据个数。 2.顺序表的销毁 //顺序表的销毁 void SeqListDestroy(SL* ps) {assert(ps);free(ps-a);ps-a NULL;ps-size 0;ps-capacity 0; } 我们在来看一下顺序表的销毁对于顺序表的销毁也是比较简单的我们的顺序表中数据指针所指向的区域是在堆区的所以我们要对这个堆区进行释放掉。然后将其置空最后size和capacity都置为0即可 3.顺序表打印 //顺序表的打印 void SeqListPrint(SL s) {int i 0;for (i 0; i s.size; i){printf(%d , s.a[i]);}printf(\n); } 如上代码所示由于是打印数据所以我们传一个形参就已经可以了。当然传顺序表的地址也是没有任何问题的。然后就是使用一个循环来进行打印即可。 4.顺序表的尾插以及扩容函数 //扩容函数 void CheckCapacity(SL* ps) {assert(ps);if (ps-size ps-capacity){SLDateType* tmp (SLDateType*)realloc(ps-a, sizeof(SLDateType) * (ps-capacity) * 2);if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;} } //顺序表的尾插 void SeqListPushBack(SL* ps,SLDateType x) {assert(ps);CheckCapacity(ps);ps-a[ps-size] x;ps-size; } 如上代码所示我们想要对顺序表进行尾插那么首先我们得确保一下当前的容量是否足够为了代码的简洁我们直接将检查容量封装成一个函数在检查容量的过程中如果size和capacity相等那么就意味着函数需要扩容了。我们使用realloc函数进行扩容即可需要注意的是进行扩容的时候要使用一个新的指针进行接收这个扩容后的地址不然一旦扩容失败后果得不偿失。我们一般采用的是扩容二倍。当然这里我们可以根据自己的想法进行调整。 扩容成功以后由于是一个数组那么就很简单的直接将数组的最后一个元素直接赋值即可然后size就可以了 5.顺序表的头插 //顺序表的头插 void SeqListPushFront(SL* ps, SLDateType x) {assert(ps);CheckCapacity(ps);int i 0;for (i ps-size - 1; i 0; i–){ps-a[i 1] ps-a[i];}ps-a[0] x;ps-size; } 对于顺序表的头插我们仍然是先检查容量这里就体现我们之前将扩容封装成一个一个函数的优势了。然后使用一个循环将整个数组的值向后移动一个空间。最后将第一个元素给插入x即可 6.顺序表的尾删 //顺序表的尾删 void SeqListPopBack(SL* ps) {assert(ps);if (ps-size 0){printf(无可删除数据\n);return;}ps-size–; } 对于这个尾删我们特别需要主要的是当size为0的时候就没有数据不需要删除即可这里可以采用assert暴力截止也可以使用return温柔的拦截 然后我们直接让size–就可以了 7.顺序表的头删 //顺序表的头删 void SeqListPopFront(SL* ps) {assert(ps);if (ps-size 0){printf(无可删除数据\n);return;}int i 0;for (i 0; i ps-size - 1; i){ps-a[i] ps-a[i 1];}ps-size–; } 对于顺序表的头删也是需要注意size为0的情况然后将从下标为1的元素开始全体元素向前移动的一个空间即可最后size– 8.顺序表的查找 //顺序表的查找 int SeqListFind(SL* ps, SLDateType x) {assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1; } 对于顺序表的查找我们就直接采用循环遍历的方式即可如果找到了则返回下标否则返回-1 9.顺序表在pos位置的插入 //顺序表在pos位置的插入 void SeqListInsert(SL* ps, int pos, SLDateType x) {assert(ps);assert(pos 0 pos ps-size);CheckCapacity(ps);int i 0;for (i ps-size - 1; i pos; i–){ps-a[i 1] ps-a[i];}ps-a[pos] x;ps-size; } 如上代码所示在pos位置的插入那么首先需要注意的是pos的范围要合理pos应该大于等于0且小于等于sizepos等于size其实就是尾插 然后检查容量使用循环将原来pos以及之后的位置统一向后移动一个空间然后将pos位置的值赋值即可最后size 10.顺序表在pos位置的删除 //顺序表在pos位置的删除 void SeqListErase(SL* ps, int pos) {assert(ps);assert(pos 0 pos ps-size);int i 0;for (i pos; i ps-size - 1; i){ps-a[i] ps-a[i 1];}ps-size–; } 对于在pos位置的删除那么思路与前面也是极其相似的首先需要注意的是pos的范围这里要小心了pos是不可以等于size的 然后就是通过循环将pos后面的数据统一向前覆盖即可 3.顺序表完整代码 SeqList.h #pragma once //静态顺序表 //typedef int SLDateType; // //#define N 10 // //typedef struct SeqList //{ // SLDateType a[N]; // int size; //}SL; #includestdio.h #includemalloc.h #includeassert.h #define INIT_CAPACITY 4 //动态顺序表 typedef int SLDateType;typedef struct SeqList {SLDateType* a;//指向数据的指针int size;int capacity; //容量 }SL;//顺序表的初始化 void SeqListInit(SL* ps); //顺序表的销毁 void SeqListDestroy(SL* ps); //顺序表的打印 void SeqListPrint(SL ps); //顺序表的尾插 void SeqListPushBack(SL* ps,SLDateType x); //顺序表的头插 void SeqListPushFront(SL* ps, SLDateType x); //顺序表的尾删 void SeqListPopBack(SL* ps); //顺序表的头删 void SeqListPopFront(SL* ps); //顺序表的查找 int SeqListFind(SL* ps, SLDateType x); //顺序表在pos位置的插入 void SeqListInsert(SL* ps, int pos, SLDateType x); //顺序表在pos位置的删除 void SeqListErase(SL* ps, int pos); SeqList.c #define _CRT_SECURE_NO_WARNINGS 1 #includeSeqList.h//顺序表的初始化 void SeqListInit(SL* ps) {assert(ps);ps-a (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);if (ps-a NULL){perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY; } //顺序表的销毁 void SeqListDestroy(SL* ps) {assert(ps);free(ps-a);ps-a NULL;ps-size 0;ps-capacity 0; } //顺序表的打印 void SeqListPrint(SL s) {int i 0;for (i 0; i s.size; i){printf(%d , s.a[i]);}printf(\n); } //扩容函数 void CheckCapacity(SL* ps) {assert(ps);if (ps-size ps-capacity){SLDateType* tmp (SLDateType*)realloc(ps-a, sizeof(SLDateType) * (ps-capacity) * 2);if (tmp NULL){perror(realloc fail);return;}ps-a tmp;ps-capacity * 2;} } //顺序表的尾插 void SeqListPushBack(SL* ps,SLDateType x) {assert(ps);CheckCapacity(ps);ps-a[ps-size] x;ps-size; } //顺序表的头插 void SeqListPushFront(SL* ps, SLDateType x) {assert(ps);CheckCapacity(ps);int i 0;for (i ps-size - 1; i 0; i–){ps-a[i 1] ps-a[i];}ps-a[0] x;ps-size; } //顺序表的尾删 void SeqListPopBack(SL* ps) {assert(ps);if (ps-size 0){printf(无可删除数据\n);return;}ps-size–; } //顺序表的头删 void SeqListPopFront(SL* ps) {assert(ps);if (ps-size 0){printf(无可删除数据\n);return;}int i 0;for (i 0; i ps-size - 1; i){ps-a[i] ps-a[i 1];}ps-size–; } //顺序表的查找 int SeqListFind(SL* ps, SLDateType x) {assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1; } //顺序表在pos位置的插入 void SeqListInsert(SL* ps, int pos, SLDateType x) {assert(ps);assert(pos 0 pos ps-size);CheckCapacity(ps);int i 0;for (i ps-size - 1; i pos; i–){ps-a[i 1] ps-a[i];}ps-a[pos] x;ps-size; } //顺序表在pos位置的删除 void SeqListErase(SL* ps, int pos) {assert(ps);assert(pos 0 pos ps-size);int i 0;for (i pos; i ps-size - 1; i){ps-a[i] ps-a[i 1];}ps-size–; } Test.c #define _CRT_SECURE_NO_WARNINGS 1 #includeSeqList.hvoid TestSeqList1() {SL s;SeqListInit(s);SeqListPushBack(s, 1);SeqListPushBack(s, 2);SeqListPushBack(s, 3);SeqListPushBack(s, 4);SeqListPushBack(s, 5);SeqListPrint(s);SeqListPushFront(s, 4);SeqListPushFront(s, 3);SeqListPushFront(s, 2);SeqListPushFront(s, 1);SeqListPrint(s);SeqListPopBack(s);SeqListPopBack(s);SeqListPopBack(s);SeqListPrint(s);SeqListPopFront(s);SeqListPopFront(s);SeqListPopFront(s);SeqListPrint(s);SeqListPopFront(s);SeqListPrint(s);SeqListPopFront(s);SeqListPrint(s);SeqListPopFront(s);SeqListPrint(s);SeqListPopFront(s);SeqListPrint(s);SeqListPopFront(s);SeqListPopFront(s);} void TestSeqList2() {SL s;SeqListInit(s);SeqListPushBack(s, 1);SeqListPushBack(s, 2);SeqListPushBack(s, 3);SeqListPushBack(s, 4);SeqListPushBack(s, 5);SeqListPrint(s);int pos SeqListFind(s, 3);SeqListInsert(s, pos, 5);SeqListInsert(s, pos, 6);SeqListInsert(s, pos, 7);SeqListPrint(s);SeqListErase(s, pos);SeqListErase(s, pos);SeqListErase(s, pos);SeqListPrint(s);} int main() {//TestSeqList1();TestSeqList2();return 0; } 三、顺序表的经典题目 1.移除元素 题目链接力扣 解一暴力循环法 即利用顺序表在某个位置的删除只要某个位置满足删除的条件就将后面的数据全部移动到前面来。但是效率太低时间复杂度达到了O(N²) 解二使用新数组 开辟一个新的数组如果原数组中的这个元素不是需要移除的元素则直接拷贝到新数组中如果是需要移除的元素则不拷贝最后将新数组拷贝到原来的数组中即可如果新数组开辟在了堆区那么要记得释放空间这种方法的时间复杂度和空间复杂度均为O(N)显然不满足题目要求 解三使用双指针 思路与解二基本类似但是不同的是我们可以利用两个下标来实现我们的思路我们设置两个下标src和dst我们让src去遍历整个数组如果在src处的值不是val则将src处的值拷贝到dst中然后src和dst均 如果是val则src。其余不动代码如下 int removeElement(int* nums, int numsSize, int val) {int src 0;int dst 0;int i 0;for (i 0; i numsSize; i){if (nums[i] ! val){nums[dst] nums[src];dst;src;}else{src;}}return dst; } 2.删除有序数组中的重复项 题目描述力扣 对于这道题我们的思路和第一道题是基本一致的采用双指针的方法  如上图所示我们使用src和dst两个下标src初始值设置为1dst设置为0那么当src和dst的值相等的时候src。如果不相等则先让dst然后将src处的值赋值给dst最后src。代码如下 int removeDuplicates(int* nums, int numsSize) {int src 1;int dst 0;for (src 1; src numsSize;){if (nums[src] nums[dst]){src;}else{dst;nums[dst] nums[src];src;}}return dst 1; } 3.合并两个有序数组 题目描述力扣 解一直接合并然后排序 最简单的方式就是直接暴力合并然后采用排序算法就可以了。但是这是一个俗手。时间复杂度较高 解二归并 对于这道题而言我们可以采用归并的思路 首先是设置三个下标end1end2end。 然后我们循环比较end1和end2所指向的较大值将较大值赋给end所指向的位置。然后赋值的end和被赋值的end均–。 当end2的值先变成了负数的时候那么自然是最好的状态此时肯定有序。 但是当end1的值先变成了负数的时候那么end2的数据并未完全存放到nums1中此时我们需要将end2的剩余元素给插入到nums1中 具体代码如下 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 m - 1;int end2 n - 1;int end m n - 1;while (end1 0 end2 0){if (nums1[end1] nums2[end2]){nums1[end] nums1[end1];end–;end1–;}else{nums1[end] nums2[end2];end–;end2–;}}if (end1 0){while (end2 0){nums1[end] nums2[end2];end2–;end–;}} } 好了本期内容就到这里 如果对你有帮助的话不要忘记点赞加收藏哦