虫子 顺序表 内核必备，基本算法，linux二次发育，项目远见

举报
虫子VV 发表于 2022/04/21 13:46:23 2022/04/21
【摘要】 顺序表 线性表 顺序表（本质上就是数组） 概念及结构 顺序表一般可以分为： 1. 静态顺序表：使用定长数组存储元素。 2. 动态顺序表：使用动态开辟的数组存储。 接口函数（==这里教你闭坑，不然有时候你不知道怎么死的（值传递与址传递的区别）==） 顺序表初始化 SeqListInit 值传递 址传递 尾插函数SeqListPushBack 顺序表打印函数SeqListPrint 顺序表销毁...

顺序表

线性表

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

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

image-20211013044050038

==但是今天这篇博客只讲顺序表==

顺序表（本质上就是数组）

概念及结构

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

顺序表一般可以分为：

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

image-20211013143551055

#pragma once

//方便改数组的大小
#define N 100

typedef int SLDataType; //这样会很方便修改

//静态顺序表
typedef struct SeqList
{
	SLDataType a[N];
	SLDataType size;//表示数组中存储了多少个数据
}SL;

void SeqListPushBack(SL* ps, SLDataType x);

==静态的特点是满了就不让插入， 缺点就是我们不知道给多大的空间合适，给大了浪费，给小了“犯罪”，所以就出现了动态顺序表==

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

==既然都动态了，那么也就没有空间大小N的必要了，我们用指针即可==

image-20211013144258306

//方便改数组的大小
//#define N 100

typedef int SLDataType; //这样会很方便修改

//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int size;//表示数组中存储了多少个数据
	int capacity;//数组实际能存数据的空间容量是多大
}SL;

void SeqListPushBack(SL* ps, SLDataType x);

接口函数（==这里教你闭坑，不然有时候你不知道怎么死的（值传递与址传递的区别）==）

顺序表初始化 SeqListInit
值传递

image-20211013163251415

==这里有一个告诫就是vs13与vs19不同，vs13你sl不初始化也可以跑过去，而vs19sl不初始化是跑不过去的，我把vs19跑不过去的图放在下面==

image-20211013163557670

址传递

==既然实参的是不能传给形参，那么我们就把地址传过去==、

image-20211013164548292

//顺序表初始化
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

尾插函数SeqListPushBack

image-20211013183046474

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		//压根就没有空间		 
		//空间满的情况，扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("开辟失败\n");//没有开辟成功
			exit(-1);//异常结束
		}
		//成功扩容后
		ps->a = tmp;//把新的地址给他
		ps->capacity = newcapacity;//容量给他

	}
	//空间足够的情况
	ps->a[ps->size] = x;
	ps->size++;
}

==但是有时候一直调试去看我们接口写的怎么样，会很浪费时间，所以我们得写个打印函数==

顺序表打印函数SeqListPrint

image-20211013190434096

//顺序表打印
void seqListPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

==我们做到这一步基本可以看成顺序表起步成功，现在我们需要对顺序表销毁，实际上我们是知道，最后的最后才是顺序表的销毁，但是我们这里可以实现了（你可以可理解成单片机的最小系统或者丐版微星一个意思）==

顺序表销毁函数SeqListDestory

image-20211013192915639

//顺序表销毁
void seqListDestory(SL* ps)//就是释放内存，防止内存溢出
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

==最小系统板好了我们就一个一个加模块==

尾删函数SeqListPopBack

==温柔==

image-20211013195023732

//尾删
void SeqListPopBack(SL* ps)
{
	//温柔做法
	if (ps->size > 0)
	{
		ps->size--;
	}
}

==粗暴==（我一个大男人比较喜欢粗暴一点的做法，直接了当）

image-20211013195541371

//尾删
void SeqListPopBack(SL* ps)
{
	////温柔做法
	//if (ps->size > 0)
	//{
	//	ps->size--;
	//}
	//粗暴
	assert(ps->size > 0);//断言不为真直接报错，管你不轻
	ps->size--;
}

==在写头插之前，我们思考一下，你要插入，肯定要考虑到是否需要扩容，那么就与之前尾插里面的扩容重了，所以可以抽取出来单独写一个函数==

顺序表检查容量函数SeqListCheckCapacity

image-20211013215212561

//顺序表检查容量
void SeqListCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		//压根就没有空间		 
		//空间满的情况，扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("开辟失败\n");//没有开辟成功
			exit(-1);//异常结束
		}
		//成功扩容后
		ps->a = tmp;//把新的地址给他
		ps->capacity = newcapacity;//容量给他
	}
}

==然后用那个检查容量就可以很轻松的扩容了==

头插函数SeqListPushFront

image-20211013220311078

//头插
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++;
}

头删SeqListPopFront

image-20211013223446010

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

顺序表查找函数SeqListFind

image-20211015073022427

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

顺序表插入函数SeqListInsert

image-20211015082837373

//顺序表插入函数
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	//断言不在范围内直接结束
	assert(pos>=0 && pos<=ps->size);
	//检查扩容
	SeqListCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (pos<=end)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//然后再把数据给当前位置
	ps->a[pos] = x;
	ps->size++;
}

==所以头插尾插就不需要写了，直接调用插入函数即可==

顺序表删除函数SeqListErase

image-20211015085810783

//顺序表删除函数
void SeqListErase(SL* ps, int pos)
{
	//断言不在范围内直接结束
	assert(pos >= 0 && pos < ps->size);
	//删除不需要考虑扩容,直接挪动数据 
	int begin = pos;
	while (begin+1<ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

==所以头删尾删也就可以 复用掉==

练习题

例1移除元素

image-20211015095858252

image-20211015100121235

==我们先分析一下题，他对空间复杂度是有要求的，对时间复杂度没有什么要求==

image-20211015154149033

int removeElement(int* nums, int numsSize, int val){
    int i = 0;
    int* cur = nums;
    for(i = 0;i<numsSize;i++)
    {
        if(val ^ nums[i])
        {
           *cur++ = nums[i];            
        }
    }
    return cur-nums;
}

例2删除有序数组中的重复项

image-20211015104806009

image-20211015121126097

==我们不能空看我们得画图解决，题目直接把空间定死，不会给你开额外的数组了，也就只能多指针解决==

脑内模拟一番，一个定位指针，两个游标指针，应该可以解决

image-20211015130608900

int removeDuplicates(int* nums, int numsSize){
    if(numsSize == 0)//空数组跳出
    return 0;
    int* cur = nums;//定位指针
    int* head = nums;//游标头指针
    int* tail = nums+1;//游标尾指针
    while(tail<nums+numsSize)
    {
        if(*head == *tail)
        {
            tail++;
        }
        else
        {
            *cur = *head;
            cur++;
            head = tail;
            tail++;
        }
    }
    *cur = *head;//最后一个不管等不等都强制赋值
    cur++;
    return (cur-nums);
}

例3合并两个有序数组

image-20211015131749592

image-20211015144752976

image-20211015151706645

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int* p1 = nums1+m-1;
    int* p2 = nums2+n-1;
    int* cur = nums1+m+n-1;
    while(p1>=nums1 && p2>=nums2)
    {
        *cur-- = *p1>*p2 ? *p1-- : *p2--;//三目运算符
    }
    while(p2>=nums2)
    {
        *cur-- = *p2--;
    }
}
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
人工智能 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入