数据结构之顺序表

用户10923276

发布于 2024-03-28 18:12:13

1060

发布于 2024-03-28 18:12:13

文章被收录于专栏：北飞的山羊知识库北飞的山羊知识库

一、概念及结构

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

顺序表一般可以分为：

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

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

二、具体代码实现

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

#pragma once

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

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

// 对数据的管理:增删查改 

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

//销毁
void SeqListDestroy(SeqList* ps);

//打印
void SeqListPrint(SeqList* ps);

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

//头插
void SeqListPushFront(SeqList* ps, SLDateType x);

//查看顺序表容量，若满了就扩容
void CheckSeqlist(SeqList* ps);

//头删
void SeqListPopFront(SeqList* ps);

//尾删
void SeqListPopBack(SeqList* ps);

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

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);

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

//SeqList.c
#include "SeqList.h"


void SeqListInit(SeqList* ps)
{
	int i = 0;
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 5);
	ps->capacity = 5;
	ps->size = 0;

	for (i = 0; i < ps->capacity; i++)
	{
		ps->a[i] = 0;
	}
}

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

void CheckSeqlist(SeqList* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a,sizeof(SLDateType) * (ps->capacity) * 2);
		ps->capacity *= 2;//若容量满了就扩容为原来的两倍
		if (tmp != NULL)
		{
			ps->a = tmp;
		}
	}
}

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


void SeqListPushFront(SeqList* ps, SLDateType x)
{
	assert(ps);
	CheckSeqlist(ps);
	int j = ps->size;
	for (; j > 0; j--)
	{
		ps->a[j] = ps->a[j- 1];
	}
	ps->a[0] = x;
	ps->size++;
}


void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int j = 0;
	for (j = 0; j < ps->size-1; j++)
	{
		ps->a[j] = ps->a[j + 1];
	}
	ps->size--;
}

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}


void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->size && pos >= 0);
	CheckSeqlist(ps);
	int j = ps->size;
	for (; j >pos; j--)
	{
		ps->a[j] = ps->a[j - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}


void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos < ps->size && pos >= 0);
	int j;
	for (j = pos; j < ps->size-1; j++)
	{
		ps->a[j] = ps->a[j + 1];
	}
	ps->size--;
}

//test.c
#include "SeqList.h"

int main()
{
	SeqList s;
	SeqListInit(&s);

	SeqListPushBack(&s, 10);
	SeqListPushBack(&s, 20);
	SeqListPushBack(&s, 30);
	SeqListPushBack(&s, 40);
	SeqListPushBack(&s, 50);
	SeqListPushFront(&s, 0);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListInsert(&s, 1, 1);
	SeqListPrint(&s);

	SeqListErase(&s, 1);
	SeqListPrint(&s);

	SeqListDestroy(&s);

	return 0;
}