第五章 数据结构之线性结构

第五章 数据结构之线性结构

第一节 线性表

一、概念
    线性表是指由有限个类型相同的数据元素组成的集合，它有以下的特点：
    1.有唯一的头结点(即第一个数据元素)和尾结点(即最后一个数据元素)；
    2.除结点外，集合中的每个数据元素均只有一个前驱；
    3.除尾结点外，集合中的每一个数据元素均只有一个后继。

二、线性表的存储结构
    1、顺序结构：是通过数组说明分配连续地址的存储区，通过下标引用数组的相应元素。
    2、链式结构：通过指引元素类型的变量对线性表中元素进行动态分配存储。

三、顺序存储结构
   1、一维数组
   ① 数组存储的结构在数组声明时就需要事先分配相应的连续内存空间用来存放数据。
   ② 按首地址（表中第一个元素的地址）的位移来访问数组每一个元素的。
   若第一个元素的地址是a，每个元素占用的存储空间为L，则数组的第i个元素的地址可以用如下公式计算：
                       d(i)=a+(i-1)*L
   2、二维数组
   ① 定义方法：<数组名>:array[1..n,1..m] of <元素类型>
   ② 对于行为n，列为m的二维数组的元素访问方法： 若第一个元素的地址是a，每个元素占用的存储空间为L，则数组的第(i,j)个元素的地址可以用如下公式计算：
     按行寻址：d(i,j)=a+(i-1)*m*L+(j-1)*L
     按列寻址：d(i,j)=a+(j-1)*n*L+(i-1)*L

四、链式存储结构　
    链表是这样一种线性表，它的元素由数据和指针两部分组成，数据部分存放结点的有关信息，指针部分存放下一个结点的位置。
    优点：可根据需要分配数据元素的存储区，也可随时撤消链表中数据元素的存储区，插入删除操作只须改变指针，无须移动数据。
    缺点：它的数据元素必须在数据项以外至少增加一个指向后继元素的指针类型的数据项，查找其中的某个元素时必须中从第一个元素开始逐个往后找。

一个实例：
Type
 pointer=^node;
 node=Record;
       data:real;
       next:pointer;
      End;
Var
  head,next:pointer;

 
  1.Head为表的首指针，指向链表的第一个结点。
  2.整个链表的存取必须从head指针出发，沿着每个结点的next指针顺序进行，最后个结点的next指针为“空”（nil）.