线性表中的顺序表和链表是最基本数据结构，这两种数据结构中最基本的方法便是插入、删除，链表还有定位。要说掌握了数据结构的线性表，那么你必须能够随时写出线性表的实现，这样才算掌握。线性表看着简单，但是要真正掌握，还是需要付出一定的努力的。下面是我自己写的线性表的实现，希望通过不断练习加深巩固数据结构的基础知识！
1.顺序表
package List;
class SeqList {
private int defaultSize = 10;
private int maxSize ;
private int size;
private Object[] list;
public SeqList()
{
init(defaultSize);
}
public SeqList(int size)
{
init(size);
}
private void init(int size)
{
maxSize = size;
size = 0;
list = new Object[maxSize];
}
//插入
public void insert(int i, Object obj)
{
//省略2个条件判断
for(int j = size; j > i; j--)
{
list[j] = list[j - 1];
}
list[i] = obj;
size++;
}
//删除
public Object delete(int i)
{
Object obj = list[i];
for(int j = i; j < size - 1; j++)
{
list[j] = list[j + 1];
}
size--;
return obj;
}
//获取元素
public Object getData(int i)
{
return list[i];
}
//测试
/* 插入元素：1
插入元素：2
插入元素：3
插入元素：4
插入元素：5
顺序表为：1 2 3 4 5
顺序表为：3 4 5
*/
public static void main(String args[])throws Exception
{
SeqList list = new SeqList();
for(int i = 0; i < 5; i++)
{
list.insert(i, new Integer(i+1));
System.out.println("插入元素：" + (i + 1));
}
System.out.print("顺序表为：");
for(int i = 0; i < list.size; i++)
{
System.out.print(list.getData(i) + " ");
}
System.out.println();
list.delete(0);
list.delete(0);
System.out.print("顺序表为：");
for(int i = 0; i < list.size; i++)
{
System.out.print(list.getData(i) + " ");
}
System.out.println();
}
}
2.链表
package List;
import java.util.Scanner;
class Node
{
private Object element;
private Node next;
//构造头结点
public Node(Node next)
{
this.next = next;
}
//构造普通节点
public Node(Node next, Object element)
{
this.element = element;
this.next = next;
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public class LinkedList {
private Node head;
private Node current;
private int size;
public LinkedList()
{
head = current = new Node(null);
size = 0;
}
//定位
public void index(int i )
{
//省略判断条件
//定位到头结点
if(i == -1)
{
current = head;
return ;
}
current = head.getNext();
int j = 0;
while( current != null && j < i)
{
current = current.getNext();
j++;
}
}
//插入
public void insert(int i, Object obj)
{
//省略判断
index(i - 1);
current.setNext(new Node(current.getNext(), obj));
size++;
}
//删除
public Object delete(int i)
{
//省略判断
index(i - 1);
Object obj = current.getNext().getElement();
current.setNext( current.getNext().getNext());
return obj;
}
//返回元素
public Object getData(int i)
{
//省略判断
index(i);
return current.getElement();
}
public int size()
{
return size;
}
//测试
/* 请输入第1个整数：2
请输入第2个整数：4
请输入第3个整数：6
请输入第4个整数：8
请输入第5个整数：10
单链表元素为：2 4 6 8 10
大小为：5
删除第1、2个后的数据为：4 8 10 程序结束！
*/
public static void main(String args[])throws Exception
{
Scanner reader = new Scanner(System.in);
int num = 0;
LinkedList list = new LinkedList();
for(int i = 0; i < 5; i++)
{
System.out.print("请输入第" + (i+1) + "个整数：");
num = reader.nextInt();
list.insert(i, num);
}
System.out.print("单链表元素为：");
list.index(0);
while(list.current != null)
{
System.out.print(list.current.getElement() + " ");
list.current = list.current.getNext();
}
System.out.println();
System.out.println("大小为：" + list.size());
list.delete(0);
list.delete(1);
System.out.print("删除第1、2个后的数据为：");
list.index(0);
while(list.current != null)
{
System.out.print(list.current.getElement() + " ");
list.current = list.current.getNext();
}
}
}3.循环链表
package List;
import java.util.Scanner;
class CycleNode
{
private Object element;
private CycleNode next;
public CycleNode(CycleNode next)
{
this.next = next;
}
public CycleNode(CycleNode next, Object element)
{
this.next = next;
this.element = element;
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public CycleNode getNext() {
return next;
}
public void setNext(CycleNode next) {
this.next = next;
}
}
public class CycleLinkedList {
private CycleNode current;
private CycleNode head;
private int size;
public CycleLinkedList()
{
current = head = new CycleNode(null);
head.setNext(head);
size = 0;
}
//定位
public void index(int i)
{
//...
if(i == -1)
{
current = head;
}
current = head.getNext();
int j = 0;
while(current.getNext() != head && j < i)
{
current = current.getNext();
j++;
}
}
//插入
public void insert(int i, Object obj)
{
//...
index(i - 1);
current.setNext(new CycleNode(current.getNext(), obj));
size++;
}
//删除
public void delete(int i)
{
//...
index(i - 1);
current.setNext(current.getNext().getNext());
size--;
}
//获取元素
public Object getData(int i)
{
index(i);
return current.getElement();
}
//为空
public boolean isEmpty()
{
return size == 0;
}
//测试
/* 请输入第1个数：2
请输入第2个数：4
请输入第3个数：6
请输入第4个数：8
请输入第5个数：10
您输入的数为：2 4 6 8 10
是否为空：false
大小：5
链表最后一个数的下一个数是：2
*/
public static void main(String args[])throws Exception
{
CycleLinkedList cycleLinList = new CycleLinkedList();
Scanner reader = new Scanner(System.in);
for(int i = 0; i < 5; i++)
{
System.out.print("请输入第" + (i + 1) + "个数：");
int num = reader.nextInt();
cycleLinList.insert(i, num);
}
System.out.print("您输入的数为：");
for(int i = 0; i < cycleLinList.size; i++)
{
System.out.print(cycleLinList.getData(i) + " ");
}
System.out.println();
System.out.println("是否为空：" + cycleLinList.isEmpty());
System.out.println("大小：" + cycleLinList.size);
System.out.print("链表最后一个数的下一个数是：");
cycleLinList.index(cycleLinList.size - 1);
//cycleLinList.current.next指向头结点，但头结点无值，输出null。
//必须再next才能到达第一个值
System.out.print(cycleLinList.current.getNext().getNext().getElement());
}
}
4.双向循环链表
package List;
import java.util.Scanner;
class DoubleNode
{
private Object element;
private DoubleNode prior;
private DoubleNode next;
public DoubleNode(DoubleNode prior, DoubleNode next)
{
this.prior = prior;
this.next = next;
}
public DoubleNode(DoubleNode prior, DoubleNode next, Object element)
{
this.prior = prior;
this.next = next;
this.element = element;
}
public Object getElement() {
return element;
}
public void setElement(Object element) {
this.element = element;
}
public DoubleNode getPrior() {
return prior;
}
public void setPrior(DoubleNode prior) {
this.prior = prior;
}
public DoubleNode getNext() {
return next;
}
public void setNext(DoubleNode next) {
this.next = next;
}
}
public class DoubleLinkedList {
private DoubleNode current;
private DoubleNode head;
private int size;
public DoubleLinkedList()
{
current = head = new DoubleNode(null, null);
head.setNext(head);
head.setPrior(head);
size = 0;
}
//定位
public void index(int i)
{
//...
if(i == -1)
{
current = head;
return ;
}
current = head.getNext();
int j = 0;
while(current != head && j < i)
{
current = current.getNext();
j++;
}
}
//插入
public void insert(int i, Object obj)
{
//...
index(i - 1);
DoubleNode element = new DoubleNode(current, current.getNext(), obj);
current.getNext().setPrior(element);
current.setNext(element);
size++;
}
//删除
public Object delete(int i)
{
//...
index(i - 1);
Object obj= current.getNext().getElement();
current.getNext().getNext().setPrior(current);
current.setNext(current.getNext().getNext());
size--;
return obj;
}
//获取元素
public Object getData(int i)
{
//...
index(i);
return current.getElement();
}
//测试
/* 请输入第1个数：2
请输入第2个数：4
请输入第3个数：6
请输入第4个数：8
请输入第5个数：10
您输入的数为：2 4 6 8 10
第1个数的前后分别是：null 4
删除第2个元素后的数为：2 6 8 10
*/
public static void main(String args[])throws Exception
{
DoubleLinkedList doubleList = new DoubleLinkedList();
Scanner reader = new Scanner(System.in);
//输入1 2 3 4 5
for(int i = 0; i < 5; i++)
{
System.out.print("请输入第" + (i + 1) + "个数：");
int num = reader.nextInt();
doubleList.insert(i, num);
}
System.out.print("您输入的数为：");
for(int i = 0; i < doubleList.size; i++)
{
System.out.print(doubleList.getData(i) + " ");
}
System.out.println();
//输出：null 2
System.out.print("第1个数的前后分别是：");
doubleList.index(0);
System.out.print(doubleList.current.getPrior().getElement() + " ");
System.out.println(doubleList.current.getNext().getElement() + " ");
//删除第一个元素 2
doubleList.delete(1);
System.out.print("删除第2个元素后的数为：");
for(int i = 0; i < doubleList.size; i++)
{
System.out.print(doubleList.getData(i) + " ");
}
System.out.println();
}
}
我对线性表的实现做了一些总结，有兴趣的可以看一下：
线性表、堆栈、队列的实现总结
分享到：
相关推荐
2第二章 线性表（顺序表 链表）.pdf
这有线性表的操作:顺序存储,链存储结构, 单链表,顺序表,循环链表,双向链表
顺序表；2.线性链表；3.约瑟夫环。 北工大电控学院《数据结构与算法》课程的其它章节程序实验及作业代码亦已在本站上传，需要的同学可进入作者的空间或通过搜索获取。本代码为上传者原创，仅供个人学习参考使用，...
c语言数据结构线性表实验（包括顺序表和链表）
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
双向链表的API和C语言...另外还有线性表顺序存储、单链表、循环链表的C语言实现，文章及代码资源均已上传，可在专栏《数据结构与算法学习笔记》中查看，欢迎大家查看下载，如果内容有不合理的地方，欢迎大家批评指正。
代码主要实现了顺序表 链表 双链表的增删查改操作及链表逆置等常用线性表算法
利用C++实现以下经典数据结构与算法：线性表（顺序表、链表、静态链表、三元组）、栈（双栈、共享栈）、队列（任务调度、循环队列、双向队列、链队列）、数组（特殊矩阵、稀疏矩阵压缩）、串（朴素模式匹配、KMP算法...
数据结构Java线性表顺序表与链表小结PPT学习教案.pptx
数据结构与算法----线性表及Java实现顺序表、链表、栈、队列 定义线性表节点的结构.pdf
包含数据结构中线性表、链表、队列、栈、串等几种结构的常见操作，以及顺序和链式存储过程
线性表实现代码(内涵顺序表静态动态分配，循环，单双链表)
首先，逐行读取指定文件中的数据，并进行解析后保存在顺序表中。其中，文件中每行数据格式为“学号,姓名,年龄”，比如“SA10225048,[yyw1] 张三,24”。 （提示：采用顺序表结构时，顺序表中每个表元素包含三类信息...
线性表，数据结构的核心内容，快来看看看吧，都很有用的
C++数据结构线性表用链表实现学生信息系统
数据结构：图解链表，用链表实现栈（c语言版） 栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶（top），表头端称为栈低（bottom）。不含元素的空表称为空栈。因为栈限定在表尾进行...
（1）创建一个顺序表，存放在数组 A[N]中，元素的类型为整型，设计算法调整 A，使其左边的所有元素小于 0，右边的所有元素大于 0（要求算法的时间复杂度和空间复杂度均为 O(n)）。 （2）建立一个循环单链表，其节点...
基于线性表的图书管理系统，《数据结构（C语言版 第2版）》严蔚敏 实验一
第二章 线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示和实现上节复习链表是线性表的链式存储表