王道计算机考研 数据结构C语言复现-第二章-单链表

这篇文章收录了王道考研课程中涉及的数据结构的所有代码。此外，本博客可能会添加一些额外的代码（不仅限于王道考研），因为408考试中会频繁考察一些冷门的知识点，所以这篇博客会涵盖所有相关的代码。这也是我数据结构的第一轮复习，希望能与大家共同进步。由于博客篇幅的限制，可能无法一次性包含所有内容，

你想要的都在下面！！！

// @FileName  :DanLianBiao.c
// @Time      :2023/8/12 17:39
// @Author    :YKW
# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList; //LNode *L ==LinkList L
//LinkList强调单链表，LNode*强调节点
//typedef struct LNode L;
bool InitList(LinkList L) {
/*  无头节点单链表，头节点没有data
    L=NULL;//无节点空表
    return true;*/
    L = (LNode *) malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L->next = NULL;
    return true;
}

bool IsEmpty(LinkList L) {
    return L == NULL;
}

//表长度
int Length(LinkList L) {
    int len = 0;
    LNode *p = L;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

//按位查找，返回第i个元素（带头节点
LNode *GetElem(LinkList L, int i) {
    if (i < 1)
        return NULL;
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找，找到数据域==e的节点
LNode *LocateElem(LinkList L, int e) {
    LNode *p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}
//展示链表data
bool Show(LinkList L) {
    LNode *p = L->next;
    printf("List:\t");
    while (p != NULL) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
    if (p == NULL)
        return false;
    return true;
}
//后插操作，在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL)
        return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL)//内存分配失败
        return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
//前插操作，在p节点之前插入元素e
bool InsertPriorNode(LNode *p, int e) {
    if (p == NULL)
        return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if (s == NULL)//内存分配失败
        return false;
    s->next = p->next;
    p->next = s;//s连接到p之后
    s->data = p->data;//s和p交换元素位置
    p->data = e;
    return true;
}
//按位序删除
bool ListDelete(LinkList L, int i, int *e) {
    if (i < 1)
        return false;
    LNode *p = GetElem(L, i - 1);
    if (p == NULL)
        return false;
    if (p->next == NULL)//i-1后面无其他节点
        return false;
    LNode *q = p->next;//被删除的节点
    *e = q->data;//用e带出被删除的值
    p->next = q->next;//对接两段
    free(q);
    return true;
}
//删除指定节点p
bool DeleteNode(LNode *p) {
    if (p == NULL)
        return false;
    LNode *q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    free(q);
    return true;
}
//在第i位置插入元素e,带头节点
bool ListInsert1(LNode *L, int i, int e) {
    LNode *p = L, *cnt;
    cnt = (LNode *) malloc(sizeof(LNode));
    cnt->data = e;
    for (int j = 0; j < i - 1; j++) {
        p = p->next;
    }
    p->next = cnt;
    cnt->next = (p->next)->next;
    return true;
}//我的方法
bool ListInsert2(LinkList L, int i, int e) {
    if (i < 0)
        return false;
    LNode *p = GetElem(L, i - 1);//找到第i-1个节点
    /*LNode *p;
    int j=0;
    p=L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }*/
    /*    if(p==NULL)
            return false;
        LNode *s=(LNode*) malloc(sizeof (LNode));
        s->data=e;
        s->next=p->next;
        p->next=s;
        return true;*/
    return InsertNextNode(p, e);
}

//头插法建立单链表
LinkList List_HeadInsert(LinkList L) {
    LNode *s;
    int x;
    L->next = NULL;
    printf("The next number:");
    scanf("%d", &x);
    while (x != -1) {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        Show(L);
        printf("The next number:");
        scanf("%d", &x);
    }
    return L;
}

//尾插法建立单链表
LinkList List_TailInsert(LinkList L) {
    int x;
    LNode *s, *r = L;//r为尾指针
    scanf("%d", &x);
    while (x != -1) {
        s = (LinkList) malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

int main() {
    LinkList L = NULL;//L是指针
    L = (LinkList) malloc(sizeof(LNode));//malloc要在外部使用

    List_HeadInsert(L);
    int i = 0, e = 0;
    printf("插入操作，输入数字i   e:");
    scanf("%d%d", &i, &e);
    ListInsert2(L, i, e);
    Show(L);
/*
    printf("删除操作，输入数字i :");
    scanf("%d",&i);
    ListDelete(L,i,&e);
    Show(L);}*/
}