文章目录

• 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个数据空间。
   思考：如何解决以上问题呢？这就需要链表的结构来解决。

推荐阅读

• 

  脆柿就是还没熟的柿子吗
• 

  if else if理解订正
• 

  安卓单机游戏排行榜前十名手游，安卓手机有哪些游戏好玩 单机的
• 

  《锦瑟》最后一联表达了诗人什么样的思想情感？
• 

  有纹身的女人才是最性感的
• 

  腊八节民间有哪些传统习俗 腊八节有什么传统文化
• 

  婚姻一方精神病可以离婚吗
• 

  形容下雨天心情不好的句子
• 

  隔夜稀饭怎么会变粉色
• 

  雪梨银耳汤做法有哪些 银耳雪梨猪手汤怎么制作
• 

  癌症|2020中国十大高发癌症｜世界癌症日
• 

  朝加偏旁组词 朝加偏旁到底能组成啥字呢
• 

  qq看点免流量吗? QQ怎么查看免流量特权
• 

  gta5中文字幕怎么设置
• 

  php加密客户端数据加密 php加密后怎么运行
• 

  在试用期内辞职随时能拿到工资吗
• 

  哪种天气情况下瓜果会甜一些
• 

  高德地图怎么叫车？
• 

  枪神2，枪神2目前使用的人多吗能不能评价一下
• 

  童年第十章主要内容 童年简介

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