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

zhyin

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

1. #include<iostream>
   
2. using namespace std;
   
3. #define OK 1
   
4. #define ERROR 0
   
5. typedef int Status;
   
6. typedef int ElemType;
   
7. typedef struct LNode
   
8. {
   
9.         ElemType data;                //结点的数据域
   
10.         struct LNode *next;           //结点的指针域
    
11. }LNode,*LinkList;
    
12. 
    
13. Status CreateList_H(LinkList &L,int n)         //前插法创建单链表
    
14. {
    
15.         LNode *p;
    
16.         L=new LNode;
    
17.         L->next=NULL;                        //构造一个带头结点的空链表
    
18.         for(int i=0; i<n; ++i)
    
19.         {
    
20.                 p=new LNode;
    
21.                 cin>>p->data;
    
22.                 p->next=L->next;
    
23.                 L->next=p;
    
24.         }
    
25.         return OK;
    
26. }
    
27. 
    
28. Status CreateList_R(LinkList &L,int n)         //后插法创建单链表
    
29. {
    
30.         LNode *p,*r;
    
31.         L=new LNode;
    
32.         L->next=NULL;                        //构造一个带头结点的空链表
    
33.         r=L;
    
34.         for(int i=0; i<n; ++i)
    
35.         {
    
36.                 p=new LNode;
    
37.                 cin>>p->data;
    
38.                 p->next=NULL;
    
39.                 r->next=p;
    
40.                 r=p;
    
41.         }
    
42.         return OK;
    
43. }
    
44. 
    
45. LNode *LocatElem(LinkList L,ElemType e)       //在单链表中查找值为e的元素
    
46. {
    
47.         LNode *p;
    
48.         p=L->next;
    
49.         while(p && p->data!=e)
    
50.                 p=p->next;
    
51.         return p;
    
52. }
    
53. 
    
54. Status ListInsert(LinkList &L,int i,ElemType e)       //在单链表中第i个位置插入值为e的新结点
    
55. {
    
56.         LNode *s,*p=L;
    
57.         int j=0;
    
58.         while(p && (j<i-1))
    
59.         {
    
60.                 p=p->next;
    
61.                 ++j;
    
62.         }
    
63.         if(!p || (j>i-1))
    
64.                 return ERROR;
    
65.         s=new LNode;
    
66.         s->next=p->next;
    
67.         p->next=s;
    
68.         return OK;
    
69. }
    
70. 
    
71. Status ListDelete(LinkList &L,int i)        //在单链表中删除第i个元素
    
72. {
    
73.         LNode *p=L;
    
74.         int j=0;
    
75.         while(p->next && (j<i-1))
    
76.         {
    
77.                 p=p->next;
    
78.                 j++;
    
79.         }
    
80.         if(!(p->next) || (j>i-1))
    
81.                 return ERROR;
    
82.         LNode *q=p->next;
    
83.         p->next=q->next;
    
84.         delete q;
    
85.         return OK;
    
86. }
    
87. 
    
88. void TraveseList(LinkList L)         //输出单链表的各个结点
    
89. {
    
90.         LNode *p=L;
    
91.         if(p==NULL)
    
92.         return;
    
93.         else
    
94.         {
    
95.                 cout<<p->data<<" ";
    
96.                 TraveseList(p->next);
    
97.         }
    
98. }
    
99. int main()
    
100. {
     
101.         LNode *L,*p;
     
102.         char ch;
     
103.         int choose=-1, i, e, n;
     
104.         cout<<"1.创建单链表\n2.查找\n3.插入\n4.删除\n5.输出\n0.退出"<<endl;
     
105.         while(choose!=0)
     
106.         {
     
107.                 cout<<"请选择：";
     
108.                 cin>>choose;
     
109.                 switch(choose)
     
110.                 {
     
111.                 case 1:
     
112.                         {
     
113.                                 cout<<"请输入要输入的数据个数: ";
     
114.                                 cin>>n;
     
115.                 cout<<"请选择:\na.前插法创建单链表\nb.后插法创建单链表"<<endl;
     
116.                                 cin>>ch;
     
117.                                 cout<<"请输入数据: ";
     
118.                                 if(ch=='a')
     
119.                                 {
     
120.                                         if(CreateList_H(L,n))
     
121.                                                 cout<<"创建单链表成功!"<<endl;
     
122.                                         else
     
123.                                                 cout<<"创建单链表失败!"<<endl;
     
124.                                 }
     
125.                                 if(ch=='b')
     
126.                                 {
     
127.                                         if(CreateList_R(L,n))
     
128.                                                 cout<<"创建单链表成功!"<<endl;
     
129.                                         else
     
130.                                                 cout<<"创建单链表失败!"<<endl;
     
131.                                 }break;
     
132.                         }
     
133.                 case 2:
     
134.                         {
     
135.                                 cout<<"请输入要查找的值: "<<endl;
     
136.                                 cin>>e;
     
137.                                 if(p=LocatElem(L,e))
     
138.                                         cout<<e<<"的地址是"<<p<<endl;
     
139.                                 else
     
140.                                         cout<<"查找失败!"<<endl;
     
141.                         }break;
     
142.                 case 3:
     
143.                         {
     
144.                                 cout<<"请分别输入要插入的值及位置: "<<endl;
     
145.                                 cin>>e>>i;
     
146.                                 if(ListInsert(L,i,e))
     
147.                                 {                       
     
148.                                         cout<<"插入成功!"<<endl;
     
149.                                         ++n;
     
150.                                 }
     
151.                                 else
     
152.                                         cout<<"插入失败!"<<endl;
     
153.                         }break;
     
154.                 case 4:
     
155.                         {
     
156.                                 cout<<"请输入要删除的元素位置: "<<endl;
     
157.                                 cin>>i;
     
158.                                 if(ListDelete(L,i))
     
159.                                 {       
     
160.                                         cout<<"已删除!"<<endl;
     
161.                                         --n;
     
162.                                 }
     
163.                                 else
     
164.                                         cout<<"删除失败!"<<endl;
     
165.                         }break;
     
166.                 case 5:
     
167.                         {
     
168.                                 TraveseList(L);
     
169.                                 cout<<endl;
     
170.                         }break;
     
171.                 }
     
172.         }
     
173.         return 0;
     
174. }

复制代码

人造人

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

#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;
}

人造人

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

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 00:18
这类问题，自己调试一下就发现问题了吧

#include

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

人造人

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

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

流月飞星