目录
概念及结构
接口函数实现
顺序表的初始化
容量判断
顺序表尾插
顺序表尾删
顺序表头插
顺序表头删
顺序表查找
顺序表指定位置插入
顺序表指定位置删除
打印顺序表
销毁顺序表
顺序表完整代码
概念及结构
顺序表作为线性表的一种,它是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般分为:
1、静态顺序表——使用定长数组进行存储元素。
#define N 100
//顺序表的静态存储
typedef int SLDatatype;
typedef struct SeqList
{
SLDataType Data[N]; //定长数组
int size; //有效数据个数
}SeqList;
这种存储方式在存储数据时比较有局限性,当数据存储量非常小的时候,数组长度太长,会造成空间的浪费;当数据存储量非常大的时候,数组空间可能会不够,但是这种存储方式不能进行扩容。所以在实现顺序表时,我们通常使用的是动态顺序表。这样能够提高我们的空间利用率。
2、动态顺序表——使用动态开辟的数组进行存储元素。
//顺序表的动态存储
typedef int SLDatatype;
typedef struct SeqList
{
SLDataType* Data; //定长数组
int size; //有效数据个数
int capacity; //空间容量的大小
}SeqList;
接口函数实现
顺序表的初始化
//初始化链表
void SLInit(SeqList* ps)
{
assert(ps); //判空,如果传入的空指针,后面对它进行解引用就会报错
ps->data = NULL; //将data初始化为空指针
ps->capacity = ps->size = 0;
}
现在顺序表的初始化完成了,接下来就是顺序表的增删查改了。
在实现顺序表增加元素的函数功能前,首先我们先实现一个检查顺序表是否已经存满。如果已经存满了,那么我们就需要对它进行扩容。
容量判断
//容量判断
void Check_Capacity(SeqList* ps)
{
assert(ps);
if (ps->capacity == ps->size) //判断顺序表中有效数据个数是否已经达到容量大小
{
int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
//如果容量为0的话,此时就是第一次向顺序表中添加元素,capacity就设为4
//如果容量不为0,此时就是有效数据个数达到容量,就进行扩容,新容量设置为原容量的2倍
SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType));
if (tmp == NULL) //如果扩容失败,就终止程序。
{
perror("ralloc fail");
exit(-1);
}
ps->data = tmp;
ps->capacity = new_capacity;
}
}
这里扩容使用的是realloc函数,当我们进行第一次插入的时候,ps->data指针还是空指针,这时我们也可以使用realloc,realloc函数在使用的时候,如果传入的指针是空指针,它的作用就与malloc相同。
顺序表尾插
//顺序表尾插
void SL_PushBack(SL* ps, SLDataType x)
{
assert(ps);
Check_Capacity(ps);
ps->data[ps->size] = x;
ps->size++;
}
顺序表尾删
//顺序表尾删
void SL_PopBack(SL* ps)
{
assert(ps);
assert(ps->size > 0); //如果顺序表中已经没有元素,那么就不用进行删除,所以
//这里需要检查顺序表中是否还有元素。
ps->size--;
}
无论是尾删还是头删,都要对顺序表进行检查表中是否还有元素。
顺序表头插
//顺序表头插
void SL_PushFront(SL* ps, SLDataType x)
{
assert(ps);
Check_Capacity(ps); //检查容量
//将所有数据向后移动一位
for (int i = ps->size - 1; i >= 0; i--)
{
ps->data[i + 1] = ps->data[i];
}
ps->data[0] = x;
ps->size++;
}
头插时不仅要对容量进行检查,同时,我们也要将数据向后移动一位再进行插入操作,不然会造成数据丢失。
顺序表头删
//顺序表头删
void SL_PopFront(SL* ps)
{
assert(ps);
//如果顺序表中只有一个数据,那么直接将数据个数-1
//如果对数据进行挪动,会造成越界
if (ps->size == 1)
{
ps->size--;
return;
}
如果数据个数不为1,就将数据中第2个到最后一个都往前移动一位
for (int i = 1; i < ps->size; i++)
{
ps->data[i - 1] = ps->data[i];
}
ps->size--;
}
顺序表查找
//顺序表查找
int SL_Find(SeqList* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->data[i] == x)
{
//找到就返回下标
return i;
}
}
//找不到就返回-1
return -1;
}
顺序表指定位置插入
//顺序表指定位置插入
void SL_Insert(SeqList* ps, int pos, SLDataType x)
{
assert(ps);
//判定pos是否合法
assert(pos <= ps->size);
assert(pos >= 0);
Check_Capacity(ps); //检查容量是否够用
//将pos位置后的元素全部都向后移动一位
for (int i = ps->size-1; i >= pos; i--)
{
ps->data[i + 1] = ps->data[i];
}
ps->data[pos] = x;
ps->size++;
}
顺序表指定位置删除
//顺序表指定位置删除
void SL_Erase(SeqList* ps, int pos)
{
assert(ps);
//检查pos位置是否合法
assert(pos >= 0);
assert(pos < ps->size);
//将pos位置后面的元素全都向前移动一位
for (int i = pos; i < ps->size; i++)
{
ps->data[i] = ps->data[i + 1];
}
ps->size--;
}
有了顺序表指定位置的插入和删除后,我们就可以对尾插尾删、头插头删进行改写:
//尾插
void SL_PushBack(SeqList* ps, SLDataType x)
{
SL_Insert(ps, ps->size, x);
}
//尾删
void SL_PopBack(SeqList* ps)
{
SL_Erase(ps, ps->size - 1);
}
//头插
void SL_PushFront(SeqList* ps, SLDataType x)
{
SL_Insert(ps, 0, x);
}
//头删
void SL_PopFront(SeqList* ps)
{
SL_Erase(ps,0);
}
打印顺序表
//打印顺序表
void SLPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->data[i]);
}
printf("\n");
}
销毁顺序表
//销毁顺序表
void SL_Destroy(SeqList* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = ps->size = 0;
}
顺序表完整代码
SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* data;
int size;
int capacity;
}SeqList;
//初始化顺序表
void SLInit(SeqList* ps);
//删除顺序表
void SL_Destroy(SeqList* ps);
//打印顺序表
void SLPrint(SeqList* ps);
//检查容量
void Check_Capacity(SeqList* ps);
//尾插尾删
void SL_PushBack(SeqList* ps,SLDataType x);
void SL_PopBack(SeqList* ps);
//头插头删
void SL_PushFront(SeqList* ps, SLDataType x);
void SL_PopFront(SeqList* ps);
//顺序表查找
int SL_Find(SeqList* ps, SLDataType x);
//顺序表指定位置插入
void SL_Insert(SeqList* ps, int pos, SLDataType x);
//顺序表指定位置删除
void SL_Erase(SeqList* ps, int pos);
SeqList.c文章来源:https://www.toymoban.com/news/detail-846097.html
#include "SeqList.h"
void SLInit(SeqList* ps)
{
assert(ps);
ps->data = NULL;
ps->capacity = ps->size = 0;
}
void SL_Destroy(SeqList* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = ps->size = 0;
}
void SLPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->data[i]);
}
printf("\n");
}
void Check_Capacity(SeqList* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("ralloc fail");
exit(-1);
}
ps->data = tmp;
ps->capacity = new_capacity;
}
}
void SL_PushBack(SeqList* ps, SLDataType x)
{
//assert(ps);
//Check_Capacity(ps);
//ps->a[ps->size] = x;
//ps->size++;
SL_Insert(ps, ps->size, x);
}
void SL_PopBack(SeqList* ps)
{
//assert(ps);
//assert(ps->size > 0);
//ps->size--;
SL_Erase(ps, ps->size - 1);
}
void SL_PushFront(SeqList* ps, SLDataType x)
{
//assert(ps);
//Check_Capacity(ps);
//for (int i = ps->size - 1; i >= 0; i--)
//{
// ps->a[i + 1] = ps->a[i];
//}
//ps->a[0] = x;
//ps->size++;
SL_Insert(ps, 0, x);
}
void SL_PopFront(SeqList* ps)
{
//assert(ps);
//if (ps->size == 1)
//{
// ps->size--;
// return;
//}
//for (int i = 1; i < ps->size; i++)
//{
// ps->data[i - 1] = ps->data[i];
//}
//ps->size--;
SL_Erase(ps,0);
}
int SL_Find(SeqList* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->data[i] == x)
{
return i;
}
}
return -1;
}
void SL_Insert(SeqList* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos <= ps->size);
assert(pos >= 0);
Check_Capacity(ps);
for (int i = ps->size-1; i >= pos; i--)
{
ps->data[i + 1] = ps->data[i];
}
ps->data[pos] = x;
ps->size++;
}
void SL_Erase(SeqList* ps, int pos)
{
assert(ps);
assert(pos >= 0);
assert(pos < ps->size);
for (int i = pos; i < ps->size; i++)
{
ps->data[i] = ps->data[i + 1];
}
ps->size--;
}
以上就是顺序表相关实现的全部内容了,希望能够帮到大家。文章来源地址https://www.toymoban.com/news/detail-846097.html
到了这里,关于【数据结构】C语言实现顺序表(超级详细)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!