基础---单链表的实现（带头）

2023-11-25 13:24:40

数据结构与算法

基础---链表

链表是干什么的

在谈这个问题之前，我们先来看另一个问题：

一组数据1，2，3，4，5，6，7，8，9以顺序储存的方式存在于内存中。
当我想要在1后面插入数字6怎么办呢？
解：将数字2，3，4，5，6，7，8，9依次在内存中向后移动一位，形成1，2，2，3，4，5，6，7，8，9，然后将第二个2替换成6。over

这样一看顺序结构在执行插入删除等操作时需要一大堆步骤，太过于繁琐。然而，链式储存方式的出现就很好的解决了这个问题——链式结构的数据不需要呆在一起。

数组利用顺序储存的方式来储存数据，而链表利用链式储存的方式储存数据。

顺序储存：在内存中，一个个数据紧挨着储存。

链式储存：在内存中，一个个数据分布在内存的各个地方。

链式储存可以将自己存数据的地方分成两部分，一部分储存数据，另一部分指向下一个储存数据的节点。这样就做到了将数据在内存的任意位置存放。

单链表

种类

基础---单链表的实现（带头）

基本术语

  • 结点：单链表是一种链式存取的数据结构，链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。基础---单链表的实现（带头）

1.单链表的实现(带头链表)

1.1定义一个结点
//使用结构体来定义一个结点。注: 只要不是关键字，那就都是变量名,不必因为看着太规范而怀疑它为关键字。
typedef struct Node{
    int data;//储存数据，DATA部分。
    struct Node *next;//储存指针，NEXT部分。
}Node,*LinkedList;//Node是结构体struct Node的别名，*LinkedList是一个指向struct Node的指针。
1.2初始化结点
LinkedList listinit(){
    Node *L;
    L=(Node*)malloc(sizeof(Node));      //开辟空间 
    if(L==NULL){                     //判断是否开辟空间失败，这一步很有必要
        printf("申请空间失败");
        //exit(0);                  //开辟空间失败可以考虑直接结束程序
    }
    L->next=NULL;       //指针指向空
}
//检查很有必要，但下面那几个创建单链表的似乎都没检查。
//（没试过）下面那几个初始结点的操作，似乎可以直接用这个函数代替掉。这个函数里面写好检查开辟成功与否的方法，再初始化结点时更加方便也更加安全。

基础---单链表的实现（带头）

1.3创建单链表（重点）

分为两种创建方式：（好像还有有头结点的和没头结点的，暂时没看）

//头插入法创建单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
  
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;     //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
/*
一步一步的分析：
1.声明了一个指针变量L，这个指针变量储存了一个结构体的地址。而这个结构体里还可以有一个指针，这个指针（NEXT）不要和这个指针变量本身储存的指针混淆。也就是L储存了一个地址，L->next储存了另外的地址，L的地址指向这个结构体，L->next的指针指向另外的结构体。
长话短说就是L是一个地址，*L才是一个结构体。
//第一轮循环
2.开辟了一个内存空间，目标结构体算是正式诞生了，这个结构体的next指向NULL。
3.声明了一个指针变量p，开辟结构体内存空间。
4.*p的data存上数据x，*p的next存上*L的next
5.*L的next存上当前结构体p的地址（不要忘了p是一个指针变量，存的是*p的地址）
//第二轮循环
2.3.声明了一个新的指针变量p，这个指针变量和前面p那个毫无关系。
4.新p的data存上数据，新p的next存上*L的next，
由第一轮循环我们可以知道此时的*L的next储存的是第一轮那个*p的地址，这样第二个p就顺理成章地指向了第一个p。
5.*L的next存上当前结构体p的地址
//第三轮循环
。。。
*/

头插法图例：

基础---单链表的实现（带头）
//尾插法创建单链表
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;            //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}
/*
这些分析默认读者理解了头插法，所以采取简写的形式。
1.创建一个头结点*L
2.创建一个容器r用于后面的移动。
//第一轮循环
3.创建结构体*p
4.存数据
5.看似是*r的next其实是*L的next，事实上两者就是一个东西，因为上文把L指针所储存的地址赋值给了r，L和r指向的是一个东西。
6.像步骤5一样，让r和p指向同一个东西---第一个*p
//第二轮循环
3.创建新结构体*p
4.存数据
5.看似是*r的next其实是步骤一中*p的next，事实上两者就是一个东西，因为上文把第一个p指针所储存的地址赋值给了r，第一个p和r指向的是一个东西。
6.像步骤5一样，让r和p指向同一个东西---第二个*p
//第三轮循环
3.创建新结构体*p
4.存数据
5.看似是*r的next其实是步骤二中*p的next，事实上两者就是一个东西，因为上文把第二个p指针所储存的地址赋值给了r，第二个p和r指向的是一个东西。
6.像步骤5一样，让r和p指向同一个东西---第三个*p
//第四轮循环
。。。
7.循环完毕后，很容易发现，最后一个*p的next是没有值的，我们需要手动添加一个NULL给最后的*p
*/

尾插法图例：

基础---单链表的实现（带头）

1.4遍历单链表
//遍历输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
}
//p只有为NULL的时候，while循环才能被跳出。
//没有破坏原链表，因为p是一个新定义的指针，没有涉及到原链表的指针。
1.5修改单链表
//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
1.6插入新结点
//单链表的插入，在链表的第i个位置插入x的元素
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;         //将前置结点的next给新结点，使其指向原第i个结点。
    pre->next = p;               //使前置结点指向新结点。
  
    return L;
}
1.7删除结点
//单链表的删除，在链表中删除值为x的元素
  
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;					//
        p = p->next;				//这两步操作完成后，pre始终落后p一个结点的身位。
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}
//当循环到目标结点时，也就是while在退出循环的前一次循环中，pre通过循环的第一步指向目标删除节点的前一个结点，p通过循环的第二步，指向了目标删除节点。
//跳出循环后，让前驱节点指向后继结点，从而实现删除的效果。
//这个被删除的结点需要用free()函数来释放内存空间。
1.8完整的单链表代码
#include <stdio.h>
#include <stdlib.h>
 
//定义结点类型
typedef struct Node {
    int data;           //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
    struct Node *next;          //单链表的指针域
} Node,*LinkedList;
 
//单链表的初始化
LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间
    if(L==NULL){    //判断申请空间是否失败
        exit(0);    //如果失败则退出程序
    }
    L->next = NULL;          //将next设置为NULL,初始长度为0的单链表
    return L;
}
 
 
//单链表的建立1，头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
 
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
}
 
 
//单链表的建立2，尾插法建立单链表
 
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
 
    return L;
}
 
 
//单链表的插入，在链表的第i个位置插入x的元素
 
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
 
    return L;
}
 
 
//单链表的删除，在链表中删除值为x的元素
 
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}
 
//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
 
 
//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
} 
 
int main() {
    //创建 
    LinkedList list;
    printf("请输入单链表的数据：以EOF结尾\n");
    printf("以EOF结尾就是在末尾ctrl+z一下(windows系统下)\n");
    list = LinkedListCreatT();
    //list=LinkedListCreatT();
    printList(list);
     
    //插入 
    int i;
    int x;
    printf("请输入插入数据的位置：");
    scanf("%d",&i);
    printf("请输入插入数据的值：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    printList(list);
     
    //修改
    printf("请输入修改的数据：");
    scanf("%d",&i);
    printf("请输入修改后的值：");
    scanf("%d",&x);
    LinkedListReplace(list,i,x);
    printList(list);
     
    //删除 
    printf("请输入要删除的元素的值：");
    scanf("%d",&x);
    LinkedListDelete(list,x);
    printList(list);
 
    return 0;
}

补充知识：成员运算符

基础---单链表的实现（带头）

上一篇：@Reference、@Resource、@Autowired的区别


下一篇：详解MRS CDL整体架构设计