海口模板建站平台_网站营销概念_互联网营销策划案_媒体软文发布平台

前言

本文介绍顺序表相关知识点及三道leetcode练习题

正文

1. 线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。它是一种在实际中广泛使用的数据结构，常见的线性表有顺序表、链表、栈、队列、字符串等。

线性表在逻辑上是线性结构，即连续的一条直线。但在物理结构上不一定连续，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表

2.1 概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

顺序表的底层结构是数组，是对数组的封装，实现了常用的增删改查等接口。

2.2 分类

• 静态顺序表：使用定长数组存储元素。

//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct seqList
{SLDataType a[N];//定长数组int size; //有效数据个数
}SL;

静态顺序表存在缺陷，空间给少了不够用，给多了造成空间浪费。

• 动态顺序表：按需申请空间。

//动态顺序表--按需申请
typedef struct SeqList
{SLDataType* a;int size; //有效数据个数int capacity;//空间容量
}SL;

2.3 动态顺序表的实现

本文采用多文件结构，包含初始化、销毁、扩容、插入删除、查找等函数声明。
后续会有一个通讯录代码采用单文件结构示例
SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;      //有效数据个数int capacity;  //空间容量
}SL;//typedef struct SeqList SL;void SLPrint(SL* ps);
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);//指定位置之前插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 删除POS位置的数据
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include"SeqList.h"//初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容//realloc第二个参数，单位是字节SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//判断空间是否足够SLCheckCapacity(ps);//空间足够的情况下ps->arr[ps->size++] = x;
}//头插
void SLPushFront(SL* ps, SLDataType x)
{//温柔的处理方式//if (ps == NULL)//{//	return;//}assert(ps != NULL);//判断空间是否足够SLCheckCapacity(ps);//将顺序表中所有数据向后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}//尾删
void SLPopBack(SL* ps)
{//ps：限制参数不能直接给NULL//ps->size：顺序表为空assert(ps && ps->size);--ps->size;
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}//指定位置之前插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据整体向后挪动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;++ps->size;
}
// 删除POS位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos之后的数据整体向前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}
//查找
int SLFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}//未找到return -1;
}
//销毁
void SLDestroy(SL* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

test.c

#include"SeqList.h"
//根据需求取消注释即可
void test01()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(&sl);//SLPushBack(&sl, 5);//SLPushFront(&sl, 1);//SLPushFront(&sl, 2);//SLPushFront(&sl, 3);//SLPushFront(&sl, 4);//4 3 2 1//SLPushFront(NULL, 1);////SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);//SLPrint(&sl);//SLPopBack(&sl);
////SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);
////SLInsert(&sl, 4, 100);//SLPrint(&sl);//SLErase(&sl, 3);//SLPrint(&sl);//int find = SLFind(&sl, 22222);//printf("%d",find)//SLDestroy(&sl);
}int main()
{test01();return 0;
}

2.4 顺序表算法题

前两道题目都运用了双指针法，第三道是一道经典例题，希望可以仔细琢磨
相关题目可在LeetCode上练习：

2.4.1移除元素：

https://leetcode.cn/problems/remove-element/description/

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

2.4.2 删除有序数组中的重复项：

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

int removeElement(int* nums, int numsSize, int val)
{//双指针法int dst = 0;int src = 0;while (src < numsSize){if (nums[src] != val){nums[dst] = nums[src];dst++;}src++;}return dst;
}

2.4.3 合并两个有序数组：

https://leetcode.cn/problems/merge-sorted-array/description/

int removeDuplicates(int* nums, int numsSize){int dst = 0;int src = dst + 1;while (src < numsSize){if (nums[src] != nums[dst] && ++dst != src){nums[dst] = nums[src];}++src;}return dst + 1;}

2.5 顺序表问题与思考

• 中间/头部的插入删除，时间复杂度为O(N)。
• 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
• 增容一般是呈2倍的增长，会有一定的空间浪费。

至于如何解决就是链表的内容了

总结

顺序表是我们所学的第一种数据结构，但实际上在C语言的部分就应该做，如果有帮助希望给予支持，谢谢。