线性表中的顺序表和链表是最基本数据结构，这两种数据结构中最基本的方法便是插入、删除，链表还有定位。要说掌握了数据结构的线性表，那么你必须能够随时写出线性表的实现，这样才算掌握。线性表看着简单，但是要真正掌握，还是需要付出一定的努力的。下面是我自己写的线性表的实现，希望通过不断练习加深巩固数据结构的基础知识！
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();
}
}
我对线性表的实现做了一些总结，有兴趣的可以看一下：
线性表、堆栈、队列的实现总结
分享到：
相关推荐
本仓库利用C++实现以下经典数据结构与算法：线性表（顺序表、链表、静态链表、三元组）、栈（双栈、共享_Data-structures-and-algorithms
在这个"C语言数据结构线性表实验"中，我们将深入探讨两种实现线性表的方法：顺序表和链表。 1. **顺序表**： - **定义**：顺序表是将数据元素存储在一块连续的内存区域中，每个元素都有一个固定的索引位置。 - **...
根据提供的文档信息，我们可以深入探讨线性表的相关概念及其两种主要实现形式——顺序表与链表。 ### 线性表定义 线性表是一种基本的数据结构，它由一系列具有相同特性的数据元素组成，这些元素按照一定的顺序排列...
在本主题中，我们将深入探讨线性表的两种主要实现方式：顺序表和链式存储。 **顺序表**是一种将线性表中的元素连续存储在内存中的数据结构。这种存储方式使得访问元素变得非常高效，因为元素的位置可以通过其索引...
数组实现的线性表称为顺序表，操作简单但插入和删除元素效率较低；链表则通过指针连接元素，插入和删除操作更灵活，但需要额外的空间存储指针。 2. **链表**：链表是一种动态数据结构，每个元素（节点）包含数据和...
在本压缩包中，我们重点关注了三种类型的线性表：顺序表、链表和双链表，以及它们的增删查改操作和链表逆置等常见算法。 顺序表是一种最简单的线性表实现，它在内存中是连续存储的，可以通过数组来表示。对于顺序表...
线性表的基本操作在双向链表中表现为以下几种： 1. 插入操作：在双向链表中插入节点，需要考虑插入位置，可能是表头、表尾或者中间某个位置。插入操作涉及修改插入点的前后节点的指针，以确保链表的完整性。 2. ...
《基于线性表的图书管理系统》是一个典型的C语言实现的数据结构应用案例，它结合了顺序表和链表这两种基本的线性数据结构。这个系统旨在模拟图书馆中的图书管理操作，如添加、删除、查找和显示图书信息。在这个系统...
在计算机科学中，线性表可以采用顺序存储结构或链式存储结构来实现。本篇主要讨论的是链式存储结构的线性表，也就是链表。 链表是一种动态数据结构，它的优点在于内存分配是按需进行的，即每个节点只在需要时才被...
顺序表；2.线性链表；3.约瑟夫环。 北工大电控学院《数据结构与算法》课程的其它章节程序实验及作业代码亦已在本站上传，需要的同学可进入作者的空间或通过搜索获取。本代码为上传者原创，仅供个人学习参考使用，...
- 以下是一个简单的代码片段，展示如何创建一个双向循环链表： ```cpp int main() { DblList list; list.CreatDblList(list.first); list.output(list.first); list.addToHead(list.first); list.addToTail...
顺序表是线性表的顺序存储结构，它使用一块连续的内存空间来存储表中的元素。这种结构的特点包括： - 容量固定：在创建时需要预先分配空间，难以进行动态扩展。 - 访问速度快：由于元素连续存储，可以实现快速的随机...
在本压缩包中，"线性表实现代码(内涵顺序表静态动态分配，循环，单双链表)" 提供了线性表在不同情况下的具体实现，包括顺序表和链表两种基本形式，以及它们的不同操作方式。 1. **顺序表**： - 静态分配：在内存中...
循环链表是一种特殊的线性表，它通过将链表的尾节点指向头节点，形成了一个闭环的数据结构。与普通链表相比，循环链表在处理某些问题时更加方便，比如实现队列、模拟游戏中的轮流机制等。 ### 八种功能概述 1. **...
本次实验旨在深入理解并实践数据结构中的线性表概念，具体聚焦于链表与顺序表的设计与实现。实验选取了学生成绩管理系统作为应用场景，通过对学生基本信息（包括学号、姓名、性别、年龄及各科目成绩）的管理，进一步...
双向链表的API和C语言...另外还有线性表顺序存储、单链表、循环链表的C语言实现，文章及代码资源均已上传，可在专栏《数据结构与算法学习笔记》中查看，欢迎大家查看下载，如果内容有不合理的地方，欢迎大家批评指正。
9. **就地逆置双向循环链表**：不改变节点的值，仅调整每个节点的`prior`和`next`指针，使得链表的顺序反转，同时交换头结点和尾结点。 在算法复杂度方面，除了求线性表长度是O(1)外，其他操作如插入、删除、逆置等...
本实验报告旨在介绍顺序表和链表的基本概念、实现算法和性能分析。实验主要分为两个部分：顺序表和链表。在顺序表部分，我们将学习顺序表的建立、插入元素、删除元素和遍历算法。在链表部分，我们将学习链表的建立、...