单链表的操做

2021年09月15日 阅读数:1
这篇文章主要向大家介绍单链表的操做,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

单链表的操做包括:建立单链表、输出单链表长度 、输出单链表、删除节点、插入节点、单链表排序、单链表逆置。虽然思路都很简单,可是真写程序类运行时就遇到各类错误。node

 

  
  
  1. #include<iostream>  
  2. using namespace std;  
  3.  
  4. struct node  
  5. {  
  6.     int data;  
  7.     node *next;  
  8. };  
  9.  
  10. //创建单链表  
  11. node * creat()  
  12. {  
  13.     node *head;  
  14.     head=(node *)malloc(sizeof(node));  
  15.     node *p=head;//保存下头  
  16.     while(1)  
  17.     {     
  18.         int x;  
  19.         scanf("%d",&x);  
  20.         if(x==0)  
  21.             break;  
  22.         node *s=(node *)malloc(sizeof(node));//增长一个节点  
  23.         s->data=x;  
  24.         p->next=s;  
  25.         p=s;  
  26.           
  27.     }  
  28.     head=head->next;  
  29.     p->next=NULL;//注意结尾赋空  
  30.     return head;  
  31. }  
  32.  
  33. //求单链表长度  
  34. int length(node * head)  
  35. {  
  36.     node *p=head;  
  37.     int len=1;  
  38.     while(p->next!=NULL)  
  39.     {  
  40.         p=p->next;  
  41.         len++;  
  42.     }  
  43.     return len;  
  44. }  
  45.  
  46. //打印单链表  
  47. void print(node *head)  
  48. {  
  49.     node *p=head;  
  50.     while(p!=NULL)  
  51.     {  
  52.         printf("%d  ",p->data);  
  53.         p=p->next;  
  54.  
  55.     }  
  56.     printf("\n");  
  57. }  
  58.  
  59. //删除单链表中的某元素  
  60. node *del(node *head,int num)  
  61. {  
  62.     node *p1,*p2;  
  63.     p1=head;  
  64.     while(p1->next!=NULL)  
  65.     {  
  66.         if(p1->data==num)  
  67.             break;  
  68.         else 
  69.         {  
  70.             p2=p1;  
  71.             p1=p1->next;  
  72.         }  
  73.     }  
  74.     if(p1->data==num)  
  75.     {  
  76.         if(p1==head)  
  77.         {  
  78.             head=p1->next;  
  79.             free(p1);  
  80.         }  
  81.         else 
  82.         {  
  83.             p2->next=p1->next;  
  84.             free(p1);  
  85.         }  
  86.     }  
  87.     else 
  88.         printf("%d cannot find",num);  
  89.     return head;  
  90. }  
  91.  
  92.  
  93. //单链表插入元素   原表升序排列  
  94. node *insert(node *head,int num)  
  95. {  
  96.     node *p1,*p2;  
  97.     p1=head;  
  98.     node *in=(node *)malloc(sizeof(node));  
  99.     in->data=num;  
  100.     while(p1->next!=NULL)  
  101.     {  
  102.         if(p1->data<num)//注意无等号  
  103.         {  
  104.             p2=p1;  
  105.             p1=p1->next;  
  106.         }  
  107.         else   
  108.             break;  
  109.     }  
  110.     if(head==p1)  
  111.     {  
  112.         in->next=p1;  
  113.         head=in;  
  114.     }  
  115.     if(p1->data>=num)//注意有等号  
  116.     {  
  117.         in->next=p2->next;p2->next=in;  
  118.     }  
  119.     else 
  120.     {  
  121.         p1->next=in;  
  122.         in->next=NULL;  
  123.  
  124.     }  
  125.     return head;  
  126. }  
  127.  
  128. //单链表升序排序  
  129. node *sort(node *head)  
  130. {  
  131.     node *p=head;  
  132.     int n=length(head);  
  133.     for(int i=1;i<n;i++)//注意i从1开始  
  134.     {  
  135.         p=head;  
  136.         for(int j=0;j<n-i;j++)  
  137.         {  
  138.             if(p->data>p->next->data)  
  139.             {  
  140.                 int tmp=p->data;  
  141.                 p->data=p->next->data;  
  142.                 p->next->data=tmp;  
  143.             }  
  144.             p=p->next;  
  145.         }  
  146.     }  
  147.     return head;  
  148. }  
  149.  
  150. //单链表逆置  
  151. node *reserve(node *head)  
  152. {  
  153.     node *p1=head;  
  154.     node *p2=head->next;  
  155.     while(p2)  
  156.     {  
  157.         node *p3=p2->next;//p3存下来  
  158.         p2->next=p1;  
  159.         p1=p2;  
  160.         p2=p3;  
  161.     }  
  162.     head->next=NULL;  
  163.     head=p1;  
  164.     return head;  
  165. }  
  166. int main()  
  167. {  
  168.     node *head=creat();  
  169.     print(head);  
  170.     int n=length(head);  
  171.     printf("%d\n",n);  
  172.     del(head,4);  
  173.     print(head);  
  174.     sort(head);  
  175.     print(head);  
  176.     insert(head,5);  
  177.     print(head);  
  178.     node *hed=reserve(head);  
  179.     print(hed);  
  180.     return 1;  
  181.  

 

单链表的操做_休闲