数据结构线性表

目录

2.1 线性表的基本概念

2.2 线性表的顺序表示

2.3 线性表的链式表示

2.3.1 单链表

2.3.2 循环单链表

2.3.3 双向链表

2.3.4 双向循环链表

2.3.5 静态链表

---

牢固掌握线性表在两种存储结构下的各种基本操作，牢记各种算法思想

2.1 线性表的基本概念

·Def：线性表是具有相同特性的n(n>=0)个数据元素组成的一个有限序列，是一种逻辑结构，其中n为表长，n=0时为空表

·特点：

①表中元素具有逻辑上的顺序性，表中元素有其先后次序

②表中元素都是数据元素，每个元素都是单个元素

③表中元素的数据类型都相同，每个元素占有相同大小的存储空间

④表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容

·基本操作：

InitList(&L)：初始化表。构造一个空的线性表

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e

ListDelete(&,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值

PrintList (L)：输出操作。按前后顺序输出线性表L的所有元素值

Empty(L)：判空操作。若L为空表，则返回true,否则返回false

DestroyList (&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间

2.2 线性表的顺序表示

·顺序表：线性表的顺序存储称为顺序表，即把逻辑上相邻的数据元素存储在物理上也相邻的存储单元中的存储结构，且占用一片连续的存储空间

·顺序表的存储位置：顺序表是一种随机存取的存储结构，表中的任一数据元素都可以随机存取，假设每个元素占L个存储单元，所有元素的存储位置均可由第一个数据元素的存储位置得到: Loc(ai)=Loc(a1)+(i-1)L

·顺序表的特点：

优点：①随机访问，即通过首地址和元素序号可在时间0(1)内找到指定的元素

②存储密度高，每个结点只存储数据元素

缺点：③逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素

④静态的存储模式，拓展容量不方便，不能自由扩充

·顺序表的基本操作：

1）查找：在线性表L中查找与指定值e相同的数据元素的位置，从表一端开始，逐个对记录的关键字和给定值比较，若找到返回该元素的位置序号，若未找到返回0

int LocateElem(SqList L, int e){
   for(inti= 0;i< L.length; i++){   //查找成功，返回序号
      if(L.elem[i]==e)
      return i;
   }
   return 0;         //查找失败，返回0

最好情况：查找元素在表头，仅需比较一次， 时间复杂度为0(1)

最坏情况：查找元素在表尾(或不存在)时，需要比较n次，时间复杂度为0(n)

平均情况：假设每个元素被查找的概率相同(Pi= 1/n)，则在长度为n的线性表中查找元素所需比较的平均次数： ASL=ΣPi*Ci=1/nΣi=n+1/2

所以顺序表查找的平均时间复杂度为O(n)

2）插入：

①判断插入位置i是否合法以及表的存储空间是否已满，若已满返回ERROR

②将第n至第i位的元素依次向后移动一个位置，空出第i个位置

③将要插入的新元素e放入第i个位置，表长+1，插入成功

bool ListInsert (SqList &L, int i, ElemType e) {
  if(i<1||i>L.length+1)     //判断i的范围是否有效
    return false;
  if (L. length>=MaxSize)   //当前存储空间已满，不能插入
    return false;
  for (int j=L.length;j>=i;j--) //将第i个元素及之后的元素后移
    L.data[j]=L.data[j-1];
  L.data[i-1]=e;           //在位置i处放入e
  L. length++;              //线性表长度加1
  return true;
}

最好情况：在表尾插入(即i=n+ 1)，元素后移语句将不执行，时间复杂度为0(1)

最坏情况：在表头插入(即i= 1)，元素后移语句将执行n次，时间复杂度为O(n)

平均情况：假设在第i个位置上插入结点的概率相同(Pi= 1/(n+1))，则在长度为n的线性表插入一个结点时，移动结点的平均次数 ASL=1/(n+1)Σ(n-i+1)=1/(n+1)(n+...+1+0)=n/2

所以顺序表插入的平均时间复杂度为O(n)

3）删除

①判断删除位置i是否合法,将待删除的元素保留在e中

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

③表长减1,删除成功

bool ListDelete (SqList &L,int i, Elemtype &e) {
    if(i<1||i>L.length)        //判断i的范围是否有效
      return false;
    e=L.data[i-1];              //将被删除的元素赋值给e
    for(int j=i;j//将第i个位置后的元素前移
      L.data[j-1]=L.data[j];
    L.length--;               //线性表长度减1 
    return true;
}

最好情况：删除表尾元素(即i=n)，无须移动元素，时间复杂度为0(1)。

最坏情况：删除表头元素(即i= 1),移动除表头元素外的所有元素，时间复杂度为O(n)。

平均情况:假设删除第i个位置上结点的概率相同(Pi= 1/n)，则在长度为n的线性表中删

除一个结点所需移动结点的平均次数ASL=1/nΣ(n-i)=(n-1)/2

所以顺序表删除的平均时间复杂度为O(n)

2.3 线性表的链式表示

2.3.1 单链表

·Def：单链表表示线性表的链式存储，通过一组任意的存储单元来存储线性表中数据元素

·单链表的结点结构：每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针，其中data为数据域，next为指针域

 ·头指针与头结点：通常用头指针来标识一个单链表，当头指针L=null时表示一个空表；为了操作上的方便，在表的第一个结点之前附加一个结点称为头结点，头结点的数据域可以没有信息，指针域指向表的第一个结点

 【头结点的优点】：①无论链表是否为空，头指针都指向头结点的非空指针，空表和非空表的处理得到了统一；②由于第一个数据结点的位置存放在头结点的指针中，因此在链表的第一个位置上和在表的其他位置上的操作一致

·单链表的基本操作：

1）建立单链表

①头插法--从空表开始，生成新结点，将读取的数据存放到新结点的数据域中，再将新结点插入到当前链表的表头

【例如建立单链表abcde】：输入的次序与链表中节点的次序相反

void CreateList_H(LinkList &L, int n){
    L = new LNode;
    L->next = NULL;           //先建立一个带头节点的单链表
    for(inti= n; i>0; i--){
      p = new Lnode;          //生成新节点p=(Lnode *)nalloc(sizeof(LNode));
      cin>> p->data;           //输入元素值scanf(&p->data);
      p->next = L->next; 
      L->next= P;
    }
}

算法时间复杂度为O(n)

②尾插法--增加一个尾指针r，每读入一个元素申请一个新结点，将新结点插入尾结点后，r指向新结点，使其始终指向当前链表的尾结点

void CreateList_H(LinkList &L，int n){
    L= new LNode; L->next = NULL; //先建立一个带头节点的单链表
    r= L;                         //尾指针r指向头节点
    for(inti=0; i
      p = new Lnode;              //生成新节点p=(LNode *)malloc(sizeof(LNode));
      cin >> p->data;             //输入元素值scanf(&p->data);
      p->next = NULL;
      r->next=P;                //插入到表尾
      r= P;                     //r指向新的尾节点
    }
}

算法时间复杂度为O(n)

2）查找结点

①按序查找：从第一个结点出发，顺着指针逐个往下搜索，直到找到第i个结点，否则返回最后一个结点的指针域null，算法复杂度为O(n)

LNode *GetElem (LinkList L,int i) {
    int j=1;             //计数，初始为1
    LNode *p=L->next;    //第1个结点指针赋给p
    if(i==0)
      return L;          //若i等于0，则返回头结点
    if(i<1)
      return NULL;       //若i无效，则返回NULL
    while(p&&j//从第1个结点开始找，查找第i个结点
      p=p->next;
      j++;
      return p;           //返回第i个结点的指针，若i大于表长，则返回NULL
    }
}

②按值查找：从首结点开始，依次将给定值与各结点数据域的值比较，若相等则返回该结点的指针，若找不到则返回null，算法的时间复杂度为O(n)

LNode *LocateElem (LinkList L, ElemType e) {
     LNode *p=L->next;
     while (p!=NULL&&p->data!=e) //从第 1个结点开始查找data域为e的结点
       p=p->next;
       return P;                //找到后返回该结点指针，否则返回NULL
}

3）插入结点：将某个新结点插入到单链表的第i个位置上，先检查插入位置的合法性，查找到第i-1个结点，再插入新结点，将新结点的指针域指向第i个结点，再将第i-1个结点的指针域指向新结点，如下图：

int ListInsert_L(LinkList &L, int i, int e){
    p=L; j=0;
    while(p && j-1){          //寻找第i-1个节点
      p= p->next; j++;
    }
    if(!p||j> i-1) return 0;  //大于表长+ 1或者小于1，插入位置非法
    s=new Lnode; s->data=e; //生成新的节点s
    s->next = p->next;      //将节点s插入L中
    p->next = s;
    return 1;
}

 线性表不需要移动元素，只需修改指针，时间复杂度为O(1)；但是由于要从头查找前驱结点，所消耗的时间复杂度为O(n)

 4）删除结点：删除单链表中第i个结点，先检查删除位置的合法性，再查找表中第i-1个结点，保存要删除的结点，令第i-1个结点指针指向第i+1个结点，最后释放第i个结点的空间，算法时间复杂度与插入操作相同

Status ListDelete ( LinkList *L，int i, ElemTypet *e ){
    int j;
    LinkList p, q;
    P= *L;
    j=1;
    while (p->next && j< i){     /*遍历寻找第 1个元素*/
       p = p->next;
       ++j;
    }
    if(!(p->next)||j>i)
       return ERROR;             /*第i个元素不存在*/
    q =p->next;
    p->next = q->next;          /*将q的后继赋值给p的后继*/
    *e =q->data;                /*将q结点中的数据给e*/
    free (q) ;                  /*让系统回收此结点，释放内存*/
    return OK;
}

 5）求表长：从首结点开始，依次计数所有结点，每访问一个结点，计数+1，直到访问到空结点为止，算法复杂度为O(n)

int ListLength(LinkList L){
    LNode *p; p = L->next;
    i= 0;
    while(p != NULL){
      i++;
      p-p->next; 
    }
    return i;
}

2.3.2 循环单链表

  由于单链表在在访问过程中只能访问后继节点，不能访问前驱结点，且如果长期操作尾结点时效率较低，我们引入循环单链表

·Def：在单链表的基础上头尾相接，表中最后一个结点的指针域指向头结点，使整个链表形成一个环，此时表中没有指针域为null的结点，因此判空时判断头结点的指针是否为头指针（此判断也可作为遍历时的终止条件）

1）用头指针表示的循环单链表：寻找尾结点需要遍历整个表，时间复杂度为O(n)

2）用尾指针表示的循环单链表：设置尾指针后，头指针即为r->next，对表头表尾的操作均为O(1)，操作效率大大提高 

2.3.3 双向链表

  循环单链表虽然实现了从任一结点出发沿链能找到q其他前驱结点，但是时间仍为O(n)，因此我们为结点设置两个指针域，一个指向前驱，一个指向后继，这样的链表就是双链表

·基本操作：双向链表的查找与单链表相同，在插入与删除上与单链表有较大不同，双链表可以很方便的找到结点的前驱后继，因此插入删除操作的时间复杂度均为O(1)

1）插入：在p所指结点后插入结点s

 【注】：语句顺序不唯一，但是由于①②两步均需要用到p->next，要保证p的后继结点指针不掉，①②两步必须在④之前完成

2）删除：删除p结点的后继结点q

2.3.4 双向循环链表

  对于双向链表来说，当访问到尾结点时，想要访问首结点又需要向前依次遍历，这又让效率降低了，所以在循环单链表的基础上，同样设置双向循环链表

·Def：在双向链表的基础上，让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点

2.3.5 静态链表

·Def： 静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址( 数组下标)，又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间，其插入删除操作与动态链表相同，只需要修改指针不需要移动元素，但总的来说没有单链表使用起来方便

 【总结】：