数据结构链表单链表的建立 C语言版

迷南。 2022-06-09 04:23 207阅读 0赞

#include <cstdio>
    #include <stdlib.h>
    typedef struct Node
    {
        int data;
        struct Node * next;
    } Node,* Linklist;  //定义链表的结点，链表头
    
    void Initlist (Linklist *L)  //初始化链表
    {
        *L=(Linklist)malloc(sizeof(Node));
        (*L)->next=NULL;
    }
    
    void CreateFromHead(Linklist L)  //头插法建表
    {
        Node *s;
        int flag=1; int num;
        while(flag)
        {
            scanf("%d",&num);
            if(num != -1){
                s=(Node *)malloc(sizeof(Node));
                s->data=num;
                s->next=L->next;
                L->next=s;
            }
            else flag=0;
        }
        return ;
    }
    
    void CreateFromTail(Linklist L) //尾插发建表
    {
        Node *r,*s;
        r=L;  //r总是指向链表的最后结点，s是新的结点
        int flag=1; int num;
        while(flag)
        {
            scanf("%d",&num);
            if(num!= -1)
            {
                s=(Node *) malloc(sizeof(Node));
                s->data=num;
                r->next=s;
                r=s;
            }
            else{
                flag=0;
                r->next=NULL;
            }
        }
        return ;
    }
    
    int Inslist(Linklist L,int i,int e) //在链表的位置i 插入元素e  插入成功返回1 不成功返回0
    {
        Node *pre,*s;  //pre指向插入位置i的前一个结点
        pre=L;
        int k=0;
        if(i<=0) {
            printf("插入位置不合理\n");
            return 0;
        }
        while(pre!=NULL && k<i-1)
        {
            pre=pre->next;
            k++;
        }
        if(pre==NULL)
        {
            printf("插入不合理");
            return 0;
        }
        s=(Node *)malloc(sizeof(Node));
        s->data=e;
        s->next=pre->next;
        pre->next=s;
        return 1;
    }
    
    int  Delist(Linklist L,int i,int * e) //删除位置i的元素 并将删除的元素保存在e  删除成功返回1 不成功返回0
    {
        Node *pre ,*r;
        int k=0;
        pre=L;
        while(pre->next !=NULL  && k<i-1)
        {
            pre=pre->next;
            k++;
        }
        if(pre->next ==NULL)   //删除位置i的前一个结点为pre 若pre的next指向的数为空 说明没有数可删除
        {
            printf("删除不合理\n");
            return 0;
        }
        r=pre->next;
        pre->next=r->next;
        *e=r->data;
        free(r);
        return 1;
    }
    
    void DeleteSimilar(Linklist L)   //删除链表中结点相同的值
    {
        Node *pre,*backk,*r;
        pre=L->next;
        while(pre!=NULL)
        {
            r=pre;
            backk=pre->next;
            while(backk != NULL)
            {
                if(backk->data==pre->data)
                {
                     r->next=backk->next;
                     backk=backk->next;
                }
                else {
                        r=backk;
                        backk=backk->next;
                }
            }
            pre=pre->next;
        }
        return ;
    }
    
    void Output(Linklist L)  //输出单链表
    {
        Node *temp;
        temp=L->next;
        while(temp !=NULL)
        {
            printf("%d ",temp->data);
            temp=temp->next;
        }
        printf("\n");
    }
    
    int main()
    {
        Linklist L;
    
        Initlist( &L);
        printf("输入链表的值,以-1为结束标志\n");
        CreateFromTail(L);
        printf("输入链表的值\n");
        Output(L);
    
        printf("输入插入链表的位置和值\n");
        int pos,value;
        scanf("%d%d",&pos,&value);
        if(Inslist(L,pos,value))
        {
            printf("插入合理");
            Output(L);
        }
    
        printf("输入删除链表的位置\n");
        int p; int  v;
        scanf("%d",&p);
        if(Delist(L,p,&v))
        {
            printf("删除成功\n");
            printf("删除的数据为 %d \n",v);
            printf("删除数据后的链表为\n");
            Output(L);
        }
    
        printf("删除相同元素的值后的链表为\n");
        DeleteSimilar(L);
        Output(L);
        return 0;
    }