前言
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
1.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
动态和静态顺序表的创建
静态顺序表
静态顺序表：指定顺序表的大小
缺点：空间开大了浪费，空间开小了不够用
typedef int SLDataType;
#define N 10//指定大小为10
typedef struct SeqList
{
SLDataType a[N];
int sz;
}SeqList;
动态顺序表
动态顺序表：使用动态开辟的数组存储
指向动态开辟的数组，空间不够用了可以扩容
#define INIT_CAPACITY 4
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int sz;
int capacity;
}SeqList;
2.前期的准备工作
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表
初始化顺序表
//初始化
void SeqListInit(SeqList* ps)
{
assert(ps);
ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
if (ps->a == NULL)
{
perror("SeqListInit");
return;
}
ps->sz = 0;
ps->capacity = INIT_CAPACITY;
销毁顺序表
//销毁
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->sz = ps->capacity = 0;
}
检查容量
void SeqListCheakcapacity(SeqList* ps)
{
assert(ps);
if (ps->sz == ps->capacity)//如果数组大小和容量相同，则扩容
{
//扩容
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("SeqListPushback");
return;
}
ps->a = tmp;
ps->capacity = ps->capacity * 2;
}
}
打印
//打印
void SeqListPrint(SeqList* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->sz; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
3.顺序表的增删查改等功能
尾插
先检查容量是否满了，如果买了扩容，然后在当前sz位置直接插入就是尾部插入。
//尾插
void SeqListPushback(SeqList* ps, SLDataType x)
{
assert(ps);
SeqListCheakcapacity(ps);//检查容量
ps->a[ps->sz] = x;//插入到当前sz位置
ps->sz++;
}
尾删
sz当前的位置就是尾部，直接sz–即可
//尾删
void SeqListPopback(SeqList* ps)
{
assert(ps);
assert(ps->sz > 0);
ps->sz--;
}
头插
头插思想是把数据依次向后移动移位，然后再把数据插入到下标为0的位置
//头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
assert(ps);
SeqListCheakcapacity(ps);
int end = ps->sz - 1;
while (end >= 0)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->sz++;
}
头删
数据依次向前覆盖，最后第一个数据就会消失，再–sz即可
//头删
void SeqListPopFront(SeqList* ps)
{
assert(ps);
assert(ps->sz > 0);
int i = 0;
for (i = 0; i < ps->sz; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->sz--;
}
指定位置插入
定义一个end指向最后一个值，然后依次把值向后挪动，while循环end>=pos
每次end- -，最后end就会走到pos的位置
//指定插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
SeqListCheakcapacity(ps);
assert(ps);
assert(pos >= 0 && pos <= ps->sz);
int end = ps->sz - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->sz++;
}
指定位置删除
pos后面的一个值，放到pos位置，依次类推，直到sz的位置文章来源：https://www.toymoban.com/news/detail-454848.html
//指定删除
void SeqListEease(SeqList* ps, int pos)
{
assert(ps);
int end = pos;
while (end < ps->sz)
{
ps->a[end] = ps->a[end + 1];
end++;
}
ps->sz--;
}
查找
遍历整个顺序表，如果有相同的值，则返回下标，没有返回-1文章来源地址https://www.toymoban.com/news/detail-454848.html
//查
int SeqListFind(SeqList* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->sz; i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
总代码
SeqList.c
#include "SeqList.h"
//初始化
void SeqListInit(SeqList* ps)
{
assert(ps);
ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
if (ps->a == NULL)
{
perror("SeqListInit");
return;
}
ps->sz = 0;
ps->capacity = INIT_CAPACITY;
}
//销毁
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->sz = ps->capacity = 0;
}
//打印
void SeqListPrint(SeqList* ps)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->sz; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//检查容量
void SeqListCheakcapacity(SeqList* ps)
{
assert(ps);
if (ps->sz == ps->capacity)
{
//扩容
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("SeqListPushback");
return;
}
ps->a = tmp;
ps->capacity = ps->capacity * 2;
}
}
//尾插
void SeqListPushback(SeqList* ps, SLDataType x)
{
assert(ps);
SeqListCheakcapacity(ps);
ps->a[ps->sz] = x;
ps->sz++;
}
//尾删
void SeqListPopback(SeqList* ps)
{
assert(ps);
assert(ps->sz > 0);
//if (ps->sz == ps->capacity)
// return;
ps->sz--;
}
//头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
assert(ps);
SeqListCheakcapacity(ps);
int end = ps->sz - 1;
while (end >= 0)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->sz++;
}
//头删
void SeqListPopFront(SeqList* ps)
{
assert(ps);
assert(ps->sz > 0);
int i = 0;
for (i = 0; i < ps->sz; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->sz--;
}
//指定插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
SeqListCheakcapacity(ps);
assert(ps);
assert(pos >= 0 && pos <= ps->sz);
int end = ps->sz - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->sz++;
}
//指定删除
void SeqListEease(SeqList* ps, int pos)
{
assert(ps);
int end = pos;
while (end < ps->sz)
{
ps->a[end] = ps->a[end + 1];
end++;
}
ps->sz--;
}
//查
int SeqListFind(SeqList* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->sz; i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
SeqList.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define INIT_CAPACITY 4
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int sz;
int capacity;
}SeqList;
//初始化
void SeqListInit(SeqList* ps);
//销毁
void SeqListDestroy(SeqList* ps);
//打印
void SeqListPrint(SeqList* ps);
//检查容量
void SeqListCheakcapacity(SeqList* ps);
//增删查改
void SeqListPushback(SeqList* ps, SLDataType x);
void SeqListPopback(SeqList* ps);
void SeqListPushFront(SeqList* ps, SLDataType x);
void SeqListPopFront(SeqList* ps);
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
void SeqListEease(SeqList* ps, int pos);
int SeqListFind(SeqList* ps, SLDataType x);
Test.c
void Test2()
{
SeqList ps;
SeqListInit(&ps);
SeqListInsert(&ps, 0, 1);
SeqListInsert(&ps, 1, 2);
SeqListInsert(&ps, 2, 3);
SeqListInsert(&ps, 3, 4);
SeqListInsert(&ps, 4, 5);
SeqListPrint(&ps);
int ret = SeqListFind(&ps, 3);
printf("%d\n", ret);
SeqListPrint(&ps);
SeqListEease(&ps, 0);
SeqListPrint(&ps);
SeqListDestroy(&ps);
}
int main()
{
Test2();
return 0;
}
到了这里，关于【数据结构＜顺序表＞】C语言的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
