单链表常用运算问题（基于VC）

风花雪月

针对单链表的常用运算：创建、查找、删除、插入、浏览、求链表的长度。两个version主要是针对查找、删除中存在的两种情况，即满足条件的所有结点的运算和程序控制语句中满足条件的第一个结点的运算。
（一） 满足所有条件的所有结点的运算

1. #include "iostream.h"
   
2. typedef struct node
   
3. { int data;
   
4. struct node *next;
   
5. }List;
   
6. List *Create();                      //创建链表
   
7. int Len(List *h);                    //链表的长度
   
8. void Locate(List *h,int x);            //查找所有数据域为x的结点
   
9. void Insert(List *h,int n,int x);         //在第n位插入结点x
   
10. void Del(List *h,int x);               //删除所有数据域为x的结点
    
11. void Browse(List *h);                //浏览链表
    
12. 
    
13. void main()
    
14. {   List *head;
    
15.   int Length,z,n;
    
16.   head=Create();
    
17.   Length=Len(head);
    
18.   cout<<"链表的长度为："<<Length<<"\n";
    
19.   cout<<"请输入您要插入的位置：";
    
20.   cin>>n;
    
21.   cout<<"请输入您要插入的数：";
    
22.   cin>>z;
    
23.   Insert(head,n,z);
    
24.   Browse(head);
    
25.   cout<<"请输入您要查找的数：";
    
26.   cin>>z;
    
27.   Locate(head,z);
    
28.   Browse(head);
    
29.   cout<<"请输入您要删除的数：";
    
30.   cin>>z;
    
31.   Del(head,z);
    
32.   Browse(head);
    
33. }
    
34. 
    
35. List *Create()
    
36. { List *h,*s,*r;
    
37. int x,tag;
    
38. cout<<"请输入结束标志：";
    
39. cin>>tag;
    
40.     h=new List;
    
41. h->data=NULL;
    
42. r=h;
    
43. cout<<"请输入数据：";
    
44. cin>>x;
    
45. while(x!=tag)
    
46. {
    
47.   s=new List;
    
48.   s->data=x;
    
49.         r->next=s;
    
50.   r=s;
    
51.   cout<<"请输入数据：";
    
52.   cin>>x;
    
53. }
    
54. r->next=NULL;
    
55. return h;
    
56. }
    
57. 
    
58. int Len(List *h)
    
59. { List *s;
    
60. int l=0;
    
61.     s=h;
    
62. while(s->next!=NULL)
    
63. {
    
64.   s=s->next;
    
65.   l++;
    
66. }
    
67. return l;
    
68. }
    
69. 
    
70. void Locate(List *h,int x)             //查找所有结点x,并找出它们所在的位置
    
71. {    List *p;
    
72.    int n=-1,flag=0;                  //由于"p=h"，故"n=-1"
    
73.    p=h;                                                              
    
74.    for(;p!=NULL;p=p->next)   
    
75.    {
    
76.     n++;
    
77.     if(p->data==x)
    
78.     {
    
79.      cout<<"在第"<<n<<"个位置有结点"<<x<<"\n";
    
80.            flag=1;                       //说明链表中有结点x
    
81.     }
    
82.    }
    
83.    if(flag==0)
    
84.     cout<<"链表中不存在结点"<<x<<"\n";
    
85. }
    
86. 
    
87. void Insert(List *h,int n,int x)
    
88. { List *s,*p;
    
89. int m=0;
    
90. s=new List;
    
91. if(s==NULL)                     //如果没有空间分配给p，说明链表已满
    
92.   cout<<"链表已满。\n";
    
93. else
    
94. {   
    
95.   p=h;
    
96.   while(p->next!=NULL&&m!=n)
    
97.   {
    
98.    p=p->next;
    
99.    m++;
    
100.   }
     
101.   if(p->next==NULL)
     
102.    cout<<"插入不合法！\n";
     
103.   else
     
104.   {
     
105.    s->data=x;
     
106.    s->next=p->next;
     
107.    p->next=s;
     
108.   }
     
109.     }
     
110. }
     
111. 
     
112. void Del(List *h,int x)                  //删除所有结点x
     
113. {   List *q;
     
114.   int flag=0;
     
115.   while(h->next)
     
116.   {
     
117.    if(h->next->data==x)
     
118.    {
     
119.     flag=1;                    //说明链表中有结点x
     
120.     q=h->next;
     
121.     h->next=q->next;
     
122.     delete q;
     
123.    }
     
124.    else
     
125.     h=h->next;
     
126.   }
     
127.   if(flag==0)
     
128.          cout<<"链表中不存在结点"<<x<<"\n";
     
129. }
     
130. 
     
131. void Browse(List *h)
     
132. { List *q;
     
133. q=h->next;
     
134. while(q!=NULL)
     
135. {
     
136.         cout<<"数据域为："<<q->data<<"\n";
     
137.   q=q->next;
     
138. }
     
139. }

复制代码

（二）程序控制语句中满足条件的第一个结点的运算。

1. #include "iostream.h"
   
2. typedef struct node
   
3. { int data;
   
4. struct node *next;
   
5. }List;
   
6. List *Create();                           //创建链表
   
7. int Len(List *h);                         /链表的长度
   
8. void Locate(List *h,int x);                 //查找数据域为x的结点
   
9. void Insert(List *h,int n,int x);              //在第n位插入结点x
   
10. void Del(List *h,int x);                    //删除数据域为x的结点
    
11. void Browse(List *h);                     //浏览链表
    
12. 
    
13. void main()
    
14. {   List *head;
    
15.   int Length,z,n;
    
16.   head=Create();
    
17.   Length=Len(head);
    
18.   cout<<"链表的长度为："<<Length<<"\n";
    
19.   cout<<"请输入您要插入的位置：";
    
20.   cin>>n;
    
21.   cout<<"请输入您要插入的数：";
    
22.   cin>>z;
    
23.   Insert(head,n,z);
    
24.   Browse(head);
    
25.   cout<<"请输入您要查找的数：";
    
26.   cin>>z;
    
27.   Locate(head,z);
    
28.   Browse(head);
    
29.   cout<<"请输入您要删除的数：";
    
30.   cin>>z;
    
31.   Del(head,z);
    
32.   Browse(head);
    
33. }
    
34. 
    
35. List *Create()
    
36. { List *h,*s,*r;
    
37. int x,tag;
    
38. cout<<"请输入结束标志：";
    
39. cin>>tag;
    
40.     h=new List;
    
41. h->data=NULL;
    
42. r=h;
    
43. cout<<"请输入数据：";
    
44. cin>>x;
    
45. while(x!=tag)
    
46. {
    
47.   s=new List;
    
48.   s->data=x;
    
49.         r->next=s;
    
50.   r=s;
    
51.   cout<<"请输入数据：";
    
52.   cin>>x;
    
53. }
    
54. r->next=NULL;
    
55. return h;
    
56. }
    
57. 
    
58. int Len(List *h)
    
59. { List *s;
    
60. int l=0;
    
61.     s=h;
    
62. while(s->next!=NULL)
    
63. {
    
64.   s=s->next;
    
65.   l++;
    
66. }
    
67. return l;
    
68. }
    
69. 
    
70. void Locate(List *h,int x)         
    
71. {    List *p;
    
72.    int n=-1,flag=0;                            //由于"p=h"，故"n=-1"
    
73.    p=h;                                                              
    
74.    for(;p!=NULL;p=p->next)  
    
75.    {
    
76.     n++;
    
77.        if(p->data==x)
    
78.        {
    
79.      cout<<"在第"<<n<<"个位置有结点"<<x<<"\n";
    
80.      flag=1;
    
81.     }
    
82.    }
    
83.    if(flag==0)
    
84.     cout<<"链表中没有结点"<<x<<"\n";
    
85. }
    
86. 
    
87. void Insert(List *h,int n,int x)
    
88. { List *s,*p;
    
89. int m=0;
    
90. s=new List;
    
91. if(s==NULL)                            //如果没有空间分配给p，说明链表已满
    
92.   cout<<"链表已满。\n";
    
93. else
    
94. {   
    
95.   p=h;
    
96.   while(p->next!=NULL&&m!=n)
    
97.   {
    
98.    p=p->next;
    
99.    m++;
    
100.   }
     
101.   if(p->next==NULL)
     
102.    cout<<"插入不合法！\n";
     
103.   else
     
104.   {
     
105.    s->data=x;
     
106.    s->next=p->next;
     
107.    p->next=s;
     
108.   }
     
109.     }
     
110. }
     
111. 
     
112. void Del(List *h,int x)               
     
113. {     List *p,*q;
     
114. int flag=0;
     
115. q=h;                                 
     
116. while(q->next!=NULL&&q->data!=x)      
     
117. {   
     
118.   p=q;
     
119.      q=q->next;
     
120. }
     
121. if(x==q->data)
     
122. {
     
123.   p->next=q->next;
     
124.      delete q;
     
125.   cout<<"删除完成！\n";
     
126. }
     
127. else
     
128.   cout<<"链表中没有结点"<<x<<"\n";
     
129. }
     
130. 
     
131. void Browse(List *h)
     
132. { List *q;
     
133. q=h->next;
     
134. while(q!=NULL)
     
135. {
     
136.         cout<<"数据域为："<<q->data<<"\n";
     
137.   q=q->next;
     
138. }
     
139. }

复制代码