1.线性表存储/物理结构

1）顺序表（顺序存储结构）
定义: 顺序存储方式的线性表。
把逻辑上相邻的元素存储在物理上也相邻的存储单元中，元素间关系由存储的邻接关系体现。
基本操作的实现：
2）链表（链式存储）

2.顺序表的实现— —静态分配

• 静态数组的特点：大小长度一旦确定，不能改变。
• 声明 data 数组时，会在内存中开辟一整片连续的存储空间，空间大小为MaxSize*sizeof(int) 。对于本次来说，大小为10 * 4B

简单小代码：

#include <stdio.h>
#define MaxSize 10  //定义最大长度
typedef struct{
    int data[MaxSize];   //静态数组存放数据
    int length;          //顺序表的当前长度
}SqList;//顺序表的类型定义

//基本操作之初始化一个顺序表
void InitList(SqList &L)
{
    for(int i=0;i<MaxSize;i++)//将所有数据元素设置为默认初始值
        L.data[i]=0;
    L.length=0;
}

int main()
{
    SqList L;     //声明一个顺序表L
    InitList(L);//初始化顺序表L
    //...未完待续~
    return 0;
}

？？？默认初始值是否一定要添加

现在来把初始化代码去掉，看看会发生什么
运行结果：

— —哦，出错！为什么会出现什么这种现象呢？
— —这是因为内存中会有遗留的“脏数据”。在声明顺序表时，分配的连续内存空间并不知道之前存储的数据，所以不设置默认值会受之前存储数据的影响，出现一些奇怪的数字。

— —有人会说：啊，C语言不是会自动给 int 型变量设置初始值嘛？
— —这里要说，设置默认值是多少这是编译器做的事情，换一个编译器就可能不会帮你做初始化工作。

3.顺序表的实现— —动态分配

• 动态分配数组的大小、容量可变，由MaxSize表示顺序表动态分配的最大容量，由length记录当前顺序表的长度。
• malloc、free 包含着 #include<stdlib.h>
• 动态申请内存空间：malloc函数
  会申请连续的一整片的内存空间，malloc 函数返回一个指针，需强制转换成你所定义的数据元素类型指针
  L.data = (ElemType *) malloc(sizeof(ElemType) * InitSize)
  其中ElemType 我所定义的为 int , InitSize即顺序表的初始长度
• 动态释放内存空间：free函数

简单小代码：

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10
typedef struct{
    int *data;
    int MaxSize;
    int length;
}SeqList;

void InitList(SeqList &L){
   L.data=(int *)malloc(InitSize*sizeof(int));//存储空间大小：10*4B
   L.length=0;
   L.MaxSize = InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){//len表示数组拓展的个数
    int *p=L.data;
    L.data=(int *)malloc(L.MaxSize+len*sizeof(int));
    for(int i=0;i<L.length;i++)
        L.data[i]/=p[i];    //将数据复制到新区域
    L.MaxSize=L.MaxSize+len;    //顺序表最大长度增加len
    free(p);    //释放原来的内存空间
}

int main()
{
    SeqList L;     //声明一个顺序表L
    InitList(L);//初始化顺序表L
    //...往顺序表中插入几个元素
    IncreaseSize(L,5);
    return 0;
}

4. 顺序表的特点

1）随机访问，即可以在O(1)时间内找到第 i 个元素。
2）存储密度高，每个节点只存储数据元素
3）拓展不方便（即使采用动态分配方式实现，时间复杂度也比较高）
4) 插入、删除操做不方便，需要移动大量元素