第一章：线性表（1）—

第一章：线性表（1）——顺序存储

1、数据结构描述：

Linear_List=(D,R)
D={ai|ai∈D0   i=1,2,....   n>=0}
R={N}
N={<ai-1,ai>|ai-1,ai∈D0  i=2,3,4,...}
D0是某个数据对象

2、术语：

直接前驱：ai-1是ai的前驱 i=2,3,4,...n

直接后继：ai+1是ai的后继 i=1,2,...n-1

空表：n=0

长度：数据元素个数n

3、线性表上常见的运算

　　1）初始化Initiate(L):创建一个空的线性表L

　　2）求长度Length(L)：返回表中元素个数

　　3）访问一个元素Get(L,i)：返回线性表的第i个元素

　　4）求前驱Prior(L,elem)：返回线性表中elem元素的前驱

　　5）求后继Next(L,elem)：返回线性表中elem元素的后继

　　6）查找（定位）Locate(L,x)：求x数据元素在线性表中的位置

　　7）插入Insert(L,i,b)：将数据元素插入到线生表L的第i个元素之前

　　8）删除Delete(L,i)：删除线性表的第i个元素

　　9）判断是否空Empty(L)：线性表空，则返回TRUE，否则FALSE

　　10）输出线性表Print(L)：输出线性表的各个元素

　　11）其它操作：复制、分解、合并、分类等

4、线性表的ADT

ADT linear_list
{//data structure:
D={ai|ai∈D0 i=1,2,...n>=0}
R={N}
N={<ai-1,ai>|ai-1,ai∈D0 i=2,3,4,...}
D0是某个数据对象
//operations:
Inititate(L)
Length(L)
Get(L,i)
Locate(L,x)
Insert(L,i,b)
Delete(L,i)
Empty(L)
Print(L)
}ADT linear_list

5、线性表的分类

　　按数据元素分：　　

　　　　一般线性表　　字符串　　数组　　广义表

　　按实施操作分：

　　N元组——不能进行插入、删除

　　一般线性表——可以在任何位置插入、删除

　　堆栈——只能在一端插入、删除

　　队列——插入在一端、删除在另一端

　　双端队列——在两端可以插入、删除

6、线性表ADT的应用举例

　　例1：已知有线性表L，要求删除所有X的出现

Status del(list &L, ElemType x)
{k=LocateElem(L,x,equal);
    while(k!=0)
    {Listdelete(&L,k,&e);
      k=Locate(L,x,equal);
    }
    return (OK);
}

例2：已知有两个分别有序的线性表（从小到大），要求合并两个线性表，且合并后仍然有序。——归并

　　方法1：合并，再排序o((m+n)②）

　　方法2：归并，利用分别有序的特点（每一次插入都比较a,b线性表的当前元素的大小）o(m+n)

void mergelist(list La, list Lb, list &Lc)
{
    //已知线性表La和Lb中的数据元素按值非递减排列
    //归并La和Lb得到新的线性表Lc，Lc中的元素也按值非递减
    Initlist(Lc); i=j=1;k=0;
    La_len=ListLength(La); Lb_len=ListLength(Lb);
    while((i<=La_len)&&(j<=Lb_len))
    {
        GetElem(La,i,ai);GetElem(Lb,j,bj);
        if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
        else{ListInsert(Lc,++k,bj);++j;}
    }    
    while(i<=La_len){
    GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}
    while(j<=Lb_len){
    GetElem(Lb,j++,bi);ListInsert(Lc,++k,bi);}
}

6、线性表的顺序存储结构

　　1）存储方式：用一组地址连续的存储单元依次存储线性表的各个元素。具体地：假设存储每个元素占用1个存储单元，并且以所占的第一个单元的地址作为该元素的存储地址。

　　2) 特点：存储空间必须是连续的，预分配。（静态）

　　　　　　　逻辑顺序与物理顺序一致，用物理上的相邻来表示逻辑上的线性关系。

　　　　　　　任意相邻元素之间无空亲空间，且相距为l。

　　　　　　　已知基地址，可以计算出任意元素的存储地址：

　　　　　　　　　　LOC(ai)=base + (i-1)*l

　　3) 虚拟实现：

　　在高级语言中，数组是采用顺序存储的，因而，我们可以用高级语言中的数组类型来说明上面的存储方式。

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

7、各个运算在顺序存储下的虚拟实现

　　1）初始化

Status initlist_sq(SqList &L)//构造一个空的线性表
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem)exit(OVERFLOW);
    L.length=0;//空表长度为0
    L.listsize=LIST_INIT_SIZE;//初始存储容量
    reutrn OK;
}

　　2）清空表　　L.length=0;

　　3）销毁表　　free(L.elem)　　

　　4）求表长　　return (L.length)

　　5）判断空表　　if(L.length==0)　　return OK;

　　6）取表中的第i个元素

Status GetElem(SqList L, int i, ElemType &e)
{
    if(i>L.length||i<1)    return(ERROR);
    p=L.elem+(i-1);
    e=*p;    
}

　　7）定位 //查找某个元素是否存在，存在给出其位置，否则为0；

int locate_sq(SqList L, ElemType e)
{
    p=L.elem;
    for(i=1;i<=L.length;i++)
    if(*p++ ==e) return i;
    else return 0;
}

　　8）插入 //在顺序线性表L中第i个元素之前插入新元素e

Status Listinsert_Sq(SqList &L, int i, ELemType e)
{
    if(i<1||i>L.length+1)    return ERROR;
    if(L.length>=L.listsize){
    newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
    if(!newbase) exit(OVERFLOW);
    L.elem=newbase;
    L.listsize+=LISTINCREMENT;
    }
    q=&(L.elem[i-1]);
    for(p=&L.elem[L.length-1];p>=q;--p) *(p+1)=*p;
    *q=e; ++L.length; return OK;
}

　　9）删除

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
    if((i<1)||(i>L.length)) return ERROR;
    p=&(L.elem[i-1]);
    e=*p;
    q=L.elem + L.length-1;
    for(++p;p<=q;++p)  *(p-1)=*p;
    --L.length;
    return OK;
}