⑴随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

⑵遍历单向链表。

⑶把单向链表中元素逆置（不允许申请新的结点空间）。

⑷在单向链表中删除所有的偶数元素结点。

⑸编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。

⑹利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。

⑺利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。

⑻利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）

⑽在主函数中设计一个简单的菜单，分别调试上述算法。

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 typedef struct Lnode{  8         int data;  9         struct Lnode * next; 10         }Lnode,*Linklist; 11         12         13         14 Lnode * input()//输入； 15 { 16      cout<<"请输入整型数据，以^Z结束输入\n"; 17      18      Linklist p1,p2,headlist; 19      int str; 20      headlist=(Lnode *)malloc(sizeof(Lnode)); 21      p1=p2=headlist; 22      if(p1==NULL) 23      {cout<<"存储空间申请失败，结束输入：\n";return NULL;} 24      25      headlist->next=NULL; 26      while(scanf("%d",&str)!=EOF) 27      { 28       29       30              31              32              33              p1=(Lnode *)malloc(sizeof(Lnode)); 34              35              p1->data=str; 36              p2->next=p1; 37              p2=p1; 38              p2->next=NULL; 39       } 40              41              return headlist; 42 } 43              44 bool output(Linklist headlist)//输出； 45 { 46               Linklist p1; 47               p1=headlist->next; 48               if(!p1) 49               return 0; 50               while(p1!=NULL) 51               { 52                             cout<
         
          data<<' '; 53                              p1=p1->next; 54               } 55               cout<
          
           next; 64 65 while(p->next!=NULL) 66 { 67 count++; 68 p=p->next; 69 } 70 return count; 71 } 72 73 bool fz(Linklist headlist,int n)//对链表元素进行反转； 74 { 75 int i,j,k,t; 76 Linklist p1,p2; 77 k=n/2; 78 p1=p2=headlist; 79 if(headlist->next==NULL) 80 return false; 81 for(i=1;i<=k;i++) 82 {p2=p2->next; 83 84 85 p1=p2; 86 for(j=i+1;j<=n-i+1;j++) 87 {p1=p1->next;} 88 t=p2->data;p2->data=p1->data;p1->data=t; 89 } 90 return true; 91 } 92 93 94 95 int delete_even(Linklist headlist)//删除偶数； 96 { 97 98 Linklist p1,p2; 99 if(headlist->next==NULL)100 {cout<<"链表是空表\n";return 0;}101 p1=headlist->next;102 p2=headlist;103 while(p1)104 {105 if(p1->data%2==0)106 {p2->next=p1->next;107 free(p1);108 p1=p2->next;109 }110 else111 {112 p1=p1->next;113 p2=p2->next;114 }115 }116 117 118 return 1;119 }120 121 122 Linklist divide(Linklist headlist)//将链表分割为两个；返回偶数链表的头地址；123 {124 Linklist p1,p2,p3;125 int t;126 if(headlist->next==NULL)127 {cout<<"链表为空表\n";return NULL;}128 int i,j,k;129 for(p1=headlist->next;p1->next!=NULL;p1=p1->next)130 {131 p3=p1;132 if(p3->data%2==1)133 continue;134 for(p2=p1->next;p2!=NULL;p2=p2->next)135 {136 if(p2->data%2==1)137 p3=p2;138 }139 if(p1!=p3)140 {141 t=p1->data;p1->data=p3->data;p3->data=t;142 }143 }144 145 for(p1=headlist->next,p2=headlist;p1!=NULL;p1=p1->next,p2=p2->next)146 {147 if(p1->data%2==0)148 break;149 }150 151 if((p1!=NULL)&&(p1!=headlist->next))152 {p3=(Linklist)malloc(sizeof(Lnode));153 p3->next=p1;154 p2->next=NULL;155 return p3;156 }157 else if(p1==headlist->next)158 {cout<<"链表元素全为偶数\n";return headlist;}159 else160 {cout<<"链表元素全为奇数\n";return NULL;}161 162 163 164 }165 166 int delete_list(Linklist headlist)//将链表清空；167 { if(headlist==NULL)168 return 0;169 Linklist p1,p2;170 p1=headlist;p2=p1->next;171 while(p2)172 {173 174 free(p1);175 p1=p2;176 p2=p2->next;177 }178 free(p1);179 return 1;180 }181 182 183 int insert(Linklist headlist,int e)//非递减插入元素；184 {Linklist p2,p1,p3;185 p2=headlist;186 p1=p2->next;187 while(p1)188 { if(p1->data>e)189 break;190 p2=p2->next;191 p1=p1->next;192 }193 194 195 p3=(Linklist)malloc(sizeof(Lnode));196 if(p3==NULL)197 {cout<<"空间申请失败\n";return 0;}198 p3->data=e;199 p3->next=p1;200 p2->next=p3;201 return 1;202 }203 204 205 int length_list(Linklist headlist)//求链表长度；206 {207 Linklist p;208 int count=1;209 p=headlist->next;210 211 while(p->next!=NULL)212 {213 count++;214 p=p->next;215 }216 return count;217 }218 219 bool sort(Linklist headlist,int n)//排序；220 {221 int i,j,k;222 int t,s;223 Linklist p1,p2;224 p1=p2=headlist->next;225 k=n-1;226 for(i=k;i>=1;i--)227 {p1=p2=headlist->next;228 p1=p2->next;229 for(j=1;j<=i;j++)230 {231 if(p2->data
           
            data)232 {t=p2->data;p2->data=p1->data;p1->data=t;}233 p1=p1->next;234 p2=p2->next;235 }236 }237 return true;238 }239 240 241 242 Linklist union1_list(Linklist head1,Linklist head2)//将两个链表合并为一个,合并后仍为非递减；243 {244 Linklist p;245 p=head2->next;246 while(p)247 {248 insert(head1,p->data);249 p=p->next;250 }251 delete_list(head2);252 return head1;253 }254 255 256 257 int main(int argc, char *argv[])258 {Linklist headlist;259 headlist=input();260 cout<<"输出输入的元素\n";261 262 output(headlist);263 264 fz(headlist,length(headlist));265 cout<<"逆置后的元素为\n";266 267 output(headlist);268 delete_even(headlist);269 cout<<"删除偶数后的链表序列为：\n";270 output(headlist);271 cout<<"将链表分割为奇数和偶数的两部分\n";272 Linklist p=divide(headlist);273 if(p==NULL)274 {cout<<"偶数链表为空表\n";275 cout<<"奇数链表为：\n";276 output(headlist);277 delete_list(headlist);278 }279 else if(p==headlist)280 {cout<<"奇数链表为空表\n";281 cout<<"偶数链表为\n";282 output(headlist);283 delete_list(headlist);284 }285 else286 { cout<<"偶数链表的元素为\n";287 output(p);288 delete_list(p);289 cout<<"奇数链表的元素为\n";290 output(headlist);291 delete_list(headlist);292 }293 294 cout<<"非递减整数序列：\n";295 headlist=input();296 cout<<"输入的元素为\n";297 output(headlist);298 cout<<"请输入要插入的元素\n";299 int e;300 cin>>e;301 insert(headlist,e);302 cout<<"插入后的链表为\n";303 output(headlist);304 delete_list(headlist);305 Linklist head1,head2,head3;306 cout<<"非递减整数序列1：\n";307 head1=input();308 cout<<"输入的表1为\n";309 output(head1);310 cout<<"非递减整数序列2：\n";311 head2=input();312 cout<<"输入的表2为\n";313 output(head2);314 315 316 317 head3=union1_list(head1,head2);318 cout<<"合并后的非递减链表为\n";319 output(head3);320 sort(head3,length_list(head3));321 cout<<"合并后的非递增链表为\n";322 323 output(head3);324 delete_list(head3);325 326 327 328 329 system("PAUSE");330 return EXIT_SUCCESS;331 }