1 #include
     
        2 #include
      
         3   4 typedef struct node  5 {  6     int data;  7     struct node *next;  8 }Node,*pNode;  9  10 pNode Creat_list();//创建一个单链表 11 void Traverse_list(pNode head);//遍历链表 12 int Len_list(pNode head);//求链表长度 13 bool Delete_list(pNode head,int n,int &a);//删除链表的第n个节点，并将所删除节点的值传入a中 14 bool Insert_list(pNode head,int n,int a);//在链表的第n个节点前插入一个新的节点，且新节点的值为n 15 bool Reverse_list(pNode head);//反转单链表 16  17  18 using namespace std; 19  20 int main() 21 { 22     int delval; 23     int length=0; 24     pNode listhead=Creat_list(); 25     cout<<"链表元素为："; 26     Traverse_list(listhead); 27  28     cout<
       
        next=NULL; 65     cout<<"Please input the number of list element:"; 66     cin>>n; 67     cout<
        
         >a; 84  85             pNode newnode=(pNode)malloc(sizeof(Node)); 86             if(newnode==NULL) 87             { 88                 cout<<"创建新节点失败"<
         
          next=newnode;//现在的midnode指向的是newnode的上一个节点 95                 newnode->data=a; 96                 newnode->next=NULL; 97                 midnode=newnode;//现在的midnode指向最新的节点 98             } 99         }100         101         return head;102     }103 }104 105 106 107 //遍历链表108 void Traverse_list(pNode head)109 {110     if(head->next == NULL)111     {112         cout<<"链表为空"<
          
           next != NULL)122 {123 midnode=midnode->next;124 cout<
           
            data<<" ";125 }126 cout<
            
             next==NULL)139 {140 return 0;141 }142 143 else144 {145 pNode midnode=(pNode)malloc(sizeof(Node));146 147 if(midnode==NULL)148 {149 cout<<"分配中间节点内存失败！";150 return 0;151 }152 153 midnode=head;154 while(midnode->next != NULL)155 {156 midnode=midnode->next;157 len++;158 }159 return len;160 }161 }162 163 164 165 //删除链表中的第n个节点(头结点视为链表的第0个节点)，并返回所删除元素的值到a中166 bool Delete_list(pNode head,int n,int &a)167 {168 int length=Len_list(head);//链表的长度169 170 if(n<=0 || n>length)171 {172 cout<<"被删除元素的序数非法！"<
             
              next;180 a=midnode->data;181 head->next=midnode->next;182 free(midnode);183 184 return true;185 }186 187 188 else189 {190 int i=0;191 192 pNode midnode1=(pNode)malloc(sizeof(Node));193 midnode1=head;194 195 while(i
              
               next;198 i++;199 }//出while循环时，midnode指向的是第n-1个节点200 201 pNode midnode2=(pNode)malloc(sizeof(Node));202 midnode2=midnode1->next;//midnode2是被删除的节点203 a=midnode2->data;204 midnode1->next=midnode2->next;205 free(midnode2);206 207 return true;208 }209 }210 211 212 //在链表中第n个节点前插入一个值为a的新节点213 bool Insert_list(pNode head,int n,int a)214 {215 int len=Len_list(head);216 217 if(n<=0 || n>len)218 {219 cout<<"插入元素的位置非法！";220 return false;221 }222 223 else if(n==1)224 {225 pNode midnode=(pNode)malloc(sizeof(Node));226 if(midnode==NULL)227 {228 cout<<"分配中间节点内存失败！";229 return false;230 }231 232 midnode->data=a;233 midnode->next=head->next;234 head->next=midnode;235 236 return true;237 }238 239 else240 {241 int i=0;242 243 pNode midnode1=(pNode)malloc(sizeof(Node));244 if(midnode1==NULL)245 {246 cout<<"分配中间节点内存失败！";247 return false;248 }249 250 midnode1=head;251 while(i
               
                next;254 i++;255 }//出while循环时midnode1指向的是第n-1个节点256 257 258 pNode midnode2=(pNode)malloc(sizeof(Node));259 if(midnode2==NULL)260 {261 cout<<"分配新节点内存失败！";262 return false;263 }264 265 midnode2->data=a;266 midnode2->next=midnode1->next;267 midnode1->next=midnode2;268 269 return true;270 }271 }272 273 274 //反转单链表275 bool Reverse_list(pNode head)276 {277 int len=Len_list(head);278 279 if(len==0 || len==1)280 {281 cout<<"链表元素过少，不能反转！";282 return false;283 }284 285 else286 {287 pNode midnode1=(pNode)malloc(sizeof(Node));288 pNode midnode2=(pNode)malloc(sizeof(Node));289 if(midnode1==NULL || midnode2==NULL)290 {291 cout<<"分配中间节点内存失败！";292 return false;293 }294 295 midnode1=head->next;296 midnode2=midnode1->next;297 midnode1->next=NULL;298 299 while(midnode2->next != NULL)300 {301 pNode X=midnode2->next;302 midnode2->next=midnode1;303 midnode1=midnode2;304 midnode2=X;305 }306 midnode2->next=midnode1;307 head->next=midnode2;308 309 return true;310 }311 }