数据结构 - 链式存储结构-单向链表

姜皓 2019-11-05

链式存储结构-单向链表

//linkedlist.c
#include <stdio.h>
#include <stdlib.h>

//类型
typedef struct node{
    int data;  //数据区域
    struct node *next; // 下一个节点的指针
    //    linklist_t* next;//  编译器  只能从上往下解释

}linklist_t;

//创建
linklist_t* create_linklist()
{
    linklist_t* list=malloc(sizeof(linklist_t));

    list->next=NULL;//指针变量 赋值为 NULL

    return list;
}
//判空
int isnull_linklist(linklist_t* list)
{
    if(list==NULL)
        return 0;

    return list->next==NULL;
}
//插入
int insert_linklist(linklist_t* list,int data)
{
    //1
    if(list==NULL)
        return -1;

    //2
    linklist_t* newnode=create_linklist();
    newnode->data=data;

    //3
    newnode->next=list->next;

    //4
    list->next=newnode;
    
    return 0;
}
//删除
int delete_linklist(linklist_t* list)
{
    //1
    if(list==NULL||isnull_linklist(list))
        return -1;

    //2
    linklist_t* temp=list->next;

    //3
    //list->next=list->next->next;
    list->next=temp->next;

    free(temp);

    return 0;
}

//查找
//1. 返回节点地址 比返回第几个要更方便
//2. 返回 节点前一个节点的地址比返回  本节点地址更方便
//方便除了修改以外,插入,删除等操作。
linklist_t* locate_linklist(linklist_t* list,int data)
{
    //1
    if(list==NULL||isnull_linklist(list))
        return NULL;

    //2 遍历
    while(list->next!=NULL)
    {
        if(list->next->data==data)
            return list;

        list=list->next;
    }
    
    return NULL;
}
//修改
int change_linklist(linklist_t* list,int data)
{
    if(list==NULL||isnull_linklist(list))
        return -1;

    list->next->data=data;

    return 0;
}
//打印
int print_linklist(linklist_t* list)
{
    //1
    if(list==NULL||isnull_linklist(list))
        return -1;

    //2
    while(list->next!=NULL)
    {
        printf("%3d ",list->next->data);
        list=list->next;
    }
    printf("\n");

    return 0;
}
//逆打印1 递归  影分身  
void re_print_linlist_digui(linklist_t* list)
{
    if(list->next==NULL)
        return ;   //   void 类型返回   return ;

    re_print_linlist_digui(list->next);

    printf("%3d ",list->next->data);

    return ;//不写 由编译器替你补齐
}
//长度
int length_linklist(linklist_t* list)
{
    //1
    if(list==NULL||isnull_linklist(list))
        return 0;

    int sum=0;
    //2
    while(list->next!=NULL)
    {
        sum++;
        list=list->next;
    }
    return sum;
}
//清空
int clear_list(linklist_t* list)
{
    if(list==NULL||isnull_linklist(list))
        return -1;

    while(!isnull_linklist(list))//while(length_linklist(list))//while(list->next!=NULL)
    {
        delete_linklist(list);
    
    }
    return 0;
}

//销毁
int destroy_linklist(linklist_t* list)
{
    if(list==NULL)
        return -1;

    if(!isnull_linklist(list))
        clear_list(list);

    free(list);

    return 0;
}


//逆打印2 过河拆桥
//
//使用之前的基本函数
//
//过河?      桥?   --》另 一个  链表
//
//
//拆?
//
//思路:    插入  1.2.3.。。。。20 顺序 插入 
//而  打印的时候   20 。19.。。。。3.2.1 的顺序 打印
//
//要求   -》1.2.3.。。20  打印出来?
int re_print_linlist_guohechaiqiao(linklist_t* list)
{
    //1
    if(list==NULL||isnull_linklist(list))
        return -1;

    linklist_t* temp=create_linklist();
    //创建的逆序表
    //
    
    while(list->next!=NULL)
    {
        insert_linklist(temp,list->next->data);

        list=list->next;
    }
    print_linklist(temp);
    destroy_linklist(temp);

    return 0;
}

int main(int argc, const char *argv[])
{
    linklist_t* list=create_linklist();//创造头结点
    

    int i;

    for(i=1;i<=20;i++)
    {
        insert_linklist(list,i*10);
        print_linklist(list);
    
    }

    change_linklist(locate_linklist(list,150),888);
    print_linklist(list);

    insert_linklist(locate_linklist(list,888),150);
    print_linklist(list);

    delete_linklist(locate_linklist(list,888));
    print_linklist(list);

    re_print_linlist_digui(list);
    printf("\n");

    re_print_linlist_guohechaiqiao(list);

    printf("length_linklist %d\n",length_linklist(list));

    clear_list(list);

    printf("length_linklist %d\n",length_linklist(list));

    destroy_linklist(list);

#if 0

    for(i=1;i<=20;i++)
    {
        delete_linklist(list);
        print_linklist(list);
    }
#endif

    return 0;
}