数据结构——单链表

2020-06-16   106 次阅读

请注意，本文编写于  310  天前，最后编辑于  140  天前，内容可能已经不具有时效性，请谨慎参考。

摘要：单链表的基本操作，由于太久没有复习数据结构了，导致该忘的都忘了，所以在这里记录重新学习数据结构的笔记，以备以后查看。

单链表

链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表节点定义

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode;

此处定义了一个单链表的结构体，里面包含数据以及下一个数据的单链表指针。

创建节点

LNode *create_LNode(ElemType data){
    LNode *ret = (LNode*)malloc(sizeof(LNode));
    ret->data = data; //C中将NULL作为空指针之用，C++用nullptr
    return ret;
}

此处可以直接传入数据进行创建节点，当创建头节点时可以用NULL进行数据传入；

头插法创建单链表

int create_link_head(LNode *L,ElemType data[],int n){//传入头结点，数组，数组元素的个数
    LNode *p;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;
    L->next = NULL;
    for(i=0;i<n;i++){
        p = create_LNode(data[i]);
        p->next = L->next;
        L->next = p;
    }
    return L;
}

image-20200616173642497

tips：

因为是头插法，所以插入后的顺序是数组的倒序。

尾插法创建单链表

int create_link_tail(LNode *L,ElemType data[],int n){ //n为插入的个数
    LNode *p,*q;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;         //申请L为头节点
    q = L;
    for(i = 0; i< n ;i++){
        p = create_LNode(data[i]);
        q ->next = p;
        q = q->next;    //p = q;
    }
    q ->next = NULL;    //将最后一个节点指为NULL
    return L;
}

获取链表的长度

int get_length(LNode *L){
    int ret =0;
    if(L == NULL)
        return ret;
    while(L->next != NULL){
        ret++;
        L = L->next;
    }
    return ret;
}

获取链表中指定位置的节点指针

LNode *get_node(LNode *L,int p){ //p的范围是（1~N）不包含头结点
    LNode* ret;
    int count = 0;
    //ret = L->next;
    ret = L;
    while( ret != NULL && count< p){
        count++;
        ret = ret->next;
    }
    return ret;
}

获取单链表中data值第一次出现的节点指针

LNode *get_first_elem_node(LNode *L,ElemType data){
    LNode* ret = L->next;
    while(ret != NULL && ret->data != data){
        ret = ret->next;
    }
    return ret;
}

在指定的节点后插入节点

int insert_elem(LNode *L,int p,ElemType data){
    LNode *m = NULL;
    LNode *n = NULL;
    if(p<0 || L->next == NULL)
        return 0;
    m = get_node(L,p);
    n = (LNode*)malloc(sizeof(LNode));
    n->next = m->next;
    n->data = data;
    m->next = n;
    return 1;
}

删除节点

删除某个下标的节点,并返回被删除的节点的指针

LNode *delete_node(LNode *L,int p){
    LNode *ret = NULL;
    LNode *m = NULL;
    if(p < 1 || get_length(L)==0 ) //当删除的节点位置小于1或者长度为0时
        return 0;
    m = get_node(L,p-1);
    ret = m->next;
    m->next = m->next->next;
    return ret;
}

合并表

合并两个元素递增的单链表到一个新的单链表且依然有序

LNode* merge_link(LNode* A,LNode* B,LNode* C){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r;
    C = (LNode*)malloc(sizeof(LNode));
    C->data=NULL;
    r = C;
    while(p!=NULL && q!=NULL){
        if(p->data<=q->data){
            r->next=p;
            p=p->next;
            r=r->next;
        }
        else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    //下面的操作是另一个不为空的表剩下都归并到新的表的后面
    if(p==NULL)
        r->next = q;
    if(q==NULL)
        r->next = p;
    return C;
}

打印单链表

void print_link(LNode *L){
    while(L->next){
        L = L->next;
        printf("%3d",L->data);
    }
    printf("\n");
}

完整的函数（包含测试部分）

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode;

//初始化节点
LNode *create_LNode(ElemType data){
    LNode *ret = (LNode*)malloc(sizeof(LNode));
    ret->data = data; //C中将NULL作为空指针之用，C++用nullptr
    return ret;
}

//尾插法建立单链表
int create_link_tail(LNode *L,ElemType data[],int n){ //n为插入的个数
    LNode *p,*q;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;         //申请L为头节点
    q = L;
    for(i = 0; i< n ;i++){
        p = create_LNode(data[i]);
        q ->next = p;
        q = q->next;    //p = q;
    }
    q ->next = NULL;    //将最后一个节点指为NULL
    return L;
}
//头插法建立单链表
int create_link_head(LNode *L,ElemType data[],int n){
    LNode *p;
    int i;
    L = (LNode*)malloc(sizeof(LNode));
    L->data = NULL;
    L->next = NULL;
    for(i=0;i<n;i++){
        p = create_LNode(data[i]);
        p->next = L->next;
        L->next = p;
    }
    return L;
}

//获取单链表的长度
int get_length(LNode *L){
    int ret =0;
    if(L == NULL)
        return ret;
    while(L->next != NULL){
        ret++;
        L = L->next;
    }
    return ret;
}

//获取链表中指定位置的节点指针
LNode *get_node(LNode *L,int p){
    LNode* ret;
    int count = 0;
    //ret = L->next;
    ret = L;
    while( ret != NULL && count< p){
        count++;
        ret = ret->next;
    }
    return ret;
}

//获取单链表中data值第一次出现的节点指针
LNode *get_first_elem_node(LNode *L,ElemType data){
    LNode* ret = L->next;
    while(ret != NULL && ret->data != data){
        ret = ret->next;
    }
    return ret;
}

//在指定的节点后插入节点
int insert_elem(LNode *L,int p,ElemType data){
    LNode *m = NULL;
    LNode *n = NULL;
    if(p<0 || L->next == NULL)
        return 0;
    m = get_node(L,p);
    n = (LNode*)malloc(sizeof(LNode));
    n->next = m->next;
    n->data = data;
    m->next = n;
    return 1;
}

//删除某个下标的节点,并返回被删除的节点
LNode *delete_node(LNode *L,int p){
    LNode *ret = NULL;
    LNode *m = NULL;
    if(p < 1 || get_length(L)==0 ) //当删除的节点位置小于1或者长度为0时
        return 0;
    m = get_node(L,p-1);
    ret = m->next;
    m->next = m->next->next;
    return ret;
}

//合并两个元素递增的单链表到一个新的单链表且依然有序
LNode* merge_link(LNode* A,LNode* B,LNode* C){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r;
    C = (LNode*)malloc(sizeof(LNode));
    C->data=NULL;
    r = C;
    while(p!=NULL && q!=NULL){
        if(p->data<=q->data){
            r->next=p;
            p=p->next;
            r=r->next;
        }
        else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    if(p==NULL)
        r->next = q;
    if(q==NULL)
        r->next = p;
    return C;
}

//打印单链表
void print_link(LNode *L){
    while(L->next){
        L = L->next;
        printf("%3d",L->data);
    }
    printf("\n");
}

int main()
{
    LNode *A,*B,*C;
    int i;
    LNode* LOCAL;
    int data1[5]={9,7,5,3,1};
    int data2[7]={2,4,6,8,10,12,14};
    A = create_link_head(A,data1,5);
    B = create_link_tail(B,data2,7);
    print_link(A);
    print_link(B);

    i = get_length(A);
    printf("\nA的长度为:%d\n\n",i);

    LOCAL = get_first_elem_node(A,3);
    printf("A的第一次出现元素3的指针为：%d\n",LOCAL);
    printf("验证LOCAL的data为：%d\n\n",LOCAL->data);

    LOCAL = NULL;
    LOCAL = get_node(A,2);
    printf("A的第2位的指针为：%d\n",LOCAL);
    printf("验证LOCAL的data为：%d\n\n",LOCAL->data);

    //在指定的节点后插入节点
    insert_elem(B,2,5);
    print_link(B);
    printf("\n");
    //删除节点
    LOCAL = NULL;
    LOCAL= delete_node(B,3);
    print_link(B);
    printf("验证被删除的LOCAL->data为：%d\n\n",LOCAL->data);
    //合并两个单链表
    C=merge_link(A,B,C);
    print_link(C);
    printf("\n");

    return 0;
}

tips:

在函数中创建的节点要传出才能使用噢

本文由 hongCYu 创作，如果您觉得本文不错，请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
原文链接：https://hongcyu.cn/posts/datastruct-list2.html
最后更新于：2020-12-03 16:22:52

Coffee