devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

单链表的创建及插入，删除，查找数据

作者：我家小花儿 | 2024-07-28 08:01:50

赞

踩

单链表的创建及插入，删除，查找数据

创建链表，插入数据，查找数据，删除数据（算法笔记）

  1.  
  2. #include <iostream>
  3. #include <cstdio>
  4. using namespace std;
  5. const int N=10;
  6. struct node
  7. {
  8.     int data;
  9.     node* next;
  10. };
  11. node* create(int array[]);
  12. int search(node* head,int x);
  13. void insert(node* head,int pos,int x);
  14. void del(node* head,int x);
  15. int main()
  16. {
  17.     int array[N]={1,2,3,4,5,5,6,5,3,9};
  18.     node* l=create(array);
  19.     node* s=create(array);
  20.     node* i=create(array);
  21.     node* d=create(array);
  22.     l=l->next;
  23.     printf("建立链表:\n");
  24.     while(l!=NULL)
  25.     {
  26.         printf("%d ",l->data);
  27.         l=l->next;
  28.     }
  29.     printf("\n查找:\n");
  30.     int ans=search(s,5);
  31.     printf("%d",ans);
  32.     printf("\n插入:\n");
  33.     insert(i,3,9);
  34.     i=i->next;
  35.     while(i!=NULL)
  36.     {
  37.         printf("%d ",i->data);
  38.         i=i->next;
  39.     }
  40.     printf("\n删除\n");
  41.     del(d,3);
  42.     d=d->next;
  43.     while(d!=NULL)
  44.     {
  45.         printf("%d ",d->data);
  46.         d=d->next;
  47.     }
  48.  
  49.     cout << "\nHello world!" << endl;
  50.     return 0;
  51. }
  52. node* create(int array[])
  53. {
  54.     node *p,*head,*pre;
  55.     head=new node;
  56.     head->next=NULL;
  57.     pre=head;
  58.     for(int i=0;i<N;i++)
  59.     {
  60.         p=new node;
  61.         p->data=array[i];
  62.         p->next=NULL;
  63.         pre->next=p;
  64.         pre=p;
  65.     }
  66.     return head;
  67. }
  68. int search(node* head,int x)    //查找单链表中x的个数
  69. {
  70.     node *p=head->next;
  71.     int count=0;
  72.     while(p!=NULL)
  73.     {
  74.         if(p->data==x)
  75.             count++;
  76.         p=p->next;
  77.     }
  78.     return count;
  79. }
  80. void insert(node* head,int pos,int x)   //在第pos号插入数据x
  81. {
  82.     node* p=head;
  83.     for(int i=0;i<pos;i++)
  84.     {
  85.         p=p->next;
  86.     }
  87.     node *q=new node;
  88.     q->data=x;
  89.     q->next=p->next;
  90.     p->next=q;
  91. }
  92. void del(node* head,int x)  //删除值为x的结点
  93. {
  94.     node* p=head->next;
  95.     node* q=head;
  96.     while(p!=NULL)
  97.     {
  98.         if(p->data==x)
  99.         {
  100.             q->next=p->next;
  101.             delete(p);
  102.             p=q->next;
  103.         }
  104.         else
  105.         {
  106.             q=p;
  107.             p=p->next;
  108.         }
  109.     }
  110. }
  111.  
  112. ​

下面个代码是看c和指针写出来的，但我感觉有点问题！

书上最后一个代码是这样给出的，他想传递的应该是链表第一个结点的地址，而不是头结点的地址，否则头结点是没数据的，即不应该与new_value比较。然而，传递了第一个结点的地址，insert函数必然会移动linkp的位置，因为没有另外的变量存储数据，那么问题来了，在主函数中，输出数据的时候，怎么从第一个数据开始输出，这儿的头结点的位置已经移动到new_value的前面一个节点了。所以，妾以为，用一个变量代替linkp更加合适，此事此时递给linkp的是链表的头结点，即头结点便不用移动，方便后续数据处理或者输出，即我写的那个完整的代码！

//c和指针给的代码
int insert(register node **linkp,int new_value)
    {
        register node *current;
        register node *p;
        while((current=*linkp)!=NULL && current->data<new_value)
               linkp=¤t->next;
        p =(node *)malloc(sizeof(node));
        if(p==NULL)
            return 0;
        p->data=new_value;
        p->next=current;
        *linkp=p;
        return 1;
    }

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <algorithm>
  4. using namespace std;
  5. struct node
  6. {
  7.     int data;
  8.     node *next;
  9. };
  10. node *create(int array[],int n);
  11. int insert(register node **linkp,int new_value);
  12. //node* insert(register node **linkp,int new_value);
  13. int main()
  14. {
  15.     int a[]={1,4,5,8,9,12,15,2,36,5,9,8,5,5,98};
  16.     int n=sizeof(a)/sizeof(a[0]);
  17.     sort(a,a+n);
  18.     for(int i=0;i<n;i++)
  19.     {
  20.         printf("%3d",a[i]);
  21.     }
  22.     printf("\n");
  23.     printf("创建链表:\n");
  24.     node *q=create(a,n);
  25.     q=q->next;
  26.     while(q!=NULL)
  27.     {
  28.         printf("%3d",q->data);
  29.         q=q->next;
  30.     }
  31.     printf("\n");
  32.     printf("插入一个数后:\n");
  33.     node *i=create(a,n);
  34.     insert(&i,-1);
  35.     insert(&i,25);
  36.     insert(&i,-10);
  37.     i=i->next;
  38.     while(i!=NULL)
  39.     {
  40.         printf("%3d",i->data);
  41.         i=i->next;
  42.     }
  43.     printf("\n");
  44.  
  45.  
  46. }
  47.  
  48. node *create(int array[],int n)
  49. {
  50.     node *p,*pre,*head;
  51.     head=new node;
  52.     head->next=NULL;
  53.     pre=head;
  54.     for(int i=0;i<n;i++)
  55.     {
  56.         p=new node;
  57.         p->data=array[i];
  58.         p->next=NULL;
  59.         pre->next=p;
  60.         pre=p;
  61.     }
  62.     return head;
  63. }
  64.  
  65. int insert(register node **linkp,int new_value)
  66. {
  67.     register node *precious;
  68.     precious=NULL;
  69.     register node *current;
  70.     register node *p;
  71.     current=(*linkp)->next;
  72.     while(current!=NULL&&current->data<new_value)
  73.     {
  74.         precious=current;
  75.         current=current->next;
  76.     }
  77.     p =(node *)malloc(sizeof(node));
  78.     if(p==NULL)
  79.         return 0;
  80.     p->data=new_value;
  81.     p->next=current;
  82.     if(precious==NULL)
  83.         (*linkp)->next=p;
  84.     else
  85.         precious->next=p;
  86.     free(p);
  87.     return 1;
  88. }

经过苦心“修炼”，终于找出了解决办法，insert函数的返回值为 node*，返回头节点：


node* insert(register node **linkp,int new_value)
{
    node* pre = *linkp;

    register node *current;
    register node *p;

    *linkp=(*linkp)->next;  //因为是带头结点的链表，所以要取头结点的下一个结点
    while((current=*linkp)!=NULL && current->data<new_value)
           linkp=¤t->next;
    p =(node *)malloc(sizeof(node));
    if(p==NULL)
        return NULL;
    p->data=new_value;
    p->next=current;

    if(pre->next==current)  //如果插入的数是在头节点的下一个位置，也就是插入的数最小
        pre->next=p;
    else
        *linkp=p;   //不能写成 (*linkp->next)->nect=p ; 原因我尚未弄清楚，我只知道会出现死循环
    return pre;
}

整体代码如下：

  1.  
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. using namespace std;
  6. struct node
  7. {
  8.     int data;
  9.     node *next;
  10. };
  11. node *create(int array[],int n);    //带头节点的链表
  12. node* insert(register node **linkp,int new_value);
  14. int main()
  15. {
  16.     int a[]={1,4,5,8,9,12,15,2,36,5,9,8,5,5,98};
  17.     int n=sizeof(a)/sizeof(a[0]);
  18.     sort(a,a+n);
  19.     for(int i=0;i<n;i++)
  20.     {
  21.         printf("%3d",a[i]);
  22.     }
  23.     printf("\n");
  24.     printf("创建链表:\n");
  25.     node *q=create(a,n);
  26.     q=q->next;
  27.     while(q!=NULL)
  28.     {
  29.         printf("%3d",q->data);
  30.         q=q->next;
  31.     }
  32.     printf("\n");
  33.     printf("插入一个数后:\n");
  34.     node *i=create(a,n);
  35.  
  36.     i=insert(&i,-1);
  37.     i=insert(&i,25);
  38.     i=insert(&i,-10);
  39.  
  40.     i=i->next;
  41.     while(i!=NULL)
  42.     {
  43.         printf("%3d",i->data);
  44.         i=i->next;
  45.     }
  46. }
  47.  
  48. node *create(int array[],int n)
  49. {
  50.     node *p,*pre,*head;
  51.     head=new node;
  52.     head->next=NULL;
  53.     pre=head;
  54.     for(int i=0;i<n;i++)
  55.     {
  56.         p=new node;
  57.         p->data=array[i];
  58.         p->next=NULL;
  59.         pre->next=p;
  60.         pre=p;
  61.     }
  62.     return head;
  63. }
  64.  
  65.  
  66. node* insert(register node **linkp,int new_value) //返回头节点
  67. {
  68.     node* pre = *linkp;
  69.  
  70.     register node *current;
  71.     register node *p;
  72.  
  73.     *linkp=(*linkp)->next;  //因为是带头结点的链表，所以要取头结点的下一个结点
  74.     while((current=*linkp)!=NULL && current->data<new_value)
  75.            linkp=&current->next;
  76.     p =(node *)malloc(sizeof(node));
  77.     if(p==NULL)
  78.         return NULL;
  79.     p->data=new_value;
  80.     p->next=current;
  81.  
  82.     if(pre->next==current)  //如果插入的数是在头节点的下一个位置，也就是插入的数最小
  83.         pre->next=p;
  84.     else
  85.         *linkp=p;   //不能写成 (*linkp->next)->nect=p ; 原因我尚未弄清楚，我只知道会出现死循环
  86.     return pre;
  87. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/893359
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号