带头节点的双向循环链表数据结构

用C++和Java实现带头节点的双向循环链表，要继承linearList类，并实现它的所有功能，另外，必须实现双向迭代器。

实现带头节点的双向循环链表，要具有以下的功能：

判断表是否为空，如果为空则返回true，不空返回false.
给出表中数据元素的个数。
给定一个索引（位置），返回指向该位置的数据元素的指针，如果给定的位置号不合法，则返回空指针。
给定数据元素x，如果表中有该元素，则返回x第一次出现的索引，若x 不存在，则返回-1.
删除给定索引的数据元素。
给定索引index ,数据元素x，将x插入到index的位置。

完整资源请去https://download.csdn.net/download/qq_38971487/10903512

C++：设计一个结构体struct chainNode，再设计一个具体类 class doubleChain 作为抽象类 class linearList的派生类实现类linearList中的所有方法，外加实现双向迭代器；

C++：

linearList.h:
#ifndef SRC_LINEARLIST_H_
#define SRC_LINEARLIST_H_
#include <iostream>
#include <iterator>
#include <algorithm>

template <typename T>
class linearList {
public:
	virtual ~linearList(){};//需要定义
	virtual bool empty() const = 0;
	virtual int size() const = 0;
	virtual T& get(int theIndex) const = 0;
	virtual int indexOf(const T& theElement) const = 0;
	virtual void erase(int theIndex) = 0;
	virtual void insert(int theIndex, const T& theElement) = 0;
	virtual void output(std::ostream& out) const = 0;
};

#endif /* SRC_LINEARLIST_H_ */

doubleChain.h:
#ifndef DOUBLECHAIN_H_
#define DOUBLECHAIN_H_

#include<iostream>
#include<sstream>
#include<string>
#include<iterator>

#include"linearList.h"

template<typename T>
struct chainNode
{
	T element;
	chainNode<T>* next;//可以将chainNode<T>简写为chainNode，因为这是在class chainNode的作用域内
	chainNode<T>* prev;

	chainNode(){next = NULL;prev = NULL;}
	chainNode(const T& element){
		this->element = element;
		next = NULL;
		prev = NULL;
	}
	chainNode(const T& element,chainNode* next,chainNode* prev)//可以将chainNode<T>简写为chainNode，因为这是在class chainNode的作用域内
	{
		this->element = element;
		this->next = next;
		this->prev = prev;
	}
};

template<class T>
class doubleChain : public linearList<T>{
public:
	doubleChain(int initialCapacity = 10);
	~doubleChain();
	bool empty()const{return listSize == 0;}
	int size() const{return listSize;}
	T& get(int theIndex) const;
	int indexOf(const T& theElement) const;
	void erase(int theIndex);
	void insert(int theIndex, const T& theElement);
	void output(std::ostream& out) const;

public:
	void checkIndex(int theIndex) const;
	chainNode<T>* headNode;
	int listSize;

	class iterator;
	iterator begin() const{
		return iterator(headNode->next);
	}
	iterator end() const{
		return iterator(headNode);
	}

class iterator : public std::iterator<std::bidirectional_iterator_tag,T>{//一个类，提供返回类型的iterator_category表示的双向迭代器函数
public:
	iterator(chainNode<T>* theNode = NULL){
		node = theNode;
	}
	T& operator*() const{
		return node->element;
	}
	T* operator->()const{
		return &node->element;
	}
	bool operator == (const iterator right) const{
		return node == right.node;
	}
	iterator& operator++(){
		node = node->next;
		return *this;
	}
	iterator operator++(int){
		iterator old = *this;
		node = node->next;
		return old;
	}
protected:
	chainNode<T>* node;
};

};





#endif /* DOUBLECHAIN_H_ */

doubleChain.cpp:
#include"doubleChain.h"

template<class T>
doubleChain<T>::doubleChain(int initialCapacity)//建立一个空表
{
	if (initialCapacity < 1)
	   throw std::invalid_argument("Initial capacity = " + std::to_string(initialCapacity) + " Must be > 0");
	headNode = new chainNode<T>();
	headNode->next = headNode;
	headNode->prev = headNode;
	listSize = 0;
}

template<class T>
doubleChain<T>::~doubleChain()//析构函数
{
	chainNode<T>* currentNode = headNode->next;
	while(currentNode != headNode)//循环删除所有节点
	{
		chainNode<T>* nextNode = currentNode->next;
		delete currentNode;
		currentNode = nextNode;
	}
	delete headNode;//删除头结点
}

template<class T>
void doubleChain<T>::checkIndex(int theIndex) const//判断索引是否有效
{
	if(theIndex < 0 || theIndex > listSize)
	{
		throw std::out_of_range("index = "+ std::to_string(theIndex)+ "size = "+ std::to_string(listSize));

	}
}



text.cpp:
#include"doubleChain.cpp"
#include<numeric>
using std::cout;
using std::endl;
int main(){
	doubleChain<int> y(2);
	cout<<"y的初始尺寸为 "<<y.size()<<endl;
	if(y.empty())
		cout<<"y为空"<<endl;
	else
		cout<<"y不为空"<<endl;

	y.insert(0,1);
	y.insert(1,2);
	y.insert(2,3);
	y.insert(3,4);
	y.insert(4,5);
	y.insert(4,6);
	cout<<"插入6后y应该为 1 2 3 4 5 6"<<endl;
	cout<<"y的尺寸为"<<y.size()<<endl;
	if(y.empty())
		cout<<"y为空"<<endl;
	else
		cout<<"y不为空"<<endl;
	cout<<y<<endl;
	cout<<"元素4的索引为:"<<y.indexOf(4)<<endl;
	y.erase(0);
	cout<<"删除0号元素后应该为 2 3 4 6 5:"<<endl;
	cout<<y<<endl;
	y.erase(3);
	cout<<"删除3号元素后应该为 2 3 4 5:"<<endl;
	cout<<y<<endl;
	return 0;
}

Java：设计一个接口interface linearList<T>，设计一个类class doubleChainNode<T>相当于C++中的结构体，设计一个类class doubleChainjava<T>实现了了接口linearList<T>所有方法，以及实现迭代器接口Iterable<T>中的一个方法Iterator<T> iterator();

Java:

linearList.java:
public interface linearList<T> {
	public boolean empty();
	public int size();
	public T get(int theIndex) throws Exception;
	public int indexOf(T theElement);
	public void erase(int theIndex) throws Exception;
	public void insert(int theIndex,T theElement) throws Exception;
	public void output();

}

doubleChainNode.java:
public class doubleChainNode<T> {
	T element;
	doubleChainNode<T> next;
	doubleChainNode<T> prev;
	
	public doubleChainNode() {next = prev = null;}
	public doubleChainNode(T element) {
		this.element = element;	
		next = prev = null;
		}
	public doubleChainNode(T element,doubleChainNode<T> prev,
			doubleChainNode<T> next) {
		this.element = element;
		this.prev = prev;
		this.next = next;
	}

}


doubleChain.java:
import java.util.*;

public class doubleChain<T> implements linearList<T>,Iterator<T>{
	public doubleChainNode<T> headNode;//指向链表的头结点
	public int listSize;//链表的元素个数
	
	private void checkIndex(int theIndex) throws Exception{//判断索引是否有效
		if(theIndex<0 || theIndex >= listSize)//索引要在0和listSize之间
			throw new Exception("index = "+theIndex+"size = "+listSize);//抛出异常
		
	}
	public doubleChain(int initialCapacity) throws Exception{//doubleChain的构造函数，创建一个空链表
		if(initialCapacity < 1) {//定义时链表长度<1就抛出异常
			throw new Exception("Initial capacity = "+initialCapacity+"Must be > 0 ");
			
		}
		headNode = new doubleChainNode<T>(null);//空的头结点
		headNode.next = headNode;//头结点的next指向头结点
		headNode.prev = headNode;//头结点的prev指向头结点
		listSize = 0;//链表内没有元素
	}
	

	
	


	public Iterator<T> iterator(){//迭代器
		class Myiterator implements Iterator<T>{
			public doubleChainNode<T> currentNode = headNode;
			public boolean hasNext() {//判断currentNode是否等于头节点
				return currentNode.next != headNode;
			}
			public T next() {//返回element
				if(currentNode.next != headNode) {
					currentNode = currentNode.next;
					return currentNode.element;
				}
				return null;
			}
		}
		return new Myiterator();
	}

	public boolean hasNext() {

		return false;
	}
	
	public T next() {

		return null;
	}
}

text.java:
import java.util.Iterator;


public class text {
	public static void main(String[] args)throws Exception{
		doubleChain<Integer> p = new doubleChain<Integer>(5);
		p.insert(0,1);
		p.insert(1,2);
		p.insert(2,3);
		p.insert(3,4);
		p.insert(0,5);
		
		if(p.empty())
			System.out.println("y为空");
		else
			System.out.println("y不为空");
		System.out.println("p的尺寸为 "+p.size());
		System.out.print("p是");
		p.output();
		System.out.print("\n 元素1的索引为 "+p.indexOf(1));
		System.out.println("\n 索引为2的元素为 "+p.get(2));
		p.erase(3);
		System.out.println("删除3后p为");
		p.output();
		p.insert(2, 6);
		System.out.println("\n 2号位置上插入6后p为");
		p.output();
		System.out.println("\n 迭代器列表是:");
		for(Iterator<Integer> iter = p.iterator(); iter.hasNext();) {
			Integer i = (Integer)iter.next();
			System.out.println(i);
		}

	}

}

带头节点的双向循环链表数据结构

C++：

Java:

继续阅读

Java String.format方法的简单使用

neo4j之cypher使用文档

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

线性表之顺序表的实现

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method