数据结构——线性表（一）

        我们在学习C语言的时候都用过数组，再学深一点大概会学到结构体，链表之类的。正常情况下，对于这一类的数据结构，我们都能看到他们的共同点。每一个数据项之间都只跟另一个数据项链接，所以我们把这一类的数据结构叫做线性表。不考虑实际内存地址的分配，从逻辑意义上看，我们可以把数据项都连起来，形成一个像表一样的东西。

        那么首先就让我们来看看线性表的第一种形式吧———顺序存储结构。

        其实顺序存储结构说白了就是我们曾经接触的C语言中的数组。但是数组的长度是不可变的，可是我们线性表的长度可变，且所需要的存储空间也是随着需要而改变，所以我们在这里用动态分配的方式给线性表分配空间。下面则是线性表的顺序存储结构。

#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define LIST_INIT_SIZE 100    //线性表存储空间的初始分配量
#define LISTINCREMENT 10    //线性表存储空间的分配增量
#define ElemType int
typedef struct
{
    int *elem;    //存储空间基址
    int length;    //当前长度
    int listsize;    //当前分配的存储容量
} SqList;
           

        在上述定义中，指针elem存储的是线性表的基地址，length是线性表目前的实际长度。listsize则是初始化时，我们为线性表分配的初始空间大小。

        知道了线性表的存储结构之后，我们就得开始新建一个线性表了啊，也就是线性表的初始化。所谓的线性表的初始化就是我们为要建的线性表分配一个连续的已预订好大小的存储空间，同时将线性表的当前长度设为0，用listsize表示线性表的存储容量，一旦因为插入新的元素而导致空间不足时，可以用realloc函数进行再分配，为线性表增加一个大小为LISTINCREMENT的空间。

int InitList_Sq(SqList &L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem) return ERROR;    //存储分配失败
    L.length=0;    //空线性表长度为0
    L.listsize=LIST_INIT_SIZE;    //这是初始的存储容量
    return OK;

}
           

        现在我们就建好了一个线性表啊！有了一个空线性表之后，我们就该实现线性表的各种功能了——首先是最基本的插入和删除。

        对于插入功能，我们有两种思路。第一种就是直接插入到线性表已存储的数据后面，另一种就是我们提供一个i值，然后插入到线性表第i个位置。

        第一种思路的实现

int ListInsert_Sq(SqList &L,int e)
{
    int *newbase,*q,*p;
    if(L.length>=L.listsize)    //当前存储空间已满，要增加分配
    {
        newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
                if(!newbase)exit(ERROR);    //存储失败
        L.elem=newbase;    //新的线性表基址
        L.listsize=L.listsize+LISTINCREMENT;    //增加存储容量
    }
    p=&(L.elem[L.length]);    //p为插入数据的位置
    *q=e;    //插入数据e
    L.length++;    //实际顺序表的长度+1
    return OK;
}
           

         第二种思路的实现

int ListInsert_Sq(SqList &L,int i,int e)
{
    int *newbase,*q,*p;
    if(i<1||i>L.length+1) return ERROR;    //i值不合法
    if(L.length>=L.listsize)      //当前存储空间已满，要增加分配

    {
        newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
                if(!newbase)exit(ERROR);    //存储失败

        L.elem=newbase;    //新的线性表基址
        L.listsize=L.listsize+LISTINCREMENT;    //增加存储容量
    }
    q=&(L.elem[i-1]);    //q为插入位置
    p=&(L.elem[L.length-1]);    //表尾
    for(; q<=p; p--)    //插入位置和之后的所有元素后移
    {
        *(p+1)=*(p);
    }
    *q=e;    //插入e
    L.length++;    //实际顺序表的长度+1
    return OK;
}
           

        现在我们就来实现线性表的删除吧

int SqList_Delete(SqList &L,int i,int &e)
{
    int *q,*p;
    if((i<1)||(i>L.length)) return ERROR;    //i值不合法
    p=&(L.elem[i-1]);    //p为被删除的元素的位置
    e=*p;    //被删除的元素赋值给e
    q=L.elem+L.length-1;    //表尾的地址
    for(++p;p<=q;++p)    //被删除之后的元素向前移
    {
        *(p-1)=*p;
    }
    --L.length;    //实际顺序表的长度-1
    return OK;
}
           

        那再让我们看看线性表顺序存储结构的其他操作吧

        一、查看空表

ListEmpty(SqList L)
{
        if(L.length==0) return TRUE;
        else return FALSE;
}
           

        二、查看线性表中第i个位置的值

GetElem(SqList L,int i,ElemType &e)
{
	if(i<1||i>L.length) return ERROR;    //i值不合法
	e=L.elem[i];
	return OK;
}
           

        三、返回cur_e的前驱元素

PriorElem(SqList L,int cur_e,Elemtype &pre_e)
{
	int *p,*q;
	if(cur_e==L.elem[1]) return ERROR;    //cur_e不能是线性表第一个数据元素
	p=L.elem;    //线性表基地址
	q=L.elem+L.length-1;    //线性表表尾地址
	for(;p<=q;p++)    //遍历查找跟cur_e相等的元素
	{
		if(cur_e==*p) break;
	}
	if(p<=q) pre_e=*(--p);    //如果找到则将cur_e的前驱赋值给pre_e，否则返回ERROR
        else return ERROR;
	return OK;
}
           

四、返回cur_e的后驱元素

NextElem(SqList L.int cur_e ElemType &next_e)
{
	int *p,*q;
	p=L.elem;    //线性表基地址
	q=L.elem+L.length+1;    //线性表表尾地址
	for(;p<=q;p++)    //遍历查找跟cur_e相等的元素
	{
		if(cur_e==*p) break;
	}
	if(p<q) next_e=*(--p);    //如果找到则将cur_e的前驱赋值给pre_e，否则返回ERROR。注意cur_e不能是表尾元素
	else return ERROR;
	return OK;
}
           

我们知道，线性表的顺序存储结构的特点是在逻辑关系上相邻的两个元素在物理地址上也相邻。因此，我们可以用一个简单的式子就能得到任意元素的存储位置。然而，从另一方面来看，这种严格的相邻性也造成了这种存储结构的缺点：当你要进行数据的插入或者删除时，需要移动大量的元素。于是，我们便有了接下来的另一种线性表的存储结构——链式存储结构。它不要求逻辑关系上相邻的两元素在物理地址上也相邻，因此就避免了顺序存储结构的缺点。