线性表（1）--基础知识

一、线性表的概念

线性表（Linear List）是一种线性数据结构，其特点是：在数据元素的非空有限集合中，存在唯一的一个被称做“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个之外，集合中的每一个数据元素均只有一个前驱；除最后一个之外，集合中每个数据元素均只有一个后继。

二、线性表的顺序存储

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素。以这种形式存储的线性表被称为顺序表。顺序表的逻辑顺序与物理顺序是一致的。

顺序表具有按数据元素的序号随机存取的特点。由于高级程序设计语言中的数组类型也有随机存取的特性，因此通常都是用数组来描述数据结构中的顺序存储结构。

#define LIST_INIT_SIZE 100
typedef struct{ElemType *elem;int length;
}SqList;

1.顺序表的初始化

即为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为0.

void InitList(SqList &L)
{L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(L.elem==NULL){printf("存储分配失败！\n");exit(1);}L.length=0;
} 

在表的第i(1<=i<=n)个元素之前插入一个值为e的新元素，插入后使原表长度加一。插入时须将第n至第i（共n-i+1）个元素后移一位。此时时间复杂度为O(n)。

int ListInsert(SqList &L,ElemType e,int i)
{if(i<0||i>L.length)return 0;//插入不成功else{for(j=L.length;j>i;j--){L.elem[j]=L.elem[j-1];}L.elem[i]=e;L.length++;return 1;//插入成功 } 
}

3.删除操作

将表中第i(1<=i<=n)个元素从线性表中删除，原表长度减一。删除时须将第i+1至第n(共n-i)个元素前移一位。此操作时间复杂度为O(n)。

int ListDelete(SqList &L,int i)
{if(i<0||i&