线性表的顺序表示和实现，动态分配存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

在非空有限的条件下，存在唯一的一个表头结点，唯一的一个表尾结点，除去第一个元素之外，每个数据元素都只有一个前驱，除去最后一个元素之外，每一个数据元素都只有一个后继。

线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性（属于同一数据对象，类似数组）。线性表的数据元素间有序偶关系。

随机存取——知道顺序表起始位置LOC(A)和每个元素所占内存的大小sizeof(ElemType)后，可知道任意一个元素的位置。

假设线性表的每个元素需占用 L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第 i +1个数据元素的存储位置 LOC ( ai+1）和第 i 个数据元素的存储位置 LOC ( ai）之间满足下列关系：

LOC (ai+1)= LOC ( ai)+ L

一般来说，线性表的第 i 个数据元素 ai，的存储位置为

LOC ( ai)= LOC ( a1)+( i -1) *L

式中 LOC ( a1）是线性表的第一个数据元素 a 的存储位置，通常称做线性表的起始位置或基地址。

只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，线性表的顺序存储结构是一种随机存取的存储结构。

它的特点是，为表中相邻的元素 ai和 ai+1赋以相邻的存储位置 LOC (ai）和 LOC ( ai+1)。

每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。

由于高级程序设计语言中的数组类型也有随机存取的特性，通常都用数组来描述数据结构中的顺序存储结构。

//静态分配结构存储

#define MaxSize 10 //最大长度

typedef struct{

int data[MaxSize]; //静态数组存放数据元素

int length; //顺序表当前长度

}SqList; //顺序表类型定义

定义一个结构体，包含两个成员变量，分别用来存放数据元素和顺序表长度，并为该结构体起了一个别名SqList，可以直接用SqList定义一个结构体变量。

//静态分配初始化

void InitList(SqList &L){

L.Length=0;

}

由于线性表的长度可变，且所需最大存储空间随问题不同而不同，需要动态分配存储空间。

//动态分配结构存储

#define InitSize 100 //表长度的初始定义

typedef struct{

ElemType *data; //指示动态分配数组的指针

int MaxSize; //最大容量

int length; //当前个数

}SeqList;

malloc函数

malloc动态内存分配函数，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址。

malloc函数的返回的是无类型指针，所以在使用时一定要强制转换为所需要的类型。

malloc函数头文件，free函数头文件，系统库函数，提前注明，

#include<malloc.h>

#include<stdlib.h>

//动态分配初始化

void InitList(SeqList &L){ L.data=(ElemType*)malloc(MaxSize*sizeof(ElemType));

L.length=0;

L.MaxSize=InitSize;

}

//使用malloc函数申请sizeof(SqList)大小的存储空间，并用指针L指向这片空间，将顺序表的长度初始化为0。

销毁顺序线性表

void DestroyList(SqList *&L)

{free(L);//释放储存空间

}

顺序线性表插入元素

bool ListInsert(SqList *&L,int i,ElemType e)

{ int j;

if (i<1 || i>L->length+1)//判断插入位置正确性

return false;

i--; //将顺序表位序减1转化为elem下标

for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置

L->data[j]=L->data[j-1];

L->data[i]=e;//当j=i时

L->length++; //顺序表长度增1

return true;

}

挑战自己