顺序表的基本操作(初始化、插入、删除、查询、扩容、打印、清空等)

admin • 2021-11-20 20:35 • C/C++

顺序表的基本操作

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

初始化

初始化结构体，开辟空间

void SeqListInit(SeqList* ps, size_t inite_capicity)
{
	assert(ps);
	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
	if (NULL == ps->arr)
	{
		exit(1);
	}
	ps->capicity = inite_capicity;
	ps->size = 0;
}

清空

因为动态内存申请用完空间必须释放，所以存在这个函数

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capicity = 0;
		ps->size = 0;
	}
}

打印

打印顺序表内容

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

扩容

增加顺序表的容量

static void SeqListRealloc(SeqList* ps)
{
	SLDataType* temp = ps->arr;
	temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
	if (temp != NULL)
	{
		// 若申请则将扩容后的地址赋给ps->size
		// 这样做的目的是防止空间申请失败后原有空间的地址无法找回
		ps->arr = temp;
	}
	ps->capicity *= 2;
}

尾插法

尾插法只需要将元素放入最会一个位置，并对size加上1即可

void SeqListPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	//先判断是否已满，如果已满则需要扩容
	if (ps->size == ps->capicity)
	{
		SeqListRealloc( ps);//调用扩容函数
	}
	ps->arr[ps->size] = data;//将数据放到顺序表的结尾
	ps->size++;//有效元素增加一个
}

判空

插入操作前都要判断顺序表是否已满

static int IsSeqListEmpty(SeqList* ps)
{
	assert(ps);
	if (0==ps->size)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

尾删法

尾删只需要将实际元素个数减一即可

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		ps->size--;
	}
}

头插法

顺序表所有元素向后移动一个单位，在第一个位置插入数据

void SeqListPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
	}
	//***将ps->size强转成int类型，否则计算时会发生类型提升***
	for (int i = (int)ps->size - 1; i >= 0; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//所有元素向后移动一个单位
	}
	ps->arr[0] = data;//将元素插入顺序表头部
	ps->size ++;//元素个数加1
}

头删法

将第一个元素以后的所有元素向前移动一个单位

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = 0; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素个数减1
	}
}

查询

查询表中是否有某一元素，若存在则返回其下标

int SeqListFind(SeqList* ps, SLDataType data)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == data) 
		{
			return i;
		}
	}
	return -1;//未找到返回-1
}

任意位置插入

函数的第二个参数为要插入的位置，第三个参数为要插入的数据，与头插原理相似

void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
	}

	for (int i = (int)ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移动一个单位
	}
	ps->arr[pos] = data;//将元素插入顺序表头部
	ps->size++;//元素个数加1
}

任意位置删除

从某一要删除的元素位置开始，后面所有元素向前移动一个单位

void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = (int)pos; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素个数减1
	}
}

完整代码

下面给出线性表操作的完整代码，代码的注释对每步的作用有详细的介绍：

其中work.h头文件主要完成包含头文件和结构体、各个函数的声明
main.c源文件是程序的入口，并在这里实现测试用例，具体使用时，结构体变量在main.c中定义
work.c源文件是各个操作的具体函数的实现

work.h

#pragma once
#include<stdio.h>
#include<windows.h>
#include<stdlib.h>
#include<assert.h>
#define MAXSIZE 50

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//起始地址 
	size_t capicity;//容量
	size_t size;//有效数据

}SeqList;

//下面这些都是函数声明
void SeqListInit(SeqList* ps,size_t inite_capicity);//初始化
void SeqListDestory(SeqList* ps);//空间释放
void SeqListPushBack(SeqList* ps, SLDataType data);//尾插
void SeqListPopBack(SeqList* ps);//尾删
void SeqListPushFront(SeqList* ps,SLDataType data);//头插法
void SeqListPopFront(SeqList* ps);//头删法
int SeqListFind(SeqList* ps, SLDataType data);//查找
void SeqListInsert(SeqList* ps, size_t pos, SLDataType x);//任意位置插入
void SeqListErase(SeqList* ps, size_t pos);//任意位置删除
void SeqListPrint(SeqList* ps);//顺序表打印

main.c

#include"work.h"

//测试用例
void TestSeqList()
{
	SeqList s;
	SeqList* ps = &s;
	SeqListInit(ps, MAXSIZE);

	SeqListPushBack(ps, 1);//尾插法增加5个元素
	SeqListPushBack(ps, 2);
	SeqListPushBack(ps, 3);
	SeqListPushBack(ps, 4);
	SeqListPushBack(ps, 5);
	SeqListPrint(ps);//打印输出

	SeqListPopBack(ps);//尾删法删除一个元素
	SeqListPrint(ps);//打印输出 

	SeqListPushFront(ps, 0);	//头插法增加一个元素
	SeqListPrint(ps);	//打印输出 

	SeqListPopFront(ps);//头删法删除一个元素
	SeqListPrint(ps);	//打印输出 

	//调用查找函数并返回下标，若不存在返回值为-1
	printf("%dn", SeqListFind(ps, 2));
	printf("%dn", SeqListFind(ps, 10));

	SeqListInsert(ps, 4, 5);//第4个位置插入
	SeqListPrint(ps);

	SeqListErase(ps, 5);//第5个位置删除
	SeqListPrint(ps);

	SeqListDestory(ps);
}

int main()
{
	TestSeqList();//调用测试函数
	system("pause");
	return 0;
}

work.c

#include"work.h"

//初始化函数
void SeqListInit(SeqList* ps, size_t inite_capicity)
{
	assert(ps);
	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * inite_capicity);
	if (NULL == ps->arr)
	{
		exit(1);
	}
	ps->capicity = inite_capicity;
	ps->size = 0;
}

//堆空间释放释放函数
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capicity = 0;
		ps->size = 0;
	}

}

//顺序表打印函数
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("n");
}

//扩容函数
static void SeqListRealloc(SeqList* ps)
{
	SLDataType* temp = ps->arr;
	temp = (SLDataType*)realloc(ps->arr, ps->capicity * 2);
	if (temp != NULL)
	{
		// 若申请则将扩容后的地址赋给ps->size
		// 这样做的目的是防止空间申请失败后原有空间的地址无法找回
		ps->arr = temp;
	}
	ps->capicity *= 2;
}

//尾插法
void SeqListPushBack(SeqList* ps, SLDataType data)
{
	assert(ps);
	//先判断是否已满，如果已满则需要扩容
	if (ps->size == ps->capicity)
	{
		SeqListRealloc( ps);//调用扩容函数
	}
	ps->arr[ps->size] = data;//将数据放到顺序表的结尾
	ps->size++;//有效元素增加一个

}

//判空函数
static int IsSeqListEmpty(SeqList* ps)
{
	assert(ps);
	if (0==ps->size)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//尾删法
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		ps->size--;//尾删只需要将实际元素个数减一即可
	}
}

//头插法
void SeqListPushFront(SeqList* ps, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
	}
	//***将ps->size强转成int类型，否则计算时会发生类型提升***
	for (int i = (int)ps->size - 1; i >= 0; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//所有元素向后移动一个单位
	}
	ps->arr[0] = data;//将元素插入顺序表头部
	ps->size ++;//元素个数加1
}

//头删法
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = 0; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素个数减1
	}
}


//查询
int SeqListFind(SeqList* ps, SLDataType data)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == data) 
		{
			return i;
		}
	}
	return -1;//未找到返回-1
}

//任意位置插入
void SeqListInsert(SeqList* ps, size_t pos, SLDataType data)
{
	assert(ps);
	if (ps->size == ps->capicity)
	{
		SeqListRealloc(ps);//若顺序表空间已满调用扩容函数
	}

	for (int i = (int)ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//pos位置及其以后所有元素向后移动一个单位
	}
	ps->arr[pos] = data;//将元素插入顺序表头部
	ps->size++;//元素个数加1
}

//任意位置删除
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	if (!IsSeqListEmpty(ps))
	{
		for (int i = (int)pos; i < (int)ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;//元素个数减1
	}
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c语言后端开发语言数据结构

二维码

C语言——初阶指针

< <上一篇

指针（初阶）

下一篇>>

搜索内容

顺序表的基本操作(初始化、插入、删除、查询、扩容、打印、清空等)

顺序表的基本操作

初始化

清空

打印

扩容

尾插法

判空

尾删法

头插法

头删法

查询

任意位置插入

任意位置删除

完整代码

最新文章

分类

标签云