数据结构:静态链表

首先我们让数组的元素都是由两个数据域组成,data和cur。也就是说,数组的每一个下标都对应一个data和一个cur。

数据域data用来存放数据元素,也就是通常我们要处理的数据;而游标cur相当于单链表中的next指针,

存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表。

数组的第一个元素,即下标为0的元素的cur就存放备用链表的第一个结点的下标;而数组的最后一个元素的cur

则存放第一个有数值的元素的下标,相当于单链表的头节点作用,当整个链表为空时,则为0,表示无指向。如图3-12-2所示

现在如果我们需要在“乙”和“丁”之间插入一个值为“丙”的元素,只需要将“乙”的cur改为7,表示下一位是“丙”,并将“丙”的cur改为3,表示下一位是丁。

如图3-12-3所示。

现在如果我们删除了第一个元素“甲”,表示现在“甲”这个位置空出来了,如果未来有新人要来则优先考虑这里,所以删除的位置成为第一个优先空位,即首元素的cur为1, 第一个元素位置的cur改为8,而下标为8的位置cur改为9,最后元素位置的cur改为2,如图3-12-4所示。

示例代码:(改编自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXSIZE 100

typedef int ElemType;
/* 线性表的静态链表存储结构 */
typedef struct Node
{
    ElemType data;
    int cur; //为0时表示无指向
} StaticLinkList[MAXSIZE];

/* 将一维数组array中各分量链成一个备用链表,array[0].cur为头指针,"0"表示空指针 */
bool InitList(StaticLinkList array)
{
    cout << "InitList..." << endl;
    for (int i = 0; i < MAXSIZE - 2; i++)
    {
        array[i].cur = i + 1;
    }

    array[MAXSIZE - 2].cur = 0;
  /* 最后一个元素也是不可用的,倒数第二个元素的cur为0 */
    array[MAXSIZE - 1].cur = 0;   /* 目前静态链表为空,最后一个元素的cur为0 */

    return true;
}
/* 若备用空间链表非空,则返回分配的结点下标,否则返回0 */
int Malloc_SLL(StaticLinkList array)
{
    int k = array[0].cur;
    if (k)
        array[0].cur = array[k].cur;/* 下一个分量用来做备用 */

    return k;
}
/*  将下标为pos的空闲结点回收到备用链表 */
void Free_SLL(StaticLinkList array, int pos)
{
    array[pos].cur = array[0].cur; /* 把第一个元素的cur值赋给要删除的分量cur */
    array[0].cur = pos; /* 把要删除的分量下标赋值给第一个元素的cur */
}

int ListLength(StaticLinkList array)
{
    int i = array[MAXSIZE - 1].cur;
    int j = 0;
    while(i)
    {
        i = array[i].cur;
        ++j;
    }
    return j;
}
/*  在array中第pos个元素之前插入新的数据元素Elem  */
bool ListInsert(StaticLinkList array, int pos, ElemType Elem)
{
    cout << "Insert List from pos: " << pos << " Item " << Elem << endl;
    if (pos < 1 || pos > ListLength(array) + 1)
        return false;

    int k = MAXSIZE - 1;
    int i = Malloc_SLL(array); /* 获得空闲分量的下标 */

    if (i)
    {
        array[i].data = Elem;

        for (int l = 1; l <= pos - 1; l++)
            k = array[k].cur;

        array[i].cur = array[k].cur;/* 把第pos个元素之前的cur赋值给新元素的cur */
        array[k].cur = i;/* 把新元素的下标赋值给第pos个元素之前元素的cur */
        return true;
    }

    return false;
}
/*  删除在array中第pos个数据元素   */
bool ListDelete(StaticLinkList array, int pos)
{
    cout << "Delete List from pos: " << pos << endl;
    if (pos < 1 || pos > ListLength(array))
        return false;

    int k = MAXSIZE - 1;

    for (int l = 1; l <= pos - 1; l++)
        k = array[k].cur;

    int j = array[k].cur;
    array[j].cur = array[pos].cur;

    Free_SLL(array, j);

    return true;
}

bool ListTraverse(StaticLinkList array)
{
    cout << "List Traverse : " << endl;
    int k = MAXSIZE - 1;
    while (array[k].cur != 0)
    {
        k = array[k].cur;
        cout << array[k].data << ' ';
    }

    cout << endl;
    return true;
}


int main(void)
{
    StaticLinkList SSL;
    InitList(SSL);
    for (int i = 1; i < 5; i++)
        ListInsert(SSL, i, i);
    ListTraverse(SSL);

    ListDelete(SSL, 3);
    ListTraverse(SSL);
    cout << "List Length : " << ListLength(SSL) << endl;

    return 0;
}

输出为:

静态链表在插入和删除操作时不需要移动元素,只需要修改游标,从而改进了在顺序存储结构中插入和删除操作需要移动

大量元素的缺点;但并没有解决连续分配存储带来的表长难以确定的问题;并且失去了顺序存储结构随机存取的特性。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏李成熙heyli

babel到底将代码转换成什么鸟样?

前言 将babel捧作前端一个划时代的工具一定也不为过,它的出现让许多程序员幸福地用上了es6新语法。但你就这么放心地让babel跑在外网?反正我是不放心,我就...

31410
来自专栏编程之旅

线性表的顺序存储结构

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有50个座位,那蔺老师会把这10...

662
来自专栏Golang语言社区

【翻译】Golang语言-是面向对象语言吗?

原文:http://spf13.com/post/is-go-object-oriented 前言 为了真正理解面向对象的含义,我们需要回顾一下这个概念的起源。...

3688
来自专栏王硕

原 pg查询树的简单解读

34013
来自专栏Ryan Miao

java枚举类型学习

用的不多,但用的时候仅仅简单的使用,不太明白原理,今天就系统的学一下枚举。参考:java编程思想。 Update: 枚举可以当做数据字典来存储,通常只要一个字段...

2799
来自专栏恰同学骚年

Hadoop学习笔记—11.MapReduce中的排序和分组

  从上图中可以清楚地看出,在Step1.4也就是第四步中,需要对不同分区中的数据进行排序和分组,默认情况下,是按照key进行排序和分组。

732
来自专栏鸿的学习笔记

线性表之顺序存储结构

线性表的数据对象集合为{a1,a2,...an},每个元素的数据类型均为DataType。

592
来自专栏Java技术栈

equals 和 hashCode 到底有什么联系?一文告诉你!

Java的基类Object提供了一些方法,其中equals()方法用于判断两个对象是否相等,hashCode()方法用于计算对象的哈希码。equals()和ha...

993
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第3章 Kotlin语言基础第3章 Kotlin语言基础《Kotlin极简教程》正式上架:参考资料

学习任何东西,都是一个由表及里的过程。学习一门编程语言也一样。对于一门编程语言来说,“表” 就是基本词汇(关键字、标识符等)、句子(表达式)和语法。

942
来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

1829

扫码关注云+社区