数据结构|Chapter2：线性表

Posted on | In , | |

摘要：本文是第二章线性表的笔记。线性表是最基本、最简单、也是最常用的一种数据结构。

线性结构

  • 存在唯一的首位元素a1
  • 存在唯一的末位元素an
  • ai+1是ai的直接后继（1<i<=n）
  • ai-1是ai的直接前驱（1<=i<n）

线性表的定义

线性表的逻辑结构

1.线性表：由n个类型相同的数据元素（a1，a2,…,an）构成的有限序列。记作L = （a1，a2,…,an）。
2.表长（表的长度）：线性表中数据元素的数目。
3.空表：不含数据元素的线性表。

抽象数据类型的线性表

  • ADT：三元组，包括数据对象，数据关系，基本操作。

ADT List
{ 数据对象：D={ai|ai∈ElemSet,i=1,2,,…n,n>=0}
数据关系：R1={| ai-1,ai∈D,i=2,,…n}
基本操作：
1.IniList(&L) //构造空表L。
2.DestroyList(&L) //销毁线性表L
3.ClearList(&L) //置L为空表
4.ListEmpty(L) //判断L是否为空表
5.ListLength(L) //求表L的长度
6.GetElem(L,i,&e) //取元素ai,由e返回ai
7.LocateElem(L,e,compare()) //查找符合条件的元素
8.ListInsert(&L,i,e) //元素ai之前插入新元素e
9.ListDelete(&L,i,&e) //删除第i个元素
10.DeleteElem(&L,x) //删除元素值为x的元素
… … }ADT List

btw:为什么有的在L前加了&而有的没加：当操作对线性表或其中的元素作了修改，则是&L；若无修改，则为L。

  • 定义：一个数学模型以及定义在该模型上的一组操作。
  • 作用：抽象数据类型可以使我们更容易描述现实世界。
  • 关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

操作

  • 基本操作
  • 可利用基本操作组成更复杂的操作

    EG.将线性表Lb中的且不在线性表La中的数据元素合并到La中。 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //算法：判断两个线性表的长度——用循环结构将符合条件的元素插入La中（判断Lb中的每个元素是否在La中，不在的话就插入）        
    void union(List &La, List &Lb) //合并线性表 
    {
        La_len = ListLength(La); 
        Lb_len = ListLength(Lb);    
        for (i=1;i<=Lb_len;i++) 
        {
            GetElem(Lb,i,e) //取Lb的第i个数据元素赋给e；即依次取出所有Lb中的元素    
            if(!LocateElem(La,e,equal)) 
              ListInsert(La,++La_len,e); //判断e在La中是否存在，不存在则插入
        }
    }

线性表的顺序表示

  • 顺序分配：将线性表中的元素依次存放到计算机存储器中一组连续地址的存储单元中，这种分配方式称为顺序分配或顺序映像。由此得到的存储结构称为顺序存储结构或向量(一维数组）。

    一般形式：i——an——存储地址：LOC(i) = b+（i-1） p （1<=i<=n）
    b：表的首地址/元素a1的地址；
    p：1个数据元素所占存储单元的数目；
    maxleng：最大长度，为某个常数 [序号maxleng——存储地址：b+(maxleng-1)    p]

  • 顺序访问

  • 随机访问
  • 线性表顺序结构在C语言中的定义（静态分配）? 
1
2
3
4
5
6
7
8
9
10
11
12
#define maxleng 100    
typedef struct         
  { ElemType elem[maxleng]；//下标:0,1,...,maxleng-1   
    int length；            //表长 
   } SqList；  
  SqList La；  
   ..........  
 其中：typedef---别名定义，SqList----结构类型名    
       La----结构类型变量名    
       La.length---表长    
       La.elem[0]----a1    
       La.elem[La.length-1]---an
  • 线性表顺序结构在C语言中的定义（动态分配）? 
1
2
3
4
5
6
7
8
9
10
11
12
 #define LIST_INIT_SIZE 100 
 #define LISTINCREMENT 10       
 typedef struct         
   { ElemType *elem；//存储空间基地址   
     int length；    //表长 
     int listsize;   //当前分配的存储容量   
                     //（以sizeof(ElemType)为单位   
    } SqList；  
   SqList Lb；  
其中：   typedef--别名定义，   SqList---结构类型名          
         Lb---结构类型变量名   Lb.length---表长     
         Lb.elem[0]---a1       Lb.elem[Lb.length-1]--an

插入算法的实现举例

1.插入操作移动元素次数分析：
在（a1,a2,…,ai,…an)中ai之前插入新元素e
当插入点为： 1 2 … i … n n+1
需移动元素个数: n n-1 … n-i+1 … 1 0
则插入一个元素时移动元素的平均值是：
n+1
Eis=∑pi(n-i+1)=[1/(n+1)]*(n+(n-1)+…+1+0)=n/2
i=1
注：算法时间复杂度为O(n)

2.删除操作及移动元素次数的分析：
将元素ai删掉，并得到删除后的线性表 

1
2
3
4
5
6
7
8
9
//算法：先判断元素ai的合法性——若不合法则返回Error/若合法则继续——定位ai元素（在第i-1号地址）并赋给变量e——用循环结构将ai后的所有元素往前挪一位（共L.length-1个元素；赋值法）
int ListDelete_Sq(SqList  &L,int I,ElemType &e)     
{if (i<1 || i>L.length)     
          return ERROR; 
 e=L.elem[i-1]; 
 for(j=i;j<=L.length-1;j++) 
	 L.elem[j-1]=L.elem[j]; 
 L.length--;  return OK;    
}

移动元素个数= n-1 n-2 … n-i … 0
假定qi是在各位置删除元素的概率，且：q1=q2=…=qn=1/n
则删除一个元素时移动元素的平均值是:
n
Edl=∑qi(n-i)=1/n*((n-1)+…+1+0)=(n-1)/2
i=1
注：算法时间复杂度为O(n)

顺序结构的评价

优点：

  • 随机存取结构，存取任何元素的时间都是一个常数，速度快
  • 结构简单，元素逻辑相邻也物理相邻
  • 不适用指针，节省存储空间

缺点：

  • 插入和删除元素需要移动大量元素，消耗时间
  • 需要一个连续的存储空间
  • 插入元素可能发生“溢出”
  • 自由区中的存储空间不能被其他数据占用/共享

线性表的链式存储结构

单链表

1.单链表的一般形式

  • 不带表头结点的单链表：在首节点前无头结点的单链表
  • 带表头结点的单链表：在首节点有无头结点的单链表

    1.头结点：在单链表的第一个结点之前附设的一个结点。头结点的数据域可以不存储任何信息，其指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。作用是使所有链表（包括空表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他位置的插入、删除操作一致。[头结点的指针域指向首节点的指针从而使此指针非空]

    2.链表的结点结构：
    ┌───┬───┐
    │data │next │
    └───┴───┘
    data域—存放结点值的数据域
    next域—存放结点的直接后继的地址（位置）的指针域（链域）
    单链表逻辑结构

Thanks!