学习笔记：顺序表和链表（一、顺序表）

首先来个导言：

1.数组的优势：下标的随机访问，物理空间连续。数组指针用[ ]或者 * , 结构体指针用 - >   

2.书写习惯 test.c写出主体框架 QelList.c写出结构体、头文件、函数声明  QelList.c写出函数的实现 

3.挪动：如果从前往后挪会覆盖数据，那么久从后往前挪

4.直接写控制台，容易出错，建议写成一个个test_SeqList_pushback（）这种类型的函数进行调试。在测试函数中进行创建、初始化、操作、销毁

5.增删查改的时候，要想后从start开始还是从end开始

正式内容：

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结

构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物

理上存储时，通常以数组和链式结构的形式存储

2. 顺序表

2.1 概念及结构

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

上完成数据的增删查改。

顺序表一般可以分为：

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

如：

typedef int SLDatetype

#define N 10

Struct Seqlist

{

    SLDatetype arr[N];   

    int size;    //存储有效数据的个数

};

//劣势：空间固定（小了不够用，多了浪费）

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

如：

typedef int SLDatetype

#define N 10

Struct Seqlist

{

    SLDatetype *  arr;   

    int size;    //存储有效数据的个数

    int capacity   //容量

};

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪

费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实

现动态顺序表。

typedef int SLDataType ;

// 顺序表的动态存储

typedef struct SeqList

{

SLDataType * array ; // 指向动态开辟的数组

size_t size ; // 有效数据个数

size_t capicity ; // 容量空间的大小

} SeqList ;

// 基本增删查改接口

// 顺序表初始化

void SeqListInit ( SeqList * psl , size_t capacity );

// 检查空间，如果满了，进行增容

void CheckCapacity ( SeqList * psl );

// 顺序表尾插

void SeqListPushBack ( SeqList * psl , SLDataType x );

// 顺序表尾删

void SeqListPopBack ( SeqList * psl );

// 顺序表头插

void SeqListPushFront ( SeqList * psl , SLDataType x );

// 顺序表头删

void SeqListPopFront ( SeqList * psl );

// 顺序表查找

int SeqListFind ( SeqList * psl , SLDataType x );

// 顺序表在 pos 位置插入 x  //Insert 插入

void SeqListInsert ( SeqList * psl , size_t pos , SLDataType x );

// 顺序表删除 pos 位置的值    //        Erase  //擦除

void SeqListErase ( SeqList * psl , size_t pos );

// 顺序表销毁

void SeqListDestroy ( SeqList * psl );            //destroy

// 顺序表打印

void SeqListPrint ( SeqList * psl );

modify    修改

find    查找

//只要插入数据，就要关注容量  //check --  移动 --  push/insert

当需要往后挪动数据的时候，想好是从最后一个开始后移还是从第一个开始后移