|
|
 #include <iostream>
#include <stdio.h>
#include <iostream.h>
template <class T>
  struct SLNode {
 T data;
SLNode<T> *next;
  SLNode(SLNode<T> *nextNode=NULL){
next = nextNode;
 }
SLNode(const T &item,SLNode<T> *nextNode=NULL){
data = item;
next = nextNode;
}
 };
template <class T>
class SLList{
private:
SLNode<T> *head;
SLNode<T> *tail;
SLNode<T> *currptr;
int size;
public:
SLList();
SLList(const T &item);
~SLList();
bool IsEmpty()const;
int Length()const;
bool Find(int k, T &item)const;
int Search(const T &item)const;
void InsertFromHead(const T &item);
void InsertFromTail(const T &item);
bool DeleteFromHead(T &item);
bool DeleteFromTail(T &item);
void Insert(int k,const T &item);
void Delete(int k,T &item);
void ShowListMember();
};
//构造函数
template <class T>
SLList<T>::SLList(){
head = tail = currptr = new SLNode<T>();
size = 0;
}
//构造函数
template <class T>
SLList<T>::SLList(const T &item){
tail = currptr = new SLNode<T>(item);
head = new SLNode<T>(currptr);
size = 1;
}
//析构函数
template <class T>
SLList<T>::~SLList(){
SLNode<T> *temp;
while(!IsEmpty()){
temp = head->next;
head -> next = temp -> next;
delete temp;
}
}
//判断链表是否为空
template <class T>
bool SLList<T>::IsEmpty()const{
return head->next == NULL;
}
//返回链表的长度
template <class T>
int SLList<T>::Length()const{
return size;
}
//查找第k个节点的阈值
template <class T>
bool SLList<T>::Find(int k,T &item)const {
if(k < 1){
cout<<"illegal position !"<<endl;
}
SLNode<T> *temp = head;
int count = 0;
while(temp != NULL && count < k){
temp = temp->next;
count++;
}
if(temp == NULL){
cout<<"The list does not contain the K node !"<<endl;
return false;
}
item = temp->data;
return true;
}
//查找data阈值为item是表的第几个元素
template <class T>
int SLList<T>::Search(const T &item)const {
SLNode<T> *temp = head->next;
int count = 1;
while(temp != NULL && temp->data != item) {
temp = temp->next;
count++;
}
if(temp == NULL) {
cout<<"The node does not exist !"<<endl;
return -1;
}
else {
return count;
}
}
//从表头插入
template <class T>
void SLList<T>::InsertFromHead(const T &item) {
if(IsEmpty()) {
head->next = new SLNode<T>(item,head->next);
tail = head->next;
}
else {
head->next = new SLNode<T>(item,head->next);
}
size++;
}
//从表尾插入
template <class T>
void SLList<T>::InsertFromTail(const T &item) {
tail->next = new SLNode<T>(item,NULL);
tail = tail->next;
size++;
}
//从表头删除
template <class T>
bool SLList<T>::DeleteFromHead(T &item) {
if(IsEmpty()) {
cout<<"This is a empty list !"<<endl;
return false;
}
SLNode<T> *temp = head->next;
head->next = temp->next;
size--;
item = temp->data;
if(temp == tail) {
tail = head;
}
delete temp;
return true;
}
//从表尾删除
template <class T>
bool SLList<T>::DeleteFromTail(T &item) {
if(IsEmpty()) {
cout<<"This is a empty list !"<<endl;
return false;
}
SLNode<T> *temp = head;
while(temp->next != tail) {
temp = temp->next;
}
item = tail->data;
tail = temp;
tail->next=NULL;
temp = temp->next;
delete temp;
size--;
return true;
}
//在第k个节点后插入item值
template <class T>
void SLList<T>::Insert(int k,const T &item) {
if(k < 0 || k > size) {
cout<<"Insert position Illegal !"<<endl;
return;
}
if(k == 0) {
InsertFromHead(item);
return;
}
if(k == size) {
InsertFromTail(item);
return;
}
SLNode<T> *temp = head->next;
int count = 1;
while(count < k) {
count++;
temp = temp->next;
}
SLNode<T> *p = temp->next;
temp->next = new SLNode<T>(item,p);
size++;
}
//删除第k个节点的值，保存在item中
template <class T>
void SLList<T>::Delete(int k,T &item) {
if(k <= 0 || k > size) {
cout<<"Ileegal delete position !"<<endl;
return;
}
if(k == 1){
DeleteFromHead(item);
return;
}
if(k == size){
DeleteFromTail(item);
return;
}
SLNode<T> *temp = head->next;
int count = 1;
while(count < k-1) {
count++;
temp = temp->next;
}
SLNode<T> *p = temp->next;
temp->next = p->next;
p->next = NULL;
item = p->data;
delete p;
size--;
}
template <class T>
void SLList<T>::ShowListMember() {
cout<<"List Member : ";
SLNode<T> *temp = head->next;
while(temp != NULL){
cout << temp -> data << " ";
temp = temp -> next;
}
cout<<endl;
}
/**//*
1.引入了InsertFronHead,InsertFromTail,DeleteFromHead和DeleteFromTail用来实现
Insert和Delete函数，是一个比较好的方法。
2.SLNode(T &item,SLNode<T> *nextNode)这个构造函数设计的非常巧妙，便于其他成员
函数的实现。
3.插入，删除分为：表头，表尾，中间插入（删除）三种情况
*/
int main()
{
int item;
SLList<int> list(12);
list.Insert(0,11);
cout<<"list number:"<<list.Length()<<endl;
list.ShowListMember();
list.Insert(2,14);
cout<<"list number:"<<list.Length()<<endl;
list.ShowListMember();
list.Insert(2,13);
cout<<"list number:"<<list.Length()<<endl;
list.ShowListMember();
list.Delete(2,item);
cout<<"item = "<<item<<endl;
cout<<"list number:"<<list.Length()<<endl;
list.ShowListMember();
list.Delete(1,item);
cout<<"item = "<<item<<endl;
cout<<"list number:"<<list.Length()<<endl;
list.ShowListMember();
list.Delete(2,item);
cout<<"item = "<<item<<endl;
cout<<"list number:"<<list.Length()<<endl;
list.ShowListMember();
return 0;
}
|