目录
2.1优点:我们可以根据实际情况,对内存进行自由分配,从而不造成内存分配浪费!
1.线性表
线性表
（
linear list
）
是
n
个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。
2.顺序存储结构(顺序表)
顺序存储结构(顺序表)的定义:线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素
2.1顺序表一般可以分为：
?1. 静态顺序表：使用定长数组存储元素
? 1.1静态顺序表:顺序表的大小是确定的,容量是固定的.
? ? ? ? ? ? ? ? ? ? ? ?
代码如下:
?
?
#define N 10000//运用宏定义,可以方便修改容量的大小
typedef int SLDataType;//运用宏定义,可以根据情况改变存储类型
// 静态顺序表
typedef struct SeqList
{
SLDataType a[N];
int size; // 表示数组中存储了多少个数据
}SL;? ? ? ?结论:静态顺序表不是很常量,了解就行.
2. 动态顺序表：使用动态开辟的数组存储。(重要)
2.1优点:我们可以根据实际情况,对内存进行自由分配,从而不造成内存分配浪费!
2.2顺序表的定义
typedef int sldatatype;//根据实际情况,可以改变存储的类型
typedef struct {
sldatatype* a;//开辟数组a
int size;//多少个数据
int capacity;//容量是多大
}sl;?2.3顺序表的初始化
//顺序表初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;//赋值0
}
//指针设为空指针,ps指向的容量和数据都赋值0
?2.4顺序表增容:
? ? ? ? ? ? ? ? ? ? ? ? 请记住:两种情况都要扩容:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 内存还未开辟
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 内存满了开辟
? ? ? ? ? ? ? ? ? ? ? ?代码如下?
void SeqListCheckCapacity(SL* ps)//顺序表扩容
{
// 如果没有空间或者空间不足，那么我们就扩容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);//扩容都要这种判断是否成功
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}?
2.5顺序表的删除
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);//防止越界
int begin = pos + 1;//遍历从0开始,要加1//取出要删掉的数字
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];//删掉的元素的位置后面每个元素都要往前挪.
++begin;
}
ps->size--;
}
? ? ? ? ? 思路? :
? ? ? ? ? ? ? ? ? ? ? ? 1.取出要删掉的数字;
? ? ? ? ? ? ? ? ? ? ? ? 2.删掉的元素的位置后面每个元素都要往前挪.
2.6顺序表的查找:? ?
//输入你要查找的数据，找到这个数据就返回数据的下标，找不到就返回-1.
int SeqListFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;//查找对应那个数据的下标
}
}
return -1;
}????????思路:
? ? ? ? ? ? ? ?1.查找你要找的数据
? ? ? ? ? ? ? ?2.找得到,就返回该数据的下标
? ? ? ? ? ? ? ?3.找不到就返回-1
2.7顺序表的打印
???????
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}2.8顺序表的释放
顺序表释放://扩容就要释放//但只能有一个
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;//释放都要这样
}
?2.9顺序表的插入
//顺序表插入
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
// 温柔的处理方式
/*if (pos > ps->size || pos < 0)
{
printf("pos invalid\n");
return;
}*///防止越界
// 粗暴的方式
assert(pos >= 0 && pos <= ps->size);
//两种方式都可以,但推荐粗暴的方式
SeqListCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];//增加位置,把前面的都推到后面去
--end;
}
ps->a[pos] = x;
ps->size++;
2.10顺序表的头插头删
顺序表头插
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);//扩容
//挪动数据
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
//SeqListInsert(ps, 0, x);其实用插入就足够了
}
顺序表头删
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
//挪动数据
int begin = 0;
while (begin < ps->size-1)
{
ps->a[begin] = ps->a[begin+1];
++ begin;
}
int begin = 1;
while (begin < ps->size)
{
ps->a[begin-1] = ps->a[begin];
++begin;
}
ps->size--;
//SeqListErase(ps, 0);用这个删除就足够了
}
2.11顺序表的尾插尾删
//顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
/*SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;*/
SeqListInsert(ps, ps->size, x);//用插入就可以代替
}
//顺序表尾删
void SeqListPopBack(SL* ps)
{
// 温柔处理方式
//if (ps->size > 0)
//{
// //ps->a[ps->size - 1] = 0;
// ps->size--;
//}
// 暴力处理方式
/*assert(ps->size > 0);
ps->size--;*/
SeqListErase(ps, ps->size-1);//用删除就可以删除
}
?