线性表

2021-07-20  本文已影响0人  猫大人H

2.1 线性表的定义和特点

线性表

定义：由n（n≥0）个数据元素（节点） a1 ,a2, ...an组成的有序列。

逻辑特征

线性表是一种典型的线性结构。

2.2案例引入

顺序存储结构存在问题

  • 存储空间分配不灵活

  • 运算的空间复杂度高

==> 链式存储结构

总结

2.3 线性的类型定义

抽象数据类型线性表的定义如下：

ADT list{

数据对象：D ={ai|ai属于Elemset,(i=1,2,...,n,n≥0)}

数据关系：R={<ai-1,ai>|ai-1,ai属于D,(I=2,3,...,n)}

基本操作：

InitList(&L); DestroyList(&L);

ListInsert(&L,i,e); ListDelete(&L,i&e);

......等等

}ADT List

基本操作（一）

  • 以上所提及的运算是逻辑结构上定义的运算。只要给出这些运算的功能是"做什么"，至于"如何做"等实现细节，只有待确定了存储结构之后才考虑

  • 在计算机内，线性表有两种基本的存储结构

    顺序存储结构和链式存储结构。

2.4 线性表的顺序表示和实现

线性的顺序表示又称为顺序存储结构或顺序映像。

顺序存储定义

把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

简言之，逻辑上相邻，物理上也相邻。

线性表的第1个数据元素 a1 的存储位置，称作线性表的起始位置或基地址。

顺序表中元素存储位置的计算

线性表顺序存储结构占用一片连续的存储空间。知道某个元素的存储位置就可以计算其他元素的存储位置。

 假设线性表的每个元素需占 *l* 个存储单元，则第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置之间满足关系：

        **LOC(a<sub>i+1</sub>) = LOC(a<sub>i</sub>) + *l***

由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

        **LOC(a<sub>i+1</sub>) = LOC(a<sub>1</sub>) +（i-1）x *l***
顺序表的特点
顺序表的顺序存储表示

顺序表（元素） \begin{cases} 地址存储\\ 依次存放\\ 随机存取\\ 类型相同\\ \end{cases} 数组（元素） → 用一位数组表示顺序表

线性表长度可变（删除）

数组长度不可动态定义。 → 用变量表示顺序表的长度属性

#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
  typedef struct{
    ElemType elem[LIST_INIT_SIZE];
    int length; //当前长度
  }SqList;
顺序表的查找算法分析
int LocateElem(SqList L,ElemType e){
  //在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）
  for(i=0;i<L.length;i++){
    if(L.elem[i] == e) return i+1;  
  }
  return 0;//查找失败，返回0
}
顺序表的插入

线性表的插入运算是指在表的第 i （1≤ i ≤n+1）个位置上，插入一个新结点 e ，使长度为 n 的线性表（a1,...,ai-1,ai,...,an）变成长度为 n+1 的线性表 （a1,...,ai-1,e,ai,...,an）

算法思想：

  1. 判断插入位置 i 是否合法。
  2. 判断顺序表的存储空间是否已满，若已满返回ERROR。
  3. 将第 n 至第 i 位的元素依次向后移动一个位置，空出第 i 个位置。
  4. 将要插入的新元素 e 放入第 i 个位置。
Status ListInsert_Sq(SqList &L,int i,ElemType e){
  if(i<1||i>L.lengtf+1) return ERROR; //i值不合法
  if(L.length == MAXSIZE) return ERROR;//当前存储空间已满
  for(int j=L.length-1;j>=i-1;j--){
    L.elem[j+1] = L.elem[j]  
  }
  L.elem[i-1] = e;
  L.length++;
  return OK;
}
顺序表的删除

线性表的删除运算是指将表的第 i (1 ≤ i ≤ n)个结点删除，使长度为 n 的线性表（a1,...,ai-1,ai,...,an）变成长度为 n-1 的线性表 （a1,...,ai-1,ai+1,...,an）

算法思想：

  1. 判断删除位置 i 是否合法 （合法值为 1 ≤ i ≤ n）。

  2. 将欲删除的元素保留在 e 中。

  3. 将第 i+1 至第 n 位的元素依次向前移动一个位置。

  4. 表长减1，删除成功返回OK。

    Status ListDelete_Sq(SqList &L,int i,&e){
  if(i<1||i>L.length) return ERROR;
  e = L.elem[i-1];
  for(int j=i;j<=L.length-1;j++){
    L.elem[j-1] = L.elem[j];
  }
  L.length--;
  return OK;
}

算法分析

顺序表的特点
  1. 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致。
  2. 在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等。
顺序表的操作算法分析
顺序表有缺点

2.5 线性表的链式表示和实现

与链式存储有关的术语
  1. 结点：数据元素的映像。由数据域和指针域两部分组成
  2. 链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
  3. 单链表、双链表、循环链表：
    • 结点只有一个指针域的链表，称为单链表或者线性链表
    • 结点有两个指针域的链表，称为双链表
    • 首尾相接的链表称为循环链表
  4. 头指针、头结点和首元结点：
    • 头指针：是指向链表中第一个结点的指针
    • 首元结点：是指链表中存储第一个元素 a1 的结点
    • 头结点：是在链表的首元结点之前附设的一个结点；
如何表示空表
在链表中设置头结点有什么好处？

  1. 便于首元结点的处理

    首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理；

  2. 便于空表和非空表的统一处理

    无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

头结点的数据域内装的是什么？

头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。

链表（链式存储结构）的特点
  1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
  2. 访问时只能通过头指针近入链表，并通过每个节点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等，这种存取元素的方法被称为顺序存取法。

顺序表：随机存取

链表：顺序存取

单链表的存储结构
typedef struct Lnode{     //声明节点的类型和指向结点的指针类型
  ElemType data;          //结点的数据域
  struct Lnode *next;     //结点的指针域
}Lnode, *LinkList         //LinkList为指向结构体Lnode的指针类型

定义链表L: LinkList L;

定义结点指针p: *LNode p; LinkList p

单链表基本操作的实现
单链表的查找、插入、删除算法时间效率分析
  1. 查找：
    • 因线性链表只能顺序存取，即在查找时要从头指针找起，查找时间复杂度为 O(n)。
  2. 插入和删除：
    • 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
    • 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n)。
2.5.3 循环链表

循环链表：是一种头尾相接的链表 （即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）。

优点：从表中任一结点出发均可找到表中其他结点。

注意：由于循环链表中没有 NULL 指针，故涉及遍历操作时，其终止条件就不再像非循环链表那种判断 p 或 p->next 是否为空，而是判断它们是否等于头指针。
头指针表示单循环链表 \begin{cases} 找 a1 的时间复杂度： O(1) \\ 找 an 的时间复杂度： O(n)\\ \end{cases} 不方便
注意：表的操作常常是在表的收尾位置上进行
尾指针表示单循环链表 \begin{cases} a1 的存储位置是： R->next->next \\ an 的存储位置是： R\\ \end{cases} 时间复杂度:O(1)

带尾指针循环链表的合并（将Tb合并在Ta之后）

分析有哪些操作？

LinkList Connect(LinkList Ta,LinkList Tb){
                                       //假设Ta、Tb都是非空的单循环链表
  p=Ta->next;                          //①p存表头结点
  Ta->next = Tb->next->next;           //②Tb表头连结Ta表尾
  delete Tb->next;                     //③释放Tb表头结点
  Tb->next = p;                        //④修改指针
  return Tb; 
}
2.5.4 双向链表

单链表的结点→有指示后继的指针域→找后继结点方便；

即：查找某及诶单的后继结点的执行时间为O(1)。

→无指示前驱的指针域→找前驱结点难；

即：查找某结点的前驱结点的执行时间为O(n)。

定义

双链表：子啊单链表的每个结点里再增加一个指向其直接前驱的指针域 prior ,这样链表中就形成了有两个方向不同的链，故称为双向链表。

双向链表的结构可定义如下：

typedef struct DuLNode{
  Elemtype  data;
  struct DuLNode  &prior,*next;
}DuLNode,*DuLinkList;
双向循环链表

和单链的循环表类似，双向链表也可以有循环表

双向链表特性

  1. 双向链表结构的对称性（设指针 p 指向某一结点）：

    p->prior->next = p = p->next->prior

  2. 在双向链表中有些操作（如：Lis他Length、GetElem等），因仅涉及一个方向的指针，故它们的算法与线性表的相同。但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为 O(n)。

【算法2.13】双向链表的插入
void ListInsert_DuL(DuLinkList &L,Int i,ElemType e){
  //在带头结点的双向循环链表 L 中第 i 个位置之前插入元素 e
  if(!(p = GetElemP_DuL(L,i))) return ERROR;
  S = new DuLNode;
  s -> data = e;
  s -> prior = p -> prior;
  p -> prior -> next = s;
  s -> next = p;
  p -> prior = s;
  return OK;
}//ListInsert_DuL
[算法2.14] 双向链表的删除
void ListDelete_DuL(DuLink &L,Int i,ElemType &e){
  //删除带头结点的双向循环链表 L 的第 i 个元素， 并用 e 返回
   if(!(p = GetElemP_DuL(L,i))) return ERROR;
   e = p -> data;
   p -> prior = p -> next;
   p -> next -> prior = p -> prior;
  free(p);
  return OK;
}//ListDelete_DuL
单链表、循环链表和双向链表的时间效率比较
链表类型 查找表头结点（首元结点） 查找表尾结点 查找结点*p 的前驱结点
带头结点的单链表L L->next<br />时间复杂度O(1) 从L->next一次向后遍历<br />时间复杂度O(n) 通过p->next无法找到其前驱
带头结点仅设头指针L的循环单链表 L->next<br />时间复杂度O(1) 从L->next一次向后遍历<br />时间复杂度O(n) 通过p->next可以找到其前驱<br />时间复杂度O(n)
带头结点仅设尾指针R的循环单链表 R->next<br />时间复杂度O(1) R<br />时间复杂度O(1) 通过p->next可以找到其前驱<br />时间复杂度O(n)
带头结点的双向循环链表L L->next<br />时间复杂度O(1) L->prior<br />时间复杂度O(1) L->prior<br />时间复杂度O(1)

2.6 顺序表和链表的比较

链式存储结构的优点
链式存储结构的缺点
存储密度

存储密度是指节点数据本身所占的存储量和整个结构结构中所占的存储量之比，即：
存储密度 = \frac{节点数据本身占用的空间}{结点占用的空间总量}
一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1（100%），而链表的存储密度小于1。

比较
比较项目\存储结构 顺序表 链表
空间| 存储空间 预先分配，会导致空间闲置或溢出现象 动态分配，不会出现存储空间闲置或溢出现象
空间| 存储密度 不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1 需借助指针来体现元素间的逻辑关系，存储密度小于1
时间| 存取元素 随机存取，按位置访问元素的时间复杂度为O(1) 顺序存取，按位置访问元素时间复杂度为O(n)
时间| 插入、删除 平均移动约表中一半元素，时间复杂度为O(n) 不需移动元素，确定插入、删除位置后，时间复杂度为O(1)
使用情况 ①表长变化不大，且能事先确定变化的范围<br />②很少进行插入或删除操作，经常按元素位置序号访问数据元素 ①长度变化较大<br />②频繁进行插入或删除操作

2.7 线性表的应用

1.[算法2.15] 线性表的合并
void union(List &a,List Lb){
  La_len = ListLength(La);
  Lb_len = ListLength(Lb);
  for(i=1,i<=Lb_len;i++){
    GetElem(Lb,i,e);
    if(!LocateElem(La,e)) ListInsert(&La,++La_len,e);
  }
}
2.有序表的合并
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
  pa = pa->next;
  pb = pb->next;
  pc = Lc = La; //用La的头结点作为Lc的头结点
  while(pa&&pb){
    if(pa->data<=pb->data){
      pc->next = pa;
      pc = pa;
      pa = pa->next;
    }else{
      pc->next = pb;
      pc = pb;
      pb = pb->next;
    }
    pc->next = pa?pa:pb; //插入剩余段
    delete Lb; //释放Lb的头结点
  }
}

2.8 案例分析与实现

【案例2.1】一元多项式的运算：实现两个多项式加、减、乘运算
【案例2.2】稀疏多项式
【案例2.3】图书管理系统

类C语言有关操作补充

  1. C 语言的内存动态分配
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);
  1. C++ 的动态存储分配
new 类型名T （初值列表） EG:int *p1 = new int; or int *p1 = new int(10)
  功能：
     申请用于存放 T 类型对象的内存空间，并依初值列表赋以初值
  结果值：
     成功：T 类型的指针，指向新分配的内存
     失败：0 （NULL）

delete 指针P
  功能：
     释放指针 P 所指向的内存。P 必须是 new 操作的返回值
  1. C++ 中的参数传递
传值方式
传地址方式--指针变量作参数
传地址方式--数组名作参数
传地址方式--引用类型作为参数

什么是引用？？？

引用：它用来给一个对象提供一个替代的名字。

#include <iostream.h>
void main(){
  int i=5;
  int &j=i;
  i=7;
  cout<<"i="<<i<<"j="<<j;
}
//j是一个引用类型，代表 i 的一个替代名，i 值改变时，j 值也跟着改变，所以会输出i=7,j=7

引用类型做形参的三点说明

  1. 传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。

  2. 引用类型作参数，在内存中并没有产生实参的副本，它直接对实参操作；

    而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量较大时，用引用比用一般变量传递参数的时间和空间效率都好。

  3. 指针参数虽然也能达到与使用引用的效果，但在被调用函数中需要重复使用“*指针变量名” 的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。

上一篇 下一篇

猜你喜欢

热点阅读