学无先后,达者为师

网站首页 编程语言 正文

数据结构:顺序表和链表学习小结

作者:爱笑的蓝孩子~ 更新时间: 2022-09-22 编程语言

一、顺序表

二.链表

目录

 一、顺序表

二.链表



一.顺序表

1.基本概念:是指用一组地址连续的存储单元依次存储数据元素的线性结构。我们常见的顺序表有数组。

2.操作方面:可以基本实现数据的增删改查,因为有下标索引,所以查询工作很方便,效率很高。但是在增加元素和删除就不是很方便了,因为元素要整体移位置,会比较麻烦,下面的链表可以解决这个问题。

3.时间复杂度的对比:如图所示

二.链表

1.链表和顺序表有所区别,储存地址不一定是连续的。当查询操作多的时候一般用顺序表,删除和插入多的一般用链表,选择合适的数据结构很重要。

2.单链表有head头结点,后继结点,尾结点指向为null。用指针进行遍历时,While(p.next!=null)即可。

图示:

3.head头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等类的附加信息。头结点的指针域指向首元结点。并且头结点不计入链表的长度。

4.注意:单链表只有后继结点,可以向后移动,不可以回头。当结点在向后移动时,要保存p结点往后的结点,可以设置一个临时q=p.next来保存p的后继结点。

5.在插入时,注意顺序,如:要求在head和head.next之间插入一个s,代码如下:

s.next=head.next;   

head.next=s;(注:两者顺序不能调换)

6.删除时,单链表与顺序表比较很是方便,时间复杂度是O(1),只需将要删除的结点的后继结点改为待删除结点的后继结点即可。

在java中删除的结点会自动回收,在c语言中要自己释放删除的结点:free(p)。

实现代码如下:

                 s.next=p.next; (s为待删除结点p的前一个结点)

7.头插法:倒序排列——可以理解为将其插在head和head.next之间。实现代码:将数组元素值传递给s结点,for循环遍历

                  s.next=L.head.next;

                   L.head.next=s;

图示:

注:在实际运用中一般要用一个q来临时保存s的后继结点。

8.尾插法:正序排列——可以理解为一个个按顺序插在head后面。实现代码:将数组元素值传递给s结点,for循环遍历

将t设置为L.head

t.next=s;

            t=s;//将t向后移动

图示:

9.单链表例题:

(一)求中位数:

方法一,找到编号(n-1)/2+1位置的结点即可。其中可以用Math.cell(n/2f)向上取整代替,其中f是为了使其里面变成double类型。

方法二,快慢指针法,快指针一次移动两个结点,慢结点一次移动一个结点。所有当快指针遍历完时,慢指针只走了一般,即所指向的位置就是中位数。

(二)统计最大值个数:

方法一,直观方法,先找最大值,再遍历寻找等于最大值的数,统计个数,需要用到两次while循环。

方法二,设置p指向首结点,初始化最大值为首结点的值,p=p.next不停的向后移动。

思想:当遍历未结束时,将后继的结点和max比较,比它大设置新的max值,个数记为1。再次遇到相同的值,个数再加1……知道遇到比max大的后继结点,在设置新的max值,重置个数为1,依次进行直到结束。一次while循环即可。

(三)二路归并有序表A和B合并为新的升序表C,空间复杂度为O(1),只能结点重组来建立单链表C。

(四)将A和B中的相同元素放入单链表C,不改变A和B,只能通过复制来建立单链表C。两者注意区分。

图示:

10.双链表:可以理解为高级一些的链表,结点由前端指针域,数据域和后端指针域三要素组成。每一个结点有两个指向,其中头结点的前端指向null,尾结点后端指向null。

图示如下:

11.双链表和单链表的对比:双链表更加高效,可以实现从前往后,也可以从后往前遍历;而单链表则是比较单一,只能从前往后,只有一个指针,无法找前驱结点。

在删除一个结点时,双链表不需要找到前驱结点,只需要找到删除的结点就可以实现删除操作。  

12.循环链表:顾名思义,就是是表中最后一个结点的指针域指向头结点(首节点和末节点被连接在一起),整个链表形成一个环。

                                                            图示:

13.循环链表和单链表区别:单链表的尾结点指针指向空地址,表示这就是最后的结点了。循环链表的尾结点指针是指向链表的头结点。

14.循环链表的运用:适用于存储有循环特点的数据,比如约瑟夫问题:由一群元素构成的环形链表,首先由某个元素开始报数,报到K时的那个元素需要出圈,然后又由下一个元素开始报数,直到全部的元素出圈时才结束。

原文链接:https://blog.csdn.net/qq_67931344/article/details/126910322

栏目分类
最近更新