关键词：
线性表的定义
- 线性表的逻辑特征：
- ①有且仅有一个称为开始元素的a1，她没有前趋，仅有一个后继结点a2；
- ②有且仅有一个称为终端元素的an,他没有后继，只有一个直接前驱a(n-1)；
- ③其余元素ai(2≤i≤n-1)称为内部元素，他们都有且仅有一个直接前驱a(i-1)和直接后继a(i+1)。
线性表的基本运算
- 线性表初始化
- 求表长
- 按索引值查找元素
- 按值查找
- 插入元素
- 删除
线性表的存储之顺序存储
线性表顺序存储的定义：线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组连续的存储单元里，用这种方式存储的线性表称为顺序表。
定义线性表
- 定义线性表的默认空间大小，定义一个数组，定义数组的长度，初始化一个size用来保存里面元素的个数。
/** 定义线性表默认空间大小 */
private final Integer ListSize=100;
/**定义数组长度*/
private Integer Len;
/** 定义线性表保存的数据类型
* 使用泛型*/
private Object[] list;
/**存一个当前元素的个数*/
private Integer size=0;
/**定义默认线性表*/
public SeqList()
Len = ListSize;
this.list = new Object[Len];
size++;
- 初始化线性表
- 把线性表里面的元素全部置空
/**清空线性表*/
public void clear()
for (int i = 0; i < size; i++)
list[i]=null;
size=0;
添加元素
- 这里采用尾插法，即每次默认将元素放在最后面
/**添加元素到指定位置*/
public void insert(T element , int index)
if(index>=Len || index<0)
throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
Capacity(size+1);
//将添加元素的元素往后移一位
for (int i = size-2; i >= index-1; i--)
list[i+1]=list[i];
list[index-1]=element;
size++;
/**添加元素到末尾*/
public void add(T element)
insert(element,size);
查找元素
- 这个模块分为按索引值查找，和按元素值查找
/**线性表的查找
* 按索引值查找*/
public T getNode(int index)
return (T)list[index-1];
/**按元素值查找返回索引值*/
public int LocateNode(T t)
for(int i=0;i<list.length;i++)
if(list[i].equals(t))
return i+1;
System.out.println("没有找到该元素！");
return -1;
删除元素
- 删除元素，又分为删除指定元素，和删除最后一个元素
/**删除指定位置的元素*/
public T delete(int index)
if(!OutIndex(index))
throw new IndexOutOfBoundsException("删除位置不在线性表的索引范围内！");
for (int i = index-1; i < size-1; i++)
list[i]=list[i+1];
/*if(size - index >0)
System.arraycopy(list,index,list,index-1,size-index);
*/
list[size-1]=null;
size--;
return (T) list;
/**删除最后一个元素*/
public T remove()
return delete(size-1);
打印线性表
- 打印线性表，其实就是重写一个toString方法，将线性表打印出来
/**循环打印线性表*/
@Override
public String toString()
StringBuilder sb = new StringBuilder();
if(isEmpty())
return "[]";
else
sb.append("[");
for (int i = 0; i < size-1; i++)
int a=0;
if(list[i]!=null)
sb.append(list[ i ]);
else
break;
sb.append(",");
sb.append("]");
sb.deleteCharAt(sb.indexOf(",]"));
return sb.toString();
实现的完整代码
class SeqList<T>
/** 定义线性表默认空间大小 */
private final Integer ListSize=100;
/**定义数组长度*/
private Integer Len;
/** 定义线性表保存的数据类型
* 使用泛型*/
private Object[] list;
/**存一个当前元素的个数*/
private Integer size=0;
/**定义默认线性表*/
public SeqList()
Len = ListSize;
this.list = new Object[Len];
size++;
/**定义自定义长度的线性表*/
public SeqList(int length)
Len = length;
list = new Object[Len];
size++;
/**获取当前线性表的长度*/
public int getLen()
return Len;
/**获取当前线性表元素的个数*/
public int getSize()
return size;
/**根据元素查找在线性表中的位置，未找到返回-1*/
public int getIndex(T element)
for (int i = 0; i < size; i++)
if(list[i].equals(element))
return i;
return -1;
/**判断是否表满或表空*/
private boolean OutIndex(int index)
//return size==Len;//不扩容的话，可以这样写，但是怕扩容
if(index>size || index<0)
return false;
else
return true;
/**根据索引值返回元素*/
private T getElement(int index)
if(!OutIndex(index))
throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
/* System.out.println("输入索引超过了线性的范围");
return null; */
return (T)list[index];
/**扩容*/
private T Capacity(int capacity)
if(capacity<Len)
Len = Len+(Len+1)/2;
if(capacity<Len)
Capacity(Len);
else
list = Arrays.copyOf(list,Len);
return (T) list;
return (T)list;
/**添加元素到指定位置*/
public void insert(T element , int index)
if(index>=Len || index<0)
throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
Capacity(size+1);
//将添加元素的元素往后移一位
for (int i = size-2; i >= index-1; i--)
list[i+1]=list[i];
// System.out.println("i="+i);
list[index-1]=element;
size++;
/**添加元素到末尾*/
public void add(T element)
insert(element,size);
/**判断元素表是否为空*/
public boolean isEmpty()
return size==0;
/**删除指定位置的元素*/
public T delete(int index)
if(!OutIndex(index))
throw new IndexOutOfBoundsException("删除位置不在线性表的索引范围内！");
for (int i = index-1; i < size-1; i++)
list[i]=list[i+1];
/*if(size - index >0)
System.arraycopy(list,index,list,index-1,size-index);
*/
list[size-1]=null;
size--;
return (T) list;
/**删除最后一个元素*/
public T remove()
return delete(size-1);
/**清空线性表*/
public void clear()
for (int i = 0; i < size; i++)
list[i]=null;
size=0;
/**线性表的查找
* 按索引值查找*/
public T getNode(int index)
return (T)list[index-1];
/**按元素值查找返回索引值*/
public int LocateNode(T t)
for(int i=0;i<list.length;i++)
if(list[i].equals(t))
return i+1;
System.out.println("没有找到该元素！");
return -1;
/**循环打印线性表*/
@Override
public String toString()
StringBuilder sb = new StringBuilder();
if(isEmpty())
return "[]";
else
sb.append("[");
for (int i = 0; i < size-1; i++)
int a=0;
if(list[i]!=null)
sb.append(list[ i ]);
else
break;
sb.append(",");
sb.append("]");
sb.deleteCharAt(sb.indexOf(",]"));
return sb.toString();
测试一下
- 测试代码
public static void main(String[] args)
SeqList<String> seqList = new SeqList<String>();
//添加一个元素
seqList.add("pier");
seqList.add("真好看");
seqList.add("90度点头");
System.out.println("添加后的线性表为\\n\\t"+seqList.toString());
seqList.insert("pipi",1);
System.out.println("在位置1的地方添加元素后的线性表为\\n\\t"+seqList.toString());
seqList.delete(1);
System.out.println("删除第二个元素后的线性表为\\n\\t"+seqList.toString());
System.out.println("pier时第"+seqList.LocateNode("pier")+"个元素");
System.out.println("第1个元素是"+seqList.getNode(1)+"。");
- 运行结果
数据结构线性表之实现单循环链表(代码片段)
数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实... 查看详情
线性表之顺序存储结构(顺序表)(代码片段)
目录1.线性表2.顺序存储结构(顺序表)2.1顺序表一般可以分为： 1.静态顺序表：使用定长数组存储元素 1.1静态顺序表:顺序表的大小是确定的,容量是固定的. 结论:静态顺序表不是很常量,了解就行.2.动态顺序表：... 查看详情
数据结构线性表之顺序表arraylist(代码片段)
...ArrayList。为什么我们称其为顺序表呢？原因顾名思义是该数据结构在逻辑上和物理结构上的存储顺序均是连续的。下面，我们就以一张图来说明什么是顺序表。 这个图代表逻辑上的9个元素，每一个位置均存储一个数据，数... 查看详情
数据结构学习总结线性表之顺序表(代码片段)
通过前面的学习知道，具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。那么，什么是线性表呢？线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一... 查看详情
数据结构线性表之实现单链表(代码片段)
数据结构线性表之实现单链表数据结构线性表之实现单链表相关文章单链表定义单链表相关操作数据结构线性表之实现单链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实现顺序表(三)数... 查看详情
线性表之顺序存储结构实现(上)
一，线性表的概念以及数学定义1.线性表的概念 零个或多个数据元素的有限序列。首先说明这是一个序列，也就是说数据元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都... 查看详情
数据结构——线性表之顺序表篇(代码片段)
目录前言顺序表的介绍和简单实现关于顺序表顺序表的分类顺序表的初步组成功能函数的声明功能函数的实现初始化检查容量判断是否需要扩容头插头删 尾插尾删指定数据位置插入指定数据删除寻找数据并返回下标销毁顺序表... 查看详情
数据结构与算法-线性表之静态链表(代码片段)
...针，那么在没有引用或指针的语言中，该怎么实现这个的数据结构呢？一、简介 定义：用数组代替指针或引用来描述单链表，即用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法； 上面的静态链表图有两个... 查看详情
02线性表之顺序表(代码片段)
肚子饿了就要吃 ~ 嗝 ———路飞 目录1.本章重点2.线性表3.顺序表实现3.1顺序表的概念及结构4.静态顺序表5.动态顺序表 5.1“增”尾插：头插：5.2“删”尾删头删5.3随机“插入”5.4随机“删除”5.5内存销毁5.6“改”5... 查看详情
数据结构学习总结线性表之单链表(代码片段)
一，回忆链表 链表，别名链式存储结构或单链表，用于存储逻辑关系为"一对一"的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。&nbs... 查看详情
线性链表之顺序表
...，具有这一特点的存储结构称为[随机存储]。使用的基本数据结构:数组特点：顺序存取，随机访问。/* Name:SeqList Copyright:1.0 Author:JohnnyZen Date:04/06/1721:51 Description:线性链表之顺序表*// 查看详情
线性表之顺序表(代码片段)
线性表的结构体定义：#defineMaxSize100typedefstructintdata[MaxSize];intlength;Sqlist; 顺序表在内存中以数组形式保存，是一组连续的内存空间。顺序表基本算法：构造一个空的线性表：//初始化线性表STATUSInitList(Sqlist&L)//置表长为0L.len... 查看详情
数据结构与算法合集
数据结构【Java】大话数据结构(1)线性表之顺序存储结构 【Java】大话数据结构(2)线性表之单链表 【Java】大话数据结构(3)线性表之静态链表 【Java】大话数据结构(4)线性表之循环链表 【Java】大话数据结构(5)线... 查看详情
线性表之单链表(代码片段)
在学完线性表之后，总结一下顺序表的优缺点优点无须为元素之间的逻辑结构增添额外的储存空间，自成一体。随机存取，十分方便。缺点空间利用率不高，容易造成“碎片”。插入删除操作需要移动大量的元素。当线性... 查看详情
线性表之顺序存储-顺序表(代码片段)
顺序表的操作[x]向有序顺序表插入一个元素[x]顺序表的冒泡排序[x]顺序表的删除操作[x]顺序表中元素的查找[x]顺序表的逆置[x]删除顺序表中的相同元素[x]向顺序表的指定位置插入元素[x]打印顺序表顺序表的存储结构#definemaxsize100/... 查看详情
数据结构线性表循环链表之约瑟夫环(代码片段)
（一）前提41个人报数，1-3，当谁报数为3，谁就去嗝屁。现在获取他们嗝屁的顺序（二）实现结构顺序：3->1->5->2->4 （三）代码实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<time.h>#defineOK1#... 查看详情
day1线性表之顺序存储
...驱和后继。存储结构用一组地址连续的存储单元以此存放线性表中的数据元素。LOC（ai）=LOC(ai-1)+sizeofLOC（ai）=LOC(a1)+(i-1)×sizeof*sizeof是每个数据元素所占存储空间大小*线性表中元素位序从一开始，数组从0开始表示方法静态1 查看详情
数据结构(线性表之单链表)(代码片段)
文章目录🥇为何要使用链表🥇单链表是什么单链表的数据存储方式🥇单链表之创建链表🥇单链表之打印链表🥇单链表之计算链表长度🥇单链表之增删查改单链表之头插法单链表之尾插法单链表之把一个... 查看详情