前言
本文章主要讨论的是什么是线性表，线性表的种类，以及动态线性表和静态线性表的区别，还有用线性表如何实现数据的增删查改
一、线性表是什么？？
1.线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：链表、顺序表、栈、队列、字符串 线性表在逻辑上是线性结构，也就是说是连续的一条直线，但在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链表结构的形式存储。 最简单的一种线性表就是数组。
2.顺序表
概念及结构 顺序表是用一段物理地址连续的储存单元 依次储存数据的元素的线性结构，一般情况下采用 数组存储。在数组上完成数据的增删查改。 顺序表一般分为： 静态顺序表：使用定长数组存储（静态时偏多的） 动态顺序表：使用动态开辟的数组存储。 静态顺序表的定义方式：
代码语言：javascript复制#define N 10
struct A
{
int a[N];
int size;
};顺序表的目的：把数据存储起来
顺序表特点： 1.连续的物理空间存储–数组 2.数据必须是从头开始，依次存储 静态顺序表问题： 给少了不够用，给多了用不完浪费，不能灵活控制
3.动态顺序表
代码语言：javascript复制typedef int IT;
typedef struct A
{
IT* a;
int size;//
int capacity;
}SA;二、如何使用动态顺序表
1.动态顺序表的初始化
代码语言：javascript复制void AInit(SA* s)
{
s->a = NULL;
s->capacity = 0;
s->size = 0;
}2.动态顺序表的扩容
代码语言：javascript复制void Acapacitycheck(SA* s)
{
if (s->size == s->capacity)
{
int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
IT* tmp = (IT*)realloc(s->a, newcapacity*sizeof(IT));
if (tmp == NULL)
{
printf("realloc file");
exit(-1);
}
else
{
s->a = tmp;
s->capacity = newcapacity;
}
}
}三、动态顺序表实现增删查改
1.首插和尾插
代码语言：javascript复制void Apushback(SA* s, IT x)
{
Acapacitycheck(s);
s->a[s->size] = x;
s->size ;
}
//首插
void Apushfront(SA* s, IT x)
{
Acapacitycheck(s);
int end = s->size - 1;
while (end >= 0)
{
s->a[end 1] = s->a[end];
end--;
}
s->a[0] = x;
s->size ;
}2.首删和尾删
代码语言：javascript复制void Apopback(SA* s)
{
assert(s->size > 0);
//s->a[s->size - 1] = 0;
s->size--;
}
void Apopfront(SA* s)
{
int start = 1;
assert(s->size > 0);
while (start < s->size)
{
s->a[start - 1] = s->a[start];
start ;
}
s->size--;
}3.任意位置删除和任意位置插入
代码语言：javascript复制//数据的插入
void Ainsert(SA* s, int pos, IT x)
{
assert(pos < s->size);
Acapacitycheck(s);
int end = s->size - 1;
while (end >=pos)
{
s->a[end 1] = s->a[end];
end--;
}
s->a[pos] = x;
s->size ;
}
//数据的删除
void Aerase(SA* s, int pos)
{
assert(pos < s->size && s->size>0);
int start = pos 1;
while (start < s->size)
{
s->a[start-1] = s->a[start];
start ;
}
s->size--;
}4.空间的销毁以及查数据和改数据
代码语言：javascript复制//销毁空间
void Adestroy(SA* s)
{
free(s->a);
s->a = NULL;
s->capacity = 0;
s->size = 0;
}
//查数据
int Afind(SA* s, IT x)
{
for (int i = 0;i < s->size;i )
{
if (s->a[i] == x)
{
return i;
}
}
return -1;
}
//改数据
void Amodity(SA* s, int pos, IT x)
{
assert(pos < s->size);
s->a[pos] = x;
}四、将其封装在一个菜单中
1. A.h文件
代码语言：javascript复制#pragma once//防止头文件被重复包含
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int IT;
typedef struct A
{
IT* a;
int size;//
int capacity;
}SA;
void AInit(SA* s);
void Aprintf(SA* s);
void Apushback(SA* s, IT x);
void Apushfront(SA* s, IT x);
void Apopback(SA* s);
void Apopfront(SA* s);
void Ainsert(SA* s, int pos, IT x);
void Aerase(SA* s, int pos);
void Adestroy(SA* s);
//查改
int Afind(SA* s, IT x);
void Amodity(SA* s, int pos, IT x);2. A.c文件
代码语言：javascript复制#include "A.h"
void AInit(SA* s)
{
s->a = NULL;
s->capacity = 0;
s->size = 0;
}
//初始化
void Aprintf(SA* s)
{
for (int i = 0;i < s->size;i )
{
printf("%d ", s->a[i]);
}
}
//扩容
void Acapacitycheck(SA* s)
{
if (s->size == s->capacity)
{
int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
IT* tmp = (IT*)realloc(s->a, newcapacity*sizeof(IT));
if (tmp == NULL)
{
printf("realloc file");
exit(-1);
}
else
{
s->a = tmp;
s->capacity = newcapacity;
}
}
}
//尾插
void Apushback(SA* s, IT x)
{
Acapacitycheck(s);
s->a[s->size] = x;
s->size ;
}
//首插
void Apushfront(SA* s, IT x)
{
Acapacitycheck(s);
int end = s->size - 1;
while (end >= 0)
{
s->a[end 1] = s->a[end];
end--;
}
s->a[0] = x;
s->size ;
}
//尾删
void Apopback(SA* s)
{
assert(s->size > 0);
//s->a[s->size - 1] = 0;
s->size--;
}
void Apopfront(SA* s)
{
int start = 1;
assert(s->size > 0);
while (start < s->size)
{
s->a[start - 1] = s->a[start];
start ;
}
s->size--;
}
void Ainsert(SA* s, int pos, IT x)
{
assert(pos < s->size);
Acapacitycheck(s);
int end = s->size - 1;
while (end >=pos)
{
s->a[end 1] = s->a[end];
end--;
}
s->a[pos] = x;
s->size ;
}
void Aerase(SA* s, int pos)
{
assert(pos < s->size && s->size>0);
int start = pos 1;
while (start < s->size)
{
s->a[start-1] = s->a[start];
start ;
}
s->size--;
}
//将空间销毁掉
void Adestroy(SA* s)
{
free(s->a);
s->a = NULL;
s->capacity = 0;
s->size = 0;
}
int Afind(SA* s, IT x)
{
for (int i = 0;i < s->size;i )
{
if (s->a[i] == x)
{
return i;
}
}
return -1;
}
void Amodity(SA* s, int pos, IT x)
{
assert(pos < s->size);
s->a[pos] = x;
}3. test.c文件
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include "A.h"
void menu()
{
printf("****************************************n");
printf("1.尾插数据 2.头插数据 n");
printf("3.尾删数据 4.头删数据 n");
printf("5.打印数据 0.退出 n");
printf("****************************************n");
printf("请输入操作数:");
}
int main()
{
int option = 0;
SA s;
AInit(&s);
int x = 0;
do
{
menu();
scanf("%d", &option);
switch (option)
{
case 1:
printf("请输入你要插入的数据，以-1结束n");
do
{
scanf("%d", &x);
if (x != -1)
{
Apushback(&s, x);
}
} while (x != -1);
break;
case 2:
printf("请输入你要插入的数据，以-1结束n");
do
{
scanf("%d", &x);
if (x != -1)
{
Apushfront(&s, x);
}
} while (x != -1);
break;
case 3:
printf("请确定尾删几次:");
scanf("%d", &x);
for (int i = 0;i < x;i )
{
Apopback(&s);
}
break;
case 4:
printf("请确定头删删几次:");
scanf("%d", &x);
for (int i = 0;i < x;i )
{
Apopfront(&s);
}
break;
case 5:
Aprintf(&s);
printf("n");
break;
case 0:
printf("退出程序n");
break;
default:
printf("请重新输入");
break;
}
} while (option!=-1);
return 0;
}五、总结
顺序表不是很难，勤加练习还是很容易掌握的
