数据结构chapter_02
2019-06-19 13:23:02 9 举报AI智能生成
数据结构java第二章
作者其他创作
大纲/内容
线性结构特点
唯一"第一个数据元素"
唯一"最后一个数据元素"
除第一个,每个元素均有唯一一个直接前驱
除最后一个,唯一一个直接后驱
顺序表示与实现
定义
一组地址连续的存储单元依次存储线性表的数据元素
用顺序存储实现的线性表成为顺序表
逻辑顺序与物理顺序一致
随机存取结构,采用数组存储数据元素
设每个元素占c个存储单元 Loc(ai) = Loc(a0) + (i-1)*c
原则
泛型类
成员变量必须为私有权限
构造方法
自动扩充容量
指定元素序号不正确的操作处理
插入操作
n+1个位置可以插入数据,概率p = 1/(n+1) 总的移动次数 n-i 平均总移动次数为 O(n)
删除操作
删除第i个元素的概率为1/n,移动节点的次数为:n-i-1,平均移动次数为O(n)
对象相等的比较
长度相同且对应元素相同
this与list引用同一顺序表对象
两个顺序表对象,this.n != list.n , 则不相等
两个顺序表对象 , this.n == list.n且所有元素对应相等,则相等
浅拷贝
深拷贝
链式表示与实现
链式存储结构
用一组任意的存储单元存储线性表中的数据元素,可以连续 , 可以不连续,甚至零散
若顺序表浅拷贝,this.element与list.element引用同1️⃣数组,则this.element == list.element
逻辑顺序与物理顺序不一定相同
节点结构:数据域和地址域
每个节点只含一个地址域,称为单链表
每个节点含两个地址域则成为双链表
单链表
单链表节点的连接
单链表节点的连接
单链表的遍历
插入操作
空表插入/头插入
head = new Node<T>(x , head);
中间插入/尾插入
front.next = new Node<T>(x ,front.next);
删除操作
头删除
head=head.next
中间/尾删除
front.next = front.next.next
头结点
使链表的(包括空表)的头指针非空,则对单链表的插入,删除操作不需要取分操作位置
不存储数据
双链表
分为前驱与后继节点
结构与特性
空双链表
head.next == null && head.prev == null
非空双链表
p= p.next.prev=p.prev.next
抽象数据类型
线性表
元素个数n为线性表的长度
n=0时为空表
数据类型定义
??? PPT
0 条评论
下一页
