[size=xx-large][/size] 1.首先来谈谈数据在计算机世界的存储方式,数据元素在计算机中有两种不同的表示方法;一种是顺序的、一种是非顺序的。并由此得到两种不同的存储方式;既顺序存储结构、链式存储结构。
顺序存储结构主要是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系,典型的数据结构就是经常用到的数组、线性表,其实线性表也是基于数组来实现的,
存储方式如下:
a表示数组的起始地址;
数组元素 a[0] a[1] a[2] … a[i] … a[n]
地 址 α α+1 α+2 … α+i α+ n
二维数组也是类似如此: for example Array[m][n]; 其相当于由m个一维数组构成的数据存储,Array[i][0]指向每一个一维数组的起始地址;
[img]
[/img]
2.有了数组这一种基本的数组结构作为基础,接下来,我们是否会进行一些扩展呢?
首先我们认识了数组是什么?它有什么优、缺、点,它适合什么样的场合?对我们编程更有利?
利用数组来组织数据结构
优点是:存储效率高,存取速度快。
缺点:
a. 对于数据元素个数动态增长的情况,由于数组个数不能自由扩充,一旦空间用完
就不能再向里加入新元素,否则,就会导致系统停工。
b. 插入、删除操作不方便,因为插入、删除操作会导致大量元素的移动,对于数组长度过大的话系统也可能没有那么多的连续的存储空间来开辟;
首先我们一步一步的来,首先对于缺点a,我们是否可进行优化?使其能够实现动态添加的功能,首先我们要明确一点,要优化其本质的实现机制还是数组,只不过我们要实现自动扩容的功能;因此我们可以这样做:
给定一个数组的初始空间大小,这毫无疑问,数组吗,在定义时就要指定空间大小,其次当我们在往这个容器添加元素时,当空间不够时,我们将向系统申请一个空间更大的数组,申请完成后再进行拷贝赋值;
具体实现代码如下:
package java0418;
public class MyQueue<E> {
int origin = 100;
int increase = 10;
Object Array[] = new Object[0];
int len = 0;
/*
* 无参构造
*/
public MyQueue() {
Array = new Object[origin];
}
/*
* 用户自定义一个队列的初始长度
*/
public MyQueue(int len) {
origin = len;
Array = new Object[len];
}
/*
* 用户自定义容器的初始长度和增长幅度
*/
public MyQueue(int len, int inc) {
origin = len;
increase = inc;
Array = new Object[len];
}
/*
* 添加元素的方法add();
*/
public void add(E data) {
if (len >= Array.length) {
Object Arc[] = new Object[Array.length + increase];
System.arraycopy(Array, 0, Arc, 0, Array.length);
Array = Arc;
}
Array[len++] = data;
}
public E getElement(int index) {
E e = (E) Array[index];
return e;
}
}
做到这一步,哎!长叹一口气!对于缺点a我们到是可以解决了,但是我们有没有发现每次在空间不够的时候我们都要重新拷贝一次(System.arraycopy(Array, 0, Arc, 0, Array.length);
)
你写的这个程序是要给用户用的,当然咯你自己用的话也行,只不过这样就达不到我们写程序的最终目的了吧,乔布斯不是说过嘛:“活着就是要改变世界”,怎么改变啊?就是让更多的用户来用你的程序,给用户提供方便、友好、快捷的软件服务。所以我们不能把程序写死,要适当增加一些可供用户选择的服务,比如上面的小小列子吧,有的用户可能用的时候存放的数据并不是很多,它就可以指定小一点的初始长度和增长幅度,反之就可以设置大一点。
3.对于b来说,我们想怎么解决呢?想想我们上面讨论的都是应用了计算机的顺序存储结构,那对于这个问题我们是否可以应用计算机的随机链式存储来实现呢?答案是肯定的,不然要这个链式存储结构干嘛,于是我们就可以想到用链表来存放数据,
链表有两个域,一个是数据域,一个是指针域,数据域是存放你要存储的数据,指针域就是指向链表下一个节点的指针;
指针作为维系结点的纽带,可以通过它实现链式存储。假设有五个学生某一门功课的成绩分别为A、B、C、D和E,这五个数据在内存中的存储单元地址分别为1248、1488、1366、1022和1520,其链表结构如图所示。
[img]
[/img]
链表有一个“头指针”变量,图中以 head表示,它存放一个地址,该地址指向链表中第一个结点,第一个结点又指向第二个结点……直到最后一个结点。该结点不再指向其他结点,它称为“表尾”,它的地址部分存放一个“NULL”(表示“空地址”),链表到此结束。链表中每个结点都包括两个部分:用户需要用的实际数据和下一个结点的地址。
然后我们就可以根据链表的特性构造一个链表类:
package com.hust.edu.dynProxy;
public class MyList<E> {
private E data; // 数据域
private MyList<E> next; // 指向下一个节点的指针域
/*
* 相应的get和Set方法
*/
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public MyList<E> getNext() {
return next;
}
public void setNext(MyList<E> next) {
this.next = next;
}
}
再用一个类来进行创建一个链表:插入操作
[img]
[/img]
删除操作:
[img]
[/img]
具体实现代码如下;
package com.hust.edu.dynProxy;
public class LinkList<E> {
private MyList<E> root; // 链表的头结点
private MyList<E> teml; // 链表的尾节点
/*
* 对链表进行加入操作
*/
public void add(E data) {
if (root == null) {
root = new MyList<E>();
teml = new MyList<E>();
root.setData(data);
teml = root;
}
else {
MyList<E> tem = new MyList<E>();
tem.setData(data);
teml.setNext(tem);
teml = tem;
}
}
/*
* 对链表进行查找
*/
public E getElement(int index) {
int i = 1;
MyList<E> tem = new MyList<E>();
tem = root;
while (i < index && tem != null) {
i++;
tem = tem.getNext();
}
if (i == index && tem != null) {
return (E) tem.getData();
}
return null;
}
/**
* 在指定的位置插入元素
*/
public void insert(E data, int index) {
int i = 1;
MyList<E> tem = new MyList<E>();
tem = root;
while (tem != null && i < index) {
i++;
tem = tem.getNext();
}
if (tem == null) {
return;
}
else {
MyList<E> p = new MyList<E>();
p.setData(data);
p.setNext(tem.getNext());
tem.setNext(p);
}
}
/**
* 删除第index个元素
*/
public void delete(int index) {
int i = 1;
MyList<E> tem = new MyList<E>();
tem = root;
if (index == 1) {
root = root.getNext();
}
while (tem != null && i < index) {
i++;
tem = tem.getNext();
}
if (tem == null) {
return;
}
else {
MyList<E> q = new MyList<E>();
q = tem.getNext();
tem.setNext(q.getNext());
}
}
/**
* 打印链表
*/
public void printLink() {
MyList<E> tem = new MyList<E>();
tem = root;
while (tem != null) {
System.out.println((E) tem.getData());
tem = tem.getNext();
}
}
public static void main(String[] args) {
LinkList<String> lin = new LinkList<String>();
lin.add("I ");
lin.add("want ");
lin.add("to ");
lin.add("play ");
lin.add("a ");
lin.add("game... ");
String s = lin.getElement(4);
lin.delete(1);
System.out.println(s);
lin.printLink();
}
}
运行结果如下:
play
want
to
play
a
game...
小结:
a.链表优于数组的:
1.插入与删除的操作.如果数组的中间插入一个元素,那么这个元素后的所有元素的内存地址都要往后移动.删除的话同理.只有对数据的最后一个元素进行插入删除操作时,才比较快.链表只需要更改有必要更改的节点内的节点信息就够了.并不需要更改节点的内存地址.
2.内存地址的利用率方面.不管你内存里还有多少空间,如果没办法一次性给出数组所需的要空间,那就会提示内存不足,磁盘空间整理的原因之一在这里.而链表可以是分散的空间地址.
3.链表的扩展性比数组好.因为一个数组建立后所占用的空间大小就是固定的.如果满了就没法扩展.只能新建一个更大空间的数组.而链表不是固定的,可以很方便的扩展.
b.链表的缺点是不利于查找,只能通过顺次指针访问,查询效率低;
总之,当你碰到什么样的问题时,根据问题的性质选择恰当的数据结构进行优化你的程 序,
各有利弊,避其锋芒 击其惰归。
- 大小: 66.5 KB
- 大小: 34.8 KB
- 大小: 11.9 KB
- 大小: 10.7 KB
分享到:
相关推荐
3.2.3 队列的链表存储结构 3.3 栈和队列的算法实现举例 习题三 第4章 串 4.1 串的基本概念 4.2 串的存储结构 4.2.1 串的顺序存储 4.2.2 串的链表存储 4.2.3 串变量的存储映象 4.3 串的运算 4.3.1 串的运算...
【习0.5】 实验0.5 找出一个二维数组的鞍点 2 【习0.6】 实验0.6 复数类。 2 【习0.7】 实验0.8 图形接口与实现图形接口的类 2 第1章 绪论 3 【习1.1】 实验1.1 判断数组元素是否已按升序排序。 3 【习1.2】 实验1.3...
9.1 单端优先队列和双端优先队列 9.2 左倾树 9.3 二项式堆 9.4 Fibonacci堆 9.5 配偶堆 9.6 对称最小-最大堆 9.7 区间堆 9.8 参考文献和选读材料 第10章 高效二叉查找树 10.1 最优二叉查找树 10.2 AVL树 ...
1.4.1 指针与数组 1.4.2 指针与复制构造函数 1.4.3 指针与析构函数 1.4.4 指针和引用变量 1.4.5 函数指针 1.5 多态性 1.6 C++和面向对象程序设计 1.7 标准模板库 1.7.1 容器 1.7.2 迭代器 ...
leetcode二维数组 编程练习 包含常见的编程网站的练习习题(leetcode、牛客等)----待完成中... 也同时包含复习面试的编程练习 该src/main/java目录下,以文件夹命名,表示的是不同的来源 每个文件均可单独运行 其他...
习题三 链表(线性表、栈和队列)---------------------------------------------9 习题四 串-----------------------------------------------------------------12 习题五 数组 ---------------------------------...
数组 字符串 链表 树 排序和搜索 动态规划 设计问题 数学 其他 中级算法 数组和字符串 链表 树和图 排序和搜索 数学 其他 高级算法 数组和字符串 链表 学习 数组和字符串 数组简介 二维数组简介 字符串简介 双指针...
第二章 数组 第三章 链表 第四章 栈与队列 第五章 递归 第六章 树与森林 第七章 集合与搜索 第八章 图 第九章 排序 第十章 搜索与散列 --------------- 习题从第一章到第十章(Word档) 答案从第一章到第十章(Word...
3.2.1 本章所涉及的结构体定义 56 3.2.2 顺序栈 57 3.2.3 链栈 59 3.2.4 栈的应用 60 3.2.5 顺序队 64 3.2.6 链队 66 3.3 抽象数据类型 69 ▲真题仿造 71 真题仿造答案与讲解 71 习题 真题精选 74 习题答案 真题精选...
11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用 185 11.11 类型定义符typedef 12 位运算 12.1 位运算符C语言提供了六种位运算符: 189 ...
11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用 185 11.11 类型定义符typedef 12 位运算 12.1 位运算符C语言提供了六种位运算符: 189 ...
03-004队列的定义与存储、顺序队列、链式队列、循环队列 04-001串的定义、表示与实现 04-002串的模式匹配算法 04-003串的模式匹配算法的一种改进算法 05-001数组的定义、顺序表示和实现 05-002矩阵相乘的一般算法...
用循环数组实现队列 ……… 应用 …………………………… 本章小结 ……………………………… 习题 …………………………………… 第 章 递归…………………………… 递归的概念 …………………… 递归程序设计……...
15.3.5 数组链表应用 15.4 集Set 15.4.1 排序集接口 15.4.2 哈希集和树集 15.4.3 树集应用 15.5 映射Map 15.5.1 映射接口方法 15.5.2 排序映射接口 15.5.3 哈希映射和树映射 15.5.4 哈希映射应用 15.5.5 ...
leetcode数组下标大于间距 implement data structure and algorithms data_struct: 主要包括数据结构的java实现 1.数组 2.并查集 3.图 4.链表 5.队列 6.栈 7.树 divide_conquer:分治 1.活动选择问题 2.输入一个整形...
3.4.2 循环队列——队列的顺序表示和实现 62 3.4.3 链队——队列的链式表示和实现 65 3.5 队列的应用 67 3.6 小结 69 习题 69 第4章 串、数组和广义表 73 4.1 串 73 4.1.1 串的类型定义 73 4.1.2 串...
不错的C++ 数据结构和算法教程 ...9. 数组和字符串 10.递归 11.结构 12.类和数据抽象 13.继承和组成 14.指针、类、表及虚函数 15.重载与模板 16.链表 17.栈和队列 18.查找和排序算法 19.二叉树 20.图 21.标准模板库