链表(链式存储)

使用链式存储的顺序表，称为链表。

单链表

• 头指针，链表中第一个结点的存储位置，用来标识单链表。若链表中有头结点，头指针永远指向头结点不论链表是否为空。
• 头结点，在单链表第一个结点之前附加的一个结点，主要是为了操作的方便。一般不存储任何数据或存放链表的长度。

  有了头结点，对在第一结点前插入和删除第一结点操作就统一了，不需要频繁重置头指针。头结点不是必须的。

头插法

从链表头部插入数据。需要一个头指针

点击查看

使用C++

#include <stdio.h>
#include <stdlib.h>

#define ElementType int
typedef struct LNode{
    ElementType data; // 存储数据的参数变量，称为数据域
    struct LNode *next; // 结构体自身指针，称为指针域
}LNode,*pLNode;// 结构体别名，结构体指针别名
// lNode 是结构体别名。可以同结构体名称一样，这样在函数中定义结构体变量时就可以直接使用别名，而不必使用 struct LNode
// *pLNode 等价于 struct LNode *
// 链表 头插法 初始化
pLNode InitLNodeHead(pLNode &L){
    L = (pLNode)malloc(sizeof(LNode)); //申请链表空间
    L->next =NULL; // 空链表
    L->data = 0; //链表长度
}
// 头插法
pLNode CreateHead(pLNode &L,ElementType e){ // 因为要改变结构体内容，所以 引用&L
    pLNode t;
    t=(pLNode)malloc(sizeof(LNode)); // 申请新结点数据空间
    t->data = e; // 存储数据
    t->next = L->next; // 新结点指针置空
    L->next = t; // 链接结点，头指针指向新结点地址
    L->data++; // 增加链表长度
}
// 头插法打印链表
void printLNode(pLNode L){
    int len = L->data;
    L = L->next; // 获取指针
    while (L !=NULL){
        printf("%4d",L->data); // 打印数据
        L=L->next; // 指针后移
    }
    printf("\n");
    printf("链表长度为：%d\n",len);
}

// 按位置查找
pLNode localByNum(pLNode P,int i){
    if (!P->next ||i == 0 ){
        return P; //空链时、插入第0个位置
    }
    if(i > P->data){
        return NULL; //超出链表长度
    }
    pLNode temp=P; // 获取头指针
    for (int j = 1; j<= i ; ++j) {
       temp=temp->next;// 指针后移
    }
    return temp;
}
// 按值查找
int localByValue(pLNode P,ElementType e){
    int i=0;
    if (!P->next){
        return i;
    }
    pLNode temp=P; // 获取头指针
    for (int j = 1; j<= P->data ; ++j) {
        temp=temp->next;// 指针后移
        if (temp->data == e){
            i=j;
            break; // 跳出循环
        }
    }
    return i;
}
// 按位置插入数据
bool CreateByLocal(pLNode &L,int i,ElementType e){
    if(i<1){
        return false;
    }
    if (!L->next){ // 空链时直接插入。
        if (CreateHead(L,e)){
            return true;
        }
    } else{
        pLNode temp;
        temp = localByNum(L,i-1);// 后去前一数据的指针
        if(temp){
            pLNode temps;
            temps = (pLNode)malloc(sizeof(LNode));
            temps->data = e; // 存储数据
            temps->next = temp->next; // 后指针转移
            temp->next = temps; // 插入位置指针转移
            L->data++;// 增加链表长度
            return true;
        }
    }
    return false;
}
// 按位置删除数据
bool DeleteByLocal(pLNode &L,int i){
    if(i<1 || !L->next){
        return false;
    }
    pLNode temp;
    temp = localByNum(L,i-1);// 获取对应位置的前指针
    if(temp){
        pLNode temps;
        temps = temp->next; // 获取指针
        temp->next = temps->next; // 链接新指针地址
        free(temps); // 释放空间
        L->data--;// 减少链表长度
        return true;
    }else{
        return false;
    }
}


int main() {
    pLNode L;// 定义结构体变量，用于存储数据
    InitLNodeHead(L);
    int x;
    scanf("%d",&x);
    while (x != 9999){ // 当输入 9999 时结束
        CreateHead(L,x);
        scanf("%d",&x); // 继续读取数据，直到跳出循环
    }
    printLNode(L);

    // 直接头插
    printf("请输入需要插入的数据：\n");
    fflush(stdout);
    scanf("%d",&x);
    CreateHead(L,x);
    printLNode(L);

//    // 按位置查找
    printf("请输入要查找的位置：\n");
    fflush(stdout);
    scanf("%d",&x);
    pLNode finds;
    finds = localByNum(L,x);
    if (finds){
        printf("您查找的第%d个位置的值为：%d\n",x,finds->data);
    }else{
        printf("您查找的位置错误，链表长度为：%d\n",L->data);
    }

    // 按值查找
    printf("请输入要查找的值：\n");
    fflush(stdout);
    scanf("%d",&x);
    x = localByValue(L,x);
    if (x){
        printf("您查找的值在第%d个位置。\n",x);
    }else{
        printf("您查找的不在该链表中。\n");
    }
    // 指定位置插入数据
    printf("请输入要插入的位置：\n");
    fflush(stdout);
    scanf("%d",&x);
    ElementType i;
    printf("请输入要插入的值：\n");
    fflush(stdout);
    scanf("%d",&i);
    CreateByLocal(L,x,i);
    printLNode(L);

    // 指定位置删除数据
    printf("请输入要删除的位置：\n");
    fflush(stdout);
    scanf("%d",&x);
    while (x != 9999){ // 当输入 9999 时结束
        if (DeleteByLocal(L,x)){
            printLNode(L);
        }else{
            printf("删除失败！！\n");
        }
        printf("请输入要删除的位置：\n");
        fflush(stdout);
        scanf("%d",&x); // 继续读取数据，直到跳出循环
    }
    printLNode(L);

    return 0;
}

尾插法

从链表尾部插入数据。需要头、尾指针各一个。

点击查看

使用C++

#include <stdio.h>
#include <stdlib.h>

#define ElementType int
typedef struct LNode{
    ElementType data; // 存储数据的参数变量，称为数据域
    struct LNode *next; // 结构体自身指针，称为指针域
}LNode,*pLNode;// 结构体别名，结构体指针别名
// lNode 是结构体别名。可以同结构体名称一样，这样在函数中定义结构体变量时就可以直接使用别名，而不必使用 struct LNode
// *pLNode 等价于 struct LNode *
// 链表 尾插法 初始化
pLNode InitLNodeTail(pLNode &H,pLNode &T){
    H = (LNode*)malloc(sizeof(LNode)*1); //申请链表空间
    H->next =NULL; // 空链表
    H->data = 0; //记录链表长度
    T=H; // 空链表,尾指针指向头指针
}
// 链表 尾插法 插入数据
pLNode CreateTail(pLNode &T,ElementType e){ // 因为要改变结构体内容，所以 引用&L
    pLNode t;
    int i=T->data;
    i++;
    t=(pLNode)malloc(sizeof(LNode)); // 申请新结点数据空间
    T->data =e; // 存储数据
    T->next =t; // 尾指针指向新指针
    t->data = i; // 记录链表长度
    t->next = NULL; // 新结点指针置空
    T=t; // 更新尾指针
}
// 尾插法打印链表
void printTailLNode(pLNode L){
    if(L->next ==NULL){
        printf("单链表暂无数据！\n");
    }else{
        int len;
        while (L->next !=NULL){
            printf("%4d",L->data);
            L = L->next;
            len = L->data;
        }
        printf("\n");
        if(L->next ==NULL) {
            int len = L->data;
        }
        printf("单链表长度为：%d\n",len);
    }
}
int main() {
    pLNode Head,Tail;
    Tail = (pLNode)malloc(sizeof(LNode)); // 申请尾结点数据空间
    InitLNodeTail(Head,Tail);
    int y;
    scanf("%d",&y);
    while (y != 9999){ // 当输入 9999 时结束
        CreateTail(Tail,y);
        scanf("%d",&y); // 继续读取数据，直到跳出循环
    }
    printTailLNode(Head);
    printf("请输入需要插入的数据：\n");
    fflush(stdout);
    scanf("%d",&y);
    CreateTail(Tail,y);
    printTailLNode(Head);

    return 0;
}