数据结构--线性表

简介: 基本概念线性表:有n(n>=0)个相同数据类型数据元素组成的线性结构。其实现方法见图。线性结构:除了第一个和最后一个数据元素,其余各元素只有一个前驱元素和后继元素,第一个数据元素只有一个后继元素,最后一个数据元素只有一个前驱元素。

基本概念

线性表:有n(n>=0)个相同数据类型数据元素组成的 线性结构。其实现方法见图。
线性结构:除了第一个和最后一个数据元素,其余各元素只有一个前驱元素和后继元素,第一个数据元素只有一个后继元素,最后一个数据元素只有一个前驱元素。其分类见图。
顺序存储结构:数据元素存储在一块连续的地址空间中,数据元素间的逻辑关系表现在连续的地址空间上,逻辑上相邻的数据元素在物理上也相邻。
链式存储结构:存储数据元素的空间并不连续,数据元素间的逻辑关系用指针来实现,逻辑上相邻的数据元素在物理上不一定相邻。
顺序表:采用顺序存储结构的线性表。
链表:采用链式存储结构的线性表。可分为:单链表、单循环链表、双向循环链表。



说下第二张图中的 堆栈队列:
  1. 堆栈:是一种特殊的线性表,它只允许在线性表的表头进行删除和插入操作。
  2. 队列:也是一种特殊的线性表,它只允许在线性表的表头进行删除操作,而在表尾进行插入操作。
看到这里也许有人会问,既然堆栈和队列都是线性表,那为什么在第二张图把堆栈、队列和线性表放在一个级别里呢?这个就不要去纠结这个问题哈。线性表可以采用顺序表、仿真链表和链表来实现,那么堆栈和队列当然也可以采用顺序表、仿真链表和链表来实现。因此堆栈和队列是与数据的存储结构无关的数据结构。

下面说下 顺序表仿真链表链表的区别:
其实就是各自保存数据元素间关系的方法不一样。
  1. 顺序表:数据元素的关系表现在连续的地址空间上;
  2. 仿真链表:通过保存数据元素在数组中存放的下标来保存数据元素间的关系;
  3. 链表:通过保存数据元素在内存中的存放地址(或者引用)来保存数据元素间的关系。

头结点:不存放数据元素的第一个结点;

头指针:指向头结点的指针。

带头结点与不带头结点的区别

  1. 带头结点:插入第一结点和非第一个结点时,其操作都一样的;
  2. 不带头结点:当插入第一个结点时,需要单独考虑哈。删除结点时,两者的区别与插入结点时类似。

代码实现

结点类:
public class Node{
	private Object data;
	private Node next;
	
	//如果new时,采用 new Node(null),则得到一个没有存储数据的结点,即:头结点。
	public Node(Object data){
		this.data = data;
	}
	
	public void setData(Object data){
		this.data = data;
	}
	
	public void setNext(Next next){
		this.next = next;
	}
	
	public Object getData(){
		return this.data;
	}
	
	public Node getNext(){
		return this.next;
	}
}

带头结点的单链表类:
public class HeadLinkList{
	private Node head;
	private int currentSize;
	
	public HeadList(){
		head = new Node(null);    //构造一个未存放数据的头结点。
		currentSize = 1;
	}
	
	//返回下标为 i 的那个结点的指针
	public Node index(int i){    //结点编号从0开始,头结点下标为0;
		if(i>=0 && i< currentSize ){
			Node temp = head;
			for(int j = 0 ; j < i;j++){
				temp = temp.getNext();
			}
			return temp;
		}else{
			throw new Exception("下标超界!");
		}
	}
	
	//插入结点,使其成为第 i 个结点。
	public void insertNode(Node node,int i){  
		Node temp = index(i-1);
		node.setNext(temp.getNext());
		temp.setNext(node);
		currentSize++;
	}

	//删除编号为 i 的结点
	public void deleteNode(int i){
		Node temp = index(i-1);
		temp.setNext(temp.getNext().getNext());
	}
	
	//getter setter
}



不带头结点的单链表类:
public class NoHeadLinkList{
	private Node head;
	private int currentSize;
	
	public HeadList(){
		head = null;
		currentSize = 0;
	}
	
	//返回下标为 i 的那个结点的指针
	public Node index(int i){    //结点编号从0开始;
		if(i>=0 && i< currentSize ){
			Node temp = head;
			for(int j = 0 ; j < i;j++){
				temp = temp.getNext();
			}
			return temp;
		}else{
			throw new Exception("下标超界!");
		}
	}
	
	//插入结点,使其成为第 i 个结点。
	public void insertNode(Node node,int i){
		if(head == null){
			head = node;
			currentSize++;
		}else{
			Node temp = index(i-1);
			node.setNext(temp.getNext());
			temp.setNext(node);
			currentSize++;
		}
	}

	//删除编号为 i 的结点
	public void deleteNode(int i){
		if(i == 0){
			Node temp = index(0);
			head = temp.getNext();
			temp.setNext(null);
		}else{
			Node temp = index(i-1);
			temp.setNext(temp.getNext().getNext());
		}
	}
	
	//getter setter
}
比较 HeadLinkListNoHeadLinkList这两个类,可以发现他们在 构造函数删除结点插入结点函数有点不一样,其余是一样的。




持续更新中。。。。。

目录
相关文章
|
存储 C语言
数据结构中的线性表链式存储介绍及其基本操作
链式存储是线性表的一种重要存储方式,它通过节点和指针的结构,实现了灵活的动态存储管理。本文介绍了单向链表的基本操作,并提供了相应的C语言代码示例。理解和掌握链表的操作对学习和应用数据结构具有重要意义。希望这篇博客能帮助你更好地理解线性表的链式存储。
359 2
|
9月前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
248 7
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
377 5
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
208 5
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
124 0
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
137 6
|
存储
【数据结构】线性表和顺序表
【数据结构】线性表和顺序表
100 1
|
11月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
01(数据结构考研)线性表相关操作代码
01(数据结构考研)线性表相关操作代码
160 0
|
存储 C语言
数据结构之线性表的初始化及其操作
数据结构之线性表的初始化及其操作
186 0

热门文章

最新文章