程序员经验分享-hwhale

数据结构 严薇敏 顺序表的实现(增 删 改)及其使用方法详解

2023-11-19

时间复杂度 

数据结构 时间复杂度和空间复杂度

目录

1.线性表

2.顺序表

2.1概念及结构

 2.2 接口实现

SeqList.h

SeqList.c

2.2.1初始化链表以及销毁链表的实现

初始化顺序表

 销毁顺序表

2.2.2查找元素前驱或后继的实现

查找前驱

查找后继

2.2.3查找元素和获取元素的实现

查找元素

2.2.4删除元素的实现

尾删

 头删

任意位置删除 

2.2.4增加元素的实现

尾加

malloc / calloc / realloc 区别 

扩容

 头加

任意位置添加 

1.线性表

概念：线性表是n个具有相同特征性的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，每个元素都有唯一的前去和唯一的后继，前一个元素没有前驱只有后继，最后一个元素没有后继只有前驱，常见的线性表：顺序表、链表、栈、队列、字符串。

数组不等于线性表，数组只是把元素存储起来了！可以增加一些增删改的方法！watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

2.顺序表

2.1概念及结构

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

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_13,color_FFFFFF,t_70,g_se,x_16

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

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_13,color_FFFFFF,t_70,g_se,x_16

 2.2 接口实现

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

SeqList.h

                             也可以用来实现严薇敏版数据结构的算法2.1~2.7                                        

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
//可以改变你给顺序表里面放的数据类型
typedef int Datatype;

//静态顺序表
//你数组开辟空间时候必须要知道开辟的大小

//typedef struct SeqList {
//	Datatype arr[NUM];
//	int capacity;
//	int size;
//}SeqList;


//动态顺序表
typedef struct SeqList {
	Datatype* arr;
	int capacity;
	int size;
}SeqList;

//对顺序表进行打印
void PrintSeqList(SeqList* ps);

//显示顺序表信息
void PrintSeqListData(SeqList* ps);

//初始化顺序表
void SeqListInit(SeqList* ps, int initcapacity);

//销毁顺序表
void SeqListDestory(SeqList* ps);

//获取顺序表有效元素的个数
int SeqListSize(SeqList* ps);

//获取顺序表的容量大小
int SeqListCapacity(SeqList* ps);

//检测顺序表是否为空
int SeqListEmpty(SeqList* ps);

//将顺序表置为空表
void SeqListClear(SeqList* ps);

//查找顺序表中元素
int SeqListFind(SeqList* ps, Datatype data);

//获取顺序表中对应位置的值
Datatype SeqListGet(SeqList* ps, int pos);

//查找顺序表中一个元素的前驱
Datatype SeqListGetPrior(SeqList* ps, int pos);

//查找顺序表中一个元素的后继
Datatype SeqListGetNext(SeqList* ps, int pos);

// 将顺序表中最后一个元素删除掉
void SeqListPopBack(SeqList* ps);

// 将顺序表中第一个元素删除掉
// 时间复杂度：O(N)
void SeqListPopFront(SeqList* ps);

// 往顺序表中尾插一个值为data的元素
// 时间复杂度：O(1)
void SeqListPushBack(SeqList* ps, Datatype data);

// 往顺序表中头插一个值为data的元素
// 时间复杂度是多少？O(N)
void SeqListPushFront(SeqList* ps, Datatype data);

// 删除顺序表任意位置的元素
// 时间复杂度O(N)
void SeqListErase(SeqList* ps, int pos);

// 在顺序表的任意pos位置插入元素data
// 时间复杂度O(N)
void SeqListInsert(SeqList* ps, int pos, Datatype data);

//写到这块了其实咱们顺序表存在一个巨大的问题
//你的size == capacity 在增加还行吗？
//还需要对你的arr进行扩容
//1.申请新的空间
//2.将原有数据进行拷贝
//3.旧空间的释放
//4.返回新空间的地址
void CheckCapacityMode1(SeqList* ps);

//1.申请新的空间
//2.将原有数据进行拷贝
//3.旧空间的释放
//4.返回新空间的地址
//这不和realloc一样吗
void CheckCapacityMode2(SeqList* ps);

SeqList.c

#include "SeqList.h"
void PrintSeqList(SeqList* ps)
{
	//对传入的指针进行断言
	assert(ps);
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//显示顺序表信息
void PrintSeqListData(SeqList* ps)
{
	assert(ps);
	PrintSeqList(ps);
	printf("有效元素个数为: %d \n", ps->size);
	printf("开辟容量大小为: %d \n", ps->capacity);
}

//初始化顺序表
void SeqListInit(SeqList* ps, int initcapacity)
{
	//对传入的指针进行断言
	assert(ps);
	//传入负数的体现
	initcapacity = initcapacity <= 0 ? 3 : initcapacity;
	//对顺序表开始动态申请内存
	ps->arr = (Datatype*)malloc(initcapacity * sizeof(Datatype));
	if (NULL == ps->arr) {
		assert(0);
		return;
	}
	ps->capacity = initcapacity;
	ps->size = 0;
}
//销毁顺序表
void SeqListDestory(SeqList* ps)
{
	//已经为空直接返回
	if (NULL == ps->arr) {
		printf("你的顺序表已经为空!");
		return;
	}
	//free();掉你在堆上申请的内存空间
	if (ps->arr) {
        free(ps->arr);
		ps->arr = NULL;
		ps->capacity = 0;
		ps->size = 0;
	}
}

//获取顺序表有效元素的个数
int SeqListSize(SeqList* ps)
{
	assert(ps);
	//直接返回size大小即可
	return ps->size;
}

//获取顺序表的容量大小
int SeqListCapacity(SeqList* ps)
{
	assert(ps);
	//直接返回capacity即可
	return ps->capacity;
}
//检测顺序表是否为空
int SeqListEmpty(SeqList* ps)
{
	//你的有效元素要是为0则顺序表为空
	if (0 == ps->size) {
		printf("你的顺序表为空!");
		return 1;
	}
	return 0;
}
//将顺序表置为空表
void SeqListClear(SeqList* ps)
{
	assert(ps);
	//你的有效元素要是为0则顺序表为空
	ps->size = 0;
}
//查找顺序表中元素
int SeqListFind(SeqList* ps, Datatype data)
{
	assert(ps);
	//遍历顺序表找到你的目标数字
	for (int i = 0; i < ps->size; i++) {
		if (data == ps->arr[i]) {
			printf("找到了%d!他的下标是%d", ps->arr[i], i);
			return 1;
		}
	}
	return -1;
}
//获取顺序表中对应位置的值
Datatype SeqListGet(SeqList* ps, int pos)
{
	assert(ps);
	//对pos合法性判断
	if (pos<0 || pos>ps->size - 1) {
		printf("你的pos输入有误!");
		return 0;
	}
	return (Datatype)ps->arr[pos];
}
//查找顺序表中一个元素的前驱
Datatype SeqListGetPrior(SeqList* ps, int pos)
{
	assert(ps);
	//对pos合法性判断
	if ((pos<0 || pos>ps->size - 1) && pos == 0) {
		printf("你的pos输入有误!");
		return 0;
	}
	return (Datatype)ps->arr[--pos];
}

Datatype SeqListGetNext(SeqList* ps, int pos)
{
	assert(ps);
	//对pos合法性判断
	if ((pos<0 || pos>ps->size - 1) && pos == ps->size - 1) {
		printf("你的pos输入有误!");
		return 0;
	}
	return (Datatype)ps->arr[++pos];
}

// 将顺序表中最后一个元素删除掉
//我们的size是有效元素的个数,因此即使删除,数据还在capacity,即使删除后没有被覆盖,但不会访问!
void SeqListPopBack(SeqList* ps)
{
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	if (ps->size > 0) {
		ps->size--;
	}
}

// 将顺序表中第一个元素删除掉
// 时间复杂度：O(N)
void SeqListPopFront(SeqList* ps)
{
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	//删除第一个元素之后应该要把原有数据整体向前搬运
	//如果是从后往前搬运那这样就会造成内存覆盖
	//应该从前面开始搬运
	for (int i = 1; i < ps->size; i++) {
		ps->arr[i - 1] = ps->arr[i];
	}
	//搬运结束有效元素减一
	ps->size--;
}
// 往顺序表中尾插一个值为data的元素
// 时间复杂度：O(1)
void SeqListPushBack(SeqList* ps, Datatype data)
{
	assert(ps);
    CheckCapacityMode2(ps);
	ps->arr[ps->size] = data;
	//有效元素加一
	ps->size++;
}

// 往顺序表中头插一个值为data的元素
// 时间复杂度是多少？O(N)
void SeqListPushFront(SeqList* ps, Datatype data)
{
	CheckCapacityMode2(ps);
	//在第一个位置插入，那也就是说还得进行搬运
	//这次怎么搬运呢
	//应该是从后往前搬运要是从前往后搬运就会造成内存覆盖
	for (int i = ps->size - 1; i >= 0; --i) {
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[0] = data;
	ps->size++;
}

// 删除顺序表任意位置的元素
// 时间复杂度O(N)
void SeqListErase(SeqList* ps, int pos)
{
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	//对pos合法性判断
	if (pos < 0 || pos > ps->size - 1) {
		printf("你的pos输入有误!");
		return;
	}
	for (int i = pos; i < ps->size; i++) {
		ps->arr[pos] = ps->arr[pos + 1];
	}
	ps->size--;
}

// 在顺序表的任意pos位置插入元素data
// 时间复杂度O(N)
void SeqListInsert(SeqList* ps, int pos, Datatype data)
{
	CheckCapacityMode2(ps);
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	//对pos合法性判断
	if (pos < 0 || pos > ps->size - 1) {
		printf("你的pos输入有误!");
		return;
	}
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[pos] = data;
	ps->size++;
}
//写到这块了其实咱们顺序表存在一个巨大的问题
//你的size == capacity 在增加还行吗？
//还需要对你的arr进行扩容
//1.申请新的空间
//2.将原有数据进行拷贝
//3.旧空间的释放
//4.返回新空间的地址
void CheckCapacityMode1(SeqList* ps)
{
	if (ps->size == ps->capacity) {
		//1.申请新的空间
		int newcapacity = ps->capacity * 2;
		Datatype* temp = (Datatype*)malloc(newcapacity * sizeof(Datatype));
		if (NULL == temp)
		{
			assert(0);
			return;
		}
		//2.将原有数据进行拷贝
		memcpy(temp, ps->arr, ps->size * sizeof(Datatype));
		//3.旧空间的释放
		free(ps->arr);
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

//
void CheckCapacityMode2(SeqList* ps)
{
	int newcapacity = ps->capacity * 2;
	ps->arr = (int*)malloc(sizeof(Datatype));
	if (NULL != ps->arr)
	{
		Datatype* temp = (Datatype*)realloc(ps->arr, sizeof(Datatype) * newcapacity);
		if (NULL != temp)
		{
			ps->arr = temp;
		}
		ps->capacity = newcapacity;
	}
	/*
		ps->array = (int*)realloc(ps->array, sizeof(DataType)*newCapacity);
		if (NULL == ps->array)
		{
			assert(0);
			return;
		}
		ps->capacity = newCapacity;
	*/
	//会有告警"realloc"可能会返回 null 指针：将空<>指针分配给变量（作为参数传递给"realloc"）将导致原始内存块泄漏
	//此警告指示内存泄漏，该泄漏是不正确使用重新分配函数的结果。 如果重新分配不成功
	//堆重新分配函数不会释放传递的缓冲区
	//若要更正缺陷，请将重新分配函数的结果分配给临时 ，然后在成功重新分配后替换原始指针。
}
int main() {
	
}

2.2.1初始化链表以及销毁链表的实现

初始化顺序表

void SeqListInit(SeqList* ps, int initcapacity)
{
	//对传入的指针进行断言
	assert(ps);
	//传入负数的体现
	initcapacity = initcapacity <= 0 ? 3 : initcapacity;
	//对顺序表开始动态申请内存
	ps->arr = (Datatype*)malloc(initcapacity * sizeof(Datatype));
	if (NULL == ps->arr) {
		assert(0);
		return;
	}
	ps->capacity = initcapacity;
	ps->size = 0;
}

动态链表吗，那就用动态开辟内存的方法从堆上申请空间呗，对于这个顺序表尽可能完善他的功能，当capacity为负数的时候也要检验一下，当用malloc的时候还要判断是否开辟成功（是否为空)调用完Init这个方法一定要调用destory这个方法将我们动态开辟的内存空间释放防止内存泄漏

测试

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_17,color_FFFFFF,t_70,g_se,x_16

 销毁顺序表

//销毁顺序表
void SeqListDestory(SeqList* ps)
{
	//已经为空直接返回
	if (NULL == ps->arr) {
		printf("你的顺序表已经为空!");
		return;
	}
	//free();掉你在堆上申请的内存空间
	if (ps->arr) {
        free(ps->arr);
		ps->arr = NULL;
		ps->capacity = 0;
		ps->size = 0;
	}
}

顺序表为空的话就直接返回了不用在销毁了。然后在free掉你在堆上申请的空间，让后将capacity和size置零。

测试

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

2.2.2查找元素前驱或后继的实现

查找前驱

Datatype SeqListGetPrior(SeqList* ps, int pos)
{
	assert(ps);
	//对pos合法性判断
	if ((pos<0 || pos>ps->size - 1) && pos == 0) {
		printf("你的pos输入有误!");
		return 0;
	}
	return (Datatype)ps->arr[--pos];
}

我们这里的pos是数组下标 先对传入的pos进行合法性校验，根据顺序表的概念我们可知，顺序表的每一个元素都有唯一的前驱和后继，第一个元素没有前驱，最后一个元素没有后继，而且pos是数组下标不能越界！

查找后继

//查找顺序表一个元素的后继
Datatype SeqListGetNext(SeqList* ps, int pos)
{
	assert(ps);
	//对pos合法性判断
	if ((pos<0 || pos>ps->size - 1) && pos == ps->size - 1) {
		printf("你的pos输入有误!");
		return 0;
	}
	return (Datatype)ps->arr[++pos];
}

测试

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

2.2.3查找元素和获取元素的实现

查找元素

//查找顺序表中元素
int SeqListFind(SeqList* ps, Datatype data)
{
	assert(ps);
	//遍历顺序表找到你的目标数字
	for (int i = 0; i < ps->size; i++) {
		if (data == ps->arr[i]) {
			printf("找到了%d!他的下标是%d", ps->arr[i], i);
			return 1;
		}
	}
	return -1;
}

遍历顺序表找到你的目标数字找到了返回一找不到返回-1

Datatype SeqListGet(SeqList* ps, int pos)
{
	assert(ps);
	//对pos合法性判断
	if (pos<0 || pos>ps->size - 1) {
		printf("你的pos输入有误!");
		return 0;
	}
	return (Datatype)ps->arr[pos];
}

我们这里的pos是数组下标 先对传入的pos进行合法性校验，返回pos位置的元素

2.2.4删除元素的实现

尾删

// 将顺序表中最后一个元素删除掉
//我们的size是有效元素的个数,因此即使删除,数据还在capacity,即使删除后没有被覆盖,但不会访问!
void SeqListPopBack(SeqList* ps)
{
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	if (ps->size > 0) {
		ps->size--;
	}
}

将顺序表中最后一个元素删除掉
我们的size是有效元素的个数,因此即使删除,数据还在capacity,即使删除后没有被覆盖,但不会访问!

测试

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

就很清晰的看出来数据还在capacity,即使删除后没有被覆盖

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_18,color_FFFFFF,t_70,g_se,x_16

 头删

// 将顺序表中第一个元素删除掉
// 时间复杂度：O(N)
void SeqListPopFront(SeqList* ps)
{
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	//删除第一个元素之后应该要把原有数据整体向前搬运
	//如果是从后往前搬运那这样就会造成内存覆盖
	//应该从前面开始搬运
	for (int i = 1; i < ps->size; i++) {
		ps->arr[i - 1] = ps->arr[i];
	}
	//搬运结束有效元素减一
	ps->size--;
}

先检验顺序表是否为空，要是为空的话就不操作了，直接返回，然后就是剩下的算法，怎么样子将顺序表元素一个个置位呢？

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

测试

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

任意位置删除 

// 删除顺序表任意位置的元素
// 时间复杂度O(N)
void SeqListErase(SeqList* ps, int pos)
{
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	//对pos合法性判断
	if (pos < 0 || pos > ps->size - 1) {
		printf("你的pos输入有误!");
		return;
	}
	for (int i = pos; i < ps->size; i++) {
		ps->arr[pos] = ps->arr[pos + 1];
	}
	ps->size--;
}

删除吗，还是那句话顺序表是空的删除啥？直接先判断是否为空，是空直接就返回了，第二个参数是我们的位置参数，换而言之就是数组下标，下标传进来首先就是要进行参数的合法性校验，看是不是在我们的操作范围之内，不在返回，在范围内进行操作，还是那一套搬运从前往后搬运防止内存覆盖，最后有效元素的个数--;

测试

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

2.2.4增加元素的实现

尾加

// 往顺序表中尾插一个值为data的元素
// 时间复杂度：O(1)
void SeqListPushBack(SeqList* ps, Datatype data)
{
	assert(ps);
	ps->arr[ps->size] = data;
	//有效元素加一
	ps->size++;
}

我们的size是有效元素的大小，做数组下标的时候那就是第size + 1个元素我们直接放进去就好了，最后有效元素的个数++就好了，

请问这样真的就好了吗？这个尾插的方法就没有缺陷吗？

如果尾插完之后有效元素的个数大于你所开辟的capacity呢会怎么样呢？

我们用以下测试样例

void TestSeqList()
{
	SeqList s;
	SeqListInit(&s, 3);

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushBack(&s, 6);
	SeqListPushBack(&s, 7);

	PrintSeqList(&s);
	SeqListDestory(&s);
}

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_16,color_FFFFFF,t_70,g_se,x_16

heap corruption detected检测到堆溢出了，你动态开辟就申请了三个数据类型大小的空间你一下尾插就加入了7个直接就溢出了，这个报错在debug版本会弹框release版本下不会，但是还是很危险的，你的内存泄露了！

那应该怎么办呢？

扩大我capacity容量呗！

那我们先再次复习一下动态开辟内存函数

malloc / calloc / realloc 区别 

相同点：

  1. 都是C语言标准库提供的从堆上申请内存空间的方法
  2. 需要包含stdlib.h头文件
  3. 申请成功返回空间的首地址，申请失败返回NULL，因此用户在使用时必须要对返回判定是否为空
  4. 返回值都是void* 在使用是必须进行强制类型转换
  5. 从堆上申请的空间，用完之后必需要使用free函数进行释放否则就会造成内存泄漏

不同点：

malloc ：只负责从堆上将空间申请成功，并不会将其初始化

calloc ：有两个参数 一个是元素个数一个是元素的的大小，从堆上申请空间，并且会将内存空间中的每个元素初始话为0

realloc ：函数原型

void* relloc (void* ptr,size_t size);

size_t 表示的是unsigned int 类型将ptr中的字节调整到size个

ptr表示的是是调整内存的地址当ptr == NULL 则等于是malloc了

一般relloc在调整内存是存在两种情况

1.原有空间后面有足够大的空间

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

直接向后扩充就好了

2.原有空间后面没有足够大的空间

 watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16

所以说ptr也就是堆空间的起始地址有可能是变化的！ 

扩容

扩容的时机：当顺序表中有效元素已经将空间填充满则需要扩容！

扩容大小：如果每次扩容一个单位，每次就调用一次malloc这样会使效率十分低下，但是一次性申请过多内存会导致内存空间的浪费！我们一般申请capacity的整数倍。

如何扩容：

        1.申请新的空间
        2.将原有数据进行拷贝
        3.旧空间的释放
        4.返回新空间的地址

方法实现

普通版本

//写到这块了其实咱们顺序表存在一个巨大的问题
//你的size == capacity 在增加还行吗？
//还需要对你的arr进行扩容
//1.申请新的空间
//2.将原有数据进行拷贝
//3.旧空间的释放
//4.返回新空间的地址
void CheckCapacityMode1(SeqList* ps)
{
	if (ps->size == ps->capacity) {
		//1.申请新的空间
		int newcapacity = ps->capacity * 2;
		Datatype* temp = (Datatype*)malloc(newcapacity * sizeof(Datatype));
		if (NULL == temp)
		{
			assert(0);
			return;
		}
		//2.将原有数据进行拷贝
		memcpy(temp, ps->arr, ps->size * sizeof(Datatype));
		//3.旧空间的释放
		free(ps->arr);
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}

realloc版本

//
void CheckCapacityMode2(SeqList* ps)
{
	int newcapacity = ps->capacity * 2;
	Datatype* temp1 = (int*)malloc(sizeof(Datatype) * ps ->capacity);
	assert(temp1);
	memcpy(temp1, ps->arr, ps->size * sizeof(Datatype));
	ps->arr = temp1;
	if (NULL != ps->arr)
	{
		Datatype* temp2 = (Datatype*)realloc(ps->arr, sizeof(Datatype) * newcapacity);
		if (NULL != temp2)
		{
			ps->arr = temp2;
		}
		ps->capacity = newcapacity;
	}
	
		/*ps->arr = (Datatype*)realloc(ps->arr, sizeof(Datatype)*newcapacity);
		if (NULL == ps->arr)
		{
			assert(0);
			return;
		}
		ps->capacity = newcapacity;*/
	
	//会有告警"realloc"可能会返回 null 指针：将空<>指针分配给变量（作为参数传递给"realloc"）将导致原始内存块泄漏
	//此警告指示内存泄漏，该泄漏是不正确使用重新分配函数的结果。 如果重新分配不成功
	//堆重新分配函数不会释放传递的缓冲区
	//若要更正缺陷，请将重新分配函数的结果分配给临时 ，然后在成功重新分配后替换原始指针。
}

会有告警"realloc"可能会返回 null 指针：将空<>指针分配给变量（作为参数传递给"realloc"）将导致原始内存块泄漏此警告指示内存泄漏，该泄漏是不正确使用重新分配函数的结果。 如果重新分配不成功堆重新分配函数不会释放传递的缓冲区若要更正缺陷，请将重新分配函数的结果分配给临时 ，然后在成功重新分配后替换原始指针,详细参考   C6308

为啥用的是memcpy呢？不用strcpy？

还记刚刚的堆溢出吗                 heap corruption detected

我们的字符串函数是以 \0 结尾的 假设你开辟了五个空间strcpy之后就是6个因为strcpy的本身属性：即strcpy只用于字符串复制，并且它不仅复制字符串内容之外，还会复制字符串的结束符！多了一个不久造成堆溢出吗 ！heap corruption detected

现在有了这个方法之后再看我们的尾插

测试

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_17,color_FFFFFF,t_70,g_se,x_16

 头加

// 往顺序表中头插一个值为data的元素
// 时间复杂度是多少？O(N)
void SeqListPushFront(SeqList* ps, Datatype data)
{
	CheckCapacityMode2(ps);
	//在第一个位置插入，那也就是说还得进行搬运
	//这次怎么搬运呢
	//应该是从后往前搬运要是从前往后搬运就会造成内存覆盖
	for (int i = ps->size - 1; i >= 0; --i) {
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[0] = data;
	ps->size++;
}

在第一个位置插入，那也就是说还得进行搬运这次怎么搬运呢

应该是从后往前搬运要是从前往后搬运就会造成内存覆盖

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWEFUVeW8n-S4reS5i-W8nw==,size_20,color_FFFFFF,t_70,g_se,x_16


任意位置添加 

// 删除顺序表任意位置的元素
// 时间复杂度O(N)
void SeqListErase(SeqList* ps, int pos)
{
	//顺序是空我们就不操作了
	if (SeqListEmpty(ps)) {
		return;
	}
	//对pos合法性判断
	if (pos < 0 || pos > ps->size - 1) {
		printf("你的pos输入有误!");
		return;
	}
	for (int i = pos; i < ps->size; i++) {
		ps->arr[pos] = ps->arr[pos + 1];
	}
	ps->size--;
}

还是先检测顺序表是否为空，为空返回，对操作数合法性检验，最后在搬运。

希望本篇 文章对你有帮助 ！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

算法

链表

c语言

c

数据结构 严薇敏 顺序表的实现(增 删 改)及其使用方法详解 的相关文章

随机推荐

  • java数组求和函数_Excel表格求和，难道你只会用SUM函数？（下）

    Excel求和函数 绝大部分人只会用SUM函数 今天再来分享4个求和函数 年前集齐8个求和函数年后开运 1 使用SUMXMY2函数返回两个数组中对应值差的平方和 SUMXMY2函数用于返回两数组中对应数值之差的平方和 函数语法 SUMXMY

  • 如何给keepalived配置vip（虚拟ip）

    首先为了测试机器 准备两台服务器 host1 172 28 23 73 host2 172 28 23 96 虚拟ip 172 28 23 100 第一步 在线安装keepalived中间件 sudo yum install y keepa

  • CMake Error: Cannot determine link language for target “test“.

    问题来源 project kinodyntest LANGUAGES CXX 先指定语言c add executable 后面传入的文件是 c 文件导致cmake报错 c 文件为 cpp

  • 论文笔记：STMARL: A Spatio-Temporal Multi-AgentReinforcement Learning Approach for Cooperative Traffic

    0 abstract 智能交通灯控制系统的开发对于智能交通管理至关重要 虽然已经做出了一些努力以孤立的形式来优化单个红绿灯的使用 但相关研究在很大程度上忽略了多路口红绿灯的使用受到空间影响的事实 以及历史交通状态的时间依赖性 为此 在本文中

  • 用microPython写一个ESP32的OLED的程序

    好的 我可以给你提供一些有关使用 MicroPython 在 ESP32 上编写 OLED 显示屏程序的指导 首先 你需要在 ESP32 上安装 MicroPython 固件 你可以使用 esptool 工具将 MicroPython 固件

  • iscsi多路径配置方式

    学习一个服务的过程 1 此服务器的概述 名字 功能 特点 端口号 2 安装 3 配置文件的位置 4 服务启动关闭脚本 查看端口 5 此服务的使用方法 6 修改配置文件 实战举例 7 排错 从下到上 从内到外 内容 实战 配置IP SAN多路

  • Linux升级命令yum update

    Linux升级命令有两个分别是yum upgrade和yum update 这个两个命令是有区别的 代码如下 yum y update 升级所有包同时也升级软件和系统内核 代码如下 yum y upgrade 只升级所有包 不升级软件和系统

  • Memcach基础使用

    memcache 基础课程 使用场景 memcache 服务器端的安装 推荐使用memcached memcached是memchache的升级版本 sudo su apt get install memcached usr bin mem

  • 02-12306验证码预处理（分割、转存dat、解析dat文件）

    import cv2 as cv import numpy as np import os import binascii temp path r F python StockAnalyzer test test avi img path

  • 决策分类树算法之ID3，C4.5算法系列

    一 引言 在最开始的时候 我本来准备学习的是C4 5算法 后来发现C4 5算法的核心还是ID3算法 所以又辗转回到学习ID3算法了 因为C4 5是他的一个改进 至于是什么改进 在后面的描述中我会提到 二 ID3算法 ID3算法是一种分类决策

  • 从TCP协议的原理来谈谈rst复位攻击

    在谈RST攻击前 必须先了解TCP 如何通过三次握手建立TCP连接 四次握手怎样把全双工的连接关闭掉 滑动窗口是怎么传输数据的 TCP的flag标志位里RST在哪些情况下出现 下面我会画一些尽量简化的图来表达清楚上述几点 之后再了解下RST

  • svn软件常用命令

    下载代码 命令 svn co 代码路径 查看工程中被修改的文件的内容 命令 svn diff 查看工程中文件的状态 命令 svn status 备注 状态是 M 就是被修改过 M是modify的缩写 回退被修改的文件 命令 svn reve

  • 2020中科院sci分区查询_查询SCI分区有几种方法

    查询SCI分区有几种方法 SCI分区目前有两种方法和标准 一个是中科院分区 一个是JCR分区 SCI期刊的分区有着重要意义 SCI期刊的影响因子都是浮动变化的 如果以一个影响因子的固定值来区分期刊是不合理的 不同领域内的期刊影响因子也没有可

  • Java单链表反转 详细过程

    https blog csdn net guyuealian article details 51119499 一 单链表的结点结构 data域 存储数据元素信息的域称为数据域 next域 存储直接后继位置的域称为指针域 它是存放结点的直接

  • Microsoft Dynamics CRM 安装注意事项(请朋友们补充)

    最近安装Microsoft Dynamics CRM 遇到的了很多烦人的小问题 特此记录下需要注意事项 仅供参考 服务器 Windows Server 2012 R2 Datacenter 安装及顺序 IIS gt SQLServer gt

  • 高质量、高并发的实时通信架构设计与探索

    中国互联网络信息中心 CNNIC 近日发布的第 47 次 中国互联网络发展状况统计报告 显示 截至 2020 年 12 月 我国网民规模达 9 89 亿 随着社会信息化水平持续提升及电子设备加速普及 手机网民规模持续增长 基本实现对全体网民

  • D - Robots Easy （脑残题）

    D Robots Easyhttps vjudge csgrandeur cn problem Gym 102267D 题意 对于给出的 12 12 的图 有 l 组查询 每组给出一个坐标 要求从这个坐标开始行走 遇到黑色或在边界不能走 直

  • AGPBI: {“kind“:“error“,“text“:“Program type already present: android.support.v4.os.ResultReceiver$1“

    使用环境 遇见 解决方法 第一步 object下的build gradle文件中build gradle版本号修改 第二步 object下的Gradle版本号修改 具体对应版本 没有一个固定的对应关系 取决于创建项目时创建者当时的AS环境

  • cpp: Observer Pattern

    Gold h 此文件包含 Gold 类 Observer Pattern 观察者模式 C 14 Jewelry Observer Pattern 观察者模式 2023年5月10日 涂聚文 Geovin Du Visual Studio 20

  • 数据结构 严薇敏 顺序表的实现(增 删 改)及其使用方法详解

    时间复杂度 数据结构 时间复杂度和空间复杂度 目录 1 线性表 2 顺序表 2 1概念及结构 2 2 接口实现 SeqList h SeqList c 2 2 1初始化链表以及销毁链表的实现 初始化顺序表 销毁顺序表 2 2 2查找元素前驱

热门标签