你好,游客 登录 注册 搜索
背景:
阅读新闻

线性表之顺序存储结构实现

[日期:2017-01-06] 来源:Linux社区  作者:metalsteel [字体: ]

一,上篇回顾

上一篇是描述的线性表的顺序存储结构的代码实现和分析。这一篇用来描述线性表的链式存储结构的实现。上一篇的末尾总结了线性表用顺序存储结构实现的优点和缺点,基于其缺点前人们又设计出了链式存储结构来对线性表进行补充,下面一起来分析一下链式存储结构实现线性表。

二,线性表的链式存储结构

1.链式存储结构的概念

  为了表示每个数据元素ai与直接后继元素ai+1之间的逻辑关系,对数据元素ai而言,除了存储其本身的信息以外,还需存储一个指示其直接后继元素的信息,我们把存储数据元素信息的域称为数据域,把存储后继元素位置的域称为指针域。这两部分信息组成数据元素ai的存储映像,称为结点。

  n个结点链接成一个链表,即为线性表的链式存储结构。因为链表的每个结点只包含一个指针域,因此叫做单链表。

2.头指针和头结点

  头指针:头指针是指链表指向第一个结点的指针,若链表有头结点,则头指针是指向头结点的指针。

  头结点:头结点是为了操作的统一和方便而设定的,放在链表第一结点之前,其数据域一般无意义,其指针域指向第一个结点。

  

3.链式存储结构的实现原理

1.普通链表的实现

  普通的链表是包含数据域和指针域,因此这个链表在没有用到高级的泛型编程的情况下,需要多次的修改数据域的数据类型。如果用C语言实现,则只能实现单一类型的包含,不能动态的包含相应的数据类型。

2.Linux的内核链表的实现

  Linux的内核是用C语言实现的,因此在Linux中的内核中,要实现链表则不能使用上述普通链表方式,因为上述链表不是通用链表。但是Linux创始人在28岁就发明了另一种链表的方式,如下图:

 

  让结点被包含在业务结点里,这样就可以实现了通用链表,只需要链表结点包含在业务结点内即可。

三,Linux内核链表的实现

1.链表基本功能(LinkList.h)

#ifndef LINK_LIST
#define LINK_LIST

/* 业务结点 */
typedef void Node;

/* 链表结点 */
typedef struct ListNode
{
    struct ListNode * next;
}ListNode; 

/* 链表 */
typedef struct LinkList
{
    Node * ptr;
    ListNode head;
    int length;
}LinkList;

/* 创建链表 */
LinkList * createList();

/* 链表长度 */
int length(LinkList * list);

/* 插入链表 */
void insert(LinkList * list, int pos, Node * node);

/* 删除链表 */
Node * del(LinkList * list, int pos);

/* 获取链表 */
Node * get(LinkList * list,int pos);

#endif

2.链表功能的实现(LinkList.c)

# include<stdlib.h>

/* 创建链表 */
LinkList * createList()
{
    /* 在堆上分配内存 */
    LinkList * list = (LinkList *)malloc(sizeof(LinkList));
    /* 初始化链表 */
    list->ptr = &(list->head);
    list->head.next = NULL;
    list->length = 0;

    return list;
}

/* 链表长度 */
int length(LinkList * list)
{
    return list->length;
}

/* 插入链表 */
void insert(LinkList * list, int pos, Node * node)
{
    /* 将业务结点转换为链表结点 */
    ListNode * _node = (ListNode *)node;
    /* 获取头结点 */
    ListNode * header = &(list->head);
    /* 定义posNode */
    ListNode * posNode = header;
    /* 将头结点移动到pos位置 */
    for (int i = 0; i < pos; i++)
    {
        posNode = posNode->next;
    }
    /* 判断是否是第一个结点 */
    if (posNode->next == NULL)
    {
        _node->next = NULL;
        posNode->next = _node;
    }
    else {
        _node->next = posNode->next;
        posNode->next = _node;
    }
    list->length++;
}

/* 删除链表 */
Node * del(LinkList * list, int pos)
{
    /* 判断删除位置是否合法 */
    if (pos < 0 || pos >= list->length)
    {
        return NULL;
    }
    /* 定义头结点 */
    ListNode * header = &(list->head);
    /* 定义posNode */
    ListNode * posNode = NULL;
    /* 判断是否为空表 */
    if (header->next == NULL)
    {
        return NULL;
    }
    else {
        posNode = header->next;
    }
    /* 定义前置结点用来缓存前一个结点 */
    ListNode * previous = posNode;
    /* 移动到���删除的位置 */
    for (int i = 0; i < pos; i++)
    {
        previous = posNode;
        posNode = posNode->next;
    }
    /* 定义返回结点 */
    ListNode * result = posNode;
    /* 删除 */
    previous->next = posNode->next;
    /* 链表长度减一 */
    list->length--;

    return result;
}

/* 获取链表 */
Node * get(LinkList * list,int pos)
{
    /* 获取头结点 */
    ListNode * header = &(list->head);
    /* 定义posNode */
    ListNode * posNode = NULL;
    /* 判断是否为空表 */
    if (header->next == NULL)
    {
        return NULL;
    }
    else {
        posNode = header->next;
    }
    /* 移动posNode到pos位置 */
    for (int i = 0; i < pos; i++)
    {
        posNode = posNode->next;
    }
    return posNode;
}

3.链表的测试(main.c)

# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# include"LinkList.h"

/* 定义学生结构体 */
typedef struct Student
{
    ListNode node;
    char name[64];
    int age;
}Student;

/* 主函数 */
int main()
{
    /* 定义数据 */
    Student s1 = { NULL,"刘备",56 };
    Student s2 = { NULL,"关羽",40 };
    Student s3 = { NULL,"张飞",34 };
    Student s4 = { NULL,"赵云",30 };
    Student s5 = { NULL,"马超",26 };
    Student s6 = { NULL,"黄忠",80 };

    /* 创建链表 */
    LinkList * list = createList();

    /* 链表插入 */
    insert(list, 0, &s1);
    insert(list, 0, &s2);
    insert(list, 0, &s3);
    insert(list, 0, &s4);
    insert(list, 0, &s5);
    insert(list, 0, &s6);

    /* 遍历 */
    printf("##############遍历###############\n");
    for (int i = 0; i < length(list); i++)
    {
        Student * student = (Student *)get(list, i);
        printf("name = %s,age = %d\n", student->name, student->age);
    }

    /* 删除结点 */
    del(list, 3);

    printf("##############遍历###############\n");
    for (int i = 0; i < length(list); i++)
    {
        Student * student = (Student *)get(list, i);
        printf("name = %s,age = %d\n", student->name, student->age);
    }

    return 0;
}

四,线性表的顺序存储结构和链式存储结构的比较

1.存储方式的比较

  顺序存储结构:用一段连续的存储单元依次存储线性表的数据元素。

  链式存储结构:用任意的存储单元存储线性表的数据元素。

2.时间复杂度比较

查找: 

  顺序存储结构的时间复杂度为O(1)。

  链式存储结构的时间复杂度为O(n)。

插入和删除:

  顺序存储结构需要平均移动表长的一半元素,时间复杂度为O(n)。

  链式存储结构在找到元素后,时间复杂度为O(1)。

3.空间复杂度比较

  顺序存储结构:需要预分配存储空间,分配大了造成浪费,分配小了容易溢出。

  链式存储结构:不需要预分配存储空间,只要有数据元素就分配,元素个数不受限制。

4.总结

  1.若线性表需要频繁查找,很少进行插入和删除操作,宜采用顺序存储结构。若频繁进行插入和删除操作,则宜采用链式存储结构,比如游戏开发过程中,账号信息的注册,我们平时只需要注册一次,而大多数是登录操作,即频繁查找操作,所以应该操作顺序存储结构。当我们设计游戏玩家装逼列表的时候,由于游戏装备的频繁更新,即频繁插入和删除,则宜采用链式存储结构。

  2.当线性表的元素变化较大或者根本不知道有多少元素的时候,宜采用链式存储结构,这样不需要考虑存储空间的大小问题。而如果事先知道了线性表的长度,则宜采用顺序存储结构,例如一年有12个月。

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-01/139260.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款