第一部分线性表的顺序存储(一)

时间：2010-11-20 来源：lhq_vip

一、线性表的概念： 1、线性表是一种最简单、最常用的数据结构，通常一个线性表是由n（n>=0）个性质相同的数据元素组成的有限序列，长度即为元素的个数n，当n=0时，称该表为空表。 2、非空的线性结构的特点：它具有惟一的第一个数据元素和最后一个数据元素；并且除了第一个元素以外，其他数据元素都只有一个前驱和一个后继。 3、线性表的主要存储结构：顺序存储结构和链式存储结构。（本篇主要总结顺序存储结构）二、线性表的顺序表示和实现顺序存储结构的存储可以用一维数组表示，具有固定长度。也可以用动态分配的存储结构，可以合理地利用空间。（一）一维数组表示数据结构：

typedef int datatype;
#define LIST_MAXSIZE 100
typedef struct
{
datatype data[LIST_MAXSIZE];
int length;
}Sqlist;

基本操作：

/*表的初始化*/
void InitList(Sqlist *L)
{
    L->length() = 0;
}
/*求表长*/
int ListLength(Sqlist *L)
{
    return L->length;
}
/*求表中的第i个节点*/
datatype GetElem(Sqlist *L,int i)
{
    if(i<1 || i>L->length)
        Error("position error");
    return L->data[i-1];
}
/*查找节点x在表中的第一个位置*/
int Search(int x,Sqlist *L)
{
    int i;
    for(i=0;i<L->length;i++)
        if(x == L->data[i])
            break;
    if(i == L->length)
        return 0;
    else
        retrun i+1;
}
/*在线性表中的第i个位置之前插入元新元素e*/
Status Insert_Sq(Sqlist *L,int i,datatype e)
{
    datatype * q, *p;
    if(i<1 || i>L->length)
        return ERROR;
    if(L->length > LIST_MAXSIZE-1)
        retrun ERROR;
    q = &(L->data[i-1])//插入的位置

    for(p=&(L->data[L->length-1]);p>=q;--p)
    {
        *(p+1) = *p;
    }
    *q = e;
    ++L->length;
    return OK;
}
/*第i个节点的删除*/
Status Delete_Sq(Sqlist *L,int i)
{
    datatype * p,*q;
    if(i<1 || i>L->length)
        return ERROR;
    p = &(L->data[i-1])//要删除节点的位置

    q = &(L->data[L->length-1])//表尾元素的位置

    for(;p<q;p++)
    {
        *p = *(p+1);
    }
    --L->length;
    return OK;
}

归并操作：

/*已知线性表La和Lb非递减排序，归并La和Lb得到Lc的数据元素也按非递减排序*/
Void MergeList(Sqlist *La,Sqlist *Lb,Sqlist *Lc)
{
    int La_len,Lb_len,i=j=1,k=0;
    datatype ai,bj;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i<=la_len)&&(i<=lb_len))
    {
        ai = GetElem(La,i);
        bj = GetElem(Lb,j);
        if(ai < bj)
        {
            k++;
            i++;
            ListInsert(Lc,ai);
        }
        else
        {
             k++;
             j++;
             ListInsert(Lb,bj);
        }
    }
    while(i<=La_len)
    {
         ai = GetElem(La,i);
         i++;
         k++;
         ListInsert(Lc,ai);
    }
    while(j<=Lb_len)
    {
         bj = GetElem(Lb,j);
         j++;
         k++;
         ListInsert(Lc,bj);
    }
    Lc->length = k;
}

以上算法在《数据结构（c语言版）》陈明编著清华大学出版 33页上分了三种情况，ai<bj,ai=bj,ai>bj.其实ai=bj这种情况没必要单独列出来，当然这样思路更清晰点，程序如下：

/*已知线性表La和Lb非递减排序，归并La和Lb得到Lc的数据元素也按非递减排序*/
Void MergeList(Sqlist *La,Sqlist *Lb,Sqlist *Lc)
{
    int La_len,Lb_len,i=j=1,k=0;
    datatype ai,bj;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i<=la_len)&&(i<=lb_len))
    {
        ai = GetElem(La,i);
        bj = GetElem(Lb,j);
        if(ai < bj)
        {
            k++;
            i++;
            ListInsert(Lc,ai);
        }
        else
        if（ai == bj）
        {
            k++;
            ListInsert(Lc,ai);
            i++;
            k++;
            ListInsert(Lc,bi);
            j++;
        }
        else
        {
             k++;
             j++;
             ListInsert(Lb,bj);
        }
    }
    while(i<=La_len)
    {
         ai = GetElem(La,i);
         i++;
         k++;
         ListInsert(Lc,ai);
    }
    while(j<=Lb_len)
    {
         bj = GetElem(Lb,j);
         j++;
         k++;
         ListInsert(Lc,bj);
    }
    Lc->length = k;
}

利用基本运算清除线性表中重复出现的多余节点

void Purge(List *L)
{
    int i,k;
    datatype x,y;
    for(i=1;i<ListLength(L);i++)
    {
        x = GetElem(L,i);
        k = i+1;
        while(k<=ListLength(L))
        {
             y = GetElem(L,k);
             if(x==y)
                 Delete(L,k);
             else
                 k++;
        }
    }
}

该算法的关键是Delete()算法中会自动把l->length减1。

第一部分 线性表的顺序存储(一)

第一部分线性表的顺序存储(一)