文章目录

• 1.线性表
• 2.顺序表
• • 2.1概念及结构
  • 2.2接口实现
  • • 2.2.1 SeqList.h
    • 2.2.2 SeqList.c
    • • 2.2.2.1 初始化顺序表
      • 2.2.2.2 打印顺序表
      • 2.2.2.3 释放顺序表
      • 2.2.2.4 检查容量并扩容
      • 2.2.2.5 尾插
      • 2.2.2.6 尾删
      • 2.2.2.7 头插
      • 2.2.2.8 头删
      • 2.2.2.9 在pos位置插入x
      • 2.2.2.10 删除pos位置的数据
      • 2.2.2.11 顺序表查找
      • 2.2.2.12 顺序表修改
      • 2.2.2.13 利用Erase，Insert接口简化尾插、尾删、头插、头删
      • 2.2.2.14 SeqList.c完整代码
    • 2.2.3 Test.c
    • 2.2.4 运行结果
• 3.数组相关面试题
• • 3.1. [原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。](https://leetcode-cn.com/problems/remove-element/)
  • 3.2 [删除排序数组中的重复项。](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)
  • 3.3 [合并两个有序数组](https://leetcode-cn.com/problems/merge-sorted-array/)
  • • 思路1：
    • 思路2：
    • 思路3：要求不能额外开数组。
• 4. 顺序表的问题及思考

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

文章图片

2.顺序表 2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组 上完成数据的增删查改。 顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。
文章图片

2. 动态顺序表：使用动态开辟的数组存储。
文章图片

2.2接口实现 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
我们采用分文件的方式来实现：
2.2.1 SeqList.h

#pragma once #include #include #include typedef int SLDataType; typedef struct SeqList { SLDataType *a; int size; int capacity; }SL; void SeqListInit(SL *ps); void SeqListPrint(SL *ps); void SeqListDestroy(SL *ps); void SeqListCheckCapacity(SL *ps); //增删查改等接口函数 // 时间复杂度是O(1) 尾插，尾删 void SeqListPushBack(SL* ps, SLDataType x); void SeqListPopBack(SL* ps); // 时间复杂度是O(N) void SeqListPushFront(SL* ps, SLDataType x); void SeqListPopFront(SL* ps); // 在pos位置插入x void SeqListInsert(SL* ps, size_t pos, SLDataType x); // 删除pos位置的数据 void SeqListErase(SL* ps, size_t pos); // 顺序表查找 int SeqListFind(SL* ps, SLDataType x); //顺序表改 void SeqListModify(SL *ps, size_t pos, SLDataType x);

2.2.2 SeqList.c
2.2.2.1 初始化顺序表

void SeqListInit(SL *ps) { ps->a = NULL; ps->size = 0; ps->capacity = 0; }

2.2.2.2 打印顺序表

void SeqListPrint(SL *ps) { assert(ps); for(int i=0; isize; i++) { printf("%d ",ps->a[i]); } printf("\n"); }

2.2.2.3 释放顺序表

void SeqListDestroy(SL *ps) { free(ps->a); ps->a=NULL; ps->size=ps->capacity=0; }

2.2.2.4 检查容量并扩容

void SeqListCheckCapacity(SL *ps) { if(ps->size==ps->capacity) { int newcapacity = ps->capacity == 0 ? 4:ps->capacity*2; //我们把capacity初始化为0，直接写成newcapacity=ps->capacity*2就出bug了哦 SLDataType *tmp =(SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType)); if(tmp==NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a=tmp; ps->capacity =newcapacity; } } }

文章图片

注：我们知道realloc存在原地扩和异地扩的情况，而且扩容失败会返回空指针，所以用realloc扩容一定要记得检查是否扩容成功。
2.2.2.5 尾插

void SeqListPushBack(SL *ps, SLDataType x) { SeqListCheckCapacity(ps); ps->a[ps->size]=x; ps->size++; }

2.2.2.6 尾删

void SeqListPopBack(SL *ps) { assert(ps->size > 0); ps->size--; }

2.2.2.7 头插

void SeqListPushFront(SL *ps,SLDataType x) { SeqListCheckCapacity(ps); int end = ps->size-1; while(end>=0) { ps->a[end+1]=ps->a[end]; end--; } ps->a[0]=x; ps->size++; }

文章图片

2.2.2.8 头删

void SeqListPopFront(SL *ps) { assert(ps); if(ps->size>0) { int start = 1; while(start < ps->size) { ps->a[start-1]=ps->a[start]; start++; } ps->size--; } }

【数据结构（C语言实现）|顺序表C语言版】
文章图片

2.2.2.9 在pos位置插入x

// 在pos位置插入x void SeqListInsert(SL* ps, size_t pos, SLDataType x) { assert(ps); if(pos>ps->size) { printf("pos 越界:%d\n",pos); return; } SeqListCheckCapacity(ps); int end = ps->size-1; while(end >= pos) { ps->a[end+1]=ps->a[end]; end--; } ps->a[pos]=x; ps->size++; }

大家看这种写法有没有问题。
请看下面一种情况：

文章图片

当end走到-1时，与end进行比较时会整型提升为size_t类型，会变成一个很大的数，此时程序会进入死循环。
正确的写法：

// 在pos位置插入x void SeqListInsert(SL* ps, size_t pos, SLDataType x) { assert(ps); if(pos>ps->size) { printf("pos 越界:%d\n",pos); return; } SeqListCheckCapacity(ps); size_t end = ps->size; while(end > pos) { ps->a[end]=ps->a[end-1]; end--; } ps->a[pos]=x; ps->size++; }

文章图片

注：

文章图片

2.2.2.10 删除pos位置的数据

// 删除pos位置的数据 void SeqListErase(SL* ps, size_t pos) { assert(possize); int start = pos+1; while(start < ps->size) { ps->a[start-1]=ps->a[start]; start++; } ps->size--; }

文章图片

下一次尾插数据直接覆盖4.
2.2.2.11 顺序表查找

// 顺序表查找 int SeqListFind(SL* ps, SLDataType x) { for(int i=0; isize; i++) { if(ps->a[i]==x) { return i; } } return -1; }

2.2.2.12 顺序表修改

//顺序表改 void SeqListModify(SL *ps, size_t pos, SLDataType x) { aseert(possize); ps->a[pos]=x; }

2.2.2.13 利用Erase，Insert接口简化尾插、尾删、头插、头删

void SeqListPushBack(SL* ps, SLDataType x) { assert(ps); SeqListInsert(ps, ps->size, x); }

void SeqListPopBack(SL* ps) { assert(ps); SeqListErase(ps, ps->size-1); }

void SeqListPushFront(SL* ps, SLDataType x) { assert(ps); SeqListInsert(ps, 0, x); }

void SeqListPopFront(SL* ps) { assert(ps); SeqListErase(ps, 0); }

2.2.2.14 SeqList.c完整代码

#include "SeqList.h" void SeqListInit(SL* ps) { ps->a = NULL; ps->size = 0; ps->capacity = 0; } void SeqListPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } void SeqListDestroy(SL* ps) { free(ps->a); ps ->a = NULL; ps->size = ps -> capacity = 0; } void SeqListCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //我们把capacity初始化为0，直接写成newcapacity=ps->capacity*2就出bug了哦 SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->a = tmp; ps->capacity = newcapacity; } } } void SeqListPushBack(SL* ps, SLDataType x) { SeqListCheckCapacity(ps); ps->a[ps->size] = x; ps->size++; } void SeqListPopBack(SL* ps) { assert(ps->size > 0); ps->size--; } void SeqListPushFront(SL* ps, SLDataType x) { SeqListCheckCapacity(ps); int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; } void SeqListPopFront(SL* ps) { assert(ps); if (ps->size > 0) { int start = 1; while (start < ps->size) { ps->a[start - 1] = ps->a[start]; start++; } ps->size--; } } // 在pos位置插入x void SeqListInsert(SL* ps, size_t pos, SLDataType x) { assert(ps); if ((int)pos > ps->size) { printf("pos 越界:%d\n", pos); return; } SeqListCheckCapacity(ps); size_t end = ps->size; while (end > pos) { ps->a[end] = ps->a[end - 1]; end--; } ps->a[pos] = x; ps->size++; } // 删除pos位置的数据 void SeqListErase(SL* ps, size_t pos) { assert((int)pos < ps->size); int start = pos + 1; while (start < ps->size) { ps->a[start - 1] = ps->a[start]; start++; } ps->size--; } // 顺序表查找 int SeqListFind(SL* ps, SLDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; } //顺序表改 void SeqListModify(SL* ps, size_t pos, SLDataType x) { assert((int)pos < ps->size); ps->a[pos] = x; }

2.2.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h"void TestSeqList1() { SL s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushBack(&s, 0); SeqListPrint(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPrint(&s); SeqListPrint(&s); SeqListPushBack(&s, 10); SeqListPushBack(&s, 20); SeqListPrint(&s); //SeqListPrint(NULL); // 越界不一定能检查出来，越界是抽查 // 就像查酒驾一样。不一定会被查到，但是我们一定不能酒驾 //int a[10]; //a[10] = 1; //a[11] = 1; //a[12] = 1; //a[100] = 1; }void TestSeqList2() { /*int* p = (int*)malloc(sizeof(int) * 10); printf("%p\n", p); int* p1 = (int*)realloc(p, sizeof(int) * 100); printf("%p\n", p1); */ SL s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushFront(&s, 0); SeqListPushFront(&s, -1); SeqListPrint(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPrint(&s); SeqListPopFront(&s); SeqListPrint(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPushFront(&s, 0); SeqListPushFront(&s, -1); SeqListPrint(&s); }void TestSeqList3() { SL s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPrint(&s); SeqListInsert(&s, 10, 100); SeqListInsert(&s, 1, 20); SeqListInsert(&s, 5, 50); SeqListInsert(&s, 0, 50); SeqListPrint(&s); SeqListDestroy(&s); }void TestSeqList4() { SL s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPrint(&s); SeqListErase(&s, 4); SeqListPrint(&s); SeqListErase(&s, 0); SeqListPrint(&s); SeqListErase(&s, 1); SeqListPrint(&s); }void TestSeqList5() { SL s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushFront(&s, -1); SeqListPushFront(&s, -2); SeqListPrint(&s); SeqListPopFront(&s); SeqListPopFront(&s); SeqListPopBack(&s); SeqListPopBack(&s); SeqListPrint(&s); }void menu() { printf("***********************************************\n"); printf("1.尾插数据 2.头插数据\n"); printf("5.打印数据 6.查找数据\n"); printf("-1.退出 \n"); printf("***********************************************\n"); }int main() { TestSeqList5(); //SL s; //SeqListInit(&s); //int option = -1; //do //{ // menu(); // printf("请选择你的操作:>"); // scanf("%d", &option); // if (option == 1) // { //printf("请输入你要尾插的数据:>"); ////int val = 0; //SLDataType val = 0; //scanf("%d", &val); //SeqListPushBack(&s, val); // } // else if (option == 5) // { //SeqListPrint(&s); // } //} while (option != -1); //SeqListDestroy(&s); return 0; }

注：
测试接口时最好写一个接口测一个接口，不要一口气写完再测试，不然你会崩溃的哦。
2.2.4 运行结果

文章图片

3.数组相关面试题 3.1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。

思路1：

查找到每一个val，依次挪动数据覆盖,时间复杂度O(N^2).

文章图片

思路2：

把不是val的值拷贝到新数组，时间复杂度O(N),空间复杂度O(N).

文章图片

思路3：

双指针，时间复杂度O(N),空间复杂度O(1)
令dst，src为0，如果src下标处的值不等于val，则nums[dst]=nums[src]，src++，dst++。否则只让src++。

文章图片

代码：

int removeElement(int* nums, int numsSize, int val) { int src = https://www.it610.com/article/0; int dst = 0; while(src < numsSize) { if(nums[src] != val) { nums[dst] = nums[src]; dst++; src++; } else { src++; } } return dst; }

3.2 删除排序数组中的重复项。
文章图片

代码：

int removeDuplicates(int* nums, int numsSize) { int src = https://www.it610.com/article/1; int dst = 0; while(src < numsSize) { if(nums[src] == nums[src-1]) { src++; } else { nums[dst] = nums[src-1]; src++; dst++; } } nums[dst] = nums[numsSize-1]; dst++; return dst; }

3.3 合并两个有序数组 思路1：

文章图片

思路2：

文章图片

思路3：要求不能额外开数组。

一种情况：

文章图片

另一种情况：

文章图片

代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int i = m-1, j = n-1; int dst = m+n-1; while(i >= 0 && j >= 0) { if(nums1[i]>nums2[j]) { nums1[dst--] = nums1[i--]; } else { nums1[dst--] = nums2[j--]; } } while(j >= 0) { nums1[dst--] = nums2[j--]; } }

4. 顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
   思考：如何解决以上问题呢？这就需要链表的结构来解决。

推荐阅读

• 

  别有幽愁暗生暗恨生下一句 别有忧愁暗恨生中幽和暗的意思
• 

  三个月宝宝腹泻怎么办
• 

  搜狐文章首篇模板
• 

  科研课题结题申请书
• 

  密切接触者要医学观察多少天
• 

  2022年河南养老金最新调整方案细则 2022年养老金上调最新消息
• 

  元气骑士 古大陆的神器 元气骑士古大陆的神器神威大全
• 

  豆角炒肉的做法
• 

  如何登录云际服务器？ 云际服务器怎么登录
• 

  新房装修改水电，一定记住这10大黄金尺寸
• 

  北仑接种hpv 2023宁波北仑HPV疫苗怎么预约
• 

  html5轮廓分析工具
• 

  列假期间可以吃芒果吗
• 

  碧蓝航线死或生联动纪念章怎么获得 假日航线角色喜好获取方式一览
• 

  大肠癌|三天一次大便和一天三次大便，哪个是大肠癌，每天排便几次算正常
• 

  五角电子分析器位置
• 

  浏览器渲染原理
• 

  林内壁挂炉打不燃显示12解决方法
• 

  u盘怎么和车载收音机连接，u盘怎么和车载收音机连接蓝牙
• 

  开水冲鸡蛋有寄生虫吗

• 笔记|C语言版单链表的建立方式
• 数据结构与算法|C语言 创建单链表
• 数据结构|C语言单链表定义及各类操作
• 数据结构|反向遍历单链表 C语言版
• C语言基础|【C语言趣味游戏】猜数字
• c语言|C语言——指针初识（三）（指针和指针数组，一级指针，二级指针详解）
• 指针|C语言中的数组指针和指针数组的区别，代码+图例详解
• 数据结构|3000字带你深入理解二叉树（图解剖析）
• 数据结构->顺序表的操作