线性表及其实现

本篇回顾数据结构中最常见的数据结构之一 线性表。
主要包含如下内容:

• 线性表的描述和特点
• 线性表的抽象数据类型描述
• 线性表的顺序存储实现
• 线性表的链式存储实现

---

什么是线性表

线性表的描述和特点

一种逻辑结构，相同数据类型的n个数据元素的有限序列，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的特点：

（1）元素个数有限 （2）逻辑上元素有先后次序

（3）数据类型相同 （4）仅讨论元素间的逻辑关系

注：线性表是逻辑结构，顺序表和链表是存储结构。

“线性表(Linear List)”：由同类型 数据元素 构成有序序列的线性结构

 表中元素个数称为线性表的长度

 线性表没有元素时，称为空表

 表起始位置称表头，表结束位置称表尾

线性表的抽象数据类型描述

类型名称：线性表（List）

数据对象集：线性表是 n (≥0)个元素构成的有序序列( a1, a2, …,an )

操作集：线性表L ∈ List，整数i表示位置，元素X ∈ ElementType，
线性表基本操作主要有：

1. List MakeEmpty()：初始化一个空线性表L；
2. ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ；
3. int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；
4. void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；
5. void Delete( int i, List L )：删除指定位序i的元素；
6. int Length( List L )：返回线性表L的长度n。

线性表的顺序存储实现

利用数组的 连续存储空间顺序存放 线性表的各元素 —- 顺序表

typedef struct LNode *List;
struct LNode
{
    ElementType Data[MAXSIZE];
    int Last;
} ;
struct LNode L;
List PtrL;

访问下标为 i 的元素：L.Data[i] 或 PtrL->Data[i]
线性表的长度：L.Last+1 或 PtrL->Last+1

主要操作的实现

• 初始化（建立空的顺序表）

  List MakeEmpty()
  {
      List PtrL;
      PtrL = (List)malloc(sizeof(struct LNode))
      PtrL->Last = -1;
  
      return PtrL;
  }

• 查找

  int Find(ElementType X, List PtrL)
  {
      int i = 0;
      while(i <= PtrL->Last && PtrL->Data[i] != X)
      {
          i++;
      }
  
      if(i > PtrL->Last)
      {
          return -1; //如果没有找到，返回-1
      }
      else
      {
          return i; //找到后返回存储的位置
      }
  }

• 插入（第 i (1≤i≤n+1)个位置上插入一个值为X的新元素)

  void Insert( ElementType X, int i, List PtrL)
  {
      int j;
      if ( PtrL->Last == MAXSIZE-1 )
      {
          printf(＂表满＂);
          return;
      }
  
      if(i < 1 || i > PtrL->Last+2)
      {
          printf(＂位置不合法＂);
          return;
      }
  
      for(j = PtrL->Last; j > i-1; j--)
      {
          //将 ai～ an倒序向后移动
          PtrL->Data[j+1] = PtrL->Data[j];
      }
      PtrL->Data[i-1] = X; //新元素插入
      PtrL->Last++; //Last仍指向最后元素
      
      return;
   }

• 删除（删除表的第 i (1≤i≤n)个位置上的元素)

  void Delete( int i, List PtrL )
  {
      int j;
      if( i < 1 || i > PtrL->Last+1 )
      { /*检查空表及删除位置的合法性*/
          printf (“不存在第%d个元素”, i );
          return ;
      }
      for ( j = i; j <= PtrL->Last; j++ )
      {
          PtrL->Data[j-1] = PtrL->Data[j]; /*将 ai+1～ an顺序向前移动*/
      }
      PtrL->Last--; /*Last仍指向最后元素*/
      return;
  }

线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻； 通过“链”建立起数据元素之间的逻辑关系。

• 插入、删除不需要移动数据元素，只需要修改“链”。

typedef struct LNode *List;
struct LNode
{
    ElementType Data;
    List Next;
};
struct Lnode L;
List PtrL;

主要操作的实现

• 求表长

  int Length ( List PtrL )
  {
      List p = PtrL;
      int j = 0;
      while ( p )
      {
          p = p->Next;
          j++;
      }
  
      return j;
  }

• 查找
  按序号查找: FindKth;

List FindKth( int K, List PtrL )
{
    List p = PtrL;
    int i = 1;
    while (p !=NULL && i < K )
    {
        p = p->Next;
        i++;
    }
    if ( i == K ) 
        return p;
    else 
        return NULL;
       /* 否则返回空 */
} 

按值查找: Find

List Find( ElementType X, List PtrL )
{
    List p = PtrL;
    while ( p!=NULL && p->Data != X )
        p = p->Next;
    return p;
}

• 插入（在第 i-1(1≤i≤n+1)个结点后插入一个值为X的新结点)

  （1）先构造一个新结点，用s指向；

  （2）再找到链表的第 i-1个结点，用p指向；

  （3）然后修改指针，插入结点 ( p之后插入新结点是 s)

• 插入操作实现

  List Insert( ElementType X, int i, List PtrL )
  {
      List p, s;
      if ( i == 1 )
      { 
          /* 新结点插入在表头 */
          s = (List)malloc(sizeof(struct LNode)); /*申请、填装结点*/
          s->Data = X;
          s->Next = PtrL;
          return s; /*返回新表头指针*/
      }
      p = FindKth( i-1, PtrL ); /* 查找第i-1个结点 */
      if ( p == NULL )
      {
          /* 第i-1个不存在，不能插入 */
          printf(＂参数i错＂);
          return NULL;
      }
      else
      {
          s = (List)malloc(sizeof(struct LNode)); /*申请、填装结点*/
          s->Data = X;
          s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/
          p->Next = s;
          return PtrL;
      }
  }

• 删除（删除链表的第 i (1≤i≤n)个位置上的结点)

  （1）先找到链表的第 i-1个结点，用p指向；

  （2）再用指针s指向要被删除的结点（p的下一个结点）;

  （3）然后修改指针，删除s所指结点;

  （4）最后释放s所指结点的空间。

• 删除操作实现

  List Delete( int i, List PtrL )
  {
      List p, s;
      if ( i == 1 )
      {
          /* 若要删除的是表的第一个结点 */
          s = PtrL; /*s指向第1个结点*/
          if (PtrL!=NULL)
              PtrL = PtrL->Next; /*从链表中删除*/
          else
              return NULL;
          free(s); /*释放被删除结点 */
          return PtrL;
      }
      p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/
      if ( p == NULL )
      {
          printf(“第%d个结点不存在”, i-1);
          return NULL;
      }
      else if ( p->Next == NULL )
      {
          printf(“第%d个结点不存在”, i);
          return NULL;
      }
      else
      {
          s = p->Next; /*s指向第i个结点*/
          p->Next = s->Next; /*从链表中删除*/
          free(s); /*释放被删除结点 */
          return PtrL;
   }
  }

---

参考资料

[浙江大学PTA]

[浙江大学数据结构公开课]