返回顶部

收藏

单链表的一些扩展功能

更多

单链表扩展功能

#include<iostream>
#include <stdlib.h>  //for exit(0) 
#include <windows.h> //for system("cls")
using namespace std;
typedef struct Node//Link 等价于S
{
    int data;
    Node *next;
}Link,*Nlink;
class LinkList
{
public:
    Nlink GetFirst();
    LinkList();
    ~LinkList();
    void LenLink();//求出链表的长度
    void menu();
    void CreateLink();
    void ModifyNode();    //修改节点
    void ModifyByNum();   //按值修改
    void ModifyBySite();  //按位置修改
    void InsertFront();    //插入节点
    void InsertBack();    //向前插入
    void InsertNode();     //向后插入
    void DeleteNode();    //删除节点
    void DeleteNum();      //删除值为N的节点
    void DeleteSite();     //删除第N个节点
    void Search();     //查找节点
    void SearchByNum();      //按  值  查找,返回 位置
    void SearchBySite();//按 位置 查找,返回  值
    void SortLink();
    void PrintLink();
private:
    Nlink first;
    int length;
};
LinkList::LinkList()
{
    length=0;
    first=new Link;
    first->next=NULL;
//  cout<<"LinkList()"<<endl;
}
Nlink LinkList::GetFirst ()
{
    return first;
}
LinkList::~LinkList ()
{
    Nlink p;
    while(first!=NULL)
    {
        p=first->next;
        delete first;
        first=p;
    }
    cout<<"~LinkList()"<<endl;
}

void LinkList::menu ()
{

    cout<<endl;
    cout<<endl;
    cout<<"\t\t*************************************"<<endl;
    cout<<"\t\t*                                   *"<<endl;
    cout<<"\t\t*   1.创建链表     2.修改节点       *"<<endl;
    cout<<"\t\t*   3.插入节点     4.删除节点       *"<<endl;
    cout<<"\t\t*   5.输出         6.查找           *"<<endl;
    cout<<"\t\t*   7.清屏         8.退出           *"<<endl;
    cout<<"\t\t*   9.排序       10.链表长        * "<<endl;
    cout<<"\t\t*************************************"<<endl;
}
void LinkList::CreateLink()
{
    Nlink p,s;
    int m=-1;
    p=first;
    int num;    
    cout<<"请输入整形的数字,(以-1结束)"<<endl;
    cin>>num;   
    while(p->next) //这句话的作用是使得每次p指针都指向尾部从而第二次输入数字的时候可以把它连接起来
        p=p->next;
    while(num!=-1)
    {
        s=new Link;
        s->data=num;
        p->next=s;
        p=s;
        length++;
        cout<<"请输入整形的数字,(以-1结束)"<<endl;
        cin>>num;       
    }
      p->next =NULL;//这一步非常重要每创建完之后要将指针指向新的节点后要将其next赋为空不然就是一个指向不确定的节点,程序就会出错。
    cout<<"链表创建完毕!"<<endl;
}
void LinkList::ModifyNode ()
{
    int flag;
    cout<<endl;
    cout<<endl;
    cout<<"****************************************"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"**   1.按值修改                       **"<<endl;
    cout<<"**   2.按位置修改                     **"<<endl;
    cout<<"**   3.退出                           **"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"****************************************"<<endl;

    do{
        cout<<"请输入你需要修改节点的方式:"<<endl;
        cin>>flag;
        switch(flag)
        {
        case 1:
            try{
            ModifyByNum();
            }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 2:
            try{
            ModifyBySite();
               }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 3:
            break;
        default:
            cout<<"你输入的有误请重新再输入!"<<endl;

        }
    }while(flag !=3);
}

void LinkList::ModifyByNum ()
{
    Nlink p;
    int num;
    int modify;
    cout<<"请输入你要修改的元素的值:";
    cin>>num;
    cout<<endl;
    cout<<"请输入要修改后的值:";
    cin>>modify;
    cout<<endl;
    p=first->next ;
    while(p!=NULL)
    {
        if(p->data ==num)
        {
            p->data=modify;
             break;//刚开始居然忘记break,这样导致的结果是永远会显示你要修改的元素不存在由于最终P指针永远会指向NULL
        }
        else
            p=p->next ;
    }
    if(!p)
    {
        throw "你要修改的元素不存在!";
        cout<<endl; 
    }
    cout<<"修改完毕,请继续操作"<<endl;
}
void LinkList::ModifyBySite ()
{
    Nlink p;
    int count=1;
    int Site;
    int modify;
    cout<<"请输入你要修改节点的位置:"<<endl;
    cin>>Site;
    p=first->next;
    while(p!=NULL && count<Site)
    {
        p=p->next;
        count++;
    }
    if(!p)
    {
        throw "你要修改的元素不存在!";
        cout<<endl; 
    }

        cout<<"请输入你要修改的新的元素的值:";
        cin>>modify;
        p->data =modify;

    cout<<"修改完毕,请继续操作"<<endl;
}
void LinkList::InsertNode ()
{
    int flag;
    cout<<endl;
    cout<<endl;
    cout<<"****************************************"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"**   1.前插入                         **"<<endl;
    cout<<"**   2.后插入                         **"<<endl;
    cout<<"**   3.退出                           **"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"****************************************"<<endl;
    do{
        cout<<"请输入你需要插入的方式:"<<endl;
        cin>>flag;
        switch(flag)
        {
        case 1:
            try {
            InsertFront();
            }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 2:
            try{
            InsertBack();
            }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 3:
            break;
        default:
            cout<<"你输入的有误请重新再输入!"<<endl;
        }
    }while(flag !=3);
}

void LinkList::InsertFront ()
{
    Nlink p,s;
    int count=1;
    int Site;
    int modify;
    p=first->next ;
    s=new Link;
    cout<<"请输入你要插入的位置";
    cin>>Site;
    cout<<"请输入你要插入值的元素:";
    cin>>modify;
    s->data =modify;
    cout<<endl;
    if(Site==1)
    {
        s->next=p;
        first->next=s;
    }
    else

    {
        while (p!=NULL && count<Site-1)
        {
            p=p->next;
            count++;
        }
    if(!p)
    {
        throw "你要插入的位置不合理!";
        cout<<endl; 
    }
      s->next=p->next;
      p->next=s;//我个白痴居然写成p->next=s->next结果这么样都是错得,真是粗心啊,一直感觉已经没错了啊,但是居然还是粗心的错了,根据运行结果看屏幕半小时才检查出来
    }
    length++;
    cout<<"插入完毕,请继续执行操作"<<endl;
}
void LinkList::InsertBack ()
{
    Nlink p,s;
    int count=1;
    int Site;
    int modify;
    p=first->next ;
    s=new Link;
    cout<<"请输入你要插入的位置";
    cin>>Site;
    cout<<"请输入你要插入值的元素:";
    cin>>modify;
    s->data =modify;
    cout<<endl;

    while (p!=NULL &&count<Site)
    {
        p=p->next;
        count++;
    }

    if(!p)
    {
        throw "你要插入的位置不合理!";
        cout<<endl; 
    }
        s->next=p->next;
        p->next=s;
        length++;
    cout<<"插入完毕,请继续执行操作"<<endl;
}

void LinkList::DeleteNode ()
{
    int flag;
    cout<<endl;
    cout<<endl;
    cout<<"****************************************"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"**   1.按值删除                       **"<<endl;
    cout<<"**   2.按位置删除                     **"<<endl;
    cout<<"**   3.退出                           **"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"****************************************"<<endl;

    do{
        cout<<"请输入你需要删除的方式:"<<endl;
        cin>>flag;
        switch(flag)
    {
        case 1:
               try
               {
               DeleteNum();
               }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 2:
            try{
            DeleteSite();
            }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 3:
            break;
        default:
            cout<<"你输入的有误请重新再输入!"<<endl;
        }
    }while(flag !=3);
}

void LinkList::DeleteNum ()
{
    Nlink p,q,s;
    int count=1;
    int flag=0;
    int num;
    p=first->next ;
    cout<<"请输入你要删除的元素的值";
    cin>>num;
    cout<<endl;
    if(p->data==num)
        first->next=first->next->next;     
    else
    {   
           q=p;
         s=p->next;
        while (s !=NULL )
        {           
        if(s->data==num)
        {
            flag=1;//很巧妙的使用标志发以后药剂的常用
            s=s->next;
            q->next=s;
            length--;
            break;
        }               
        else 
        {
            s=s->next;
            q=q->next;
        }
        }

    }   

    if(flag==0)
    {
        throw "你要删除的元素不存在!";
        cout<<endl; 
    }
    cout<<"删除完毕,请继续操作"<<endl;
}
void LinkList::DeleteSite ()

{
    Nlink p,s,q;
    int count=1;
    int Site;
    p=first->next ;
    cout<<"请输入你要删除的元素的位置";
    cin>>Site;
    cout<<endl;
        if(Site>length)//用这种方法非常巧妙的判断他得位置。我原来用!P就错了
        {

        throw "你要删除的元素不存在!";
        cout<<endl; 
        }
    if(Site==1)
        first->next=first->next->next;
    else
    {
         q=p->next;
        while(q!=NULL  && count<Site-1)
        {
            q=q->next ;
            count++;
        }
    }

        s=q->next;
        q->next=s->next;
        delete s;
        length--;   
    cout<<"删除完毕,请继续操作"<<endl;
}

void LinkList::Search ()//查找的功能明天再写
{
    int flag;
    cout<<endl;
    cout<<endl;
    cout<<"****************************************"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"**   1.按值查询                       **"<<endl;
    cout<<"**   2.按位置查询                     **"<<endl;
    cout<<"**   3.退出                           **"<<endl;
    cout<<"**                                    **"<<endl;
    cout<<"****************************************"<<endl;

    do{
        cout<<"请输入你需要查询的方式:"<<endl;
        cin>>flag;
        switch(flag)
        {
        case 1:
            try{
                SearchByNum();  
               }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 2:
            try{
            SearchBySite();
               }
            catch(char*str)
            {
                cout<<str<<endl;
            }
            break;
        case 3:
            break;
        default:
            cout<<"你输入的有误请重新再输入!"<<endl;
        }
    }while(flag !=3);
}

void LinkList::SearchByNum()
{
    Nlink p; 
    int num;
    int count=0;
    p=first->next;
    cout<<"请输入你要查询的元素:";
    cin>>num;
    while(p!=NULL)
    {     
        count++;
        if(p->data==num)
            break;
        else
            p=p->next;
    }
    if(!p)
    {
        throw "你要查找的元素不存在!";
        cout<<endl; 
    }
    cout<<"你要查找的的元素的位置在"<<count<<"位"<<endl;
    cout<<"查询完毕,请继续操作"<<endl;
}
void LinkList::SearchBySite()
{  
    Nlink p;
    int Site;
    int count=1;
    p=first->next;
    cout<<"请输入你要查询的位置:";
    cin>>Site;
    while(p!=NULL && count<Site)
    {
        p=p->next;
        count++;
    }

    if(!p)
    {
        throw "你输入的位置不正确!";
        cout<<endl; 
    }
    cout<<"第"<<Site<<"个位置的元素是"<<p->data<<endl;
    cout<<"查询完毕,请继续操作"<<endl;
}

void LinkList::SortLink()//本函数由于刚开始没有对length=0的初始化从而导致排序函数的失败
{   
    int i,j,t;
    Nlink p,q;
    for(i=0,p=first->next;i<length-1;i++)//,p=p->next)
    {
        for(j=i+1,q=p->next;j<length;j++)//,q=q->next)
        {
            if(p->data>q->data)
            {
                t=p->data;
                p->data=q->data;
                q->data=t;
            }
            q=q->next;
        }
        p=p->next;
    }
    cout<<"排序完毕,请继续选择操作"<<endl;
}
void LinkList::LenLink()
{
    //cout<<"你很好"<<endl;
    Nlink p;//等价于Node*p
    p=first->next;
    int cnt=0;
    while(p!=NULL)
    {
       cnt++;
       p=p->next ;//在写程序的时候很是马虎大意居然忘了这部从而导致这么想也想不通为什么不会输出链表的长度
       }
    if(!p)
    {
    cout<<"链表的长度是:"<<cnt<<endl;
    cout<<"链表长度已经输出,请继续选择操作!"<<endl;
    }
}
void LinkList::PrintLink()
{
    Nlink p;
    p=first->next ;
    while(p!=NULL)
    {
        cout<<p->data<<"\t";
        p=p->next;

    }
}
void  main()
{
    LinkList obj;
//  p=obj.GetFirst()->next ;错误的写法
    Nlink p;    
    int chose; //选择操作
    obj.menu();//输出菜单

    do{
        p=obj.GetFirst()->next ;//由于刚开始把这条语句放在外面导致错误由于房子外面永远也得不到first的next的地址
        cout<<"主菜单->请选择操作:";
        cin>>chose;
    //  fflush(stdin); //清空缓冲区
        switch(chose)
        {
        case 1:  
            obj.CreateLink();//创建链表,通过运行的结果发现,这个只有一次创建链表有效,再次的创建链表则会覆盖以前的链表
            break;      
        case 2: if (!p)    
                    cout<<"链表为空,请先创建链表!"<<endl;
            else  

                obj.ModifyNode();  //修改节点
                 obj.menu();
                break;

        case 3: if (!p)    
                    cout<<"链表为空,请先创建链表!"<<endl;

            obj.InsertNode();  //插入节点
              obj.menu();
            break;

        case 4: 

            if (!p)    
                    cout<<"链表为空,请先创建链表!"<<endl;

            else
                obj.DeleteNode();  //删除节点
              obj.menu();
            break;

        case 5: if (!p)    
                    cout<<"链表为空,请先创建链表!"<<endl;
            else  

                obj.PrintLink();  //输出
                obj.menu();
               break;

        case 6:if (!p)    
                   cout<<"链表为空,请先创建链表!"<<endl;
            else  

            obj.Search();  //查找
              obj.menu();
            break;
        case 7:  system("cls");             //清空屏幕
              obj.menu(); 
               break;
        case 8: 
            cout<<"\t\t************************************"<<endl;
            cout<<"\t\t***                              ***"<<endl;
            cout<<"\t\t***                              ***"<<endl;
            cout<<"\t\t***    谢谢使用链表!             ***"<<endl;
            cout<<"\t\t***    本次链表使用结束          ***"<<endl;
            cout<<"\t\t***                              ***"<<endl;
            cout<<"\t\t***                              ***"<<endl;
            cout<<"\t\t************************************"<<endl;
            break;
        case 9:   if (!p)    
                     cout<<"链表为空,请先创建链表!"<<endl;
            else
            obj.SortLink();  //插入节点
              obj.menu();
            break;

        case 10:    if (!p)    
                        cout<<"链表为空,请先创建链表!"<<endl;
                else
             obj.LenLink();  //插入节点
            obj.menu();
             break;
        default :
            cout<<"你输入的数字有误请重新再输入!";//输入错误
        }   

    }while(chose!=8); //死循环
    return;
}

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning