- #include"iostream.h"
- struct SLNode{
- int data;
- SLNode*next;
- SLNode(SLNode*nextNode=NULL){next=nextNode;}
- SLNode(const int item,SLNode*nextNode=NULL){data=item;next=nextNode;}
- };
- class SLList{
- private:
- SLNode*head;/*表头指针*/
- SLNode*currptr;/*表尾指针*/
- SLNode*now;//当前结点指针
- int size;
- public:
- SLList(void){head=currptr=new SLNode();now=NULL;size=0;};
- SLList(int item);
- ~SLList(void);
- bool IsEmpty(void)const{return head->next==NULL;};
- int length(void){return size;};
- bool Find(int k);
- bool Findnow();
- bool Findcurrent();
- int Search(const int item)const;
- void pre();
- bool Deletehead();
- bool Deletenow();
- bool Deletelast();
- void Insertlast(const int item);
- void Inserttop(const int item);
- void Insertnow(int p);
- void display();
- };
- //单链表的构造函数
- //单链表的构造函数。生成含有哨位节点和一个表结点的表
- SLList::SLList(int item)
- {
- currptr=now=new SLNode(item);
- head=new SLNode(now);
- size=1;
- };
- //单链表的析构函数
- SLList::~SLList()
- {
- while(!IsEmpty())
- {SLNode* curr;
- curr=head->next;
- head->next=curr->next;
- delete curr;
- }
- delete head;
- };
- //在当前结点后插入函数
- void SLList::Insertnow(int p)
- {
- SLNode* temp=new SLNode(p);
- Findcurrent();
- temp->next=now->next;
- now->next=temp;
- if(currptr==now)
- currptr=temp;
- size++;
- }
- //插入函数
- void SLList::Insertlast(const int item){ //在表尾进行插入函数
- currptr->next=new SLNode(item);
- currptr=currptr->next;
- size++;
- };
- //在表头进行插入函数
- void SLList::Inserttop(const int item){
- SLNode*ren=new SLNode(item);
- ren->next=head->next;
- head->next=ren;
- size++;
- }
- //存取第k个结点函数
- bool SLList::Find(int k){
- if(k>size||IsEmpty()||k<0)
- {cout<<" 存取失败"<<endl;
- return false;
- }
- int i=0;
- SLNode*q=now; //附加实验
- now=head;
- while(i<k)
- {
- i++;
- now=now->next;
- }
- int item=now->data;
- cout<<"存取成功,结点值为"<<item<<endl;
- now=q; //附加实验
- return true;
- };
- //存取当前节点的值函数
- bool SLList::Findnow()
- {
- if(IsEmpty())
- {
- cout<<"链表为空!"<<endl;
- return false;
- }
- else
- { Findcurrent();
- int stn_item=now->data;
- cout<<"存取当前结点成功 ,当前结点值为"<<stn_item<<endl;
- return true;
- }
- }
- //找到当前结点函数
- bool SLList::Findcurrent()
- {
- if(IsEmpty())
- {
- cout<<"当前链表中没有结点"<<endl;
- return false;
- }
- /*cout<<"请输入你想寻找的当前结点是第几个有效结点:"<<endl;
- int k;
- cin>>k;
- while(k<0||k>length())
- {cout<<"输入错误,请重新输入:"<<endl;
- cin>>k;
- }
- now=head;
- int i=0;
- while(i<k)
- {now=now->next;
- i++;}*/
- return true;
- }
- //查找函数
- int SLList::Search(const int item)const{
- SLNode*p=head->next;
- int i=1;
- while(p!=NULL&&p->data!=item){
- p=p->next;
- i++;
- }
- if (p!=NULL){
- cout<<"你想找的是第"<<i<<"个结点"<<endl;
- }
- else cout<<"无此结点"<<endl;
- return -1;
- };
- //找当前结点的前驱结点
- void SLList::pre()
- {
- if(IsEmpty()||now==head)
- cout<<"当前链表无结点"<<endl;
- else
- {
- SLNode* pp=head;
- while(pp->next!=now)
- {pp=pp->next;}
- now=pp;
- }
- }
- //删除哨位节点后的第一个节点
- bool SLList::Deletehead()
- {
- if(IsEmpty())
- { cout<<"链表为空"<<endl;
- return false;
- }
- SLNode* p=head->next;
- head->next=p->next;
- int deitem1=p->data;
- if(p->next==NULL)
- currptr=head;
- cout<<"已删除头结点,删除结点值为"<<deitem1<<endl;
- delete p;
- return true;
- }
- //删除当前节点的后继结点
- bool SLList::Deletenow()
- {
- Findcurrent();
- if(now==currptr||IsEmpty())
- {cout<<"当前结点无后继或链表为空"<<endl;
- return false;
- }
- SLNode* p=now->next;
- now->next=p->next;
- int deitem2=p->data;
- if(p==currptr)
- currptr=now;
- size--;
- cout<<"已删除当前结点,删除结点值为"<<deitem2<<endl;
- delete p;
- return true;
- }
- //删除结尾节点
- bool SLList::Deletelast()
- {
- if(IsEmpty())
- {
- cout<<"链表为空"<<endl;
- return false;
- }
- SLNode* p;
- p=now=currptr;
- pre();
- int deitem=currptr->data;
- now->next=NULL;
- currptr=now;
- size--;
- cout<<"已删除尾结点,删除结点值为"<<deitem<<endl;
- delete p;
- return true;
- }
- //将链表元素全部打印出来函数
- void SLList::display()
- {
- if(IsEmpty())
- cout<<"链表为空"<<endl;
- else
- {
- SLNode* cur=NULL;
- int i=0;
- cur=head->next;
- while(cur!=NULL)
- {
- i++;
- cout<<"-->"<<cur->data;
- cur=cur->next;
- }
- delete cur;
- cout<<endl;
- }
- }
- //删除函数
- /*void SLList::Delete(int k){
- if(k<1){
- cout<<"删除不合法"<<endl;
- }
- SLNode*p=head;
- int i=0;
- while(p!=NULL&&i<k-1){
- p=p->next;
- i++;
- }
- if (p=NULL){
- cout<<"无此结点"<<endl;
- return;
- }
- SLNode*q=p->next;
- p->next=q->next;
- int item=q->data;
- q=NULL;
- };*/
- int main(){
- //建立并插入元素模块测试区
- SLList list(9);
- list.Insertlast(5);
- list.Insertlast(2);
- list.Insertlast(4);
- list.Insertlast(6);
- list.Insertlast(7);
- list.Insertlast(8);
- cout<<"建立链表完毕"<<endl;
- list.display();
- //查找元素测试
- list.Search(7);
- //插入及存取测试区
- list.Find(5);
- list.Findnow();
- list.Insertnow(89);
- list.Insertnow(32);
- list.Inserttop(199);
- list.Insertlast(95);
- list.display();
- //删除结点测试区
- list.Findnow();
- list.Deletenow();
- list.Deletehead();
- list.Deletelast();
- list.display();
- //list.display();
- return 0;
- };
- //该片段来自于http://www.codesnippet.cn/detail/2304201512412.html
来源: http://www.codesnippet.cn/detail/2304201512412.html