线性表

线性表

1. 线性表逻辑结构

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

对于非空的线性表:

例子

2. 线性表的基本运算

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

3. 线性表的顺序存储(顺序表 Sequential List)

3.1. 顺序表的存储结构

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

seqlist.png

假设表中每个结点占用len个存储单元,其中第一个单元的存储地址则是该结点的存储地址,并设表中开始结点a1的存储地址(简称为基地址)是loc(a1),那么结点ai的存储地址loc(ai)可通过下式计算:loc(ai)=loc(a1)+(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开始,所以线性表的开始结点a1在线性表中的序号为1,对应的数组下标为0,ai在线性表中的序号为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. 练习

  1. 设计一个算法,求顺序表中值为x的元素的个数。
  2. 设计一个算法,将顺序表倒置。
  3. 已知一个顺序表中的各结点的值是从小到大有序的,设计一个算法,插入一个值为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. 循环单链表与单链表的不同

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. 线性表应用举例:一元多项式

一元多项式的表示 Pn(x) = p0+p1x+p2x2+...+pnxn

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. 线性表总结

顺序表与链表比较

链表的比较

线性表 (2008-02-23 15:36:38由localhost编辑)