Chapter 3 Linear Lists

第 3 章 线性表

线性表（List）

零个或多个数据元素的有限序列（有顺序）

引用性操作、加工性操作。

ADT 线性表（List）
Data
    线性表的数据对象集合为{a1，a2,...,an}，每个元素的类型均为DataType。
其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除最后一个元素
an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation
    InitList(*L):初始化操作，建立一个空的线性表L；
    ListEmpty(L):若线性表为空，返回true，否则返回false；
    ClearList(*L):将线性表清空；
    GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e；
    LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；
                    否则，返回0表示失败；
    ListInsert(*L,i,e):在线性表L中第i个位置插入新元素e；
    ListDelete(*L,i,*e):删除线性表L中第i个位置元素，并用e返回其值；
    ListLength(L):返回线性表L的元素个数；
endADT

顺序存储结构数据长度与线性表长度的区别

数组的长度是存放线性表的存储空间的长度。

在任意时刻，线性表的长度应该小于等于数组的长度：即数组的长度表示为线性表的最大长度。

顺序存储结构地址计算方法

存储器中的每个存储单元都有自己的编号，称为地址。

公式：

即第i个元素的位置可以由第一个元素的位置加上i-1个存储单元的大小(取决于类型占用多少比特)

线性表存取时间性能为O(1)，称为随机存储结构。

顺序存储结构的插入与删除

获取元素操作

#define OK 1
#define ERROR 0
/* Status是函数的类型，其值是函数结果状态代码，如OK等 */
typedef int Status

/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值，注意i是指位置，第i个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0)||i<1||i>L.Length)
        return ERROR;
    *e=L.data[i-1];

    return OK;
}

插入操作

/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->length==MAXSIZE)				/* 顺序线性表已经满了 */
        return ERROR;
    if(i<1||i>L->length+1)				/* 当i比第一位位置小或者比最后一位置后一位置还要大时 */
        return ERROR;

    if(i<=L->length)					/* 当插入数据位置不在表尾 */
    {
        for(k=L->length-1;k>=i-1;k--)	/* 将要插入位置后的元素向后移一位 */
            L->data[k+1]=L->data[k]
    }
    L->data[i-1]=e;						/* 将新元素插入 */
    L->length++;

    return OK;
}

删除操作

/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k;
    if(L->length==0)					/* 线性表为空 */
        return ERROR;
    if(i<1||i>L->length)				/* 删除位置不正确 */
        return ERROR;
    *e=L->data[i-1];
    if(i<=L->length)					/* 如果删除不是最后位置 */
    {
        for(k=i;k<L->length;k++)		/* 将删除位置后继元素前移 */
            L->data[k-1]=L->data[k]
    }
    L->length--;
    return OK;
}

顺序表储存结构的优缺点

优点	缺点
无需为表示表中元素之间的逻辑关系而增加额外的存储空间 可以快速地存取表中任意位置的元素	插入和删除操作需要移动大量元素 当线性表长度变化较大时，难以确定存储空间的容量 造成存储空间的“碎片”

线性表的链式存储结构

单链表

n个节点（ai的存储映像）连接成一个链表，即为线性表（a1，a2，a3，……，an）的链式存储结构

链表中第一个结点的存储位置叫做空指针，最后一个节点指针为“NULL”或“^”即空。

• 有时，为了方便对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。

• 头结点（数据：可以存线性表长度等公共数据；指针：指向第一个结点）

注意区分：头结点（非必要）、头指针（必要）

/* 线性表的单链表存储结构 */
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */

单列表的读取

/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;				/* 声明一个结点p */
    p=L->next;				/* 让p指向链表L的第一个结点 */
    j=1;					/* j为计数器 */
    while(p&&j<i)			/* p不为空或者计数器j还没有等于i时，循环继续 */
    {
        p=p->next;			/* 让p指向下一个结点 */
        ++j;
    }
    if((!p||j<i)
       return ERROR;		/* 第i个元素不存在 */
    *e=p->data;				/* 取第i个元素的数据 */
    return OK;
}

单链表的插入和删除

单链表的插入

复杂度：O（n）寻找结点时的while循环

/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p=*L;
    j=1;
    while(p&&j<i)						/* 寻找第i个结点 */
    {
        p=p->next;
        ++j;
    }
    if((!p||j<i)
       return ERROR;					/* 第i个元素不存在 */
    s=(LinkList)malloc(sizeof(Node));	/* 生成新的结点 */
    s->data=e;
    s->next=p->next;					/* 将p的后继结点赋值给s的后继 */
    p->next=s;							/* 将s赋值给p的后继 */
    return OK;
}

单链表的删除

/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p=*L;
    j=1;
    while(p->next&&j<i)						/* 寻找第i个结点 */
    {
        p=p->next;
        ++j;
    }
    if((!p||j<i)
       return ERROR;					/* 第i个元素不存在 */
    q=p->next;
    p->next=q->next;					/* 将q的后继赋值给p的后继 */
    *e=q->data;							/* 将q结点中的数据给e */
    free(q);							/* 让系统回收此结点，释放内存 */
    return OK;
}

单链表的整表创建

顺储存结构的创建相当于数组的初始化，而单链表不一样。

单链表属于一种动态结构，无法预先分配划定所占用空间的大小和位置。

头插法

始终让新结点在第一的位置

/* 随机产生n个元素的值，建立带表头结点的单链线性表(头插法) */
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int i;
    srand(time(0));							/* 初始化随机数种子 */
    *L=(Linklist)malloc(sizeof(Node));
    (*L)->next=NULL;						/* 先建立一个带头结点的单链表 */
    for(i=0;i<n;i++)
    {
        p=(LinkList)malloc(sizeof(Node));	/* 生成新结点 */
        p->data=rand()%100+1;				/* 随机生成100以内的数字 */
        p->next=(*L)->next;
        (*L)->next=p;						/* 插入到表头 */
    }
}

尾插法

把每次的新结点都插在终端结点的后面

/* 随机产生n个元素的值，建立带表头结点的单链线性表(尾插法) */
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int i;
    srand(time(0));							/* 初始化随机数种子 */
    *L=(Linklist)malloc(sizeof(Node));
    r=*L;
    for(i=0;i<n;i++)
    {
        p=(Node*)malloc(sizeof(Node));		/* 生成新结点 */
        p->data=rand()%100+1;				/* 随机生成100以内的数字 */
        r->next=p;							/* 将表尾终端结点的指针指向新结点 */
        r=p									/* 将当前的新结点定义为表尾终端结点 */
    }
    r->next=NULL;							/* 表示当前链表结束 */
}

单链表的整表删除

/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;		/* p指向L的第一个一个结点 */
    while(p)			/* 直到P不为NULL为之 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;	/* 使头结点指针域为空 */
    return OK;
}

关于单链表结构和顺序存储结构的经验性结论

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构

• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构

静态链表

在C语言的指针还没被发明之前，用数组描述的链表

#define MAXSIZE 1000				/* 存储空间初始分配量 */

/* 线性表的静态链表存储结构 */
typedef struct
{
    ElemType data;
    int cur;						/* 游标(Cursor),为0时表示无指向 */
}Component,StaticLinkList[MAXSIZE];

对数组的第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素（或第二个元素）的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点的作用，当整个链表为空时，则为0。

静态链表的初始化

/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space)
{
    int i;
    for(i=0;i<MAXSIZE-1;i++)
    {
        space[i].cur=i+1;
    }
    space[MAXSIZE-1].cur=0;		/* 目前静态链表为空，最后一个元素的cur为0 */
    return OK;
}

静态链表的插入操作

由于数组没有malloc()和free()等标准函数，需要自己定义实现

/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space)
{
    int i=space[0].cur;				/* 当前数组第一个元素cur存的值 */
                                    /* 就是要返回的第一个备用空闲的下标 */
    if(space[0].cur)
        space[0].cur=space[i].cur;	/* 由于要拿出一个分量来使用了 */
                                    /* 所以我们就得把他的下一个 */
                                    /* 分量用来做备用 */
    return i;
}

Status ListInsert(StaticLinkList L,int i,ELemType e)
{
    int j,k,l;
    k=MAXSIZE-1;				/* k首先是最后一个元素的下标 */
    if(i<1||i>ListLength(L)+1)
        return ERROR;
    j=malloc_SSL(L);			/* 获得空闲分量的下标 */
    if(j)
    {
        L[j].data=e;			/* 将数据赋值给此分量的data */
        for(l=1;l<=i-1;l++)		/* 找到第i个元素之前的位置 */
            k=L[k].cur;
        L[j].cur=L[k].cur;		/* 把第i个元素之前的cur赋值给新元素的cur */
        L[k].cur=j;				/* 把新元素的下标赋值给第i个元素之前元素的cur */
        return OK;
    }
    return ERROR;
}

静态链表的删除操作

/* 删除L中第i个数据元素 */
Status ListDelete(StaticLinkList L,int i)
{
    int j,k;
    if(i<1||i>ListLength(L))
        return ERROR;
    k=MAXSIZE-1;
    for(j=1;j<=i-1;j++)
        k=L[k].cur;
    j=L[k].cur;
    L[k].cur=L[j].cur;
    Free_SSL(L,j);
    return OK;
}

/* 将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space,int k)
{
    space[k].cur=space[0].cur;		/* 把第一个元素的cur值赋给要删除的分量cur */
    space[0].cur=k;					/* 把要删除的分量下标赋值给第一个元素的cur */

**关于数据结构的代码太多了...根本打不完...所以关于《大话数据结构》后面课程的代码我都不打算打了...好好理解，然后记下一些重点就好了。

循环链表

循环链表的尾结点的指针指向首结点，即单链表形成循环。这样可以方便地从任意一个结点访问所有结点

双向链表

是在单链表地每个结点中，再设置一个指向其前驱结点的指针域，可以同时方便的访问到任意结点的前驱结点或者后继结点。

• 但在进行链表的插入、删除操作时，需要更改两个指针。

• 双向链表的删除：结点之间删除顺序不影响结果

总结

线性表包括

• 顺序存储结构

• 链式存储结构（单链表、静态链表、循环链表、双向链表）