线性表顺序结构
在此只是想重修一下数据结构，一是因为自已在校时没能学好，二是因为这对自已的提高可能会有一些帮助，我看的是在学校时发的一本C语言版本的《数据结构》，清华大学出版社出版。所有定义多出于此。所有算法改成C++。学了一年多的VC，还从来没有自己动手定过一个像样的类，在这里只是想练习一下，见笑了。
线性表的定义：
简而言之，一个线性表是n个数据元素的有限序列，在数据的非空有限集中，它具有以下特征：(1)存在一个唯一的被称做“第一个”的数据元素；(2)存在唯一的一个被称做“最后一个”的数据元素。(3)除第一个之外，集合中的每个数据元素均只有一个前驱。(4)除最后一个之外，集合中每个数据元素均只有一个后继。也就是说线性表体现的是数据元素之间的唯一性、连续性。如26个英文字母表{A,B,C,D...,X,Y,Z}。
抽象数据类型线性表的定义如下：
ADT List{
数据对象：D={ai|ai∈ElemSet,i=1,2,3.,n,n≥0}
数据关系：R1={<a(i-1),a(i-1),ai∈D,i=1,2,3...,n}
InitList()
操作结果：构结一个空的线性表。
DestroyList()
初始条件：线性表已存在(已初始化)
操作结果：销毁线性表
ClearList()
初始条件：线性表已存在(已初始化)
操作结果：将线性表重置为空表
ListEmpty()
初始条件：线性表已存在(已初始化)
操作结果：若线性表为空表则返回TRUE，否则返回FALSE
ListLength()
初始条件：线性表已存在(已初始化)
操作结果：返回线性表中元素个数
GetElem(i,&e)
初始条件：线性表已存在(已初始化)
操作结果：用e返回第i个数据元素的值。
LocateElem(e,compare())
初始条件：线性表已存在(已初始化), compare是数据判定函数
操作结果：返回系i个与e满足关系compare()元素
PriorElem(cur_e,&pre_e)
初始条件：线性表已存在(已初始化)
操作结果：若cur_e是线性表中的数据元素,且不是第一个,用pre_e来返回cur_e的前驱;否则操作失败。
NextElem(cur_e,&next_e)
初始条件：线性表已存在(已初始化)
操作结果：若cur_e是线性表中的数据元素,且不是最后一个元素，则用next_e返回它的的后继，否则操
作失败，next_e无定义。
ListInsert(i,e)
初始条件：线性表已存在,1<=i<=ListLength+1
操作结果：在第i个位置之前插入新的元素e,线性表长度加1
ListDelete(i,&e)
初始条件：线性表已存在且非空，1<=i<=ListLength
操作结果：删除线性表的第i个数据元素，并用e返回其值，线性表长度减一
ListTraverse(visit())
初始条件：线性表已存在(已初始化)
操作结果：依次对线性表的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT List;
线性表的顺序表示：
线性表的线性表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。它的特点是，为表中相邻的元素ai和a(i+1)赋以相邻的位置Loc(ai)和Loc(a(i+1))。换句话说，以元素在计算机内“物理位置的相邻”来表示线性表中数据元素之间的逻辑关系。
线性表定义如下：
#define LIST_INIT_SIZE 30
#define LISTINCREMENT 5
class SqList
{
private:
int Length=0;
int ListSize=0;
public:
ElemType * elem;
GetSize();
SqList();
{ elem=NULL}
~SqList()
{
if (elem!=NULL)
free(elem);
}
status InitList();
void DestroyList(); void ClearList();
status ListEmpty(); int ListLength();
status GetElem(int i,ElemType &e);
int LocateElem(ElemType e);//在此简化处理，用来返回e的位序
status PriorElem(ElemType cur_e,ElemType &pre_e);
status NextElem(ElemType cur_e,ElemType &next_e);
status ListInsert(int i,ElemType e);
status ListDelete(int i,ElemType &e);
status ListTraverse();//对ListTraverse(visit())的简化，用来显示线性表中的元素
}
在上述定义中，指针elem指向线性表的基地址；Length用来指示线性表的长度；ListLenth()用来获得线性表的长度。ListSize用来存放顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可进行再分配。即为顺序表增加一个大小为LISTINCREAMENT个数据元素的空间，ListSize初始化值为0，GetSize返回线性表当前的空间大小。线性表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表当前长度置为0，当然这些操作也可以放在线性表的构造函数中。
status SqList::InitList()
{
if(elem!=NULL) return ERROR;
elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!elem)return OVERFLOW;
ListSize=LIST_INIT_SIZE;
Length=0;
return OK;
}
线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。就是要使长度为n的线性表（a1,a2.....a(i-1),ai,...,an）变为长度为n+1的线性表（a1,...,a(i-1),b,ai...,an）。
数据元素a(i-1)和ai之间的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑相邻的数据元素在物理位置上也是相邻的，因此除非i=n+1,否则必须移动元素才能反映这个逻辑关系的变化。
一般情况下，在第i(1<=i<=n)个元素之前插入一个元素时，需将第n至第i(共n-i+1)个元素向后移动一个位置，算法如下：
status SqList::ListInsert(int i,ElemType e)
{
//在顺序线性表第i个位置插入新的元素e,i的合法值为1<=i<=Length+1
if(i<1||i>Length+1) return ERROR;
if(Length>=ListSize)
{//当前存储空间已满，增加空间
ElemType* newbase=(ElemType*) realloc(elem,(ListSize+INCREMENT)*sizeof(ElemType));
if(!newbase) return OVERFLOW;
elem=newbase;
ListSize+=LISTINCREMENT;
}
ElemType *q=&(elem[i-1]);
for(ElemType *p=&(elem[Length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
++Length;
return OK;
}
返之，线性表的删除操作是使长度为n的线性表（a1,...a(i-1),ai,a(i+1),...,an）,变为长度为n-1的线性表（a1,..,a(i-1), a(i+1),...an），数据元素a(i-1),ai,a(i+1)之间的逻辑关系发生了变化，为了在存储结构的反映这一变化，同样需要移动元素。一般情况下，删除第i(1<=i<=n)个元素时需将从第i+1至第n(共n-i)个数据元素依次向前移动一个位置，算法如下：
status SqList::ListDelete(int i,ElemType &e)
{//在顺序线性表中删除第i个元素，并用e返回其值，i的合法值为1<=i<=Length
if(i<1||i>Length) return ERROR;//i值不合法
ElemType * p=&(elem[i-1];//p为被删除元素的位置
ElemType *q=elem+Length-1;//q为表尾元素的位置
for(++p;p<=q;++p) *(p-1)=*p;//被删除元素之后的元素左移
--Length;
return OK;
数据结构之线性表的链式存储
顺序表的存贮特点是利用物理上的相邻关系表达出逻辑上的前驱和后继关系，它要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表进行插入和删除时需要通过移动数据元素来实现线性表的逻辑上的相邻关系，从而影响其运行效率。本节介绍线性表的另一种存储形式——链式存储结构，它不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的次序关系，因此它不要求逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无需移动元素，从而提高其运行效率。链式存储结构主要有：单链表、循环链表、双向链表、静态链表等几种形式。
单链表
链表是通过一组任意的存储单元(可以连续也可不连续)来存储线性表中的数据元素。根据线性表的逻辑定义，单链表的存储单元不仅能够存储元素，而且要求能表达元素与元素之间的线性关系。对数据元素ei而言，除存放数据元素自身的信息ei之外，还需要存放后继元素ei+1所在存贮单元的地址，这两部分信息组成一个“结点”，每个结点包括两个域：数据域——存放数据元素本身的信息;指针域——存放其后继结点的地址，结点的结构如图2-5 所示。因此n个元素的线性表通过每个结点的指针域构成了一个“链条”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。为了访问单链表，我们只要知道第一个结点地址就能访问第一个元素，通过第一个元素的指针域得到第二个结点的地址，……，以此类推可以访问所有元素。这样称第一个元素的地址为“头指针”。
例如，假设有线性表(A,B,C,D,E,F,G,H)对应的链式存储结构如图1所示。头指针为1000H，最后一个结点没有后继, 其指针域必需置空(以NULL表示)，表明此表到此结束，这样就可以从第一个结点的地址开始“顺藤摸瓜”，找到每个结点。
作为线性表的一种存储结构，我们关心的是结点间的逻辑结构(线性关系)，而对每个结点的实际地址并不关心，所以通常的单链表用图2的形式表示。
链表的每个元素构成一个结点，结点定义如下：
Typedef struct node{
DataType data; /*每个元素数据信息*/
struct node *next; /*存放后继元素的地址*/
} LNode，*LinkList;
定义头指针变量：
LinkList H;
上面定义的LNode是结点的类型，LinkList是指向LNode类型结点的指针类型。 H为头指针变量，指向单链表的第一个结点,如图4(b)所示，当单链表为空时H= NULL,如图4(a)所示。
为了方便操作单链表，一般在单链表的第一个结点之前加一个称为“头结点”的附加结点，如图4(c)所示。“头结点”的设置会给单链表操作带来方便，当然，用户也可以在附加结点的数据域中存放一些与整个单链表相关的信息(如单链表长度等)，指针域中存放的是第一个数据结点的地址，空表时指针域为空(NULL)。注意：在这种情况下，以H->next等于 NULL表示单链表为空，如图4(d)所示。
声明：在以后的算法中，若不作特别说明，链表是指采用带头结点的链表形式。在链表的示意图中，通常规定用符号“∧”表示NULL。