医药电子商务网站建设,南京网站建站公司,江西省赣州市中考成绩查询时间,网站标题如何设置梳理几个名词#xff1a;
逻辑地址#xff1a;就是说是第几个元素。
物理地址#xff1a;也就是存储地址#xff0c;在计算机里具体存放的位置。
线性表的存储结构分为#xff1a;
#xff08;1#xff09;顺序存储结构#xff1a;将数据依次存储在连续的整块物理空…梳理几个名词
逻辑地址就是说是第几个元素。
物理地址也就是存储地址在计算机里具体存放的位置。
线性表的存储结构分为
1顺序存储结构将数据依次存储在连续的整块物理空间中。简称顺序表。 特点通过计算地址能直接访问任何数据元素即随机访问。适合查找不适合插入删除操作。 2链式存储结构数据分散的存储在物理空间中通过一根线保存着它们之间的逻辑关系。简称链表、线性链表。 特点在逻辑上相邻的结点在物理上不必相邻。不能随机存取只能顺序存储。适合插入删除不适合访问。 一、线性结构 与 线性表
1、线性结构是最简单、最常用的一种数据结构。
2、线性结构特点 在数据元素的非空有限集合中除了第一个元素无直接前驱、最后一个元素无直接后继外集合中其余的每个数据元素都有唯一的直接前驱和唯一的直接后继。可以想象成把所有结点用一根直线穿起来。
3、线性表
含义是由 个类型相同的数据元素组成的有限序列。 即具有相同数据类型的n个数据元素的有限序列其中n为表长n0 是一个空表。
记作 。 当n 0除第一个元素无直接前驱、最后一个元素无直接后继外其余的元素都只有一个前驱和一个直接后继。即数据元素之间具有一对一的关系。 例如英文字母表A,B,C...Z就是一个简单的线性表。表中的每一个英文字母就是一个数据元素每个元素之间存在唯一的顺序关系比如B前面就是AB后面就是C以此类推。
4、线性表的逻辑结构
如下图所示 5、线性表的长度 线性表中元素的个数 被定义为线性表的长度 时被称为空表。
6、线性表的特点
1同一性。线性表中所有数据元素都具有相同的数据类型。
2有穷性。线性表由有限个数据元素组成表的长度就是表中数据元素的个数。
3有序性。线性表中相邻数据元素之间存在着顺序关系。
7、线性表的存储 在计算机中主要有两种存储结构用来存放线性表顺序存储结构和链式存储结构。 二、线性表的顺序存储结构——顺序表
1、含义 用一组地址连续的存储单元依次存储线性表中的各个元素。使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中即通过数据元素物理存储的连续性来反映数据元素之间逻辑上的相邻关系。就是说拿一块内存把数据挨个存进去这样就能保证表里元素的逻辑顺序和物理顺序相同。
2、顺序表 采用顺序存储结构的线性表简称为顺序表。
可将顺序表归纳为关系线性化结点顺序存。
3、线性表顺序存储结构示意图 从图中可以看出在顺序表中每个结点 的存储地址是该结点在表中的逻辑位置 i 的线性函数只要知道线性表中第一个元素的存储地址基地址和表中每个元素所占存储单元的多少就可以计算出线性表中任意一个数据元素的存储地址从而实现对顺序表中数据元素的随机存取。
4、地址的计算 假设线性表中有 n 个元素每个元素占 k 个单元第一个元素的地址为 也叫基地址 则可以公式计算出第 i 个元素的地址: 5、顺序表上的操作
1查找。可以通过元素所在的序号查找它也可以通过元素内容来查找。
2增加和删除。都会涉及到对元素进行移动。
3合并多个顺序表。
例如有如下顺序表现在要在第三个元素前面插入6此时就要把第三个元素一直到最后一个元素全部向后移动一个位置。 同理删除也一样只是把元素像前移动。
6、顺序表优缺点 方便存取不适合插入和删除。 三、线性表的链式存储
一种动态存储方法。通常将采用链式存储结构的线性表称为线性链表。
分类从链接方式的角度看单链表双链表循环链表从实现角度看动态链表静态链表
1、单链表
在顺序表中用一组地址连续的存储单元
链表由一系列结点组成的元素集合。
每个节点包含两部分
1、数据域item 存储数据的地方。
2、next指向下一个节点的指针。
通过结点之间的相互连接最终串联成一个链表。
列表顺序存储
链表链式存储
链表的方法
输出当前节点的数据域节点名.item
输出当前节点的下个节点的数据域节点名.next.item
举例1手动创建一个链表 现有三个节点分别是a,b,c各节点对应的数据域的值分别是123
class Node:def __init__(self, item):self.item itemself.next Nonea Node(1) # 实例化一个对象a即创建一个新节点a
b Node(2) # 创建一个新节点b
c Node(3)
a.next b # a的下一个值指向b
b.next c # b的下一个值指向c
print(a.item) # 输出节点a的数据域的值
print(a.next.item) # 输出a 的下一个节点的值
# 结果
1
2print(a.next.next.item) # 输出a 的下一个节点的下一个节点的值即a下下个节点的值
# 结果
3
效果图如下 2、头插法、尾插法
链表的头节点head
尾节点tail
头插法新节点先连上原来的头节点然后head指向新节点。先连上再改头
node.nexthead
headnode 尾插法不光要知道头在哪也要知道尾在哪。只有一个头节点时该节点既是头节点又是尾节点即head tail都指向这个节点接着再把新节点先连上原来的尾节点 tail指向新节点先连上再改尾
tail.next node
tail node 举例、分别利用头插法、尾插法来创建一个链表
举例1头插法
用头插法分别把1,2,3插到链表里。
class Node:def __init__(self, item):self.item itemself.next Nonedef creat_linklist_head(li): # 传入一个列表列表里面的值作为各个节点的值head Node(li[0]) # 根据列表的第一个元素创建头节点for i in li[1:]: # 列表除第一个元素外剩下的元素都将作为节点的值传进去node Node(i) # 创建一个新节点nodenode.next head # 头插法 新节点要先连上原来的头节点head node # head指向新节点return heada1 creat_linklist_head([1, 2, 3])
print(a1)
# 结果
__main__.Node object at 0x000002EA5BB59128进程已结束退出代码 0结果返回的是一个内存地址说明你创建了一个Node对象并打印了它的内存地址如果想打印出Node对象的属性可以在Node类中定义一个__str__方法来返回一个可读的字符串表示形式。
即加如下代码 def __str__(self):return str(self.item)
完整代码如下
class Node:def __init__(self, item):self.item itemself.next Nonedef __str__(self): # return str(self.item)def creat_linklist_head(li): # 传入一个列表列表里面的值作为各个节点的值head Node(li[0]) # 根据列表的第一个元素创建头节点for i in li[1:]: # 列表除第一个元素外剩下的元素都将作为节点的值传进去node Node(i) # 创建一个新节点node.next head # 头插法 新节点要先连上原来的头节点head node # head指向新节点return heada1 creat_linklist_head([1, 2, 3])
print(a1)
# 结果
3
为什么结果为3
因为创建一个单链表函数返回值是head也就是头节点而我们把123按头插法插进去之后头节点的数据域就变成的3所以返回3 。
或者上面的写法中把print(a1)改下改成
print(a.item) # 输出头节点的数据域
print(a.next.item) # 输出头节点的下一个节点的数据域
结果
3
2
延申怎么遍历链表也就是说怎么从头到尾查看所有节点的数据域。
class Node:def __init__(self, item):self.item itemself.next Nonedef __str__(self):return str(self.item)def creat_linklist_head(li): # 传入一个列表列表里面的值作为各个节点的值head Node(li[0]) # 根据列表的第一个元素创建头节点for i in li[1:]: # 列表除第一个元素外剩下的元素都将作为节点的值传进去node Node(i) # 创建一个新节点node.next head # 头插法 新节点要先连上原来的头节点head node # head指向新节点return headdef print_linklist(a): # 链表的遍历while a: # 只要链表不是空的就会一直打印print(a.item, end,) # 打印节点的值a a.next # 类似i1,打印完当前节点指针指向下个节点这样才能循环遍历a1 creat_linklist_head([1, 2, 3]) # 返回头节点
print_linklist(a1)
# 结果
3,2,1,
注意
def print_linklist(a):while a: # 只要链表不是空的就会一直打印print(a.item, end,) # 打印节点的值a a.next
aa.next是循环变量类似i1的作用打印完当前节点的数据域的值后就要把指针指向下一个节点否则就一直打印当前这一个节点的数据域程序就会进入死循环这里就会一直打印3 。
可以看到头插法得到的是倒叙的因为插入的是123结果确实321下面的尾插法得到的是正序的。
举例2尾插法
class Node:def __init__(self, item):self.item itemself.next Nonedef __str__(self):return str(self.item)# 尾插法
def creat_linklist_tail(li): # 传入一个列表列表里面的值作为各个节点的值head Node(li[0]) # 将列表的第一个元素作为头节点tail head #因为此时只有一个头节点所以它既是头节点又是尾节点即head tail都指向这个节点for i in li[1:]: # 列表除第一个元素外剩下的元素都将作为节点的值传进去node Node(i) # 创建一个新节点tail.next node # 尾插法 新节点先连上原来的尾节点tail node # tail指向新节点return head # 返回头节点因为只有头节点有next方法def print_linklist(a): # 链表的遍历while a: # 只要链表不是空的就会一直打印print(a.item, end,) # 打印节点的值a a.next # 类似i1,打印完当前节点指针指向下个节点这样才能循环遍历a1 creat_linklist_tail([1, 2, 3])
print_linklist(a1)
# 结果
1,2,3,注意尾插法
第一步头节点创建之后head、tail都指向头节点。
第二步新节点要先连上原来的尾节点 tail.next node
第三步tail指向新节点tail node 举例3中间插入或删除一个节点
1、插入新节点插到链表除了首尾之外的任意位置。
假设新节点名字为 p当前节点叫 curNode
第一步先把新节点跟当前节点的下个节点相连p.nextcurNode.next
第二步当前节点的下一个节点指向pcurNode.nextp 2、删除
直接curNode.nextcurNode.next.next即可。
如果要删除的节点设为p话pcurNode.next,那么上句改成curNode.nextp.next也一样。
