水月梦镜花

水月梦镜花

关注
发信
关注(28)粉丝(399)

数据结构：顺序表(C实现)

数据结构：顺序表(C实现)-LMLPHP

一、顺序表

顺序表是用一段物理结构连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。
顺序表一般分为两种：

  • 静态顺序表：使用定长数组实现
  • 动态顺数表：使用动态开辟的数组实现

本篇文章，顺序表是使用动态开辟的数组实现(动态顺序表)。要实现的功能如下：

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

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

//打印顺序表
void SeqListPrint(SeqList* ps);

//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);

//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDateType x);

//顺序表尾删
void SeqListPopBack(SeqList* ps);

//顺序表头删
void SeqListPopFront(SeqList* ps);

//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);

//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDateType x);

//删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

//检查容量
void SeqListCheckCapacity(SeqList* ps);

二、实现思路

画图理解起来更佳！！！

1.存储结构

我们重命名int类型为SLDataType，方便以后我们修改顺序表存储元素的类型。
指针data指向动态开辟的空间，变量sz记录有效的数据元素，变量capacity记录动态开辟空间的大小。

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* data;
	int sz;
	int capacity;
}SeqList;

2.初始化顺序表(SeqListInit)

动态开辟一块空间，用data指针保存空间首地址。
此时data指向空间中有效元素为0，使sz == 0，变量capacity在等于此时开辟空间的大小。

#define SIZE 4

void SeqListInit(SeqList* ps)
{
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * SIZE);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	ps->sz = 0;
	ps->capacity = SIZE;
}

3.销毁顺序表(SeqListDestroty)

free所开辟的空间，使data == NULL，此时数据有效元素为0，空间大小为0，那么sz = 0，capacity = 0；

//销毁顺序表
void SeqListDestroty(SeqList* ps)
{
	assert(ps);

	//free(ps);
	free(ps->data);
	ps->data = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}

4.打印顺序表(SeqListPrint)

这个函数非常简单，只要遍历一遍所开辟的空间即可，注意范围是(0，sz)。

//打印顺序表
void SeqListPrint(SeqList* ps)
{
	assert(ps);

	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");

}

5.顺序表尾插(SeqListPushBack)and检查容量(SeqListCheckCapacity)

每次加入数据时，我们要先检查空间大小是否充足，再加入数据

  • 检查容量
    在尾插数据前，要检查空间大小是否充足(sz == capacity)，如果空间大小不够，要扩大空间大小，capacity记录新的空间大小。

  • 尾插元素
    变量sz不仅代表空间有效元素个数，也代表了新数据元素将要放入的位置。所以尾插元素，只要空间大小充足，那么在data[sz]处放入数据即可，不要忘记sz要加一。

//检查容量
void SeqListCheckCapacity(SeqList* ps)
{
	SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2);
	if (tmp == NULL)
	{
		perror("realloc");
		exit(-1);
	}

	ps->data = tmp;
	ps->capacity *= 2;
}



//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	ps->data[ps->sz] = x;
	ps->sz++;
}

6.顺序表头插(SeqLsitPushFront)

顺序表除了尾插，尾删不用挪到数据，其它的增删都要挪到数据。
头插数据，要先检查空间大小，再向后挪到数据，将数据放入data[0]处，sz在加一。

//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[0] = x;
	ps->sz++;
}

7.顺序表尾删(SeqListPopBack)

变量sz代表有效数据的个数，那么只要sz减一，就代表最后一个数据被删除了。

//顺序表尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->sz != 0);

	ps->sz--;
}

8.顺序表头删(SeqListPopFront)

头删数据，要将数据从后向前挪到，覆盖掉第一个数据，sz要减一。

//顺序表头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->sz != 0);

	for (int i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

9.顺序表查找(SeqListFind)

遍历一遍动态开辟的数组，如果找到了就放回下标，没有就放回-1。

//顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->sz; i++)
	{
		if (ps->data[i] == x)
		{
			return i;
		}
	}

	return -1;
}

10.在pos位置前插入元素(SeqListInsert)

要先检查空间容量是否充足和要插入的位置是否合法(要在顺序表的有效数据内)，再将pos下标后的数据向后挪到，将数据放入data[pos]处，sz加一。
这个函数思路简单，但要注意下面两点：

  • 如果pos == 0，不就是要在顺序表第一个元素前插入元素，不就是顺序表的头插。
  • 如果pos == sz，我们知道sz还表示下一个数据要放入的位置，那么我在下一个数据要放入的位置前插入元素，不就是顺序表的尾插。

理解这点后，我们以后的头插，尾插都可以用该函数复用。方便我们手撕顺序表

//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->sz);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->sz++;
}

11.删除pos位置的值(SeqListErase)

删除pos位置处的数据，先检查pos的合法性(要属于[0，sz-1])，要将数据从后向前挪到数据，sz减一。
这个函数思路简单，但要注意下面两点：

  • 如果pos == 0，不就是要删除第一个数据，不就是头删。
  • 如果pos == sz - 1，不就是要删除最后一个数据，不就是尾删。

所以对于尾删，头删函数而言，我们也可以使用该函数复用。

//删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->sz);

	for (int i = pos; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

三、代码实现

头删，头插，尾删，尾插我都复用了SeqListInsert和SeqListErase。
SeqList.h 文件存放有关函数的声明以及结构体的声明
SeqList.c 文件存放函数的定义

//SeqList.h 文件

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define SIZE 4

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* data;
	int sz;
	int capacity;
}SeqList;



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

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

//打印顺序表
void SeqListPrint(SeqList* ps);

//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDateType x);

//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDateType x);

//顺序表尾删
void SeqListPopBack(SeqList* ps);

//顺序表头删
void SeqListPopFront(SeqList* ps);

//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);

//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDateType x);

//删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

//检查容量
void SeqListCheckCapacity(SeqList* ps);

//SeqList.c 文件

#include "SeqList.h"


//初始化顺序表
void SeqListInit(SeqList* ps)
{
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * SIZE);
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	ps->sz = 0;
	ps->capacity = SIZE;
}

//检查容量
void SeqListCheckCapacity(SeqList* ps)
{
	SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2);
	if (tmp == NULL)
	{
		perror("realloc");
		exit(-1);
	}

	ps->data = tmp;
	ps->capacity *= 2;
}



//顺序表尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	/*assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	ps->data[ps->sz] = x;
	ps->sz++;*/

	SeqListInsert(ps, ps->sz, x);
}


//打印顺序表
void SeqListPrint(SeqList* ps)
{
	assert(ps);

	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");

}


//销毁顺序表
void SeqListDestroty(SeqList* ps)
{
	assert(ps);

	//free(ps);
	free(ps->data);
	ps->data = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}


//顺序表头插
void SeqLsitPushFront(SeqList* ps, SLDataType x)
{
	/*assert(ps);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > 0)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[0] = x;
	ps->sz++;*/

	SeqListInsert(ps, 0, x);
}


//顺序表尾删
void SeqListPopBack(SeqList* ps)
{
	/*assert(ps);
	assert(ps->sz != 0);

	ps->sz--;*/

	SeqListErase(ps, ps->sz - 1);
}

//顺序表头删
void SeqListPopFront(SeqList* ps)
{
	/*assert(ps);
	assert(ps->sz != 0);

	for (int i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;*/

	SeqListErase(ps, 0);
}


//顺序表查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i < ps->sz; i++)
	{
		if (ps->data[i] == x)
		{
			return i;
		}
	}

	return -1;
}


//在pos位置前插入元素
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->sz);

	if (ps->sz == ps->capacity)
	{
		SeqListCheckCapacity(ps);
	}

	int end = ps->sz;
	while (end > pos)
	{
		ps->data[end] = ps->data[end - 1];
		end--;
	}

	ps->data[pos] = x;
	ps->sz++;
}


//删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->sz);

	for (int i = pos; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

总结

以上就是顺序表的实现。谢谢支持！！！

数据结构：顺序表(C实现)-LMLPHP

07-28 14:08
Powered by LMLPHP ©2024 水月梦镜花 0.002378