简介 一种逻辑结构,相同数据类型的n个数据元素的有限序列,除第一个元素外,每个元素有且仅有一个直接前驱,除最后一个元素外,每个元素有且仅有一个直接后继。线性表的特点:(1)元素个数有限 (2)逻辑上元素有先后次序(3)数据类型相同 ...
简介
一种逻辑结构,相同数据类型的n个数据元素的有限序列,除第一个元素外,每个元素有且仅有一个直接前驱,除最后一个元素外,每个元素有且仅有一个直接后继。
线性表的特点:
(1)元素个数有限 (2)逻辑上元素有先后次序
(3)数据类型相同 (4)仅讨论元素间的逻辑关系
注:线性表是逻辑结构,顺序表和链表是存储结构。
1.顺序存储
顺序表,使用数组实现,一组地址连续的存储单元,数组大小有两种方式指定,一是静态分配,二是动态扩展。
注:线性表从1开始,而数组从0开始。
优点:随机访问特性,查找O(1)时间,存储密度高;逻辑上相邻的元素,物理上也相邻;
缺点:插入删除需移动大量元素。
顺序表相关的操作跟数组有关,一般都是移动数组元素。
这里说一下插入和删除时的边界条件,首先线性表从1开始,数组从0开始,单纯的文件说明不够直接,来看图说话吧。
插入时:对于线性表来说最小能插入的位置是1,最大能插入的位置是8(=7+1),所以 1<= index <=(7+1);移动数组元素时要注意,for (int i = count; i >= index; i--) { items[i] = items[i-1];}
删除时:只能在蓝色方块之间寻找节点删除,即1 <= index <= 7。移动元素,for (i = index; i < count; i++) { items[i-1] = items[i];}
2.链式存储
链表的定义是递归的,它或者为空null,或者指向另一个节点node的引用,这个节点含有下一个节点或链表的引用。
与顺序存储相比,允许存储空间不连续,插入删除时不需要移动大量的元素,只需修改指针即可,但查找某个元素,只能从头遍历整个链表。
Java中使用嵌套类来定义节点的抽象数据类型:
private class Node{ // 链表节点的嵌套类 T item; // 节点内容 Node next; // 后继节点}
海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理:https://www.xlkjsw.com
原标题:线性表
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。