数据结构--线性表

发表于 | 分类于 | | 热度: °C
字数统计: 4,646 | 阅读时长 ≈ 18

线性表、栈、队列、串和数组都属于线性结构。线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继之外，其他每个数据都有一个前驱和后继。线性表是最基本且最常用的一种线性结构，同时也是其他数据结构的基础。

1.线性表的定义和特点

在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表：(A,B,C,…,Z)是一个线性表，表中的数据元素是单个字母。

诸如此类由n个数据特性相同的元素构成的有限序列称为线性表.

线性表中元素的个数n (n>=0) 定义为线性表的长度，n=0时称为空表。

对于非空的线性表或线性结构，其特点是:

  • 存在唯一的一个被称作“第一个”的数据元素;
  • 存在唯一的一个被称作“最后一个”的数据元素;
  • 除第一个之外，结构中的每个数据元素均只有一个前驱;
  • 除最后一个之外，结构中的每个元素均只有一个后继。

2.线性表的顺序表示和实现

2.1 线性表的顺序储存表示

线性表的顺序表示指的是用一组地址连续的储存单元依次储存线性表的数据元素，这种表示也称作线性表的顺序储存结构或顺序映像。通常，称这种储存结构的线性表为顺序表。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。

线性表的顺序储存结构是一种随机存取的储存结构。通常都用数组来描述数据结构中的顺序储存结构。

2.2 顺序表中基本操作的实现

1.初始化

顺序表的初始化操作就是构造一个空的顺序表。

算法2.1 顺序表的初始化

[步骤]

  • 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
  • 将表的当前长度设为0.

[描述]

1
2
3
4
5
6
7
Status InitList(SqList &L)
{//构造一个空的顺序表L
  L.elem = new ElemType[MAXSIZE];     //为顺序表分配一个大小为MAXSIZE的数组空间
  if(!L.elem) exit(OVERFLOW);         //储存分配失败退出
  L.length=0;                         //空表长度为0
  return ok;
}

动态分配线性表的储存区域可以更有效地利用系统的资源，当不需要该线性表时，可以使用销毁操作及时释放占用的储存空间。

2.取值

取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值。

由于顺序储存结构具有随机存取的特点，可以直接通过数组下标定位得到，elem[i-1] 单元存储第i 个数据元素。

算法2.2 顺序表的取值

[算法步骤]

  • 判断指定的位置序号i值是否合理(1=<i<=L.length), 若不合理，则返回ERROR。
  • 若i值合理，则得到第i个数据元素L.elem[i-1]赋给参数e,通过e返回第i个数据元素的传值。

[算法描述]

1
2
3
4
5
6
Status GetElem(SqList L,int i, ElemType &e)
{
  if(i<1||i>L.length) return ERROR;      //判断i是否合理
  e=L.elem[i-1];                         //elem[i-1] 单元储存第i个数据元素
  return OK;
}

时间复杂度为 O(1)

3.查找

查找操作是根据指定的元素值e，查找顺序表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0.

算法 2.3 顺序表的查找

[算法步骤]

  • 从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i], 则查找成功，返回该元素的序号i+1.
  • 若查遍整个顺序表都没有找到，则查找失败，返回0.

[算法描述]

1
2
3
4
5
6
int LocateElem(SqList L, ElemType e)
{//在顺序表L中查找值为e的数据元素，返回其序号
  for(i=0;i<L.length;i++)
    if(L.elem[i]==e)  return i+1;  //查找成功，返回序号i+1
  return 0;                         //查找失败，返回0
}

时间复杂度为 O(n)

4.插入

线性表的插入操作是指在表的第i个位置插入一个新的数据元素e,使长度为n的线性表变成长度为n+1的线性表。一般情况下，在第i(1<=i=<n)个位置插入一个元素时，需从最后一个元素即第n个元素开始，依次向后移动一个位置，直至第i个元素(共n-i+1个元素).

算法2.4 顺序表的插入

[算法步骤]

  • 判断插入位置i是否合法(i值的合法范围是1<=i=<n+1),若不合法则返回ERROR。
  • 判断顺序表的存储空间是否已满，若满则返回ERROR。
  • 将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i=n+1时无需移动).
  • 将要插入的新元素e放入第i个位置。
  • 表长加1。

[算法描述]

1
2
3
4
5
6
7
8
9
10
Status ListInsert(SqList &L,int i, ElemType e)
{//在顺序表L中第i个位置插入新的元素e,i值的合法范围是1=<i<=L.length+1
  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;
}

时间复杂度为 O(n)

5.删除

线性表的删除操作是指将表的第i个元素删去，将长度为n的线性表变成为n-1的线性表。一般情况下，删除第i（1=<i<=n)个元素时需将第i+1 个至第n个元素(共n-i个元素） 依次向前移动一个位置（i=n时无需移动）。

算法 2.5 顺序表的删除

[算法步骤]

  • 判断删除位置i是否合法（合法值为 1<=i<=n_,若不合法则返回ERROR。
  • 将第 i+1 个至第n个的元素依次向前移动一个位置(i=n 时无需移动)。
  • 表长减1.

[算法描述]

1
2
3
4
5
6
7
8
Status ListDelete(SqList &L,int i)
{  //在顺序表L中删除第i个元素，i值的合法范围是 1<=i<=L.length
  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
  rturn OK;
}

时间复杂度为 O(n)

3.线性表的链式表示和实现

3.1单链表的定义和表示

线性表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。因此，为了表示每个数据元素 ai与其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为 结点 (node)。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点链结成一个链表。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。



用单链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻。

单链表可由头指针唯一确定

在C语言中可用“结构指针”来描述：

1
2
3
4
5
6
//--------单链表的存储结构------------
typedef struct LNode
{
  ElemType data;               //结点的数据域
  struct LNode *next;          //结点的指针域
}LNode, *LinkList;             // LinkList为指向结构体LNode的指针类型

为了提高程序的可读性，在此对同一结构体指针类型起了两个名称，LinkList与LNode,两者本质上是等价的。通常习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针；用LNode 定义指向单链表中任意结点的指针变量。例如，若定义LinkList L,则L为单链表的头指针，若定义LNodep ，则P为指向单链表中某个结点的指针，用p代表该结点。当然也可一使用定义LinkList p，这种定义形式完全等价于LNode p.
注意区分指针变量和结点变量两个不同的概念，若定义LinkList p或LNode p,则p为指向某结点的指针变量，表示该结点的地址；而*p为对应的结点变量，表示该结点的名称。

一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称为头结点。

(1) 首元结点是指链表中存储第一个数据元素a1的结点。
(2) 头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。
(3) 头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所值结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

链表增加头结点的作用：（1）便于首元结点的处理；（2） 便于空表和非空表的统一处理。

假设是指向单链表中第i个数据元素的指针，则 p->next是指向第i+1个数据元素的指针。若p->data=ai, 则p->next->data=ai+1

3.2 单链表基本操作的实现

1.初始化

单链表的初始化操作就是构造一个空表。

算法3.1 单链表的初始化

[算法步骤]

  • 生成新结点作为头结点，用头指针L指向头结点。
  • 头结点的指针域置空

[算法描述]

1
2
3
4
5
6
Status InitList(LinkLis &L)
{//构造一个空的单链表L
  L=new LNode;                                //生成新结点作为头结点，用头指针L指向头结点
  L->next=NULL;                               //头指针的指针域置空
  return OK;
}

2.取值

和顺序表不同，链表取值只能从链表的首元结点出发，顺着链域 next 逐个结点向下访问。

算法 3.2 单链表的取值

[算法步骤]

  • 用指针p指向首元结点，用j做计数器初值赋为1.
  • 从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 p不为空(NULL),并且没有到达序号为i的结点，则循环执行以下操作:
    • p指向下一个结点；
    • 计数器j相应加1；
  • 退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法，取值失败返回ERROR;否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK.

[算法描述]

1
2
3
4
5
6
7
8
9
10
11
12
Status FetElem(LinkList L,int i, ElemType &e)
{
  p = L->next;j=1;                  //初始化，p指向首元结点，计数器j初值赋为1
  while(p&&j<i)                     //顺链域向后扫描，直到为空或p指向第i个元素
  {
    p=p->next;                       //p指向下一个结点
    ++j;                             //计数器相应加1
  }
  if(!p||j>i) return ERROR;
  e=p->data;                          //取第i个结点的数据域
  return OK;
}

时间复杂度为 O(n)

3.查找
算法3.3 单链表的按值查找

[算法步骤]

  • 用指针p指向首元结点
  • 从首元结点开始依次顺着链域 next 向下查找
  • 返回p

[算法描述]

1
2
3
4
5
6
7
LNode *LocateElem(LinkList L,ElemType e)
{//在带头结点的单链表L中查找值为e的元素
  p=L->next;    初始化，指向首元结点
  while(p && p->data!=e)   //向后扫描
    p=p->next;
  return p;                    //查找成功返回值为e的结点地址p，查找失败p为NULL
}

时间复杂度为 O(n)

4.插入
算法3.4 单链表的插入

[算法步骤]

  • 查找结点 ai-1 并由指针p指向该结点
  • 生成一个新结点*s
  • 将新结点*s的数据域置为e
  • 将新结点*s的指针域指向结点 ai
  • 将结点p的指针域指向新结点s

[算法描述]

1
2
3
4
5
6
7
8
9
10
11
12
Status ListInsert(LinkList &L,int i, ElemType e)
{//在带头结点的单链表L中第i个位置插入值为e的新结点
  p=L;j=0;
  while(p&& (j<i-1))
    {p=p->next;++j;}                                   //查找第i-1个结点，p指向该结点
  if(!p||j>i-1) return ERROR;                          //i>n+1 或 i<1
  s=new LNode;                                         //生成新结点 *s
  s->data=e;                                           //将新结点数据域置为e
  s->next=p->next;                                     //将新结点*s的指针域指向结点 a<sub>i</sub>
  p->next=s;                                           //将结点*p的指针域指向新结点*s
  return OK;
}

时间复杂度为 O(n)

5. 删除

同插入元素一样，首先应该找到该位置的前驱结点 p , p->next=p->next->next;

算法 3.5 单链表的删除

[算法步骤]

  • 查找结点 ai-1并由指针p指向该结点
  • 临时保存待删除结点ai的地址在q中，以备释放
  • 将结点*p的指针域指向ai的直接后继结点
  • 释放结点ai的空间

[算法描述]

1
2
3
4
5
6
7
8
9
10
11
Status ListDelete(LinkList &L,int i)
{//在带头结点的单链表L中，删除第i个元素
  p=L;j=0;
  while((p->next) && (j<i-1))                                          //查找第i-1个结点，p指向该结点
    {p=p->next;++j;}
  if(!(p->next)||(j>i-1)) return ERROR;                                //当i>n 或i<1时，删除位置不合理
  q=p->next;                                                           //临时保存被删除结点的地址以备删除
  p->next=q->next;                                                     //改变删除结点前驱结点的指针域
  delete q;                                                            //释放删除结点的空间
  return OK;
}

时间复杂度为 O(n)

6.创建单链表

根据结点插入位置的不同，链表的创建方法分为前插法和后插法

算法3.6 前插法创建单链表

[算法步骤]

  • 创建一个只有头结点的空链表
  • 根据元素个数n，循环n次一下操作
    • 生成一个新结点 *p
    • 输入元素值赋给新结点*p的数据域
    • 将新结点*p插入到头结点之后

[算法描述]

1
2
3
4
5
6
7
8
9
10
11
void CreateList_H(LinkList &L,int n)
{
  L=new LNode;                                    
  L->next=NULL;                                                 //先建立一个带头结点的空链表
  for(i=0;i<n;++i)
  {
    p=new LNode;                                                //生成新结点 *p
    cin>>p->data;                                              //输入元素值
    p->next=L->next;L->next=p;                                 //将新结点*p插入到头结点之后
  }
}

时间复杂度为 O(n)

算法3.7 后插法创建单链表

[算法步骤]

  • 创建一个只有头结点的空链表
  • 尾指针r初始化，指向头结点
  • 根据元素个数n，循环n次一下操作
    • 生成一个新结点 *p
    • 输入元素值赋给新结点*p的数据域
    • 将新结点p插入到尾结点r之后
    • 尾指针r指向新的尾结点*p

[算法描述]

1
2
3
4
5
6
7
8
9
10
11
12
13
void CreateList_R(LinkList &L,int n)
{
  L=new LNode;
  L->next-NULL;
  r=L;                                     //尾指针r指向头结点
  for(i=0;i<n;++i)
  {
    p=new LNode;
    cin>>p->data;
    p->next=NULL;r->next=p;                     //将新结点*p插入到尾结点*r之后
    r=p;                                           //r指向新的尾结点*p
  }
}

时间复杂度为 O(n)

3.3 双向链表

以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。双向链表可克服这种单向性的缺点。

顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。在双向链表中，若d为指向表中某一结点的指针，则有 d->next->prior=d->prior->next=d

算法3.8 双向链表的插入

[算法描述]

1
2
3
4
5
6
7
8
9
10
11
12
Status ListInsert_DiL(DuLinkList &L,int i,ElemType e)
{//在带头结点的双向链表L中第i个位置之前插入元素
  if(!(p=GetElem_DuL(L,i)))                               //在L中确定第i个元素的位置指针p
    return ERROR;                                          //p为NULL时，第i个元素不存在
  s = new DuLNode;                                        //生成新结点*s
  s->data=e;                                              //新结点数据域为e
  s->prior=p->prior;                                       //将新结点*s插入L中
  p->prior->next=s;
  s->next=p;
  p->prior=s;
  return OK;
}

算法3.9 双向链表的删除

[算法描述]

1
2
3
4
5
6
7
8
9
Status ListDelete_DuL(DuLinkList &L;int i)
{//删除在带头结点的双向链表L中第i个元素
  if(!(p=GetElem_DuL(L,i)))                               //在L中确定第i个元素的位置指针p
    return ERROR;                                          //p为NULL时，第i个元素不存在
  p->prior->next=p->next;
  p->next->prior=p->prior;
  delete p;
  return OK;
}

4.顺序表和链表的比较

若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。

对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。

-------------本文结束感谢您的阅读-------------
hao14293 wechat
交流或订阅，请扫描上方微信二维码