数据结构-线性表

简介: 数据结构-线性表

线性表的逻辑结构

  • 定义:线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列。其中n为表长。当n=0时 线性表是一个空表
  • 特点:线性表中第一个元素称为表头元素;最后一个元素称为表尾元素。

除第一个元素外,每个元素有且仅有一个直接前驱。
除最后一个元素外,每个元素有且仅有一个直接后继。

线性表的顺序存储结构

  • 线性表的顺序存储又称为顺序表。

它是用一组地址连续的存储单元(比如C语言里面的数组),依次存储线性表中的数据元素,从而使得逻
辑上相邻的两个元素在物理位置上也相邻。

  • 建立顺序表的三个属性:

1.存储空间的起始位置(数组名data)
2.顺序表最大存储容量(MaxSize)
3.顺序表当前的长度(length)

  • 其实数组还可以动态分配空间,存储数组的空间是在程序执行过程中通过动态存储分配语句分配
  • 总结:

    • 1.顺序表最主要的特点是随机访问(C语言中基于数组),即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。
    • 2.顺序表的存储密度高,每个结点只存储数据元素。无需给表中元素花费空间建立它们之间的逻辑关系(因为物理位置相邻特性决定)
    • 3.顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量元素。

顺序表的操作

  • 1.插入

    • 算法思路:

      • 1.判断i的值是否正确
      • 2.判断表长是否超过数组长度
      • 3.从后向前到第i个位置,分别将这些元素都向后移动一位
      • 4.将该元素插入位置i 并修改表长
    • 代码
    • 分析:

      • 最好情况:在表尾插入(即i=n+1),元素后移语句将不执行,时间复杂度为O(1)。
      • 最坏情况:在表头插入(即i=1),元素后移语句将执行

n次,时间复杂度为O(n)。

    * 平均情况:假设pi(pi=1/(n+1) )是在第i个位置上插入

一个结点的概率,则在长度为n的线性表中插入一个结
点时所需移动结点的平均次数为

  • 2.删除

    • 算法思路:

      • 1.判断i的值是否正确
      • 2.取删除的元素
      • 3.将被删元素后面的所有元素都依次向前移动一位
      • 4.修改表长
    • 代码
    • 分析

      • 最好情况:删除表尾元素(即i=n),无须移动元素,时间复杂度为O(1)。
      • 最坏情况:删除表头元素(即i=1),需要移动除第一个元素外的所有元素,时间复杂度为O(n)。
      • 平均情况:假设pi(pi=1/n)是删除第i个位置上结点的概率,则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为

线性表的链式存储结构

  • 线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。
  • 头结点和头指针的区别?

    • 不管带不带头结点,头指针始终指向链表的第一个结点,而头结点是带头结点链表中的第一个结点,结点内通常不存储信息
  • 为什么要设置头结点?

    • 1.处理操作起来方便 例如:对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了
    • 2.无论链表是否为空,其头指针是指向头结点的非空指针,因此空表和非空表的处理也就统一了。

单链表的操作

  • 1.头插法建立单链表:

    • 建立新的结点分配内存空间,将新结点插入到当前链表的表头
    • 代码
  • 2.尾插法建立单链表:

    • 建立新的结点分配内存空间,将新结点插入到当前链表的表尾
    • 代码
  • 3.按序号查找结点

    • 在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL。
    • 代码
  • 4.按值查找结点

    • 从单链表第一个结点开始,由前往后依次比较表中各结点数据域的值,若某结点数据域的值等于给定值e,则返回该结点的指针;若整个单链表中没有这样的结点,则返回NULL。
    • 代码
  • 5.插入

    • 插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性,然后找到待插入位置的前驱结点,即第i−1个结点,再在其后插入新结点。
    • 算法思路:

1.取指向插入位置的前驱结点的指针
① p=GetElem(L,i-1);
2.令新结点s的指针域指向p的后继结点
② s->next=p->next;
3.令结点p的指针域指向新插入的结点s
③ p->next=s;

  • 6.删除

    • 删除操作是将单链表的第i个结点删除。先检查删除位置的合法性,然后查找表中第i−1个结点,即被删结点的前驱结点,再将其删除。
    • 算法思路:

1.取指向删除位置的前驱结点的指针 p=GetElem(L,i-1);
2.取指向删除位置的指针 q=p->next;
3.p指向结点的后继指向被删除结点的后继 p->next=q->next
4.释放删除结点 free(q);

双链表

  • 定义
  • 1.插入:(方法不唯一)

① s->next=p->next;
② p->next->prior=s;
③ s->prior=p;
④ p->next=s;

链表插入算法例如:

Status ListInsert_DuL(DuLinkList L, int i, LElemType_DC e)
{
    DuLinkList p, s;
    
    if(i<1 || i>ListLength_DuL(L)+1)    //先对i做出限制 
        return ERROR;

    p = GetElemPtr_DuL(L, i);            //确定第i个结点指针 
    if(!p)                                //此处若p=NULL,说明i = ListLength_DuL(L)+1
        p = L;                            //令p指向头指针    
    
    s = (DuLinkList)malloc(sizeof(DuLNode));
    if(!s)
        exit(OVERFLOW);
    s->data = e;
    
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    
    return OK;        
} 
  • 2.删除:

① p->next=q->next;
② q->next->prior=p;
③ free(q);

Status ListDelete_DuL(DuLinkList L, int i, LElemType_DC *e)
{
    DuLinkList p;
    
    if(!(p=GetElemPtr_DuL(L, i)))        //i值不合法
        return ERROR;
    
    *e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;

    free(p);
    p = NULL;
    
    return OK;
} 

循环链表&&静态链表

  • 循环单链表:循环单链表和单链表的区别在于,表中最后一个结点的指针不是NULL,而改为指向头结点,从而整个链表形成一个环
  • 循环双链表:类比循环单链表,循环双链表链表区别于双链表就是首尾结点构成环

    • 当循环双链表为空表时,其头结点的prior域和next域都等于Head。
  • 静态链表:静态链表是用数组来描述线性表的链式存储结构。

    • 数组第一个元素不存储数据,它的指针域存储第一个元素所在的数组下标。链表最后一个元素的指针域值为-1。
目录
相关文章
|
5月前
|
存储 C语言
数据结构中的线性表链式存储介绍及其基本操作
链式存储是线性表的一种重要存储方式,它通过节点和指针的结构,实现了灵活的动态存储管理。本文介绍了单向链表的基本操作,并提供了相应的C语言代码示例。理解和掌握链表的操作对学习和应用数据结构具有重要意义。希望这篇博客能帮助你更好地理解线性表的链式存储。
124 2
|
30天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
29 6
|
9天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
20 1
|
5月前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
46 0
|
30天前
01(数据结构考研)线性表相关操作代码
01(数据结构考研)线性表相关操作代码
52 0
|
1月前
|
存储 C语言
数据结构之线性表的初始化及其操作
数据结构之线性表的初始化及其操作
33 0
|
2月前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。
|
5月前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
58 5
|
5月前
|
存储 测试技术
【数据结构】操作受限的线性表,队列的具体实现
【数据结构】操作受限的线性表,队列的具体实现
44 4

热门文章

最新文章