程序员慕虎

2022-09-13 13:39 已编辑第一拖拉机制造厂拖拉机学院 Java 发布于浙江

关注

我打开了封印多年的数据结构C语言笔记——线性表

数据结构与算法极速入门系列其他文章

数据结构与算法极速入门系列（更新ing）

线性表

线性表的概念

线性表(Linear List)是由n(n≥0)个数据元素(结点)a1,a2,……,an组成的有限序列。

线性表的顺序存储

指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。
即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
采用顺序存储结构的线性表通常称为顺序表。
假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以计算出第i个元素的地址loc(ai)：
loc(ai) =loc(a1)+(i-1)×k
其中loc(a1) 称为基址。

顺序存储结构的C语言定义

#define maxsize=线性表可能达到的最大长度；
typedef  struct
{/* 线性表占用的数组空间。*/
 ElemType  elem[maxsize];
 /*记录线性表中最后一个元素在数组elem[ ]中
 的位置(下标值),空表置为-1*/
 int  last;
}SeqList;

初始化操作

线性表的初始化即构造一个空表，步骤为先定义一个指向该类型线性表的指针，然后为该指针指向的内存动态分配存储空间，然后对该内存中的线性表初始化赋值。

/*初始化顺序表*/ 
SeqList *init_SeqList()
{
    SeqList *L;
    L=malloc(sizeof(SeqList));
    L->last=-1;
    return L;
}

插入操作

线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表 (e1，…，ei-1，ei，…，en) 变成长度为n+1的线性表(e1，…,ei-1，e，ei，…，en)。

用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将原表中位置n， n-1，…， i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点e。
当i=n+1时，是指在线性表的末尾插入结点，所以无需移动结点，直接将e插入表的末尾即可。

int  InsList(SeqList *L,int i,ElemType e) 
{
 int k;
 if( (i<1) || (i>L->last+2) )//首先判断插入位置是否合法
    {printf(“插入位置i值不合法”)；return(ERROR);}
 if(L->last>=maxsize-1) 
    {printf(“表已满无法插入”)；return(ERROR);}
 for(k=L->last;k>=i-1;k--) //为插入元素而移动位置
    L->elem[k+1]=L->elem[k]; 
    L->elem[i-1]=e; //C语言数组第i个元素下标为i-1
    L->last++;
 return(OK); 
}

删除操作

线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表 (e1，…,ei-1，ei，ei+1，…，en)，变成长度为n-1的线性表(e1，…,ei-1， ei+1，…，en)。

在顺序表上实现删除运算也必须移动结点，这样才能反映出结点间的逻辑关系的变化。
若i=L->last+1，则移位语句L->elem［k-1］= L->elem［k］不执行，因为循环变量的初值大于终值，此时不需要移动元素，仅将表长度减1即可。
显然，删除算法中移位语句L->elem［k-1］= L->elem［k］的执行频度也与删除位置i有关。

int  DelList(SeqList *L,int i,ElemType *e)
 //删除顺序表L中第i个元素,并用指针参数e返回其值
{
int k;
  if((i<1)||(i>L->last+1)) {
    printf(“删除位置不合法！”);
    return(ERROR);
  } 
  *e= L->elem[i-1]; //将删除的元素存放到e所指向的变量中   
 for(k=i;i<=L->last;k++)     
     L->elem[k-1]= L->elem[k];//后面的元素依次前移

 L->last--;
 return(OK); 
}

查找操作-按序号查找

按序号查找GetData(L,i)

要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]或L->elem[i-1]。

查找操作-按值查找

要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。

int  Locate(SeqList L，ElemType e) 
{ 
    i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ 
    while ((i<=L.last)&&(L.elem[i]!=e) )    
        i++; 
    /*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/ 
    if  (i<=L.last) 
           return(i);  /*若找到值为e的元素，则返回其序号*/ 
    else 
       return(-1);  /*若没找到，则返回空序号*/
}

合并算法

已知：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。

设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素
若LA.elem[i]>LB.elem[j]，则当前先将LB.elem[j]插入到表LC中
若LA.elem[i]≤LB.elem[j] ，当前先将LA.elem[i]插入到表LC中
如此循环，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。

void merge(SeqList *LA,  SeqList *LB,  SeqList *LC) 
{
  i=0;j=0;k=0;
  while(i<=LA->last&&j<=LB->last)
      if(LA->elem[i]<=LB->elem[j]) 
         {LC->elem[k]= LA->elem[i]; i++; k++;} 
      else
         {LC->elem[k]=LB->elem[j];j++; k++;}

  while(i<=LA->last)    //当LA长,则将表LA余下元素赋给表LC
     {LC->elem[k]= LA->elem[i];i++;k++;}
  while(j<=LB->last)  //当LB长,则将表LB余下的元素赋给表LC   {LC->elem[k]= LB->elem[j];j++;k++;}
   LC->last=LA->last+LB->last; 
}

顺序存储结构的优缺点

优点

无需为表示结点间的逻辑关系而增加额外的存储空间；
可方便地随机存取表中的任一元素。

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

线性表的链式存储

链表的定义与分类

链表定义

采用链式存储结构的线性表称为链表(Linked list)。

除第一个元素外，其他每一个元素有且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有且仅有一个直接后继。

从链接方式的角度看，链表可分为

单链表
循环链表
双链表

单链表

结点(Node)

为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。

带头结点的单链表

带头结点的空单链表

单链表的存储结构描述

typedef struct Node / * 结点类型定义 * / 
{
 ElemType data;
 struct Node  * next;
}Node, *LinkList; /* LinkList为结构指针类型*/

建立单链表

头插法建表
算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。

Linklist  CreateFromHead() //带头结点的//
{
    LinkList   L;  Node  *s; int flag=1; 
    //设置标志,初值为1,当输入“$”时,flag为0,建表结束
    L=(Linklist)malloc(sizeof(Node));//为头结点分配空间
    L->next=NULL; 
    while(flag) 
    {
          c=getchar();
          if(c!='$') //为读入的字符分配存储空间
             {s=(Node*)malloc(sizeof(Node)); 
             s->data=c;s->next=L->next; L->next=s;} 
          else 
             flag=0;
    }
}

尾插法建表

Linklist  CreateFromTail() 
{
     LinkList L;  Node *r, *s;  int   flag =1; 
     L=(Node *)malloc(sizeof(Node));//为头结点分配空间
     L->next=NULL; r=L; //r指针始终动态指向链表的当前表尾
     while(flag) //输入“$”时flag为0，建表结束
      { 
         c=getchar(); 
         if(c!=’$’) {
               s=(Node*)malloc(sizeof(Node)); 
               s->data=c;
               r->next=s;
               r=s;
         }else{
             flag=0;
             r->next=NULL; 
         }
      }
}

按序号查找算法

按序号查找
算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（pL->next），用j做记数器，累计当前扫描过的结点数（初值为0），当j = i 时，指针p所指的结点就是要找的第i个结点。

//在带头结点的单链表L中查找第i个结点,若找到(1≤i≤n),则返回该结点的存储位置;否则返回NULL
Node *Get(LinkList  L, int i) 
{
 Node  *p;
 p=L; j=0; //从头结点开始扫描 
 while ((p->next!=NULL)&&(j<i) 
  {
   p=p->next; //扫描下一结点
   j ++; //已扫描结点计数器}
   if (i==j) 
     return p;   //找到了第i个结点 
   else  
    return NULL;//找不到，i≤0或i>n
}

单链表查找

按值查找
算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。

//在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL 
Node *Locate(LinkList L,ElemType key) 
{
 Node *p; p=L->next; //从表中第一个结点比较 
 while (p!=NULL) 
    if (p->data!=key)
        p=p->next;
   else  
        break; //找到结点key，退出循环 
 return p;
}

单链表插入操作

算法描述
要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。

void InsList(LinkList L,int i,ElemType e) {
    //在带头结点的单链表L中第i个结点之前插入值为e的新结点。 
    Node *pre,*s;  pre=L; int  k=0; 
    while(pre!=NULL&&k<i-1) 
    //找到第i-1个数据元素的存储位置,使指针Pre指向它
    {
     pre=pre->next; k=k+1;
    }
    if(k!=i-1)
    {
     printf(“插入位置不合理！”);return;
    } 
     s=(Node*)malloc(sizeof(Node)); //为e申请新的结点
     s->data=e; //将待插入结点的值e赋给s的数据域
     s->next=pre->next; pre->next=s;
}

单链表删除

算法描述
欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。

//在带头结点的单链表L中删除第i个元素，并保存其值到变量*e中 
void DelList(LinkList L,int i,ElemType *e) 
{
   Node *p,*r; p=L; int k =0; //寻找被删除结点i的前驱
   while(p->next!=NULL&&k<i-1)
    {p=p->next; k=k+1; } 
   if(k!=i-1) //即循环是因为p->next=NULL而跳出的
    {
       printf(“所删结点位置i不合理”);
       return ERROR;
    }
    r=p->next; 
    p->next=p->next->next; //删除结点r
   free(r); //释放被删除的结点所占的内存空间
}

循环链表

循环链表是一个首尾相接的链表。将单链表最后一个结点指针域由NULL改为指向头结点或线性表中的第一个结点，得到的单链形式循环链表称为循环单链表。

循环单链表合并为一个循环单链表

已知
有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。
算法思想
先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结点。

LinkList   merge_1(LinkList LA,LinkList LB) //将两个链表的首尾连接起来
{
 Node *p, *q; p=LA; q=LB; 
 while (p->next!=LA) p=p->next; //找到表LA的表尾
 while (q->next!=LB) q=q->next; //找到表LB的表尾
 q->next=LA;//修改表LB 的尾指针，使之指向表LA 的头结点
 p->next=LB->next;//修改表LA的尾指针，使之指向表LB 中的第一个结点
 free(LB); 
 return(LA);
}

双向链表

双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链。

双向链表的结构定义

typedef struct DNode
{
    ElemType data；
    struct DNode * prior,*next；
}DNode, *DoubleList；

双向链表的前插操作

void DlinkIns(DoubleList L,int i,ElemType e)
{
  DNode  *s,*p; 
  … /*首先检查待插入的位置i是否合法*/
  … /*若位置i合法，则让指针p指向它*/
  s=(DNode*)malloc(sizeof(DNode)); 
  if (s) 
   {
        s->data=e; 
        s->prior=p->prior; p->prior->next=s; 
        s->next=p; p->prior=s; return TRUE;
   }  
  else 
      return FALSE;
}

双向链表的删除操作

int DlinkDel(DoubleList L,int i,ElemType *e) 
  {
    DNode  *p; 
    … /*首先检查待插入的位置i是否合法*/ 
    … /*若位置i合法，则让指针p指向它*/ 
    *e=p->data; 
    p->prior->next=p->next; 
    p->next->prior=p->prior; 
    free(p); 
    return TRUE;
  }

顺序表和链表的比较

基于空间的考虑

当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构较好。

顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。若线性表的长度n变化较大，则存储规模难于预先确定。
在静态链表中，初始存储池虽然也是静态分配的，但若同时存在若干个结点类型相同的链表，则它们可以共享空间，使各链表之间能够相互调节余缺，减少溢出机会。
动态链表的存储空间是动态分配的，只要内存空间尚有空闲，就不会产生溢出。

顺序表的存储密度为1，而链表的存储密度小于1。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。
所谓存储密度(Storage Density)是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即：存储密度=结点数据本身所占的存储量/结点结构所占的存储总量。
一般地，存储密度越大，存储空间的利用率就高。在链表中的每个结点，除了数据域外，还要额外设置指针（或光标）域，从存储密度来讲，这是不经济的。

基于时间的考虑

若线性表的操作主要是进行查找，很少做插入和删除时，采用顺序表做存储结构为宜。

顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O (1) 时间内直接地存取；
链表中的结点，需从头指针起顺着链找才能取得。

对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
在链表中的任何位置上进行插入和删除，都只需要修改指针。
在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销相当可观。

#数据结构##C/C++##算法#