数据结构——线性表的链式存储结构2(静态链表)

简介: 数据结构——线性表的链式存储结构2(静态链表)

目录

前言

定义

静态链表的初始化

计算当前线性表的长度(准备工作)

静态链表的元素插入

静态链表的元素删除

静态链表的优缺点

前言

在之前我们用指针实现了单链表的功能,但对于早期的高级语言来说,他们并没有指针,那他们是怎样实现链表的呢?


有人就想出用数组来代替指针描述单链表。


首先我们让数组的元素都是由两个数据域组成,data和cur。data存放的是数据,cur来存放下一个数组的下标,从而模拟实现了指针的功能。

定义

用数组描述的链表叫做静态链表

//存储结构
#define MAXSIZE 1000
typedef int ElemType;
typedef struct
{
  ElemType data;
  int cur;
}Component,StaticLinklList[MAXSIZE];

静态链表的初始化

//初始化静态链表(给cur赋值)
void InitList(StaticLinklList space)
{
  int i;
  for (i = 0; i < MAXSIZE - 1; i++)
    space[i].cur = i + 1;
  space[MAXSIZE].cur = 0;//目前静态链表为零,最后一个元素的cur为零
}

示意图如下  

image.png

存放数据后

image.png

计算当前线性表的长度(准备工作)

//计算当前线性表的长度
int ListLength(StaticLinklList L)
{
  int j = 0;//计数器
  int i = L[MAXSIZE - 1].cur;
  while (i)
  {
    i = L[i].cur;
    ++j;
  }
  return j;
}

静态链表的元素插入

返回空闲空间的结点下标

//插入操作需先返回分量的节点下表
int Malloc_SSL(StaticLinklList space)
{
  int i = space[0].cur;//当前数组第一个元素的cur存在值
            //返回第一个备用空闲的下标
  if (space[0].cur)
    space[0].cur = space[i].cur;//把下一个分量用来备用
  return i;
}

插入元素

插入元素是通过先在第一个空闲位置处增添元素,然后与要插入位置的前一个元素交换cur从而实现的

void ListInsert(StaticLinklList L, int i, ElemType e)
{
  int j, k, l;
  k = MAXSIZE - 1;
  assert(i >= 1||i>ListLength(L));
  j = Malloc_SSL(L);
  if (j)
  {
    L[j].data = e;
    for (l = 1; l <= i - 1; l++)
      k = L[k].cur;
    L[j].cur = L[k].cur;
    L[k].cur = j;
  }
}

静态链表的元素删除

void Free_SSL(StaticLinklList space, int k)
{
  space[k].cur = space[0].cur;
  space[0].cur = k;
}
void ListDeletes(StaticLinklList L, int i)
{
  int j, k;
  assert(i>= 1||i>ListLength(L));
  k = MAXSIZE - 1;
  for (j = 1; j <= i - 1; ++j)
    k = L[k].cur;
  j = L[k].cur;
  Free_SSL(L, j);
}

静态链表的优缺点

优点:在插入和删除操作时,只需要修改游标,不需要移动元素。

缺点:失去了顺序存储结构随机存取的特性,没有解决连续存储分配带来的表长难以确定的问题。

相关文章
|
1月前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
17 0
|
1月前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
21 0
|
1月前
|
存储 算法
【数据结构和算法】--队列的特殊结构-循环队列
【数据结构和算法】--队列的特殊结构-循环队列
17 0
|
6天前
|
存储
【数据结构】树和二叉树的概念及结构
数据结构——树和二叉树的概念及结构
25 3
【数据结构】树和二叉树的概念及结构
|
14天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
18 0
【数据结构OJ题】链表的回文结构
|
1月前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
1月前
|
算法
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
7 0
|
1月前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
6天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
12 1
【数据结构】栈和队列
|
6天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
14 0
【数据结构OJ题】用栈实现队列