「数据结构」-6-线性表

2018-10-27

线性结构是计算机程序设计中最常遇见的一种操作对象，也是数据结构中最简单、最重要的结构形式之一。
简单地将，线性表（Linear List）是n个数据元素的有限序列（a₁,a₂,…,a_n）。n=0时称为空表。

线性表的特征：

对于长度为n(n>0)线性表,有且仅有一个开始结点a₁，有且仅有一个终端结点a_n
当a=1,2,..,n-1时，a_i仅有一个直接后继a_i+1
当a=2,3,..,n时，a_i仅有一个直接前驱a_i-1

线性表的基本运算

序号	运算操作	描述
1	置空表setnull(L）	将线性表L置为空表
2	求长度length(L)	返回线性表的长度
3	取结点get(L,i)	返回线性表L中第i个元素
4	定位local(L,x)	当线性表L中有值为x的数据元素时，返回最小的下标位置；若没有则返回0
5	插入insert(L,x,i)	在线性表L的第i个位置插入值为x的新元素
6	删除delete(L,i)	删除线性表L的第i个结点，并返回该结点的值

一、顺序表

一种特殊的线性表：用一组地址连续的存储单元依次存储线性表的元素。
假设顺序表的每个元素占用c个存储单元，并以第一个元素所在的内存地址为存储位置，那么第i个元素和第i+1各元素的内存地址之间存在以下关系：

Loc(a_i+1) = Loc(a_i) + c

所以顺序表第i个元素的存储位置:

Loc(a_i) = Loc(a₁) + （i-1) * c (1<=a<=n)

我们可以使用如下结构表示顺序表：

#define maxsize 1024  /* 线性表最大长度，假设是1024 */

typedef int datatype;

typedef struct {
    datatype data[maxsize];
    int last;        /* last表示线性表终端结点在向量空间中的位置，所以last+1等于线性表的当前长度 */
} sequenlist;

顺序表的基本运算

1. 插入运算

在顺序表的第i(1≤i≤n+1)个位置上，插入一个新结点x，使长度为n的顺序表：(a₁,…,a_i-1,a_i,…,a_n)变成长度为n+1的顺序表：(a₁,…,a_i-1,x,a_i,…,a_n)。

由于顺序表中的元素是储存在内存地址连续的空间上，所以插入x结点之前，需要将n,n-1,…,i这些结点依次后移到n+1,n,…,i+1上，再将空出的第i个结点插入值x。整个过程如下：

//将新结点x插入顺序表L的第i个位置上
void insert(sequenlist * L,int x,int i)
{
    int j;
    if((L->last)>=maxsize-1)
    {
        printf("表空间溢出，不允许再插入元素！\r\n");
        exit(0);
    }else
    {
        if((i<1)||(i>(L->last)+2))
        {
            printf("插入元素的下标有误!\r\n");
            exit(0);
        }else
        {
            for(j=L->last;j>=i-1;j--)
            {
                L->data[j+1] = L->data[j];     /* 结点往后移动 */
            }
            
            L->data[i-1] = x;              /* 插入x，存在（*L）data[i-1]中 */
            L->last = L->last+1;
        }
    }
}

顺序表插入结点算法的思路：

如果插入位置不合理，抛出异常；
如果线性表长度不够，则抛出异常或者动态增加容量；
从最后一个元素向前遍历到第i个元素，分别将它们向后移动一个位置；
将要插入的元素填入位置i；
表长加一；

2.删除元素

将顺序表的第i(1≤n≤n)个结点删除，使长度为n的顺序表：(a₁,…,a_i-1,a_i，a_i+1,…,a_n)变成长度为n-1的顺序表：(a₁,…,a_i-1a_i+1,…,a_n)。
与插入操作类似，删除同样需要移动元素，依次将i+1,i+2,…,n这些结点往前移动一个位置到i,i+1,…,n-1上。整个过程如下：

//sequenlist-delete elem
//删除顺序表L的第i个结点data[i-1]，并返回该节点的值
void delete(sequenlist *L,int i,int *res)
{
    int j;
    if(i<1||i>L->last)
    {
        printf("删除元素的下标有误！\r\n");
        exit(0);
    }else
    {
        *res = L->data[i-1];                 /* 获取被删除元素的值 */
        printf("被删除元素的值是[%d]\r\n",*res);
        for(j=i;j<L->last;j++)
        {
            L->data[j-1] = L->data[j];      /* 结点向前移动 */
        }
        L->last--;
    }
}

注意删除第i个元素其实是删除L->data[i-1]

顺序表删除结点算法的思路：

如果位置不合理，抛出异常；
取出被删除的元素；
从删除元素向后遍历到最后一个元素，分别将它们向前移动一个位置；
表长减一；

3.复杂度

顺序表的查询直接根据下标获取元素，时间复杂度为O(1)；插入和删除因为需要移动大量元素，其时间复杂度为O(n)。

4. 线性表顺序储存结构优缺点

优点：

无须为表中元素的逻辑关系而增加额外的存储空间
可以快速按照下标进行查找

缺点：

插入和删除操作需要移动大量元素，效率低
频繁的数据移动会造成存储空间的碎片

二、单链表

顺序表中，使用一组地址连续的存储单元来一次存放线性表的结点，因此，结点的物理次序和逻辑次序一致。而链表是使用任意的存储单元存放线性表的元素，内存地址可以不连续。因此结点不仅需要存储数据，还要存储其后继元素的地址信息。即包含数据域和指针域。
[data] | [next]
其中data是数据域，next是指针域。单链表中每个结点的存储地址是存放在其前趋结点的next域中。而开始结点没有前趋，所以设有头指针head指向开始结点，同时终端结点的指针域指向NULL。

我们可以使用如下结构来表示单链表：

typedef int datatype;   /* 存储数据元素类型 */

typedef struct node
{
datatype data;      /* 数据域 */
struct node *next;  /* 指针域 */
} linkedlist;

1. 头插法建立单链表

从空表开始，重复读入数据生成新结点，并将新结点插入当前链表的表头，直到读入结束标志为止。

//头插法建表,返回头指针
linkedlist * CREATELISTF(int n)
{
    printf("头插法建表\r\n");
    int j;
    j=0;
    int t;
    linkedlist *head, *s;
    head=NULL;              /* 链表开始为空 */
    while(j <= n)
    {
        t = j;
        s = (linkedlist *)malloc(sizeof(linkedlist));   //生成新的结点
        s->data = t;
        s->next = head;       //将新结点的指针域指向原表的开始结点
        head = s;             //更新原表的头结点
        j++;
    }
    
    return head;
}

2. 尾插法建立单链表

使用头插法生成的链表中结点顺序与元素的输入顺序相反。若要两者相同可以使用尾插法，该方法将新生成的结点插入到当前链表的表尾。

//尾插法建表,返回头指针
linkedlist *CREATELISTR(int n)
{
    printf("尾插法建表\r\n");
    int j;
    j=0;
    int t;
    linkedlist *head,*s,*r;
    head = (linkedlist *)malloc(sizeof(linkedlist));   //生成头结点head
    r = head;                   //尾结点指向头结点
    while(j <= n)
    {
        t = j;
        s = (linkedlist *)malloc(sizeof(linkedlist));  //生成新的结点
        s->data = t;
        r->next = s;                                   //将新结点插入原表的尾结点
        r = s;                                         //尾指针r指向新的表尾
        j++;
    }
    r->next = NULL;
    return head;
}

3. 单链表查找

按照序号查找
在带头结点的单链表head中查找第i个结点的存储

void getValueByindex(linkedlist *head,int i,int *res)
{
    int j;
    linkedlist *p;
    p=head; j=0;
    while((p->next != NULL) && (j<i))   //从头结点开始扫描
    {
        p = p->next;      //扫描下一个结点
        j++;              //已经被扫描结点的计数器
    }
    
    if(i==j)
    {
        *res = p->data;
    }
}

按照值查找
从头结点开始，顺着链表逐个比较每个结点的值与给定值的大小：

linkedlist *LOCAL(linkedlist *head,datatype key)
{
    linkedlist *p;
    p=head->next;
    while((p != NULL) && (p->data != key))
    {
        p = p->next;   //没有找到合适的值，继续向下循环
    }
    
    if(p == NULL)
    {
        return NULL;   //没有找到，return
    }else
    {
        return p;      //找到结点key，return
    }
}

4.单链表插入

找到插入结点的位置i
生成新结点s
新结点i的指针域指向后续结点（第i+1个结点）
第i-1个结点（新结点的前一个结点）指向新结点s

// 单链表插入
void linkedlist_insert(linkedlist *L,int i,datatype value)
{
    int j;
    j = 1;
    linkedlist * p, * s;
    p = L;
    
    while(p && j<i)  // 寻找第i个结点
    {
        p = p->next;
        j++;
    }
    
    if(!p || j>i)
    {
        printf("insert linkedlist error...\r\n");
        exit(0);
    }
    
    s = (linkedlist *)malloc(sizeof(linkedlist));  // 生成新结点
    s->data = value;
    s->next = p->next;                             // 新结点数据域，指针域赋值
    
    p->next = s;                                   //p指向新结点
}

5. 单链表删除

本文中的代码块见「我的Github-数据结构」。

本文作者： 肖鹏
本文链接： http://www.xiaopeng.pro/articles/f47ff5bf.html
版权声明： 本原创文章采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！