说明：以下内容如有侵权，请联系删除
知识框架
线性表的定义和基本操作
线性表的定义
由此，我们得出线性表的特点如下:
表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。
线性表的基本操作
一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下:
InitList ( &L):初始化表。构造一个空的线性表。
Length(L):求表长。返回线性表L的长度，即工中数据元素的个数。
LocateElem(L,e):按值查找操作。在表工中查找具有给定关键字值的元素。
GetElem(L,i):按位查找操作。获取表工中第i个位置的元素的值。
ListInsert ( &工,i, e):插入操作。在表工中的第i个位置上插入指定元素e。
ListDelete(&L, i,&e):删除操作。删除表工中第i个位置的元素并用e返回删除元素的值。
PrintList(L):输出操作。按前后顺序输出线性表工的所有元素值。
Empty(L):判空操作。若工为空表，则返回true，否则返间faise。
DestroyList(&L):销毁操作。销毁线性表，并释放线性表X所占用的内存空间。
注意:①基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同。②“&”表示C++中的引用调用。若传入的变量是措针型变量，且在函数体内要对传入的指针进行改变，则会用到指针变量的引用型。在C中采用指针的指针也可达到同样的效果。
线性表的顺序表示
顺序表的定义
顺序表–用顺序存储的方式实现线性表
顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表的实现
顺序表的实现–静态分配
#include <stdio.h>
#define MAXSIZE 10
struct SqList{
//顺序表
int data[MAXSIZE];
//顺序表长度
int length;
};
typedef struct SqList SqList;
/*
初始化顺序表
*/
void initList(SqList *list){
int i=0;
//初始化顺序表的长度为5
(*list).length=5;
//向顺序表中插入5个元素
for(;i<5;i++){
(*list).data[i]=i+1;
}
}
/*
插入：向顺序表中指定位置插入元素
SqList *list：顺序表
int index：位置
int element：元素
返回一个int型变量：
1--插入成功
0--插入失败
*/
int insertList(SqList *list,int index,int element){
int tmp=(*list).length-1;
int i=index-1;
//如果插入位置大于顺序表长度，返回0
if(index>(*list).length){
return 0;
}
//判断顺序表的空间是否已满
if((*list).length>=sizeof((*list).data)/sizeof(int)){
return 0;
}
//插入元素
for(;tmp>=i;tmp--){
(*list).data[tmp+1]=(*list).data[tmp];
}
(*list).data[i]=element;
(*list).length=(*list).length+1;
return 1;
}
/*
删除：顺序表删除指定位置的元素
SqList *list：顺序表
int index：位置
int *element：被删除的元素
返回一个int型变量：
1--插入成功
0--插入失败
*/
int deleteList(SqList *list,int index,int *element){
int tmp=(*list).length-1;
int i=index-1;
//如果删除位置大于顺序表长度，返回0
if(index>(*list).length){
return 0;
}
//如果删除位置小于1，返回0
if(index<1){
return 0;
}
*element=(*list).data[index-1];
//删除元素
for(;i<=tmp;i++){
(*list).data[i]=(*list).data[i+1];
}
(*list).length=tmp;
return 1;
}
/*
按位查找：通过位置返回顺序表的的元素
SqList list：顺序表
int index：位置
返回一个int型变量：
index位置上的元素
*/
int getElementByIndex(SqList list,int index){
return list.data[index-1];
}
/*
按值查找：
SqList list：顺序表
int element：元素
返回一个int型变量：
index位置：返回-1 说明顺序表没有此元素
*/
int getIndexByElement(SqList list,int element){
int i=0;
int index=-1;
for(;i<list.length;i++){
if(list.data[i]==element){
index=i+1;
break;
}
}
return index;
}
int main(){
SqList list;
int i=0;
int j=0;
int element=0;
initList(&list);
insertList(&list,3,8);
deleteList(&list,3,&element);
for(;j<list.length;j++){
printf("%d",list.data[j]);
}
return 0;
}
顺序表的实现–动态分配
#include <stdio.h>
#include <stdlib.h>
//顺序表的初始化长度
#define initSize 10
struct SeqList{
int *data;
//数组的最大容量
int maxSize;
//顺序表的长度
int length;
};
typedef struct SeqList SeqList;
/*
初始化顺序表：
最大容量为10
长度为5
顺序表元素为1到5
*/
void initList(SeqList *list){
int i=0;
//设置最大容量
(*list).maxSize=initSize;
//设置顺序表长度为5
(*list).length=initSize-5;
//为顺序表动态分配内存
(*list).data=(int *)malloc(sizeof(int)*initSize);
for(;i<(*list).length;i++){
(*list).data[i]=i+1;
}
}
/*
顺序表动态扩容：
SeqList *list：顺序表
int len：扩容长度
*/
void increaseSize(SeqList *list,int len){
int i=0;
int *tmp=(*list).data;
//最大容量扩容
(*list).maxSize=(*list).maxSize+len;
//重新为线性表动态分配内存
(*list).data=(int *)malloc(sizeof(int)*(*list).maxSize);
//原来元素迁移
for(;i<(*list).length;i++){
(*list).data[i]=tmp[i];
}
free(tmp);
}
/*
插入：向顺序表中指定位置插入元素
SeqList *list：顺序表
int index：位置
int element：元素
返回一个int型变量：
1--插入成功
0--插入失败
*/
int insertList(SeqList *list,int index,int element){
int tmp=(*list).length-1;
int i=index-1;
//如果插入位置大于顺序表长度，返回0
if(index>(*list).length){
return 0;
}
//判断顺序表的空间是否已满
if((*list).length>=(*list).maxSize){
return 0;
}
//插入元素
for(;tmp>=i;tmp--){
(*list).data[tmp+1]=(*list).data[tmp];
}
(*list).data[i]=element;
(*list).length=(*list).length+1;
return 1;
}
/*
删除：顺序表删除指定位置的元素
SeqList *list：顺序表
int index：位置
int *element：被删除的元素
返回一个int型变量：
1--插入成功
0--插入失败
*/
int deleteList(SeqList *list,int index,int *element){
int tmp=(*list).length-1;
int i=index-1;
//如果删除位置大于顺序表长度，返回0
if(index>(*list).length){
return 0;
}
//如果删除位置小于1，返回0
if(index<1){
return 0;
}
*element=(*list).data[index-1];
//删除元素
for(;i<=tmp;i++){
(*list).data[i]=(*list).data[i+1];
}
(*list).length=tmp;
return 1;
}
/*
按位查找：通过位置返回顺序表的的元素
SeqList list：顺序表
int index：位置
返回一个int型变量：
index位置上的元素
*/
int getElementByIndex(SeqList list,int index){
return list.data[index-1];
}
/*
按值查找：
SeqList list：顺序表
int element：元素
返回一个int型变量：
index位置：返回-1 说明顺序表没有此元素
*/
int getIndexByElement(SeqList list,int element){
int i=0;
int index=-1;
for(;i<list.length;i++){
if(list.data[i]==element){
index=i+1;
break;
}
}
return index;
}
int main(){
SeqList list;
int i=0;
int j=0;
initList(&list);
insertList(&list,3,8);
deleteList(&list,3,&j);
for(;i<list.length;i++){
printf("%d",list.data[i]);
}
increaseSize(&list,5);
return 0;
}
线性表的链式表示
