单链表几个基本操作的实现,数据结构与算法,技术交流,鱼C论坛

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

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

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

#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

{:10_266:}

页: [1]

鱼C论坛's Archiver

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