数据结构-顺序表的实现(上篇)

举报
芒果_Mango 发表于 2022/01/29 21:42:23 2022/01/29
【摘要】 线性表和顺序表 线性表线性表(linear list)是n个具有相同特性的数据元素的有限序列，是一种很常见的数据结构线性表在逻辑上是线性结构，但是在物理结构上并不一定是连续的常见的线性表有：顺序表、链表、栈、队列、字符串等 顺序表顺序表(seqlist)是物理地址连续的存储元素的线性结构，一般情况下采用数组存储,在数组上完成数据的增删查改可以认为，顺序表的本质就是数组顺序表一般可以分为：1...

线性表和顺序表

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列，是一种很常见的数据结构

线性表在逻辑上是线性结构，但是在物理结构上并不一定是连续的

常见的线性表有：顺序表、链表、栈、队列、字符串等

顺序表

顺序表(seqlist)是物理地址连续的存储元素的线性结构，一般情况下采用数组存储,在数组上完成数据的增删查改

可以认为，顺序表的本质就是数组

顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。

静态顺序表

使用定长数组存储元素。

例子：静态通讯录

#define BOOK_MAX 100
typedef int DataType //这样可以随时改变内容的类型

typedef struct address_book //通讯录内容
{
	struct perinfmt p[BOOK_MAX];//每个人信息,数组一共100个人
	DataType ID;//统计每个人编号
}SeqlistContact;//顺序表

动态顺序表

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

例子：动态通讯录

typedef struct PeopleInfo
{
    struct People* a;//指向动态开辟的结构体成员数组
    int size;//标记成员个数(有效成员个数)
    int capacity;//容量，如果不够可以增容
}PeopleInfo;

2.1.基本架构

使用typedef，类型可以不固定，后序想要更改存储的数据类型更方便

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity; // unsigned int
}SeqList;

size是有效数字个数，同时也是最后一个数据的下一个位置的下标

image-20211019195610155

2.2初始化

指针置空，一开始可以不给容量，也可以给一定的容量

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

2.3扩容

realloc ：如果传空指针，相当于malloc

realloc原理
    1.原地扩容：如果后面空间足够则在后面扩
    2.异地扩容：如果后面空间不够，则重新找一块空间开辟，把原来的数组拷贝过去，然后释放原来空间

最初就是空指针，所以最开始使用realloc时相当于是malloc

扩容每次扩两倍，要判断realloc是否成功

最后还要把新容量赋给ps->capacity，把新开辟空间的地址赋给ps->a

void CheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)
	{
		//扩容
		//如果最初容量为0，就把容量设置为4
		//如果最初容量不为0，那就两倍扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps -> capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (newcapacity));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//直接结束进程
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

2.4打印

遍历数组打印即可,ps->size标志的就是有效数字的个数

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

2.5尾插

尾插：即插入到size位置

size：标志元素个数，size下标是数组最后一个元素的下一个位置

注意：插入要判断容量是否满了 插入元素后：size++

void SeqListPushBack(SeqList* ps, SLDateType x)
{
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.6头插

把元素往后移动，然后在0位置插入元素

注意：防止元素覆盖，要从数组最后一个元素往后移动，0位置的元素也要后移

注意：插入要判断容量是否满了 插入元素后：size++

void SeqListPushFront(SeqList* ps, SLDateType x)
{
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	
	//写法2
	/*
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	*/

	ps->a[0] = x;
	ps->size++;
}

2.7尾删

注意:要考虑数组中是否还有元素可以被删除

只需让ps->size–即可，因为size标志的就是元素个数。最后一个元素虽然空间还在，但是我们已经没有权限访问了

void SeqListPopBack(SeqList* ps)
{
	//温柔处理
	if (ps->size == 0)
	{
		printf("已经没有元素\n");
		return ;
	}
	//暴力处理：assert(ps->size >0)
	ps->size--;
}

2.8头删

注意:要考虑数组中是否还有元素可以被删除

头删：即把第二个元素往前覆盖

注意：要从前面开始往前覆盖！ 删除元素：size–

void SeqListPopFront(SeqList* ps)
{
	if (ps->size == 0)
	{
		printf("已经没有元素\n");
		return ;
	}
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
	//写法2：
	//int begin = 1;
	//while (begin < ps->size)
	//{
	//	ps->a[begin - 1] = ps->a[begin];
	//	++begin;
	//}

	//写法3：
	//int begin = 0;
	//while (begin < ps->size-1)
	//{
	//	ps->a[begin] = ps->a[begin+1];
	//	++begin;
	//}

	ps->size--;	
}

2.9查找

遍历数组进行查找即可，如果数组是有序的，可以使用二分查找。如果找到了，返回对应下标，找不到返回-1

int SeqListFind(SeqList* ps, SLDateType x)
{
	//遍历查找
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	//找不到
	return -1;
}

2.10 pos位置插入

注意：插入要考虑容量是否足够的问题，还要考虑pos位置是否合法。pos位置可以在0位置插入，也可以在size位置插入(因为size标志的是成员个数，同时也是最后一个元素的下一个位置的下标) 插入后：size++

在pos位置插入：即把pos位置的数据往后移动

注意：要从后往前移动

void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	//断言：如果括号内为真就无视，如果为假就报错
	//所以写成：assert(pos < 0 || pos >ps->size)是错误的

	//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
	assert(pos >= 0 && pos<=ps->size);
	CheckCapacity(ps);

	//写法1
	//int i = 0;
	////往后移动
	//for (i = ps->size-1 ; i > pos; i--)
	//{
	//	ps->a[i+1] = ps->a[i];
	//}
	//ps->a[pos] = x;
	//ps->size++;
	
	//写法2：
	int i =ps->size ;
	while (i > pos)
	{
		ps->a[i] = ps->a[i-1];
		i--;
	}
	ps->size++;
	ps->a[pos] = x;
}

头插尾插的写法：

头插：即在0位置插入

尾插：即在size-1位置插入

头插：SeqListInsert(ps, 0, x);
尾插：SeqListInsert(ps,ps->size - 1,x)

2.11pos位置删除

注意：删除也要保证位置的合法性 删除后，size–

在pos位置删除，即把pos后面的数据向前覆盖。

从前往后移动(先移动pos+1位置的数据往前覆盖)

void SeqListErase(SeqList* ps, size_t pos)
{
	//此时pos不可以为size，
	//因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置，这个位置没有存元素，不可以删除
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size -1; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
    /*
	//写法2：
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	*/
	ps->size--;
}

头删尾删的写法

头删：SeqListErase(ps,0)
尾删：SeqListErase(ps, ps->size - 1);

2.12销毁

因为数组指向的空间是动态开辟的，所以结束时要把空间销毁，防止内存泄漏。

销毁之后要把指针置空！！防止造成野指针

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

注意事项

插入元素考虑因素：

整个顺序表空间是否满了，满了则扩容，插入之后size要++

头插：从后往前移动(先移动最后的数据)

尾插：直接插入到size位置

删除元素考虑因素

是否还有元素可以被删除，删除元素之后size–

头删：从前往后移动(先移动前面的数据进行覆盖)

尾删：直接size–即可

test.c

#include"Seqlist.h"
void Test1()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 3);
	SeqListPushFront(&s, 5);
	SeqListPushFront(&s, 6);
	SeqListPushFront(&s, 7);
	// 7 6 5 1 3
	SeqListInsert(&s, 0,1);
	SeqListPrint(&s);
}
int main()
{
	Test1();
	return 0;
}

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include"Seqlist.h"

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
void SeqListDestory(SeqList* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
void CheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)
	{
		//扩容
		//如果最初容量为0，就把容量设置为4
		//如果最初容量不为0，那就两倍扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps -> capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (newcapacity));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//直接结束进程
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x)
{
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//头插
void SeqListPushFront(SeqList* ps, SLDateType x)
{
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	int end = ps->size - 1;

	//写法2
	/*
		while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	*/

	ps->a[0] = x;
	ps->size++;
}
//头删
void SeqListPopFront(SeqList* ps)
{
	if (ps->size == 0)
	{
		printf("已经没有元素\n");
		return ;
	}
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
	//写法2：
	//int begin = 1;
	//while (begin < ps->size)
	//{
	//	ps->a[begin - 1] = ps->a[begin];
	//	++begin;
	//}

	//写法3：
	//int begin = 0;
	//while (begin < ps->size-1)
	//{
	//	ps->a[begin] = ps->a[begin+1];
	//	++begin;
	//}

	ps->size--;	
}
//尾删
void SeqListPopBack(SeqList* ps)
{
	//温柔处理
	if (ps->size == 0)
	{
		printf("已经没有元素\n");
		return ;
	}
	//暴力处理：assert(ps->size >0)
	ps->size--;
}

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
	//遍历查找
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	//找不到
	return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	//断言：如果括号内为真就无视，如果为假就报错
	//所以写成：assert(pos < 0 || pos >ps->size)是错误的

	//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
	assert(pos >= 0 && pos<=ps->size);
	CheckCapacity(ps);

	//写法1
	//int i = 0;
	////往后移动
	//for (i = ps->size-1 ; i > pos; i--)
	//{
	//	ps->a[i+1] = ps->a[i];
	//}
	//ps->a[pos] = x;
	//ps->size++;
	
	//写法2：
	int i =ps->size ;
	while (i > pos)
	{
		ps->a[i] = ps->a[i-1];
		i--;
	}
	ps->size++;
	ps->a[pos] = x;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{
	//此时pos不可以为size，
	//因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置，这个位置没有存元素，不可以删除
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size -1; i++)
	{
		ps->a[i] = ps->a[i+1];
	}
	//写法2：
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

//头删：SeqListErase(ps,0)
//尾删：SeqListErase(ps, ps->size - 1);
//
//头插：SeqListInsert(ps, 0, x);
//尾插：SeqListInsert(ps,ps->size - 1,x)

Seqlist.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
// SeqList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity; // unsigned int
}SeqList;

// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestory(SeqList* ps);
void CheckCapacity(SeqList* ps);

void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos);

写的时候遇到的坑点：

//在pos位置插入
//错误写法：
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	assert(pos >= 0 && pos<=ps->size);
	CheckCapacity(ps);
	//写法1
	//int i = 0;
	////往后移动
	//for (i = ps->size-1 ; i >= pos; i--)
	//{
	//	ps->a[i+1] = ps->a[i];
	//}
	//ps->a[pos] = x;
	//ps->size++;
	
	//写法2：
	int i =ps->size -1 ;
	while (i >= pos)
	{
		ps->a[i+1] = ps->a[i];
		i--;
	}
	ps->size++;
	ps->a[pos] = x;
}

错误原因：pos是size_t类型，无符号整形。i为整形

pos和i进行比较时，i会提升为无符号整形，即i的范围为：[0,2147483 648]，i恒大于0.所以若在pos = 0位置插入，则 i>=pos恒成立，会造成死循环。

pos为其他正数值的时候不会发生，因为i的返回时[0,2^31]，i终究会变到小于pos的值跳出循环！！，但是若pos为0，则i>=pos恒满足，死循环。所以这是个很隐藏的错误，

即使i也定义为无符号整形也是如此

i和pos进行比较不能取相等！！！防止出现pos位置取0的情况！

//正确写法：
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	//断言：如果括号内为真就无视，如果为假就报错
	//所以写成：assert(pos < 0 || pos >ps->size)是错误的

	//插入可以在size位置插入，因为size标识的是元素个数，指向的是数组最后一个元素的下一个位置
	assert(pos >= 0 && pos<=ps->size);
	CheckCapacity(ps);

	//写法1
	//int i = 0;
	////往后移动
	//for (i = ps->size-1 ; i > pos; i--)
	//{
	//	ps->a[i+1] = ps->a[i];
	//}
	//ps->a[pos] = x;
	//ps->size++;
	
	//写法2：
	int i =ps->size ;
	while (i > pos)
	{
		ps->a[i] = ps->a[i-1];
		i--;
	}
	ps->size++;
	ps->a[pos] = x;
}

同理在pos位置删除时，i和pos比较也不能取等号

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

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

全部回复

上滑加载中

设置昵称

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

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

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

确认 取消

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

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