数据结构上机实验题目要求
实现代码
//SLList.h
#ifndef SLLIST_H_INCLUDED
#define SLLIST_H_INCLUDED
template<class T>
//单链表结点结构
struct SLNode
{
T data;//数据域
SLNode<T> * next;//指针域
SLNode(SLNode * nextNode=nullptr)
{
next=nextNode;
}//构造函数
SLNode(const T&item,SLNode * nextNode=nullptr)
{
data=item;
next=nextNode;
}//构造函数
};
//单链表类
template<class T>
class SLList
{
private:
SLNode<T> * head;//头指针
SLNode<T> * tail;//尾指针
SLNode<T> * currptr;//当前指针
int listsize;
public:
SLList()
{
head=tail=currptr=new SLNode<T>();
listsize = 0;
}//构造函数，构造一个只有哨位结点的空表
SLList(T &item)
{
tail=currptr=new SLNode<T>(item);
head=new SLNode<T>(currptr);
listsize=1;
}
~SLList()
{
while(!IsEmpty())
{
currptr=head->next;
head->next=currptr->next;
delete currptr;
}
delete head;
}//析构函数
bool IsEmpty()const{return head->next==nullptr;}//判断链表是否为空
int length()const;//翻回链表的长度
void Find(int k)const;//存取，返回链表中第k个结点的字段值
int FindNow()const;//存取当前结点的值
void Search(int x)const;//查找，在链表中查找字段值为x的结点并返回其表中的位置
void Delete();//删除当前结点的后继结点
void DeleteHead();//删除表头结点
void DeleteTail();//删除表尾结点
void Insert(const T& item);//在当前结点前插入一个data为item的结点
void InsertHead(const T& item);//在表头插入一个结点
void InsertTail(const T& item);//在表尾插入一个结点
void Print();//按格式输出链表
};
#endif // SLLIST_H_INCLUDED
SLList.cpp
#include "SLList.h"
#include<iostream>
using namespace std;
template<class T>
int SLList<T>::length()const
{
return listsize;
}
template<class T>
void SLList<T>::Insert(const T& item)
{
currptr->next=new SLNode<T>(item,currptr->next);
if (tail==currptr)
tail=currptr->next;
listsize++;
}
template<class T>
void SLList<T>::InsertHead(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);
}
listsize++;
}
template<class T>
void SLList<T>::InsertTail(const T& item)
{
tail->next=new SLNode<T>(item,nullptr);
tail=tail->next;
listsize++;
}
template<class T>
void SLList<T>::Delete()
{
if (currptr==tail||IsEmpty())
{
cout<<"No next node or empty list!";
}
SLNode<T> * temp=currptr->next;
currptr->next=temp->next;
listsize--;
if(temp==tail) tail=currptr;
delete temp;
}
template<class T>
void SLList<T>::DeleteHead()
{
if (IsEmpty())
{
cout<<"Empty list!";
}
SLNode<T> * temp=head->next;
head->next=temp->next;
listsize--;
if (temp==tail) tail=head;
delete temp;
}
template<class T>
void SLList<T>::DeleteTail()
{
if (IsEmpty())
{
cout<<"Empty list!";
}
while(currptr->next!=tail)
{
currptr=currptr->next;
}
currptr->next=nullptr;
listsize--;
delete tail;
tail=currptr;
}
template<class T>
void SLList<T>::Find(int k)const
{
SLNode<T>*temp=head->next;
int i=1;
if (k>listsize)
cout<<"The number k is wrong!"<<endl;
else
{
while(temp!=nullptr && i<k)
{
temp=temp->next;
i++;
}
cout<<"The "<<k<<"th item is "<<temp->data<<endl;
}
}
template<class T>
int SLList<T>::FindNow()const
{
return currptr->data;
}
template<class T>
void SLList<T>::Search(int x)const
{
SLNode<T> * temp=head;
int position=0;
for (int i = 1;i<=listsize;++i)
{
temp=temp->next;
if (temp->data==x)
{
position = i;
break;
}
}
if(position==0)
{
cout<<"There isn't a "<<x<<" in the list!"<<endl;
}
else cout<<"The "<<x<<"\'s position is "<<position<<"!"<<endl;
}
template<class T>
void SLList<T>::Print()
{
for(SLNode<T>*temp=head->next;temp;temp=temp->next)
{
cout<<"["<<temp->data<<"]";
if(temp->next!=nullptr)
cout<<"->";
}
cout<<endl<<"The listsize is "<<listsize<<endl;
}
Test.cpp
#include "SLList.h"
#include<iostream>
#include"SLList.cpp"
using namespace std;
int main(int argc, char const *argv[])
{
SLList<int> list; //创建一个空表
while(true)
{
int i;
cout<<"What do you want to do?"<<endl;
cout<<"1.insert 2.delete 3.find 4.search"<<endl;
cin>>i;
if (i==1)
{
cout<<"1.insertnow 2.insertHead 3.insertTail 4.back"<<endl;
cin>>i;
if (i==1)
{
cin>>i;
list.Insert(i);
}
else if(i==2)
{
cin>>i;
list.InsertHead(i);
}
else if (i==3)
{
cin>>i;
list.InsertTail(i);
}
else
{
i=0;
continue;
}
list.Print();
}
else if (i==2)
{
cout<<"1.deletenow 2.deleteHead 3.deleteTail 4.back"<<endl;
cin>>i;
if (i==1)
{
list.Delete();
}
else if(i==2)
{
list.DeleteHead();
}
else if (i==3)
{
list.DeleteTail();
}
else
{
i=0;
continue;
}
list.Print();
}
else if (i==3)
{
cout<<"1.find k 2.findnow 3.back"<<endl;
cin>>i;
if (i==1)
{
cin>>i;
list.Find(i);
}
else if(i==2)
{
cout<<list.FindNow()<<endl;
}
else
{
i=0;
continue;
}
}
else
{
cin>>i;
list.Search(i);
}
}
return 0;
}
网友评论