2.1 线性表的定义和基本操作

线性表是具有相同类型的n（n>=0）个元素的有限序列，其中n为表长，当n=0时，该表为空表。

若L命名为线性表，则一般表示为L = （a1，a2，...，ai，ai+1，...，an）

2.1.1线性表的九种基本操作：

InitList(&L):初始化表，构造一个空的线性表

DestroyList(&L):销毁操作。销毁线性表并释放所占用的内存空间。

LocateElem(L,e):按值查找。

GetElem(L,i):按位查找。

ListInsert(&L,i,e):插入操作，默认线性表中的插入操作为前插。

ListDelete(&L,i,&e):删除操作，删除第i个元素并用e返回删除元素的值。

PrintList(L):输出操作。按前后顺序输出L中所有元素的值。

Empty(L):判空操作。

Length(L):求表长。

2.1.2 顺序表

线性表的顺序存储。

在连续地址上存放连续的线性表中的元素。使逻辑相邻的元素在物理存储地址上也相邻。

顺序表插入操作

bool ListInsert(Sqlist &L, int i, ElemType e){

? if(i<1||i>L.length+1)

? return false;

? if(L.length>=MaxSize)

? return false;

? for(int j=L.length; j>=i; j--)

? L.data[j]=L.data[j-1];

? L.data[i-1]=e;

? L.length++;

? return true;

}

顺序表删除操作

bool ListDelete(SqList &L, int i, ElemType &e){

? if (i<1||i>L.length)

? return false;

? e = L.data[i-1];

? for (int j = i; j < L.length; j++)

? L.data[j-1] = L.data[j];

? L.length--;

? return true;

}

顺序表按值查找操作

int LocateElem(Sqlist L, ElemType e){

? int i;

? for(i=0; i<L.length; i++)

? if (L.data[i]==e)

? return i+1;

? return 0;

}

2.1.3 单链表

typedef struct Lnode{

? ElemType data;

? struct LNode *next;

}LNode, *LinkList;

2.2 顺序表和链表的差异性

顺序存储无论静态分配还是非静态都需要预先分配合适的内存空间

链式存储在需要时分配结点空间即可，高效方便，但指针要使用额外空间。

线性表的定义和基本操作

原文：https://www.cnblogs.com/sansispace/p/13444862.html