二、线性表的概念与实现

发布时间:2020-04-20 03:03:37 作者:少年不在了
来源:网络 阅读:386

1.线性表的本质与相关操作

线性表的定义
 线性表(List)是零个或多个数据元素的集合
 线性表中的数据元素之间是有顺序的
 线性表中的数据元素个数是有限的
 线性表中的数据元素的类型必须相同
二、线性表的概念与实现
线性表的性质
 a0为线性表的第一个元素,只有一个后继
 an为线性表的最后一个元素,只有一个前驱
 除a0和an外的其它元素ai,既有前驱,又有后继
 线性表能够逐项访问和顺序存取
线性表的一些常用操作
 创建线性表
 销毁线性表
 清空线性表
 将元素插入线性表
 将元素从线性表中删除
 获取线性表中某个位置的元素
 获取线性表的长度
线性表操作的实现
 线性表在程序中表现为一种特殊的数据类型,其操作在程序中的表现为一组函数

List* List_Create();                                                       //创建线性表
void List_Destroy(List* list);                                       //销毁线性表
void List_Clear(List* list);                                           //清空线性表
int List_Insert(List* list, ListNode* node, int pos);     //将元素插入线性表
ListNode* List_Delete(List* list, int pos);                   //将元素从线性表中删除
ListNode* List_Get(List* list, int pos);                       //获取线性表中某个位置的元素
int List_Length(List* list);                                         //获取线性表的长度

2.线性表的顺序存储结构

顺序存储定义
 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。
二、线性表的概念与实现
在C语言中可以用一维数组来实现顺序存储结构
 存储空间的起始位置:数组node
 线性表的最大容量:数组长度MAXSIZE
 线性表的当前长度:length

#define MAXSIZE 20
typedef struct  _tag_List
{
    char node[MAXSIZE];
    int length;
} List;

获取元素操作
 判断线性表是否合法
 判断位置是否合法
 直接通过数组下标的方式获取元素

char Get(List* list, int pos)
{
    char ret = -1;
    if((list != NULL) && (0 <= pos ) && (pos <= list->length))
    {
        ret = list->node[pos];
    }
    return ret;
}

插入元素操作
 判断线性表是否合法
 判断插入位置是否合法
 把最后一个元素到插入位置的元素后移一个位置
 将新元素插入
 线性表长度加1
二、线性表的概念与实现

int Insert(List* list, char c, int pos)
{
    //判断线性表是否合法
    int ret = (list != NULL);
    int i = 0;
    //判断插入位置是否合法
    ret = ret && ((list->length + 1) <= MAXSIZE); 
    ret = ret && (0 <= pos);
    if(ret)
    {
        if(pos >= list->length)
            pos = list->length;
        //从最后一个元素开始到第pos个位置,分别将他们地洞到后一个位置
        for(i=list->length;i > pos; i--)
        {
            list->node[i] = list->node[i-1];
        }
        //将新元素插入
        list->node[pos] = c;
        //长度加1
        list->length++;
    }
    return ret;
}

删除元素操作
 判断线性表是否合法
 判断删除位置是否合法
 将元素取出
 将删除位置后的元素分别向前移动一个位置
 线性表长度减1
二、线性表的概念与实现

char Delete(List* list, int pos)
{
    char ret = -1;
    int i = 0;
    //判断线性表是否合法,判断删除位置是否合法
    if((list != NULL)&&(0 <= pos)&&(pos < list-> length))
    {
        ret = list->node[pos];
        for(int i=pos+1; i < list->length; i++)
            list->node[i-1] = list->node[i];
        list->length--;
    }
    return ret;
}

3.线性表的链式存储结构

链式存储定义
 为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息。
二、线性表的概念与实现
链式存储逻辑结构
 n个结点链接成一个链式线性表的结构叫做链表,当每个结点中只包含一个指针域时,叫做单链表。
链表的基本概念
 表头结点
  链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息
 数据结点
  链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息
 尾结点
  链表中的最后一个数据结点,其下一元素指针为空,表示无后继
单链表示例
二、线性表的概念与实现
在C语言中可以用结构体来定义链表中的指针域;链表中的表头结点也可以用结构体实现

//结点指针域定义
typedef struct _tag_LinkListNode{
    LinkListNode* next;
} LinkListNode;

//头结点定义
typedef struct _tag_LinkList
{
    LinkListNode header;
    int length;
} TLinkList;

//数据元素定义
struct Value
{
    LinkListNode header;
    int v;
};

获取第pos个元素操作
 判断线性表是否合法
 判断位置是否合法
 由表头开始通过next指针移动pos次后,当前元素的next指针即指向要获取的元素

LinkListNode* current = (LinkListNode*) list;
for(i=0; i<pos; i++)
{
    current = current->next;
}
ret = current->next;

插入元素操作
 判断线性表是否合法
 判断插入位置是否合法
 由表头开始通过next指针移动pos次后,当前元素的next指针即指向要插入的位置
 将新元素插入
 线性表长度加1
二、线性表的概念与实现
删除元素操作
 判断线性表是否合法
 判断插入位置是否合法
 获取第pos个元素
 将第pos个元素从链表中删除
 线性表长度减1

实现代码

推荐阅读:
  1. 线性表(1):线性表顺序存储结构的php实现
  2. Spark笔记整理(二):RDD与spark核心概念名词

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

数据结构 线性表 顺序存储

上一篇:redis(版本redis-5.0.2)的安装步骤

下一篇:不要轻易在app.js里面写方法

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》