链表基础知识整理

谁借莪１个温暖的怀抱￠ 2022-06-11 01:29 155阅读 0赞

**关于链表最重要的是搞清楚指针的指向，next域存放的是下一个结点的地址。  
1：顺序建链表要定义头指针，游动指针，尾部指针；  
逆序建立链表定义头指针和游动指针即可，每次将新的结点插在头指针后面。搞清楚指针的指向即可。**

**2：删除结点。定义一个游动指针，还要定义一个指针，为了记后一个结点的地址。**

//顺序建表：
    
    #include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int data;
        struct node *next;
    };
    
    int main()
    {
        struct node *head,*tail,*p;
        int n;
        scanf("%d",&n);
        head = (struct node *)malloc(sizeof(struct node)); //头指针申请空间
        head->next = NULL;
        tail = head;                                    //让头指针的next域为NULL,作为指针的结尾；
        int i,j=1;
        for(i=0;i<=n-1;i++)       //建立新的结点。
        {
            p = (struct node *)malloc(sizeof(struct node));//申请空间
    
            scanf("%d",&p->data);   //给新的结点的data域赋值。
            p->next = NULL;         //最终要将新插入的结点作为尾部，所以让其next域为NULL,也可以写成p->next = tail.next；(此时还不是尾部)
            tail->next  = p;  //此时将p与tail相连
            tail = p;    //所以此时p为最后一个结点，所以tail变为p
      }
       p= head->next; //因为链表只能从第一个指针开始查询，只有头指针位置可知，所以让游动指针开始为h->next的；
       while(p!=NULL)  //只要p不为空，就输出。
       {if(j==1)
           {
                printf("%d",p->data);
                j++;
           }
           else
            printf(" %d",p->data);
    
           p = p->next;//让p 不断移动、
       }
    
    
        return 0;
    }
    
    
    
    #include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int data;
        struct node *next;
    };
    
    struct node *name(int n)
    {
        struct node *head,*tail,*p;
        head = (struct node *)malloc(sizeof(struct node)); //头指针申请空间
        head->next = NULL;                                 
        tail = head;                                    //让头指针的next域为NULL,作为指针的结尾；
        int i;
        for(i=0;i<=n-1;i++)       //建立新的结点。
        {
            p = (struct node *)malloc(sizeof(struct node));//申请空间
    
            scanf("%d",&p->data);   //给新的结点的data域赋值。
            p->next = NULL;         //最终要将新插入的结点作为尾部，所以让其next域为NULL,也可以写成p->next = tail.next；(此时还不是尾部)
            tail->next  = p;  //此时将p与tail相连
            tail = p;    //所以此时p为最后一个结点，所以tail变为p
        }
        return head; //返回头指针。
    };
    void print(struct node *h)
    {
       struct node *p;
       p= h->next; //因为链表只能从第一个指针开始查询，只有头指针位置可知，所以让游动指针开始为h->next的；
       int i=1;
       while(p!=NULL)  //只要p不为空，就输出。
       {if(i==1)
           {
                printf("%d",p->data);
                i++;
           }
           else
            printf(" %d",p->data);
          
           p = p->next;//让p 不断移动、
       }
    
    };
    
    int main()
    {
        struct node *h;
        int n;
        scanf("%d",&n);
        h = name(n);    //返回到头指针的位置。因为链表只要知道了头指针便可知道整个链表是什么样的、
        print(h)//、定义的输出函数。将链表输出。
        return 0;
    }
    
    
    
    //逆序建链表：
    
    #include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int data;
        struct node *next;
    };
    struct node *name(int n)
    {
        struct node *head,*p;
        head  = (struct node *)malloc(sizeof(struct node));
        head->next = NULL;
        int i;
        for(i=0;i<=n-1;i++)
        {
            p =(struct node *)malloc(sizeof(struct node));
            scanf("%d",&p->data);
           p->next = head->next;//只有这一句和下面一句代码是不同的。即已知头结点。建立后面的结点的方法不同。
           head->next = p;
        }
        return head;
    }
    void print(struct node *head)
    {
        struct node *p;
            p = head->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p = p->next;
        }
    }
    
    int main()
    {
        int n;
        scanf("%d",&n);
        struct node *h;
        h = name(n);
        print(h);
        return 0;
    
    }
    
    //链表结点的查找
    struct node *search（struct node *h，key）
    {
      struct node *p ;
     p = h- >next;
    while(p!=NULL)
    {
        if(p->data==key)
    return  p;  //找到了返回p的地址。
        else
        p = p->next;
    } 
    return NULL;  //即未找到；
    
    }
    
    
    链表的插入函数;
    void insert(struct node *p,int key)
    {
        struct node *q;
        q = (struct node *)malloc(sizeof(struct node));
        q->next = NULL;//可有可无
        q->data = key;
        q->next = p->next;
        p->next = q;
    }
    
    
    
    //链表逆置函数：实质是逆序建表的过程：
    struct node *reverse(struct node *head)
    {
        struct node *p,*q;
        p = head->next;  //将头结点拆下来，作为新节点的头结点。
        head->next = NULL;
        q = p->next;
        while(p!=NULL)
        {
            p->next  = head->next ; 
            head->next  = p;  //将节点插在head后面。实现逆序的过程。
            p = q;
            if(q!=NULL)
            q = q->next;
        }
        return head;
    };
    
    
    //链表的归并：E题，实质是顺序建表的过程
    
    
    struct node *merge(struct node *h1,struct node *h2)
    {
        struct node *p1,*tail,*p2;
        p1 = h1->next;
        p2 = h2->next;
        tail = h1;   //设置新链表的头结点
        free(h2);
        while(p1&&p2)
        {
            if(p1->data>p2->data)   //比较，将小的放在新建链表的尾部；
            {
                tail->next = p2;
    
    
                tail = p2;
                p2 = p2->next;
                tail->next = NULL;
             }
             else
             {
                 tail->next = p1;
    
    
                tail = p1;
                 p1 = p1->next;
                tail->next = NULL;
             }
        }
        if(p1)  //进行完上述循环后，p1或p2有一个有剩余。将剩余的直接连在尾部即可。
        {
            tail->next = p1;
        }
        else
            tail->next = p2;
        return h1;
    
    
    };