线性表是由n个具有相同特性的数据元素的有限序列,是最基本、最简单、也是最常用的一种数据结构

[TOC]

数据结构:线性表

一、线性表的类型定义

  1. 由一组相同类型数据构成;
  2. 特点:
    存在唯一一个没有前驱的头元素;
    存在一个没有后继的尾元素;
    除了头与尾,每个元素只有一个直接前驱与后继;
  3. 线性表是一种典型线性结构:其数据的运算定义在逻辑结构上,而运算的具体实现是在存储结构上进行的;
  4. 基本运算:
    (1) 初始化线性表Initlist(L) // 置空
      将线性表L置为空表。
    (2) 求线性表的长度Getlen(L) // 遍历线性表,统计元素个数
      求解并返回线性表所含元素的个数n。若线性表为空,则返回整数0。
    (3) 按序号取元素Getelem(L,i) // 遍历线性表,元素定位
      读取线性表L第i个数据元素,要求满足1≤i≤Getlen(L)。
    (4) 按值查找Locate(L,x)
          在线性表L中查找值为x的数据元素,若查找成功则返回第一个值为x的元素的序号或地址; 否则,在L中未找到值为x的数据元素,返回一特殊值(例如0),表示查找失败。
    (5) 插入元素Inselem (L,i,x)
           在线性表L的第 i 个位置上插入一个值为 x 的新元素,这样使原序号为 i , i+1, ..., n 的数据元素的序号变为 i+1,i+2, ..., n+1,要求1≤i≤Getlen(L)+1,插入后原表长增1。
    (6) 删除元素Delelem(L,i)
          在线性表L中删除序号为i的数据元素,删除后使序号为 i+1, i+2,..., n 的元素变为序号i, i+1,...,n-1,要求1≤i≤Getlen(L),删除后表长减1。
  5. 两种基本存储结构:
    顺序存储结构和链式存储结构;

二、线性表的表示与实现

  • 顺序存储
  1. 基本特点:
    所有元素占用的地址空间是连续的;
    所有元素存储空间按照逻辑顺序存放;(常用数组描述)

  2. 顺序存储下常用运算:
    数据元素的插入;

数据元素的删除;

顺序表的合并;

  1. 优缺点:

    优点:

    1. 存取速度高效,通过下标来直接存储

    缺点:

    1. 插入和删除比较慢;
    2. 不可以增长长度 ;

三、线性链表的表示与实现

  • 链式存储
  1. 基本特点:
    每个元素一部分存储自身值,一部分存放前驱或者后驱指针(指针单元称为结点);
    有一个头指针指向第一个节点

    1
    2
    3
    4
    5
    6
    //C 语言采用结构数据类型描述结点如下:
    typedef struct LNode{
    ElemType data; //结点值
    struct LNode *next; //存储下一个结点的地址
    }LNode,*LinkList;
    LNode *head;
  2. 链式存储下常用运算:

    数据元素的取出:

    数据元素的插入:

    数据元素的定位:

    顺序表的合并:

  3. 优缺点:
    优点:

    1. 插入和删除速度快,保留原有的物理顺序

    缺点:

    1. 查找速度慢,因为查找时,需要循环链表访问

四、循环链表的表示与实现

​ 循环链表是另一种形式的链式存储结构,将单链表中最后一个结点的指针指向链表的头结点,使整个链表头尾相接形成一个环形,使单向链表前后相连,成为循环链表。

操作范例:将两个循环链表首尾相接进行合并,La为第一个循环链表表尾指针,Lb为第二个循环链表表尾指针,合并后Lb为新链表的尾指针,head指向整个合并后的链表。

图解:

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
具体操作如下:
LinkList list_merge(LinkList head,LinkList La,LinkList Lb)
{ LNode *p, *q;
p=(LNode *)malloc(sizeof(LNode));//为p申请空间
q=p
p=La->next; //指针p指向La链表头
q=Lb->next; //指针q指向Lb链表头
La->next=q->next;
//使链表Lb链接到La的尾部,并去掉Lb链表中的头结点
Lb->next=p; //设置Lb为链表的尾指针
head=p;
free(p);
return head;
}

五、双向链表的表示与实现

​ 单链表只有一个指向后继的指针来表示结点间的逻辑关系。故从任一结点开始找其后继结点很方便,但要找前驱结点则比较困难。双向链式是用两个指针表示结点间的逻辑关系。即增加了一个指向其直接前驱的指针域,这样形成的链表有两条不同方向的链,前驱和后继,因此称为双链表。

结构图:

非空双向链表:

优点:在需要查找前驱的操作中,就不必再从头开始遍历整个链表。这种结构极大地简化了某些操作。

1
2
3
4
5
6
7
//双向链表结点的定义如下:
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList。