线性表-双链表
#ifndef List_hpp
#define List_hpp
#include <stdio.h>
#include <iostream>
#include "string"
#include <iostream>
#include "Node.hpp"
/**
下面实现的是 线性表-单链表
*/
using namespace std;
template <typename T>
class List{
public:
List(int size=1);
~List();
void clearList();
bool listEmpty();
int listLength();
int locateElem(T *e);
bool priorElem(T *currentElem,T *preElem);
bool nextElem(T *currentElem,T *nextElem);
bool listInsert(int i,T *e);
bool listDelete(int i,T *e);
bool listInsertHead(T *t);
bool listInsertTail(T *t);
void listTraverse();
private:
Node<T> *get(int i);
Node<T> *getFirst();
Node<T> *m_Plist;
int m_iLength;
};
/**
下面实现的是 线性表-单链表
*/
template <typename T>
List<T>::List(int size){
m_Plist = new Node<T>();
m_iLength = 0;
}
template <typename T>
List<T>::~List()
{
clearList();
}
template <typename T>
void List<T>::clearList(){
Node<T> *n = getFirst();
while (n != NULL) {
Node<T> *temp = n->next;
delete n;
n = temp;
}
m_iLength = 0;
m_Plist->next = NULL;
}
template <typename T>
bool List<T>::listEmpty(){
return m_iLength == 0;
}
template <typename T>
int List<T>::listLength(){
return m_iLength;
}
template <typename T>
Node<T> *List<T>::getFirst(){
Node<T> *c = m_Plist;
while (c->previous !=NULL) {
c = c->previous;
}
return c;
}
template <typename T>
Node<T> *List<T>::get(int i){
if(i<0 || i>m_iLength){
return NULL;
}
Node<T> *currentNode = getFirst();
for(int k=0;k<i;k++){
currentNode = currentNode->next;
}
return currentNode;
}
template <typename T>
int List<T>::locateElem(T *e){
Node<T> *currentNode = getFirst();
for(int k=0;k<m_iLength;k++){
if(currentNode->data == *e){
return k;
}
currentNode = currentNode->next;
}
return -1;
}
template <typename T>
bool List<T>::priorElem(T *currentElem,T *preElem){
int i = locateElem(currentElem);
if(i == -1){
return false;
}
if(i == 0){
return false;
}
Node<T> *t = get(i);
*preElem = t->previous->data;
return true;
}
template <typename T>
bool List<T>::nextElem(T *currentElem,T *nextElem){
int i = locateElem(currentElem);
if(i == -1){
return false;
}
Node<T> *t = get(i);
*nextElem = t->next->data;
return true;
}
template <typename T>
bool List<T>::listInsert(int i, T *e){
// 根据 i 找数据，然后操作 get(i)
if(i<0 || i> m_iLength){
return false;
}
if(i == 1){
cout << " " <<endl;
}
// 获取指定元素的上一个，用来替换或者新增 i 节点数据
i = i-1<=0?0:i-1;
Node<T> *currentNode = get(i);
// 第一个元素（初始化使用）
if(m_iLength == 0){
m_Plist->data=*e;
m_Plist->next=NULL;
m_Plist->previous=NULL;
m_iLength++;
return true;
}
// 第一个元素 (插入头使用)
if(i == 0 && m_iLength > 0){
Node<T> *newNode = new Node<T>();
newNode->data=*e;
newNode->next = currentNode;
newNode->previous = currentNode->previous;
currentNode->previous = newNode;
m_iLength++;
return true;
}
Node<T> *newNode = new Node<T>();
newNode->data=*e;
newNode->next=currentNode->next;
newNode->previous = currentNode;
currentNode->next = newNode;
m_iLength++;
return true;
}
template <typename T>
bool List<T>::listDelete(int i, T *e){
if(i<0 || i>=m_iLength){
return false;
}
Node<T> *currentNode = get(1);
currentNode->previous->next = currentNode->next;
*e = currentNode->data;
delete currentNode;
currentNode = NULL;
m_iLength--;
return true;
}
template <typename T>
bool List<T>::listInsertHead(T *t){
return listInsert(0,t);
}
template <typename T>
bool List<T>::listInsertTail(T *t){
return listInsert(m_iLength,t);
}
template <typename T>
void List<T>::listTraverse(){
cout << "m_iLength" << m_iLength << endl;
Node<T> *currentNode = getFirst();
while (currentNode != NULL) {
currentNode->printNode();
currentNode = currentNode->next;
}
}
template <typename T>class Node{public: Node(){ cout << "Node()" << endl; } T data; Node *previous; // 前 Node *next; // 后 void printNode(); };template <typename T>void Node<T>::printNode(){ cout << data << endl;}
