24考研数据结构-线性表4

这篇具有很好参考价值的文章主要介绍了24考研数据结构-线性表4。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2.4.4单链表的查找操作(默认带头节点,不带头节点后续更新)

2.4.4.1 按位查找操作

GetElem(L, i): 按位查找操作,获取表L中第i个位置的元素的值;

LNode * GetElem(LinkList L, int i){
    if(i<0) return NULL;
    
    LNode *p;               //指针p指向当前扫描到的结点
    int j=0;                //当前p指向的是第几个结点
    p = L;                  //L指向头结点,头结点是第0个结点(不存数据)
    while(p!=NULL && j<i){  //循环找到第i个结点
        p = p->next;
        j++;
    }

    return p;               //返回p指针指向的值
}


注意:
1.边界情况 i=0,返回头节点;i>L.length,返回null;
2.j<i即查找到j = i 的节点,就是第i个节点。
3.平均复杂度O(n)
2.4.4.2 按值查找操作

LocateElem(L, e):按值查找操作,在表L中查找具有给定关键字值的元素;
平均复杂度O(n)

LNode * LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;    //p指向第一个结点
    //从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;           //找到后返回该结点指针,否则返回NULL
}

2.4.4.3 求单链表的长度(带和不带头节点都写了)

Length(LinkList L) :计算单链表中数据结点**(不含头结点)的个数**,需要从第一个结点看是顺序依次访问表中的每个结点。算法的时间复杂度为O(n)

带头节点:

int Length(LinkList L){
    int len=0;       //统计表长
    LNode *p = L;
    while(p->next != NULL){  //只有指向的下一个节点不为null,才len++
        p = p->next;
        len++;
    }
    return len;
}


不带头节点:

int Length(LinkList L){
    int len=0;       //统计表长
    LNode *p = L;
    while(p!= NULL){  //当前指针(即头节点指向的第一个节点)不为空即可++,
    //带头节点的链表用这种方法长度会算上头节点。
        p = p->next;
        len++;
    }
    return len;
}


2.4.4.4 知识回顾与重要考点

24考研数据结构-线性表4,408,# 数据结构,考研,数据结构

2.4.5 单链表的创建操作

2.4.5.1 头插法建立单链表

带头节点;
若不带头节点,头插法就是插入头指针指向的第一个节点
平均时间复杂度O(n)
思路:每次都将生成的结点插入到链表的表头。

LinkList List_HeadInsert(LinkList &L){       //逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点
    L->next = NULL;                          //初始为空链表,这步不能少!

    scanf("%d", &x);                         //输入要插入的结点的值
    while(x!=9999){                          //输入9999表结束
        s = (LNode *)malloc(sizeof(LNode));  //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;                         //将新结点插入表中,L为头指针
        scanf("%d", &x);   
    }
    return L;
   
}


24考研数据结构-线性表4,408,# 数据结构,考研,数据结构

2.4.5.2 尾插法建立单链表

带头节点;
若不带头节点则需要特殊处理第一次插入数据的情况,是直接赋值而不是对下一个节点赋值。
时间复杂度O(n)

思路:每次将新节点插入到当前链表的表尾,所以必须增加一个尾指针r,使其始终指向当前链表的尾结点。
好处:生成的链表中结点的次序和输入数据的顺序会一致。

LinkList List_TailInsert(LinkList &L){       //正向建立单链表
    int x;                                   //设ElemType为整型int
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)
    LNode *s, *r = L;                        //r为表尾指针
    scanf("%d", &x);                         //输入要插入的结点的值
    while(x!=9999){                          //输入9999表结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s                                //r指针指向新的表尾结点
        scanf("%d", &x);   
    }
    r->next = NULL;                          //尾结点指针置空
    return L;
}



24考研数据结构-线性表4,408,# 数据结构,考研,数据结构

注意:
头插法和尾插法在初始化的时候
头插法:
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点
    L->next = NULL;                          //初始为空链表,这步不能少!
尾插法:
	L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)
	r->next = NULL;                          //尾结点指针置空
都是为了保证最后一个节点指向的不是脏数据,即malloc动态分配空间的时候可能,
指向的是一个脏数据

24考研数据结构-线性表4,408,# 数据结构,考研,数据结构

24考研数据结构-线性表4,408,# 数据结构,考研,数据结构

2.4.5.3 链表的逆置

算法思想:逆置链表初始为空,原表中结点从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点,如此循环,直至原链表为空;

带头节点:

void listReverse(linkedList &L)
{
	node *p,*s;
	//1.准备工作
	p = L->next;
	L->next = NULL;
	
	while(p)
	{
		//2.1 s记录正在处理的结点,p记录下一轮待处理的结点
		s = p; 			//s承接上一轮记录的位置
		p = p->next; 	//p为下一轮记录位置
		//2.2 把s插入 已逆置的部分 中
		s->next = L->next;  // L->next代表已逆置的第一结点,s的指针域指向它
		L->next = s;	//(头结点的指针域,即)第一结点 设置为s
		//2.2步骤相当于:
		//s 对 队伍(已逆置部分)的队首(已逆置的第一结点)说:你不要排在柜台前了,你排在我后面
		//等队伍排在s后面后,s自己排到了柜台前
	}
}

讲解
我们先看第一轮循环做了什么:

阅读顺序:黑色(初始)、蓝色(操作)、红色(理解)

24考研数据结构-线性表4,408,# 数据结构,考研,数据结构

第二轮:

阅读顺序:黑色(初始)、蓝色(操作)、红色(理解)

24考研数据结构-线性表4,408,# 数据结构,考研,数据结构
总结
不难发现:

  1. 链表逆置利用了s、p两个指针的移动实现
    每一轮循环体执行结束后,s指向刚刚逆置成功的结点,p指向下一轮待逆置的结点

  2. 为什么需要p?
    因为2.2步骤中s->next会被改写,
    若只有s,会丢失剩余的结点,
    这时候p起到暂存的作用,等待下一轮2.1步骤中的s=p找到它。文章来源地址https://www.toymoban.com/news/detail-603302.html

到了这里,关于24考研数据结构-线性表4的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构入门精讲 | 第十六篇】并查集知识点及考研408、企业面试练习

    上一篇中我们进行了散列表的相关练习,在这一篇中我们要学习的是并查集。 在许多实际应用场景中,我们需要对元素进行分组,并且在这些分组中进行查询和修改操作。比如,在图论中,我们需要将节点按照连通性进行分组,以便进行最小生成树、最短路径等算法;在计算

    2024年02月03日
    浏览(49)
  • 【玩转408数据结构】线性表——线性表的顺序表示(顺序表)

            通过前文,我们了解到线性表是具有相同数据类型的有限个数据元素序列;并且,线性表只是一种逻辑结构,其不同存储形式所展现出的也略有不同,那么今天我们来了解一下线性表的顺序存储——顺序表。         顺序表指的是将 逻辑上相邻的元素 存储在 物理位

    2024年02月19日
    浏览(51)
  • 24考研数据结构-——绪论2

    1.4.1 渐近时间复杂度 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(n),它表示随问题规模n的增大而增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的 渐近时间复杂度 ,简称时间复杂度。 大O表示“同阶”,

    2024年02月16日
    浏览(41)
  • 【玩转408数据结构】线性表——定义和基本操作

            线性表是算法题命题的重点,该类题目实现相对容易且代码量不高,但需要最优的性能(也就是其时间复杂度以及空间复杂度最优),这样才可以获得满分。所以在考研复习中,我们需要掌握线性表的基本操作,在平时多进行代码练习。当然在考场上,我们并不一

    2024年02月19日
    浏览(44)
  • 24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域:储存顶点vi firstarc链域:指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域:与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(54)
  • 【数据结构】24王道考研笔记——串

    串(字符串)是由零个或多个字符组成的有限序列。 子串:串中任意个连续的字符组成的子序列 主串:包含子串的串 字符在主串中的位置:字符在串中的序号 子串在主串中的位置:子串的第一个字符在主串中的位置 串的基本操作: 其中串执行比较操作时,从第一个字符开

    2024年02月15日
    浏览(63)
  • 【数据结构】24王道考研笔记——图

    图的定义 有向图以及无向图 简单图以及多重图 度 顶点-顶点间关系 连通图、强连通图 子图 (有向图也一样) 连通分量 强连通分量 生成树 生成森林 边的权、带权网/图 特殊形态的图 总结: 邻接矩阵 存储带权图(网): 对角线处可以填0或∞ 空间复杂度为O(|V| 2 )只和顶

    2024年02月17日
    浏览(47)
  • 24考研数据结构-数组和特殊矩阵

    数据结构是计算机科学中的基础概念,它涉及组织和存储数据的方式以及对数据的操作。在数据结构中,数组和特殊矩阵是两种常见的数据组织形式。本文将对数组和特殊矩阵进行介绍,并讨论它们在实际应用中的特点和用途。 数组是一种线性数据结构,它由相同类型的元素

    2024年02月14日
    浏览(35)
  • 【数据结构】24王道考研笔记——栈、队列和数组

    基本概念 栈是 只允许在一端进行插入或删除操作 的线性表。 栈顶:线性表允许进行插入删除的那一端 栈底:固定的,不允许进行插入删除的那一端 空栈:不含任何元素的空表 特点: 先进后出 基本操作: 常考题型: [外链图片转存失败,源站可能有防盗链机制,建议将图片

    2024年02月09日
    浏览(68)
  • 【数据结构】24王道考研笔记——树与二叉树

    树是n个结点的有限集合,n=0时,称为空树。非空树满足: 除了根节点外,任何一个结点都有且仅有一个前驱 结点的层次(深度):从上往下数 结点的高度:从下往上数 树的高度(深度):总共有多少层 结点的度:有几个孩子(分支) 树的度:各节点的度的最大值 森林:

    2024年02月13日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包