时间戳

首页 > 技术文章 > 线性表

线性表

study-hard-forever 2019-11-05 16:42 原文

线性表

定义:
是零个或多个具有相同类型的数据元素的有限序列, 相邻元素具有前驱和后继关系.

线性表的顺序储存结构: --顺序表:

特点: 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素.
作用:线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素在物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
顺序存储的实现：一维数组存储顺序表中的数据

顺序表支持的操作:增删查改判空求长等基本操作(一维数组的简单操作)

线性表顺序表示的优点是:
(1) 无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；
(2) 可方便地随机存取表中的任一元素。

线性表顺序表示的缺点：
(1)插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；
(2) 由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。

线性表的链式存储结构及实现:

链式存储分配的特点：
根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题。
链式存储结构的实现:单链表,双向链表,循环链表等 .

单链表:
通过指针把它的一串存储结点链接成一个链 ,存储结点由两部分组成： data字段 ,link字段.
头结点:如果链表有头节点，则链式结构中的第一个节点称为头结点：其数据域可以存储一些附加信息，如链表长度；其指针域指向链表中的第一个节点。

单链表的构造:
头插法:
在这里插入图片描述

for (int i=0; i<n; i++){ 
    s=new Node<T>; 
    s->data=a[i];  //为每个数组元素建立一个结点
    s->next=first->next;
    first->next=s;
}

尾插法:
在这里插入图片描述

for (int i=0; i<n; i++)	{ 
        s=new Node<T>; 
        s->data=a[i];  //为每个数组元素建立一个结点
        r->next=s; r=s;      //插入到终端结点之后
	}
    r->next=NULL;    //单链表建立完毕，将终端结点的指针域置空

补充：不带头结点的单链表的构造:
头插法：

{
    first=NULL;
    for(int i=0;i<n;i++)    { 
         s=new node<T>;
         s->data=a[i];
         s->next=first;
         first=s;   
    }
}

尾插法：

   node<T> *r;
    head=NULL;
    if（n<=0）return;
    s=new node<T>;
    s->data=a[0];
    s->next=head;
    head=s;   
    r=head;
    for(int i=1;i<n;i++)    { 
         s=new node<T>;
         s->data=a[i];
         r->next=s;
         r=s;   
    }

单链表的插入:
1 工作指针p初始化，计数器初始化
2 查找第i-1个节点，并使工作指针p指向该节点
3 若查找不成功（P==NULL），说明位置错误，抛出位置异常，否则
3.1 生成一个元素值为x的新节点s
3.2 将s插入到p之后

代码:

template <class T>  
void LinkList<T>::Insert(int i, T x){  
   Node<T> *p; int j;
   p=first ; j=0;    //工作指针p初始化
   while (p && j<i-1)   {
     p=p->next;   //工作指针p后移
     j++;
   }
   if (!p) throw "位置";
    else { 
	  Node<T> *s;
      s=new Node<T>; 
	  s->data=x;  //向内存申请一个结点s，其数据域为x
      s->next=p->next;       //将结点s插入到结点p之后
      p->next=s;	
	}
 }

单链表的删除:
在这里插入图片描述

代码:

template <class T>  
T LinkList<T>::Delete(int i){ 
  Node<T> *p; int j;
  p=first ; j=0;  //工作指针p初始化
  while (p && j<i-1) {  //查找第i-1个结点
    p=p->next; 
    j++;
  }
  if (!p || !p->next) throw "位置";  //结点p不存在或结点p的后继结点不存在
    else {
  	     Node<T> *q; T x;
          q=p->next; x=q->data;  //暂存被删结点
          p->next=q->next;  //摘链
          delete q; 
          return x;
	}
}

在这里插入图片描述
顺序表和单链表的比较-时间性能比较结论:
若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。
对于频繁进行插入和删除的线性表， 宜采用链表做存储结构.

顺序表和单链表的比较-空间性能比较:
在链表中的每个结点，除了数据域外，还要额外设置指针域， 从存储密度来讲，这是不经济的。
所谓存储密度(Storage Density), 是指结点数据本身所占的存储量和整个结点结构所占的存储量之比， 即:
存储密度=结点数据本身所占的存储量/结点结构所占的存储总量

结论: 当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

链表的其他表示方式:

循环链表,双向链表,静态链表

循环链表:
将单链表或者双链表的头尾结点链接起来，就是一个循环链表。不增加额外存储花销，却给不少操作带来了方便,从循环表中任一结点出发，都能访问到表中其他结点。
空表构造的不同:

template <class T>
CycleLinkList<T>:: CycleLinkList( )
{
         first=new Node<T>; first->next=first;
}

将非循环的单链表改造成循环的单链表:

p=first;
while(p->next)
{ 
       p=p->next;  
 }
p->next=first

可以看出从头找到尾的效率比顺序表低很多O(1)与O(n)的区别

双链表: p->llink->rlink = p = p->rlink->llink
单链表的主要不足之处是:link字段仅仅指向后继结点，不能有效地找到前驱,双链表弥补了上述不足之处,增加一个指向前驱的指针 .

双链表的结点结构 :

template <class T>
struct  DNode{
	T  data;
	DNode<T> *llink;
	 DNode <T>*rlink;
};

空的双向链表:
在这里插入图片描述
双向链表的插入: （p存在后继结点）
在这里插入图片描述
处理原则：先处理每个方向的远端指针，再处理近端指针:

q->rlink=p->rlink;
q->llink=p;
p->rlink=q;
q->rlink->llink=q;

处理原则：先在正向链表上插入，再在逆向链表上插入:

q->rlink=p->rlink;
P->rlink=q;
q->llink=p;
q->rlink->llink=q;

插入时应考虑的特殊情况: （在表尾插入一个结点）

q->rlink=p->rlink;
P->rlink=q;
q->llink=p;
if(q->rlink)  //判断是否为空,为空时后面一行无法执行
	   q->rlink->llink=q;

静态链表:
某些程序设计语言不支持指针类型, 特点：用顺序存储结构（数组）模拟实现
在这里插入图片描述
优点：
插入和删除时不需要移动元素，直接修改指针即可，因此效率较高
缺点：
静态链表是借助于数组实现的，因此，不能动态的修改数组的大小，存在着跟静态数组一样不能按需进行存储空间的分配
间接寻址（指针数组）:
将指针和数组结合起来的一种方法，它将数组中的存储数据元素的单元改为存储指向该元素的指针

推荐阅读