目标：
1.实现单向链表
2.有序链表的合并，多项式的加法运算
一.顺序链表的实现
#pragma once
#include <iostream>
using namespace std;
const int Defualt_Size = 100;
template<class Type>
class SeqList
{
public:
SeqList(int size = Defualt_Size):
maxSize(size),currentPos(-1){
if (size > 0) {
elements = new Type[maxSize];
}
}
~SeqList(){
delete [] elements;
}
int GetLength() const {
return currentPos + 1;
}
int Find(const Type& t) const; //查找t的位置
bool IsElement(const Type& t) const;//判断t是否在链表中
bool Insert(const Type& t,int pos = 0);
bool Remove(const Type& t);
void Print() const;
bool PushBack(const Type& t);
int IsEmpty() { return currentPos == -1;}
int IsFull() { return currentPos == maxSize -1;}
Type Get(int pos) const {
return (pos < 0 || pos > currentPos) ?
(cout<<"can't find the element"<<endl,0) : elements[pos];
}
private:
Type* elements;
const int maxSize;
int currentPos;
};
template<class Type>
int SeqList<Type>::Find(const Type& t) const
{
for (int i = 0; i <= currentPos;++i) {
if (elements[i] == t) {
return i;
}
}
cout<<"can't find the element"<<endl;
return -1;
}
template<class Type>
bool SeqList<Type>::IsElement(const Type& t) const
{
if (Find(t) == -1) {
return false;
}
return true;
}
template<class Type>
bool SeqList<Type>::Insert(const Type& t,int pos)
{
if (pos < 0 || pos > currentPos + 1 || currentPos == maxSize -1) {
cout<<"failed to insert,the operat is illegal."<<endl;
return false;
}
currentPos++;
for (int i = currentPos; i > pos; --i) {
elements[i] = elements[i-1];
}
elements[pos] = t;
return true;
}
template<class Type>
bool SeqList<Type>::Remove(const Type& t)
{
//有bug,当有重复元素，只能删除一个
/*int pos = Find(t);
if (pos == -1) {
cout<<""<<endl;
return false;
}
for (int i = pos; i <= currentPos; ++i) {
elements[i] = elements[i+1];
}
currentPos--;
return true;*/
int size = currentPos;
for(int i = 0; i <= currentPos;) {
if (elements[i] == t) {
for (int j = i; j<= currentPos; ++j) {
elements[j] = elements[j+1];
}
currentPos--;
continue;//长度减少一，所以i不用自增
}
i++;
}
return true;
}
template<class Type>
void SeqList<Type>::Print() const
{
for (int i = 0; i <= currentPos; ++i) {
cout<<elements[i]<<" ";
}
cout<<endl;
}
template<class Type>
bool SeqList<Type>::PushBack(const Type& t)
{
if (currentPos == maxSize -1) {
return (cout<<"the list is full"<<endl,false);
}
elements[++currentPos] = t;
return true;
}
测试代码：
#pragma once
#include "SeqList.h"
int main()
{
SeqList<int> test(19);
test.Print();
int array[15]={2,5,8,1,9,9,7,6,4,3,2,9,7,7,9};
for(int i=0;i<15;i++){
test.Insert(array[i],0);
cout<<test.GetLength()<<endl;
}
cout<<test.Get(14)<<endl;
test.Print();
test.Insert(0,0);
test.Print();
test.Insert(0,1);
test.Print();
cout<<(test.Find(0)?"can't be found ":"Be found ")<< 0 << endl<<endl;
test.Remove(7);
test.Print();
test.Remove(9);
test.Print();
test.Remove(0);
test.Print();
test.Remove(2);
test.Print();
SeqList<double> testdouble(5);
testdouble.Insert(2.0,0);
testdouble.Insert(32.213213,0);
testdouble.Print();
SeqList<char> testchar(5);
testchar.Insert(2,0);
testchar.Insert(87,0);
testchar.Insert('c',0);
testchar.PushBack('d');
testchar.PushBack('d');
testchar.PushBack('d');
testchar.Print();
testchar.Remove('d');
testchar.Print();
return 0;
}
二.单向链表的实现
结点类：
#pragma once
#include <iostream>
using namespace std;
template<class Type>
class SingleList;
template<class Type>
class ListNode
{
private:
friend class SingleList<Type>;
ListNode():data(),next(NULL){}
ListNode(const Type& t,ListNode<Type>* n = NULL):data(t),next(n){}
~ListNode(){ next = NULL;}
public:
Type GetData() const { return data; }
friend ostream& operator << <Type>(ostream&,const ListNode<Type>&);
private:
Type data;
ListNode* next;
};
template<class Type>
ostream& operator << (ostream& out,const ListNode<Type>& node)
{
out<<node.data<<endl;
return out;
}
链表类：
#pragma once
#include "listnode.h"
template<class Type>
class SingleList
{
public:
SingleList():head(new ListNode<Type>){}
~SingleList(){
delete head;
}
void MakeEmpty();
int GetLength();
//查找第n个t
ListNode<Type>* Find(const Type& t,int n) const;
ListNode<Type>* Find(int) const;
bool Insert(const Type&,int pos = 0);
bool Modify(const Type&,int pos = -1) const;
bool Remove(int pos = 0);
void RemoveAll(const Type&);
Type Get(int pos) const;
void Print() const;
private:
ListNode<Type>* head; //表头
};
template<class Type>
void SingleList<Type>::MakeEmpty()
{
ListNode<Type>* current = head;
while (head->next) {
current = head->next;
head->next = current->next;
delete current;
}
}
template<class Type>
int SingleList<Type>::GetLength()
{
ListNode<Type>* pMove = head;
int cout = 0;
while (pMove) {
pMove = pMove->next;
cout++;
}
return cout;
}
template<class Type>
ListNode<Type>* SingleList<Type>::Find(const Type& t,int n) const
{
if (n < 1) {
cout<<"The n is invalid."<<endl;
return NULL;
}
ListNode<Type>* pMove = head;
int count = 0;
while (count != n && pMove) {
pMove = pMove->next;
if (pMove->data == t) {
count++;
}
}
if (!pMove) {
cout<<"Can't find the element of "<<n<<" times."<<endl;
return NULL;
}
return pMove;
}
//从表头开始
template<class Type>
ListNode<Type>* SingleList<Type>::Find(int n) const
{
if (n < 0) {
cout<<"the input is invalid."<<endl;
return NULL;
}
ListNode<Type>* pMove = head;
for (int i = 0; i < n && pMove; ++i) {
pMove = pMove->next;
}
if (!pMove) {
cout<<"the n is out of boundary"<<endl;
return NULL;
}
return pMove;
}
template<class Type>
bool SingleList<Type>::Insert(const Type& t,int pos = 0)
{
if (pos < 0) {
cout<<"the input is invalid."<<endl;
return false;
}
ListNode<Type>* pMove = head;
for (int i = 0; i < pos && pMove; ++i) {
pMove = pMove->next;
}
if (!pMove) {
cout<<"the pos is out of boundary."<<endl;
return false;
}
ListNode<Type>* pNode = new ListNode<Type>(t);
pNode->next = pMove->next;
pMove->next = pNode;
return true;
}
template<class Type>
bool SingleList<Type>::Modify(const Type& t,int pos) const
{
if (pos < 0) {
cout<<"the pos is out of boundary."<<endl;
return false;
}
ListNode<Type>* pMove = head->next;
for (int i = 0; i < pos && pMove; ++i) {
pMove = pMove->next;
}
if (!pMove) {
cout<<"the pos is out of boundary."<<endl;
return false;
}
pMove->data = t;
return true;
}
template<class Type>
bool SingleList<Type>::Remove(int pos)
{
if (pos < 0) {
cout<<"the pos is out of boundary."<<endl;
return false;
}
ListNode<Type>* pMove = head;
ListNode<Type>* pNext = head;
int count = 0;
while (count < pos - 1 && pMove) {
pMove = pMove->next;
count++;
}
if (!pMove) {
cout<<"fail to remove emelemt."<<endl;
return false;
}
pNext = pMove->next;
pMove->next = pNext->next;
delete pNext;
return true;
}
template<class Type>
void SingleList<Type>::RemoveAll(const Type& value)
{
ListNode<Type>* pMove = head;
ListNode<Type>* pNext = head->next;
while (pNext) {
if (pNext->data == value) {
pMove->next = pNext->next;
delete pNext;
pNext = pMove->next;
continue;
}
pMove = pMove->next;
pNext = pNext->next;
}
}
template<class Type>
Type SingleList<Type>::Get(int pos) const
{
if (pos < 0) {
cout<<"the pos is out of boundary."<<endl;
return NULL;
}
ListNode<Type>* pMove = head;
for (int i = 0; i < pos && pMove; ++i) {
pMove = pMove->next;
}
if (!pMove) {
cout<<"the pos is out of boundary."<<endl;
return NULL;
}
return pMove->data;
}
template<class Type>
void SingleList<Type>::Print() const
{
ListNode<Type>* pMove = head->next;
cout<<"head--->";
while (pMove) {
cout<<pMove->data<<"--->";
pMove = pMove->next;
}
cout<<"end"<<endl;
}
测试代码：
#include "singlelist.h"
int main()
{
SingleList<float> test;
test.Insert(1);
test.Insert(2);
test.Insert(3);
test.Insert(4);
test.Insert(5);
cout<<"the Length of the list is "<<test.GetLength()<<endl;
test.Print();
test.Modify(300,1);
test.Print();
SingleList<int> list;
for(int i=0;i<20;i++){
list.Insert(i*3,i);
}
for(int i=0;i<5;i++){
list.Insert(3,i*3);
}
cout<<"the Length of the list is "<<list.GetLength()<<endl;
list.Print();
list.Remove(5);
cout<<"the Length of the list is "<<list.GetLength()<<endl;
list.Print();
list.RemoveAll(3);
cout<<"the Length of the list is "<<list.GetLength()<<endl;
list.Print();
cout<<"The third element is "<<list.Get(3)<<endl;
cout<<*list.Find(18,1)<<endl;
list.Find(100);
list.MakeEmpty();
cout<<"the Length of the list is "<<list.GetLength()<<endl;
list.Print();
return 0;
}