【数据结构】P4线性表-顺序表简介

线性表-顺序表

• 顺序表的大纲
• 顺序表的定义
• 顺序表的实现
• • 静态分配
  • 动态分配

顺序表的大纲

顺序表的定义

顺序表存储结构 最重要的在于逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。

例子
比如逻辑中第一个元素a₁在内存中的存放位置是location，那么第二个元素a₂在内存中的存放位置是location+sizeof(a)，以此类推，a₃在内存中的存放位置就是location+sizeof(a)*2。

---

顺序表的实现 静态分配

静态数组的长度和大小一旦确定不可改变。

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int length;
}SqList;

内存会开辟一个连续的，可以存放10个(MaxSize的值)ElemType类型的空间。

范例

# include 
# 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;       //声明一个顺序表
    InitList(L);    //初始化顺序表
    for(int i=0; i<L.length; i++)
        printf("data[%d]=%d\n",i,L.data[i]);
    return 0;
}

静态分配遇到的主要问题：如果MaxSize满了怎么办？
静态数组的局限性在于其内存分配的存储空间大小的静态的，大小不可调整。
而动态分配可以调整大小，其大小可变。

---

动态分配

动态分配数组长度可调。

#define InitSize 10
typedef struct{
	ElemType *data;		//指示动态分配数组的指针
	int MaxSize;		//顺序表的最大容量
	int length;			//顺序表的当前长度
}SeqList;

malloc 与 free
malloc 与 free 的作用分别是动态的申请以及释放内存空间。

#include 
#define InitSize 10
typedef struct
{
    int *data;   //指示动态分配数组的指针
    int MaxSize; //顺序表的最大容量
    int length;  //顺序表的当前长度
} SeqList;

void InitList(SeqList L)
{
    L.data = (int *)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

void IncreaseSize(SeqList L, int 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;
    free(p);
}

int main()
{
    SeqList L;
    InitList(L);
    IncreaseSize(L,5);
    return 0;
}