【原】数据结构——线性表的顺序表示与实现（顺序表）

流楚丶格念 2022-01-14

展开全文

文章目录

线性结构的定义：

若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
可表示为：（a1 , a2 , ……, an）

线性表

线性结构表达式：（a1 , a2 , ……, an）
线性结构的特点：
① 只有一个首结点和尾结点；
② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。
简言之，线性结构反映结点间的逻辑关系是一对一的
线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是线性表

一、线性表的定义和特点

线性表的定义：用数据元素的有限序列表示
在这里插入图片描述

例1 分析26 个英文字母组成的英文表

（ A,  B,  C,  D, ……  ,  Z）
  数据元素都是字母;     
  元素间关系是线性

例2 分析学生情况登记表

在这里插入图片描述
数据元素都是记录；
元素间关系是线性
同一线性表中的元素必定具有相同特性

顺序存储结构存在问题

存储空间分配不灵活
运算的空间复杂度高

总结

线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体
应用单独编写一个程序。
从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作

二、线性表的顺序表示和实现

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

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单
元中的存储结构。
简言之，逻辑上相邻，物理上也相邻

顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，
可通过数组V[n]来实现。

在这里插入图片描述

顺序表的类型定义


#define  MAXSIZE 100     // 最大长度
typedef  struct 
{
  ElemType  *elem;     // 指向数据元素的基地址
  int  length;          // 线性表的当前长度                                                      
 }SqList；

线性表的重要五大基本操作

1、初始化线性表L （参数用引用）

Status InitList_Sq(SqList &L)//构造一个空的顺序表L
{        
    L.elem=new ElemType[MAXSIZE];   //为顺序表分配空间
    if(!L.elem) 
    exit(OVERFLOW);       //存储分配失败
    L.length=0;//空表长度为0
    return OK;
}

1、初始化线性表L （参数用指针）

Status InitList_Sq(SqList *L)  //构造一个空的顺序表L
{    
    L-> elem=new ElemType[MAXSIZE];   //为顺序表分配空间
    if(! L-> elem) exit(OVERFLOW);       //存储分配失败
    L-> length=0;              //空表长度为0
    return OK;
}

2、销毁线性表L

void DestroyList(SqList &L)
{
  if (L.elem) delete[]L.elem;    //释放存储空间
}

3、清空线性表L

void ClearList(SqList &L) 
{
   L.length=0;                //将线性表的长度置为0
}

4、求线性表L的长度

int GetLength(SqList L)
{   
return (L.length);             
}

5、判断线性表L是否为空

int IsEmpty(SqList L)
{  
if (L.length==0) 
return 1;      
   else 
   return 0;
}

取值操作

（根据位置i获取相应位置数据元素的内容）
获取线性表L中的某个数据元素的内容

int GetElem(SqList L,int i,ElemType &e)
{  if (i<1||i>L.length) 
return ERROR;   
   //判断i值是否合理，若不合理，返回ERROR
   e=L.elem[i-1];   //第i-1的单元存储着第i个数据
   return OK;
}

查找操作

在这里插入图片描述

// 在线性表L中查找值为e的数据元素
int LocateELem(SqList L,ElemType e)
{
      for (i=0;i< L.length;i++)
          if (L.elem[i]==e) 
          return i+1;                
      return 0;
}

插入操作(插在第i个结点之前)

在这里插入图片描述

算法步骤

（1）判断插入位置 i 是否合法。

（2）判断顺序表的存储空间是否已满。

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

（4）将要插入的新元素e放入第i个位置。

（5）表长加1，插入成功返回OK。

// 在线性表L中第i个数据元素之前插入数据元素e 
Status ListInsert_Sq(SqList &L,int i ,ElemType e)
{
   if(i<1 || i>L.length+1) return ERROR;           // i值不合法
   if(L.length==MAXSIZE) return ERROR;    // 当前存储空间已满     
   for(j=L.length-1;j>=i-1;j--) 
       L.elem[j+1]=L.elem[j];    //插入位置及之后的元素后移
    L.elem[i-1]=e; //将新元素e放入第i个位置
  ++L.length;     //表长增1
  return OK;
}

5.删除操作(删除第i个结点)

在这里插入图片描述

算法步骤

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

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

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

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

// 将线性表L中第i个数据元素删除
Status ListDelete_Sq(SqList &L,int i)
{
   if((i<1)||(i>L.length))
    return ERROR; // i值不合法
   for (j=i;j<=L.length-1;j++)                   
　  　L.elem[j-1]=L.elem[j];       // 被删除元素之后的元素前移  
   --L.length;                   // 表长减1
  return OK;
}