线性表

线性表

1. 线性表逻辑结构

线性表是一种典型的线性结构，是最简单且最常用的逻辑结构。

线性表是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。
数据元素的个数n定义为表的长度（n=0时称为空表）。
将非空的线性表（n＞0）记作：（a1，a2，…，an）

对于非空的线性表:

有且仅有一个开始结点a1，没有直接前趋；
有且仅有一个终结结点an，没有直接后继；
其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋a_i-1和一个a_i+1。

例子

学生成绩表中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。
英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素（结点）
一副扑克牌也是一个线性表，其中数据元素是每张牌的花色和点数

2. 线性表的基本运算

init(L)：构造一个空的线性表L，即表的初始化，使得L成为一个可以使用的空的线性表。
destroy(L)：销毁线性表L，之后L不可以再使用。
clear(L)：将线性表L清空，变成空表。
is_empty(L)：判断线性表L是否为空表。
length(L)：求线性表L中的元素个数，即求表长。
get_elem(L, i)：取线性表L中的第i个结点，这里要求1 ≤ i ≤ length_list(L)
find(L, x)：在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。
insert(L,i,x)：在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，…，n的结点变为编号为i+1，i+2，…，n+1的结点。这里1≤i≤length(L)+1，而length(L)是原表L的长度。插入后，表L的长度加1。
remove(L,i)：删除线性表L的第i个结点，使得原编号为i+1，i+2，…，n的结点变成编号为i，i+1，…，n-1的结点。这里1 ≤ i ≤ length(L)，而length(L)是原表L的长度。删除后表L的长度减1。

对于实际问题中涉及的其它更为复杂的运算，可以用基本运算的组合来实现。例如删除值为x的结点等。

3. 线性表的顺序存储（顺序表 Sequential List）

3.1. 顺序表的存储结构

采用顺序存储方式存储的线性表就称为顺序表。即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。线性表中所有结点的类型相同，每个结点所占用存储空间大小亦相同。如下图所示：

假设表中每个结点占用len个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a₁的存储地址（简称为基地址）是loc（a₁），那么结点a_i的存储地址loc（a_i）可通过下式计算：loc(a_i)=loc(a₁)+(i-1)*len,1 ≤ i ≤ n

在顺序表中，每个结点的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址，是一种可以随机访问的数据结构。

顺序表用固定长度的数组实现：

   1 #define MAXSIZE 100
   2 typedef int elem_type;
   3 typedef struct{
   4     elem_type  elem[MAXSIZE];
   5     int size; //表示数组中元素个数
   6 }seq_list;

其中，elem_type是为了描述统一而自定义的，实际使用中，可以定义为需要的类型。

由于C语言中数组的下标从0开始，所以线性表的开始结点a₁在线性表中的序号为1，对应的数组下标为0，a_i在线性表中的序号为i，对应的数组下标为i-1。

除了用数组存储线性表的元素外，顺序表还需要用一个变量来表示线性表的长度属性或者最后一个元素的位置，因此用结构类型来定义顺序表类型。

存放线性表结点的数组空间的大小MAXSIZE应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。可动态变化空间大小的实现，在后面给出。

3.2. 初始化

   1 void init( seq_list * slt) {
   2     slt->size=0;
   3 }

3.3. 遍历

   1 void print(seq_list  *slt)
   2 {
   3    int i;
   4    for( i=0; i < slt->size; i++) 
   5         printf("%5d", slt->elem[i]);
   6 }

3.4. 判断是否为空

   1 int is_empty( seq_list  *slt ) {
   2      return  slt->size==0;
   3 }

3.5. 查找值为x的结点位置

   1 int find(seq_list *slt, elem_type x)
   2 {
   3     int i=0;
   4     while(i < slt->size && slt->elem[i]!=x) 
   5         i++;
   6     return i<=slt->last? i+1:-1;
   7 }

3.6. 取得第i个结点的值

   1 elem_type get_elem(seq_list *slt, int position) {
   2     return slt->elem[position-1];
   3 }

3.7. 任意位置插入

   1 void insert(seq_list *slt, int position, elem_type x) { 
   2     int i;
   3     position--;
   4     for(i = slt->size; i > position; i--) 
   5         slt->elem[i] = slt->elem[i-1];
   6     slt->elem[position]=x;
   7     slt->size++;
   8 }

分析插入算法时间性能分析

3.8. 任意位置元素删除

void remove(seq_list *slt, int position) {
    int i;
    position--;
    for(i=position; i<slt->size-1; i++) 
        slt->elem[i]=slt->elem[i+1];
    slt->size--;
}

分析删除算法时间效率

3.9. 顺序表的用法举例

int main() {
    seq_list  sqlist;
    init_list(&sqlist);
    insert_list(&sqlist, 1, 1);
    print_list(&sqlist);
    printf("%d", locate_list(&sqlist, 10));
    printf("%d", locate_list(&sqlist, 11));
    while(!empty_list(&sqlist))
        delete_list(&sqlist, sqlist.size);
    print_list(&sqlist);
}

3.10. 练习

设计一个算法，求顺序表中值为x的元素的个数。
设计一个算法，将顺序表倒置。
已知一个顺序表中的各结点的值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序的。

4. 顺序表可变长度的实现

   1 typedef int elem_type;
   2 typedef struct{
   3     elem_type *elem;
   4     int size; //表示数组中元素个数
   5     int capacity;
   6 }seq_list;

元素所使用的内存由malloc分配，当空间用完时，自动扩展。

   1 #define INIT_SIZE 100
   2 void init( seq_list * slt) {
   3     slt->size=0;
   4     slt->capacity = INIT_SIZE;
   5     slt->elem = (elem_type *) malloc(sizeof(elem_type) * INIT_SIZE);    
   6 }

   1 void destroy( seq_list *slt) {
   2     free(slt-elem);
   3     slt->size = slt-capacity = 0;
   4 }

   1 void insert( seq_list *slt, int pos, elem_type x) {
   2     if(slt->size == slt->capacity) {
   3         slt->capacity *= 2;
   4         elem_type *p = malloc(sizeof(elem_type) * slt->capacity);
   5         for(int i = 0; i < slt->size; i++)
   6             p[i] = slt->elem[i];
   7         free(slt->elem);
   8         slt->elem = p;
   9     }
  10     /* .... */
  11     /* normal insert, same as above*/
  12 }

5. 线性表的链式存储（带头结点的单链表）

5.1. 链表的存储结构

数据结构的存储方式必须体现它的逻辑关系。在链式存储方式下，除存放一个结点的信息外，还需附设指针，用指针体现结点之间的逻辑关系。如果一个结点有多个后继或多个前驱，那么可以附设相应个数的指针，一个结点附设的指针指向的是这个结点的某个前驱或后继。

线性结构的链式存储被称为链表。链表中可以只附设一个指针指向它的后继结点的存放位置；也可以设两个指针，一个指向前驱一个指向后继。

单链表是线性表链式存储的一种形式。其中的结点一般含有两个域，一个是存放数据信息的域，另一个是存放该结点的后继结点的地址的指针域。一个单链表必须有一个首指针指向单链表中的第一个结点。

单链表存储结构实现

   1 typedef int elem_type;
   2 struct node{
   3    elem_type data;
   4    struct node *next;
   5 };
   6 typedef struct node node;
   7 typedef struct node *link_list;

普通单链表的缺点：特殊情况太多，处理起来太麻烦。改进办法：增设头结点，头结点不存放任何数据，称为带头结点的单链表。

5.2. 初始化

带头结点单链表的初始化

   1 void init(link_list *list) {
   2    *list = (link_list)malloc(sizeof(node));
   3    (*list)->next = NULL;
   4 }

5.3. 插入

基本插入算法：在给定的结点后面插入一个元素

   1 void insert(node *q, elem_type x) 
   2 {
   3    p = (node*)malloc(sizeof(node));
   4    p->data = x;
   5    p->next = q->next;
   6    q->next = p;
   7 }

插入特定位置：在给定链表的第pos个位置插入一个元素

   1 void insert_pos(link_list node, int pos, elem_type x) 
   2 {
   3    while(pos > 1) {
   4         node = node->next;
   5         pos--;
   6    }
   7    insert(node, x);
   8 }

5.4. 删除

基本删除算法：删除指定结点后面的一个元素

   1 void remove(node *pre) 
   2 {
   3    node *p = pre->next;
   4    pre->next=p->next;
   5    free(p);
   6 }

删除特定位置元素算法：删除指定链表第pos个位置上的元素

   1 void remove_pos(Node *node, int pos) 
   2 {
   3    while(pos > 1) {
   4       node = node->next;
   5       pos--;
   6    }
   7    remove(head);
   8 }

删除特定值的元素算法：删除给定单链表中值为x的元素

   1 void remove_x(node *head, elem_type x) 
   2 {
   3    node *pre = head;
   4    while(pre->next!= NULL && 
   5       pre->next->data != x) 
   6    {
   7       pre=pre->next;
   8    }
   9    remove(pre);
  10 }

5.5. 查找算法

查找单链表中第pos位置上的元素

   1 node *get_elem(node *head, int pos) 
   2 {
   3    while(pos > 0) {
   4       head = head->next;
   5       pos--;
   6    }
   7    return head;
   8 }

查找值为x的元素：

   1 node *find_x(node *head, elem_type x) 
   2 {
   3    head = head->next;
   4    while(head!=NULL && head->data != x) 
   5    {
   6       head=head->next;
   7    }
   8    return head;
   9 }

5.6. 思考

如何实现：

打印链表的每一个元素的值
求链表的长度
合并两个有序的单链表，使他们依然有序
单链表就地逆置

6. 不带头结点的单链表

不设开始的头结点，head指针直接指向第一个元素。

由于head指针的值可能会发生变化，所以插入、删除操作比较繁琐

   1 void insert(node **head, int pos, elem_type x) {
   2     node *p = malloc(sizeof(node));
   3     p->data = x;
   4     if(pos > 1) {
   5         while(pos-- > 2) {
   6             *head = (*head)->next;
   7         }
   8         p->next = (*head)->next;
   9         (*head)->next = p;
  10     } else if(pos == 1) {
  11         p->next = *head;
  12         *head = p;
  13     }
  14 }

7. 循环单链表

如果希望从表中的任意一个结点开始，都能访问到表中的所有其它结点，可以设置表中最后一个结点的指针域指向表中的第一个结点，这种链表称为循环单链表（或单循环链表）

7.1. 循环单链表与单链表的不同

单链表中某个结点p是表中最后一个结点的特征是p->next==NULL。
对于循环单链表，若首指针为head，表中的某个结点p是最后一个结点的特征应该是p->next==head。
判断单链表为空的条件是head->next==NULL
判断循环单链表为空的条件是head->next == head

7.2. 循环单链表插入

带头结点的循环链表的插入算法，与不带头结点的相同。

7.3. 循环单链表的删除

带头结点的循环链表的删除算法，与不带头结点的相同。

7.4. 只设尾指针的循环单链表

在循环单链表中，常常只设一个尾指针不设头指针。

7.5. 例子：合并两个循环单链表

带头结点的，使用头结点指针

   1 node *merge(node *head1, node *head2) {
   2     node *p1, *p2;
   3     for(p1 = head1; p1->next != head1; p1 = p1->next);
   4     for(p2 = head2; p2->next != head2; p2 = p2->next);
   5     p2->next = head1;
   6     p1->next = head2->next;
   7     free(head2);
   8     return head1;
   9 }

带头结点的，使用尾结点指针

   1 node *merge(node *tail1, node *tail2) {
   2     if(tail2->next != tail2) {
   3         node *p = tail1->next;
   4         tail1->next = tail2->next->next;
   5         free(tail2->next);
   6         tail2->next = p;
   7         return tail2;
   8     } else {
   9         free(tail2);
  10         return tail1;
  11     }
  12 }

8. 双链表

8.1. 逻辑结构

前面的各种链式表中，一个结点的指针域是指向它的后继结点的，如果需要找一个结点p的前驱结点，则必须从表首指针开始查找，当某个结点pre的指针域指向的是结点p时，即pre->next==p时，则说明pre是p的前驱结点。

如果常常需要知道一个结点的前驱和后继结点，上述的链式表是不适合的。既然单链表中每个结点有一个指针域指向它的后继结点，那自然地想到再增设一个指针域指向它的前驱结点，这就构成了双链表。

8.2. 双链表存储结构

   1 struct dnode{
   2    elem_type data;
   3    struct dnode *next;
   4    struct dnode *prior;
   5 };
   6 typedef struct dnode dnode;
   7 typedef struct dnode *dlist;

双链表的结点包括三个域，一个是存放数据信息的data域，另外两个是指针域，这里用next和prior表示，prior指向它的前驱结点，next指向它的后继结点。

8.3. 双链表的插入

   1 void insert(dnode *pre, elemtype x) {
   2     dnode *p = malloc(sizeof(dnode));
   3     p->data = x;
   4     p->prior = pre;
   5     p->next = pre->next;
   6     pre->next = p;
   7     p->next->prior = p;
   8 }

8.4. 双链表的删除

   1 void remove(dnode *p) {
   2     p->next->prior = p->prior;
   3     p->prior->next = p->next;
   4     free(p);
   5 }

9. 线性表应用举例：一元多项式

一元多项式的表示 P_n(x) = p₀+p₁x+p₂x²+...+p_nxⁿ

9.1. 数据结构表示

   1 typedef struct { 
   2    double coef; 
   3    int exp; 
   4 }elem_type;

运算：两个多项式相加、相乘

9.2. 相加

   1 node *add(node *p1, node *p2) {
   2     node *p, *tail;
   3 
   4     tail = p = malloc(sizeof(node));
   5     p->next = NULL;
   6     p1 = p1->next;
   7     p2 = p2->next;
   8     while(p1 && p2) {
   9         if(p1->data.exp == p2->data.exp) {
  10              elem_type t;
  11              t.exp = p1->data.exp;
  12              t.coef = p1->data.coef + p2->data.coef;
  13              if(t.coef) {
  14                  insert(tail, t);
  15                  tail = tail->next;
  16              }
  17              p1 = p1->next;
  18              p2 = p2->next;
  19         } else if(p1->data.exp < p2->data.exp) {
  20              insert(tail, p1->data);
  21              tail = tail->next;
  22              p1 = p1->next;
  23         } else {
  24              insert(tail, p2->data;
  25              tail = tail->next;
  26              p2 = p2->next;
  27         }
  28     }
  29     while(p1) {
  30         insert(tail, p1->data);
  31         tail = tail->next;
  32         p1 = p1->next;
  33     }
  34     while(p2) {
  35         insert(tail, p2->data);
  36         tail = tail->next;
  37         p2 = p2->next;
  38     }
  39     return p;
  40 }

10. 线性表总结

顺序表与链表比较

存储空间效率(顺序表≈1，链表<1)
时间效率
- 插入、删除：顺序表插入删除需要移动元素，链表不需要移动
- 访问：顺序表是随机访问，链表是顺序访问
- 查找：顺序表排序后可以二分查找，链表只能顺序查找

链表的比较

带头结点，不带头结点：带头结点的链表操作简便
循环，不循环：循环的链表可以只存尾指针，两端插入效率高
单链表，双链表：单链表只能单向遍历，双链表可以双向遍历