单链表几个基本操作的实现

zhyin · 发表于 2016-10-15 22:48:59

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

输出的时候前面多出那些数字怎么回事？？而且插入数据之后再输出，所插入的数值也有错误。。求解

#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
        ElemType data;                //结点的数据域
        struct LNode *next;           //结点的指针域
}LNode,*LinkList;

Status CreateList_H(LinkList &L,int n)         //前插法创建单链表
{
        LNode *p;
        L=new LNode;
        L->next=NULL;                        //构造一个带头结点的空链表
        for(int i=0; i<n; ++i)
        {
                p=new LNode;
                cin>>p->data;
                p->next=L->next;
                L->next=p;
        }
        return OK;
}

Status CreateList_R(LinkList &L,int n)         //后插法创建单链表
{
        LNode *p,*r;
        L=new LNode;
        L->next=NULL;                        //构造一个带头结点的空链表
        r=L;
        for(int i=0; i<n; ++i)
        {
                p=new LNode;
                cin>>p->data;
                p->next=NULL;
                r->next=p;
                r=p;
        }
        return OK;
}

LNode *LocatElem(LinkList L,ElemType e)       //在单链表中查找值为e的元素
{
        LNode *p;
        p=L->next;
        while(p && p->data!=e)
                p=p->next;
        return p;
}

Status ListInsert(LinkList &L,int i,ElemType e)       //在单链表中第i个位置插入值为e的新结点
{
        LNode *s,*p=L;
        int j=0;
        while(p && (j<i-1))
        {
                p=p->next;
                ++j;
        }
        if(!p || (j>i-1))
                return ERROR;
        s=new LNode;
        s->next=p->next;
        p->next=s;
        return OK;
}

Status ListDelete(LinkList &L,int i)        //在单链表中删除第i个元素
{
        LNode *p=L;
        int j=0;
        while(p->next && (j<i-1))
        {
                p=p->next;
                j++;
        }
        if(!(p->next) || (j>i-1))
                return ERROR;
        LNode *q=p->next;
        p->next=q->next;
        delete q;
        return OK;
}

void TraveseList(LinkList L)         //输出单链表的各个结点 
{
        LNode *p=L; 
        if(p==NULL)
        return;
        else
        {
                cout<<p->data<<" ";
                TraveseList(p->next);
        }
 } 
int main()
{
        LNode *L,*p;
        char ch;
        int choose=-1, i, e, n;
        cout<<"1.创建单链表\n2.查找\n3.插入\n4.删除\n5.输出\n0.退出"<<endl;
        while(choose!=0)
        {
                cout<<"请选择：";
                cin>>choose;
                switch(choose)
                {
                case 1:
                        {
                                cout<<"请输入要输入的数据个数: ";
                                cin>>n;
                cout<<"请选择:\na.前插法创建单链表\nb.后插法创建单链表"<<endl;
                                cin>>ch;
                                cout<<"请输入数据: ";
                                if(ch=='a')
                                {
                                        if(CreateList_H(L,n))
                                                cout<<"创建单链表成功!"<<endl;
                                        else
                                                cout<<"创建单链表失败!"<<endl;
                                }
                                if(ch=='b')
                                {
                                        if(CreateList_R(L,n))
                                                cout<<"创建单链表成功!"<<endl;
                                        else
                                                cout<<"创建单链表失败!"<<endl;
                                }break;
                        }
                case 2:
                        {
                                cout<<"请输入要查找的值: "<<endl;
                                cin>>e;
                                if(p=LocatElem(L,e))
                                        cout<<e<<"的地址是"<<p<<endl;
                                else
                                        cout<<"查找失败!"<<endl;
                        }break;
                case 3:
                        {
                                cout<<"请分别输入要插入的值及位置: "<<endl;
                                cin>>e>>i;
                                if(ListInsert(L,i,e))
                                {                        
                                        cout<<"插入成功!"<<endl;
                                        ++n;
                                }
                                else
                                        cout<<"插入失败!"<<endl;
                        }break;
                case 4:
                        {
                                cout<<"请输入要删除的元素位置: "<<endl;
                                cin>>i;
                                if(ListDelete(L,i))
                                {        
                                        cout<<"已删除!"<<endl;
                                        --n;
                                }
                                else
                                        cout<<"删除失败!"<<endl;
                        }break;
                case 5:
                        {
                                TraveseList(L); 
                                cout<<endl;
                        }break;
                }
        }
        return 0;
}

人造人 · 发表于 2016-10-16 00:18:56

这类问题，自己调试一下就发现问题了吧

#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
      ElemType data;             //结点的数据域
      struct LNode *next;          //结点的指针域
}LNode,*LinkList;

Status CreateList_H(LinkList &L,int n)       //前插法创建单链表
{
      LNode *p;
      L=new LNode;
      L->next=NULL;                      //构造一个带头结点的空链表
      for(int i=0; i<n; ++i)
      {
            p=new LNode;
            cin>>p->data;
            p->next=L->next;
            L->next=p;
      }
      return OK;
}

Status CreateList_R(LinkList &L,int n)       //后插法创建单链表
{
      LNode *p,*r;
      L=new LNode;
      L->next=NULL;                      //构造一个带头结点的空链表
      r=L;
      for(int i=0; i<n; ++i)
      {
            p=new LNode;
            cin>>p->data;
            p->next=NULL;
            r->next=p;
            r=p;
      }
      return OK;
}

LNode *LocatElem(LinkList L,ElemType e)    //在单链表中查找值为e的元素
{
      LNode *p;
      p=L->next;
      while(p && p->data!=e)
            p=p->next;
      return p;
}

Status ListInsert(LinkList &L,int i,ElemType e)    //在单链表中第i个位置插入值为e的新结点
{
      LNode *s,*p=L;
      int j=0;
      while(p && (j<i-1))
      {
            p=p->next;
            ++j;
      }
      if(!p || (j>i-1))
            return ERROR;
      s=new LNode;
      s->next=p->next;
      p->next=s;
      return OK;
}

Status ListDelete(LinkList &L,int i)       //在单链表中删除第i个元素
{
      LNode *p=L;
      int j=0;
      while(p->next && (j<i-1))
      {
            p=p->next;
            j++;
      }
      if(!(p->next) || (j>i-1))
            return ERROR;
      LNode *q=p->next;
      p->next=q->next;
      delete q;
      return OK;
}

void TraveseList(LinkList L)       //输出单链表的各个结点
{
      LNode *p=L;
      if(p==NULL)
      return;
      else
      {
            cout<<p->data<<" ";
            TraveseList(p->next);
      }
}
int main()
{
      LNode *L,*p;
      char ch;
      int choose=-1, i, e, n;
      cout<<"1.创建单链表\n2.查找\n3.插入\n4.删除\n5.输出\n0.退出"<<endl;
      while(choose!=0)
      {
            cout<<"请选择：";
            cin>>choose;
            switch(choose)
            {
            case 1:
                     {
                              cout<<"请输入要输入的数据个数: ";
                              cin>>n;
            cout<<"请选择:\na.前插法创建单链表\nb.后插法创建单链表"<<endl;
                              cin>>ch;
                              cout<<"请输入数据: ";
                              if(ch=='a')
                              {
                                    if(CreateList_H(L,n))
                                             cout<<"创建单链表成功!"<<endl;
                                    else
                                             cout<<"创建单链表失败!"<<endl;
                              }
                              if(ch=='b')
                              {
                                    if(CreateList_R(L,n))
                                             cout<<"创建单链表成功!"<<endl;
                                    else
                                             cout<<"创建单链表失败!"<<endl;
                              }break;
                     }
            case 2:
                     {
                              cout<<"请输入要查找的值: "<<endl;
                              cin>>e;
                              if(p=LocatElem(L,e))
                                    cout<<e<<"的地址是"<<p<<endl;
                              else
                                    cout<<"查找失败!"<<endl;
                     }break;
            case 3:
                     {
                              cout<<"请分别输入要插入的值及位置: "<<endl;
                              cin>>e>>i;
                              if(ListInsert(L,i,e))
                              {
                                    cout<<"插入成功!"<<endl;
                                    ++n;
                              }
                              else
                                    cout<<"插入失败!"<<endl;
                     }break;
            case 4:
                     {
                              cout<<"请输入要删除的元素位置: "<<endl;
                              cin>>i;
                              if(ListDelete(L,i))
                              {
                                    cout<<"已删除!"<<endl;
                                    --n;
                              }
                              else
                                    cout<<"删除失败!"<<endl;
                     }break;
            case 5:
                     {
                        //    TraveseList(L);
                              TraveseList(L->next);
                              cout<<endl;
                     }break;
            }
      }
      return 0;
}

人造人 · 发表于 2016-10-16 00:20:22

不要忘记你创建的是带头结点的空链表

Status CreateList_R(LinkList &L,int n)       //后插法创建单链表
{
      LNode *p,*r;
      L=new LNode;
      L->next=NULL;                       //构造一个带头结点的空链表
      r=L;
      for(int i=0; i<n; ++i)
      {
            p=new LNode;
            cin>>p->data;
            p->next=NULL;
            r->next=p;
            r=p;
      }
      return OK;
}

zhyin · 发表于 2016-10-16 18:29:18

人造人发表于 2016-10-16 00:18
这类问题，自己调试一下就发现问题了吧

#include

嗯，我知道是这个问题，但是想不到是在TraveseList(L->next)这里改，一开始老在TraveseList函数那里的p后面加->next ...

人造人 · 发表于 2016-10-16 18:44:10

zhyin 发表于 2016-10-16 18:29
嗯，我知道是这个问题，但是想不到是在TraveseList(L->next)这里改，一开始老在TraveseList函数那里的p后 ...

其实这样改也不好，
最好是修改TraveseList的内部
那么，这样
TraveseList(L);
就可以了，不用每次都加L->next

流月飞星 · 发表于 2016-11-17 22:53:26

账号		自动登录	找回密码
密码			立即注册