数据结构二---------线性表

线性表包括顺序表和链表，链表又包括单链表，双链表，循环链表，貌似是这样，呵呵
顺序表查询起来会比较快，相当于java里面的ArrayList
链表是插入或删除会比较快，相当于java里面的LinkedList


以下内容摘自:http://czk.8866.org/wiki/%E7%BA%BF%E6%80%A7%E8%A1%A8

线性表总结


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

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

对于非空的线性表:

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

1.顺序表的存储结构

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

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

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


2.链表的存储结构

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

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

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

循环单链表

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

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

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

双链表

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

3.顺序表与链表比较

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

链表的比较

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

评论

1 楼 zpoop 2010-02-25