无序单链表-数据结构课程设计 第3页
单链表的删除
template <class T>
void LinkedList<T>::InsertAfter(const T& item) //在当前结点后插入新的结点的函数
{
Node<T>*newNode;
if(!size) //在空表中插入
{
newNode=GetNode(item);
front=rear=newNode;
position=0;
}
else if(currptr==rear||!currptr) //在表尾结点后插入
{
newNode=GetNode(item);
rear->InsertAfter(newNode);
prevptr=rear;
rear=newNode;
position=size;
}
else //在链表的中间位置插入
{
newNode=GetNode(item, currptr->NextNode());
currptr->InsertAfter(newNode);
prevptr=currptr;
position++;
}
size++; //增加表的长度
currptr=newNode; //将插入的新结点作为当前结点
}
template <class T>
void LinkedList<T>::DeleteAt(void) //删除当前结点的函数
{
Node<T>*oldNode;
if(!prevptr) //删除的是表头结点
{
oldNode=front;
front=currptr->NextNode();
}
else
{
oldNode=prevptr->DeleteAfter(); //删除的是表中的结点
}
if(oldNode==rear)
{
//删除的是表尾结点，则修改表尾指针和当前结点位置
rear=prevptr;
position--;
}
currptr=oldNode->NextNode(); //后继结点作为新的当前结点
FreeNode(oldNode); //释放原当前结点
size--; //链表的大小减1
}
template <class T>
void LinkedList<T>::DeleteAfter(void) //删除当前结点后继的函数
{
Node<T> *oldNode;
if(size==0)
{
cerr<<" DeleteAfter: currptr postion is invalid!"<<endl;
return ;
}
oldNode=prevptr->DeleteAfter(); //保存披删除结点是指针并从链表中删除该结点
if(oldNode==rear)
{
rear=currptr; //删除的是表尾结点
}
FreeNode(oldNode); //释放披删除结点
size--; //链表大小减1
}
template<class T>
T LinkedList<T>::GetData(void)const //获取当前结点数据的函数
{
if(!size) //若表为空或已到表尾，则给出错误提示并退出
{
cerr<<" Data: currptr node not exist"<<endl;
exit(1);
}
return currptr->data;
}
template<class T>
void LinkedList<T>::SetData(const T& item) //修改当前结点数据的函数
{
if(!size) //若表为空或已到表尾，则给出错误
{
cerr<<"Data:currptr node not exist"<<endl;
exit(1);
}
currptr->data=item; //修改当前结点的值
}
template <class T>
void LinkedList<T>::Clear(void) //清空链表的函数
{
Node<T> *currNode=front, *nextNode;
while(size>1)
{
nextNode=currNode->NextNode(); //保存后继结点指针
FreeNode(currNode); //释放当前结点
front=currNode=nextNode; //原后继结点成为当前结点
size--;
}
if(size==1)
{
FreeNode(currNode);
size--;
}
front=rear=prevptr=currptr=NULL; //修改空链表数据
size=0;
position=-1;
cout<<"清除成功!"<<endl;
}
template <class T>
bool LinkedList<T>::IsEmpty(void)const // 判断表是否为空的函数
{
if(!size)
{
cout<<"表为空!"<<endl;
return false;
}
else
{
cout<<"表不为空!"<<endl;
return true;
}
}
template <class T>
void LinkedList<T>::WuXu(int k)
{
int i=1;
int t,p,s;
p=Getposition(); //获得当前结点位置
currptr=front;
s=Size(); //获取表长
while(i<s)
{
currptr=currptr->NextNode();
position++;
if (k>currptr->data) //k 是否大于当前结点值
{
p=position;
k=currptr->data;
}单链表的删除
i++;
}
cout<<"最小值结点位置："<<p<<endl;
cout<<"最小值是："<<k<<endl;
if (k%2==0) // k 是否为偶数
{
SetPosition(p);
if (currptr=front) //当前结点为表头的时候
{
currptr=currptr->NextNode();
DeleteAt();
cout<<"删除成功!"<<endl;
}
else if (currptr=rear) //当前结点为表尾
cout<<"已到达表尾,无后继!"<<endl;
else
{
DeleteAfter();
cout<<"删除成功!"<<endl;
}
}
else
{
SetPosition(p);
if(p+1==s) //当前结点为表尾
cout<<"已到表尾,无后继!"<<endl;
else
{
currptr=currptr->NextNode();
751com.cn单链表的删除
SetData(t);
cout<<"当前结点数值为："<<currptr->data<<endl;
cout<<"交换成功!"<<endl;
}
}
}
//main.cpp
#include <iostream.h>
#include<stdlib.h>
#include "LinkedList.cpp"
void main()
{
LinkedList<int> Wu; //定义对象
int n,k,i,m=1;
cout<<"请选择输入：";
while(m<6)
{
cout<<"1) 判断链表是否为空 2) 取表的长度 3) 输入数据、并求最小值和其结点 4)清除历史记录"<<endl;
cin>>m;
switch(m) //选择输入
{
case 1 : Wu.IsEmpty (); break;
case 2 : cout<<"表长为："<<Wu.Size ()<<endl; break;
case 3:
{
cout<<"输入无序组的个数：";
cin>>n;
cout<<"输入数据：";
for (i=0;i<n;i++)
{
cin>>k;
Wu.InsertAfter(k); //插入结点
}
Wu.SetPosition(0); //重置当前结点
Wu.WuXu(Wu.GetData()); //把当前数据做为实参
} break;
case 4 : Wu.Clear(); break;
default : exit(1);
}
}
}