

首页  思维导图  详情



数据结构chapter_02

2019-06-19 13:23:02   9  举报





AI智能生成

数据结构java第二章

数据结构

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

 Collect

Get Started

chapter_02

 Collect

Get Started

chapter_02

 Collect

Get Started

数据结构与算法

 Collect

Get Started

数据结构





0 条评论

下一页