数据结构-链表

时间：2024-02-18 19:13:08

实现功能：

         1. 定义结构体

typedef int data_t;

typedef struct note
{
    data_t data;
    struct note *next;
}listnote, *linklist;

                data_t data;：定义了一个名为data的字段，其类型为data_t；

                struct note *next;：定义了一个名为next的指针字段，该指针指向与当前结构体相同

        类型的下一个结构体

                listnote是struct note的别名

                linklist是一个指向struct note的指针的别名

        2. 创建一个空链表

linklist list_create(){

    linklist H;
    //1. 申请内存
    H = (linklist)malloc(sizeof(listnote));
    if(H ==NULL){
        printf("malloc failed\n");
    }
    //2. 赋初值
    H->data = 0;
    H->next = NULL;
    //3. 返回值
    return H;
}

        3. 尾部插入和遍历

                尾部插入分为三步：1. 建立一个新节点

                                ①malloc

                                ②赋初值

                             2. 找尾节点        

                             3. 实现尾部插入

int list_tail_insert(linklist H,data_t value){

    if (H == NULL)
    {
        printf("H is NULL\n");
        return -1;
    }
    
    //1.new a note
    linklist p;
    linklist q;

    if ((p=(linklist)malloc(sizeof(listnote)))== NULL)
    {
        printf("malloc is failed\n");
        return -1;
    }

    p->data = value;
    p->next = NULL;

    //2. find tail list

    q = H;
    while (q->next != NULL)
    {
        q = q->next;
    }
    
    //3. fail insert
    q->next = p;

    return 0;
}
int list_show(linklist H){

    if (H == NULL)
    {
        printf("H is NULL\n");
        return -1;
    }
    

    linklist p;
    p = H;

    while (p->next != NULL)
    {
        printf("%d ",p->next->data);
        p = p->next;
    }
    puts("");
    
}
//main函数
#include <stdio.h>
#include "linklist.h"

int main(int argc, char const *argv[])
{
    linklist H;
    int value;

    H = list_create();
    if(H == NULL){
        return -1;
    }

    printf("input:");
    while (1)
    {
        scanf("%d",&value);
        if(value == -1){
            break;
        }
        list_tail_insert(H,value);
        printf("input:");
    }
    
    return 0;
}

            遍历：

int list_show(linklist H){

    if (H == NULL)
    {
        printf("H is NULL\n");
        return -1;
    }
    

    linklist p;
    p = H;

    while (p->next != NULL)
    {
        printf("%d ",p->next->data);
        p = p->next;
    }
    puts("");
    
}

        4. 通过序号查找值

linklist list_get(linklist H,int pos){

    int i =-1;
    linklist p;

    p = H;

    if(pos == -1){
        return H;
    }

    while (i < pos)
    {
        p = p->next;
        if (p == NULL)
        {
            printf("pos is invalid\n");
            return NULL;
        }
        
        i++;
    }
    return p;
}
    //main函数

    p =list_get(H, 2);

    if (p != NULL)
    {
        printf("value = %d\n",p->data);
    }

        5. 在某一位置插入元素

int list_insert(linklist H,data_t value,int pos){

    linklist p;
    linklist q;

    if (H == NULL)
    {
        printf("H is NULL\n");
        return -1;
    }
    
    // 1. 定位节点 p （pos-1）
    p =list_get(H,pos-1);
    if (p == NULL)
    {
        printf("p is NULL\n");
        return -1;
    }
    
    // 2. 新节点q申请内存，赋初值
    if ((q = (linklist)malloc(sizeof(listnote)))== NULL)
    {
        printf("malloc failed\n");
        return -1;
    }
    
    
    q->next = NULL;
    q->data = value;
    //3.完成插入操作
    q->next = p->next;
    p->next = q;

    return 0;
}

6. 链表删除某个元素

        1. 检查链表的入口参数

        2. 找前驱

        3. 更新链表

        4. 释放删除的内存

int list_del(linklist H,int pos){

    linklist p;
    linklist q;
    //1. 
    if(H == NULL){
        printf("H is NULL\n");
        return -1;
    }
    //2.
    p = list_get(H,pos-1);

    if(p == NULL){
        return -1;
    }
    if(p->next == NULL){
        printf("delete pos invalid\n");
        return -1;
    }
    //3.
    q = p->next;
    p->next = q->next;

    //4.
    printf("free = %d\n",q->data);
    free(q);
    q = NULL;

    return 0;
}

7. 释放链表内存

linklist list_free(linklist H){

    linklist p;
    if (H == NULL)
    {
        return NULL;
    }
    

    p = H;
    printf("free:");
    while (H != NULL)
    {
        p = H;
        printf("%d ",p->data);
        H = H->next;
        free(p);
    }
    puts("");
    return NULL;
}

8. 链表反转 

int list_inver(linklist H){

    linklist p;
    linklist q;

    if (H == NULL)
    {
        printf("H is NULL\n");
        return -1;
    }
    if (H->next == NULL ||H->next->next == NULL)
    {
        return 0;
    }
    
    p = H->next->next;
    H->next->next = NULL;
    
    while (p != NULL)
    {
        q = p;
        p =p->next;
        
        q->next = H->next;
        H->next = q;

    }

    return 0;
}

 9. 求相邻结点最大值

//linklist.c 部分
linklist list_adjmax(linklist H,data_t *value){
    
    linklist p , q, r;
    data_t sum = 0;

    if (H == NULL)
    {
        printf("H is NULL\n");
        return NULL;
    }
    if(H->next == NULL ||H->next->next == NULL || H->next->next->next == NULL){
        return H;
    }
    q = H->next;
    p = q->next;
    r = q;
    sum = p->data + q->data;

    while (p->next != NULL)
    {
        p = p->next;
        q = q->next;
        if (sum < p->data + q->data)
        {
            sum =p->data + q->data;
            r = q;
        }
    }
    *value = sum;
    return r;  
}
//main
linklist r;
int sum;

r = list_adjmax(H,&sum);
    if (r != NULL && r != H)
    {
        printf("data=%d,sum=%d\n",r->data,sum);
    }

10. 合并两个有序链表

//linklist.c
int list_merge(linklist H,linklist R){

    linklist p,q,r;

    if (H == NULL)
    {
        printf("H is NULL\n");
        return -1;
    }
    
    if (R == NULL)
    {
        printf("R is NULL\n");
        return -1;
    }

    p = H->next;
    q = R->next;
    r = H;
    H->next = NULL;
    R->next = NULL;
    
    while (p && q)
    {
        if (p->data <= q->data)
        {
            r->next = p;
            p = p->next;
            r = r->next;
            r->next = NULL;
        }else{
            r->next = q;
            q = q->next;
            r = r->next;
            r->next = NULL;
        }
        if (q == NULL)
        {
            r->next = p;
        }else{
            r->next = q;
        }
        
    }

    return 0;
}
//main.c
#include <stdio.h>
#include "linklist.h"

int listmerge();

int main(int argc, char const *argv[])
{   
    linklist H,R;
    int a[]={1,3,5,7,9,243};
    int b[]={2,4,8,13};
    int i;

    H = list_create();
    if(H == NULL){
        return -1;
    }
    R = list_create();
    if(R == NULL){
        return -1;
    }
    for ( i = 0; i < sizeof(a)/sizeof(int); i++)
    {
        list_tail_insert(H,a[i]);
    }
    for ( i = 0; i < sizeof(b)/sizeof(int); i++)
    {
        list_tail_insert(R,b[i]);
    }
    list_show(H);
    list_show(R);

    list_merge(H,R);

    list_show(H);

    list_free(H);
    list_free(R); 

    return 0;
}

相关文章