// ------SingleLinkedList.h------
// Implement Single Linked List.
// Time complexities of find an element, insert an element, remove an element, copy a single linked list and clear single linked list are all O(n).
// Decrease the dependencies between member functions as far as possible when design the class.
#ifndef SINGLELINKEDLIST_H
#define SINGLELINKEDLIST_H
template<class T>
struct Node
{
T data;
Node<T> *next;
};
template<class T>
class SingleLinkedList
{
public:
SingleLinkedList();
SingleLinkedList(const SingleLinkedList<T> &pList);
~SingleLinkedList();
SingleLinkedList<T>& operator=(const SingleLinkedList<T> &pList);
void insert_head(const T &element); // Insert before the head of list.
void insert_tail(const T &element); // Insert at the tail of list.
bool first(T &element); // Get the data of the first node.
inline bool getNext(T &element); // Get the data of the next node.
bool find(const T &element); // Find data.
bool retrieve(T &element); // Retrieve data.
bool replace(const T &newElement); // Change data.
bool remove(T &element);
bool isEmpty() const;
void makeEmpty();
private:
Node<T> *head;
Node<T> *current;
inline void deepCopy(const SingleLinkedList<T> &original);
};
#endif
// ------SingleLinkedList.cpp------
#include "SingleLinkedList.h"
template<class T>
SingleLinkedList<T>::SingleLinkedList()
{
head = current = NULL;
}
template<class T>
SingleLinkedList<T>::SingleLinkedList(const SingleLinkedList<T> &pList)
{
deepCopy(pList);
}
template<class T>
SingleLinkedList<T>::~SingleLinkedList()
{
makeEmpty();
}
template<class T>
SingleLinkedList<T>& SingleLinkedList<T>::operator =(const SingleLinkedList<T> &pList)
{
if(this == &pList)
{
return this;
}
makeEmpty();
deepCopy(pList);
return this;
}
// Insert (T &element) at the head of list.
template<class T>
void SingleLinkedList<T>::insert_head(const T &element)
{
current = NULL;
Node<T> *newNode = new Node<T>;
newNode->data = element;
newNode->next = head;
head = newNode;
}
// Insert at the tail of list.
template<class T>
void SingleLinkedList<T>::insert_tail(const T &element)
{
current = NULL;
Node<T> *newNode = new Node<T>;
newNode->data = element;
newNode->next = NULL;
Node<T> *temp;
T item;
if(head == NULL)
{
head = newNode;
temp = head;
return;
}
temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
// Put the first node into element, and set the position of the first node current.
template<class T>
bool SingleLinkedList<T>::first(T &element)
{
if(head == NULL)
{
return false;
}
current = head;
element = head->data;
return true;
}
// Put the node (current->next) into element, and set current to the next node.
template<class T>
bool SingleLinkedList<T>::getNext(T &element)
{
if(current == NULL)
{
return false;
}
if(current->next == NULL)
{
current = NULL;
return false;
}
element = current->next->data;
current = current->next;
return true;
}
// True if element found; otherwise, false. Current is set in getNext().
template<class T>
bool SingleLinkedList<T>::find(const T &element)
{
T item;
if(!first(item))
{
return false;
}
do
{
if(item == element)
{
return true;
}
}while(getNext(item));
return false;
}
template<class T>
bool SingleLinkedList<T>::retrieve(T &element)
{
if(!find(element))
{
return false;
}
element = current->data;
return true;
}
template<class T>
bool SingleLinkedList<T>::replace(const T &newElement)
{
if(current == NULL)
{
return false;
}
current->data = newElement;
return true;
}
template<class T>
bool SingleLinkedList<T>::remove(T &element)
{
current = NULL;
if(head == NULL)
{
return false;
}
Node<T> *ptr = head;
if(head->data == element)
{
element = head->data;
head = ptr->next;
delete ptr;
return true;
}
while(ptr->next != NULL)
{
if(ptr->next->data == element)
{
Node<T> *tempptr = ptr->next;
element = tempptr->data;
ptr->next = tempptr->next;
delete tempptr;
return true;
}
ptr = ptr->next;
}
return false;
}
template<class T>
bool SingleLinkedList<T>::isEmpty() const
{
return head == NULL;
}
template<class T>
void SingleLinkedList<T>::makeEmpty()
{
while(head != NULL)
{
current = head;
head = head->next;
delete current;
}
current = NULL;
}
template<class T>
void SingleLinkedList<T>::deepCopy(const SingleLinkedList<T> &original)
{
head = current = NULL;
if(original.head == NULL)
{
return;
}
Node<T> *copyptr = head = new Node<T>;
Node<T> *originalptr = original.head;
copyptr->data = originalptr->data;
if(originalptr == original.current)
{
current = copyptr;
}
while(originalptr->next != NULL)
{
copyptr->next = new Node<T>;
originalptr = originalptr->next;
copyptr = copyptr->next;
copyptr->data = originalptr->data;
if(originalptr == original.current)
{
current = copyptr;
}
}
copyptr->next = NULL;
}
// ------Entry Point------
#include <iostream>
#include "SingleLinkedList.cpp"
#include <string>
using namespace std;
void main()
{
string str[6] = {"Hello","World","Welcome","To","Beijing"};
// Initialize single linked list.
SingleLinkedList<string> strLL;
for(int ix=0;ix<5;++ix)
{
strLL.insert_tail(str[ix]);
}
cout << "Traverse single linked list: ";
string element;
if(strLL.first(element))
{
cout << element << " ";
}
while(strLL.getNext(element))
{
cout << element << " ";
}
cout << endl;
SingleLinkedList<string> strLL2(strLL); // Invoke constructor
SingleLinkedList<string> strLL3 = strLL; // Overload operator "="
strLL2.first(element);
cout << "element = " << element << endl;
strLL3.first(element);
cout << "element = " << element <<endl;
if(strLL2.find(str[3]))
{
cout << "str[3] = " << str[3] << endl;
}
if(strLL3.retrieve(str[2]))
{
cout << "str[2] = " << str[2] << endl;
}
if(strLL.remove(str[1]))
{
strLL.first(element);
cout << "element after remove is " << element << endl;
}
if(strLL.isEmpty())
{
cout << "List is Empty!" << endl;
}
strLL.makeEmpty();
strLL2.makeEmpty();
strLL3.makeEmpty();
}
// Output:
/*
Traverse single linked list: Hello World Welcome To Beijing
element = Hello
element = Hello
str[3] = To
str[2] = Welcome
element after remove is Hello
*/
分享到:
相关推荐
(2)验证单链表及其基本操作的实现; (3)进一步理解算法与程序的关系,能够将单链表算法转换为对应的程序。 1.2 实验要求: (1)用头插法(或尾插法)建立带头结点的单链表; (2)对已建立的单链表实现插入、...
数据结构-单链表(c++)超全超详细(csdn)————程序
数据结构-单链表以及对单链表进行的操作
数据结构-基本算法-单链表(学生时代源码,调试可运行)
链表 单链表_C++数据结构之单链表实现
上机实验报告 课程名称: 数据结构A 实验题目: 实验一 单链表操作 专业班级: 学 号: 姓 名: 完成日期: 2017年10月11日 成 绩: 1. 实验内容、目的和要求 1. 实验内容 单链表的创建、合并和输出。 【扩展内容】...
vs2010环境c++实现单链表, s=new node(); s->data=x; s->next=p->next; p->next=s;
数据结构说明 一、自定义的数据结构: 1、achieve(课程成绩)用于存放课程成绩信息包括课程数、课程名、成绩、学分、总分和平均分。 2、inform(学生基本信息)用于存放学生基本信息,包括姓名、学号、性别等。 ...
创建单链表类,实现单链表的构造,析构,插入,删除,清空,复制运算,输入输出运算等
链表实现线性表的基本功能,继而更进一步地去活学活用的用好这个基本数据结构,最后更好的编程续写出更完美的程序片段
数据结构c++ 线性表 单链表 【4】Chapter3 线性表1-顺序表及单链表
此资源是用C++ 实现了数据结构中单链表的实现
C/C++算法与数据结构:循环单链表的实现代码!能运行!适用于初学者
数据结构上机实践C--两单链表创建以及它们的交集.cpp
数据结构课程,是关于单链表的实现及其应用程序,希望可以帮助你
数据结构中单链表的实现,包括两个链表的合并,求交集,求并集,增加,删除,插入功能
数据结构(顺序表和单链表)C++实现 我在自学数据结构,代码是我自己写的,水平有限。
数据结构,单链表冒泡法排序数据结构,C++实现,可输入式程序
数据结构C++ 单链表的实现 实现链表的建立、遍历、查找、删除等。 博客地址:https://blog.csdn.net/qq_39400324/article/details/122630503
链表 使用C++实现链表数据结构之单链表