提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

数据结构（3）单链表

2023-02-18 16:42:48 时间

前前后后看了四天左右吧，一方面把单链表过了几遍，另一方面也补全了一些基础，诸如 &引用，结构体指针，封装 等等内容，感觉难点不是代码怎么敲，而是要想明白每个操作的逻辑以及一些容易忽略的边界条件，为什么要有这些边界条件，没有这个条件会影响到哪些特殊情况？想明白这些很重要。

单链表

建表

typedef struct LNode{
    int data;//数据域
    struct LNode *next;//指向下一个结点的指针域
}LNode,*LinkList;

单链表本质就是一个结点指向下一个结点

  • 关于LNode和LinkList，目前的理解：
    • 首先这个结构体表示的是一个结点，结点内有两个成员——数据域和指针域，LNode是这个结构体的一个别名，所以可以用LNode* L，定义一个指向这个结点的指针。
    • LinkList是一个*结构体指针（详情见C结构体），表示LinkList是指向这个结构的指针
LNode * L;
LinkList L;

所以上面这两个语句在含义上是相同的，都表示L是指向这个结构的指针

只不过

  • 使用LinkList时强调这是一个单链表
  • 使用LNode *时强调这是一个结点

头插法建立链表

int HeadInsert(LinkList &L){
    int x;//你要插入的数据
    L = (LNode*) malloc(sizeof (LNode*));
    L->next = NULL;//创建头结点，并初始化为空链表
    LNode *s;
    scanf("%d",&x);
    while(x!=9999) {
        s = (LNode *) malloc(sizeof(LNode *));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return OK;
}

头插，顾名思义就是每次插入新的结点时，都插在头结点的后面，所以对应步骤为

  1. 创建头结点（开空间创建结点，并next指向NULL）
  2. 创建s结点（你要插入元素进去的结点）
  3. 输入插入值，进入循环
    • 为s申请空间
    • s->data = x 插入数据域
    • 通过指针域变换操作把s插到头结点L的后面
    • 输入插入值，开启新一轮循环

插入

int Insert (LinkList &L,int i,int e){
    if(i<1){
        return ERROR;
    }
    LNode* p;
    int j = 0;//p当前指向第j个结点，0就是指向头结点
    p = L;//p先指向头指针
    while(p!=NULL && j<i-1){
        p = p->next;
        j++;
    }
    if(p==NULL){
        return ERROR;//假设一共有8个结点，要在i=10处插，则循环完一遍后j=9，但是链表中第9位没有结点
    }
    LNode *s = (LNode *) malloc(sizeof (LNode*));
    s->next = p->next;
    p->next = s;
    s->data = e;
    return OK;
}

找到插入位置的前一个节点p，新建s插进去即可

注意边界条件：p == NULL 的情况（你要进入位置的前一个结点是空结点）

后插(在指定结点的后面插入)

int InsertNext(LNode *p,int e){
    if(p == NULL){
        return ERROR;//再议
    }
    LNode *s = (LNode*) malloc(sizeof (LNode*));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
  • 因为强调的是在一个结点后面插，所以函数的形参是LNode*类型的
  • 然后申请空间插入即可

前插(在指定结点之前插入)

int InsertPrior (LNode *p,int e){
    if(p == NULL){
        return ERROR;
    }
    LNode *s;
    s = (LNode *) malloc(sizeof (LNode*));
    if(s == NULL){
        return ERROR;//内存分配失败，是每个场景都可能出现的问题
    }
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return OK;
}

单链表只能窥探一个指定结点之后的所有结点，之前的结点是未知的，所有想要在一个结点的前面插入一个元素，就要进行一波偷天换日，具体步骤如下：

  • 新建结点s，通过指针域变换插入到p结点的后面
  • s的数据域变为p的数据域
  • p的数据域变为要插入的e

删除

int Delete(LinkList &L,int i,int *e){
    if(i<1){
        return ERROR;
    }
    LNode *p;
    int j = 0;
    p = L;
    if(p!=NULL && j<i-1){
        p = p->next;
        j++;
    }
    if(p == NULL){	
        return ERROR;//p是头结点
    }
    if(p->next == NULL){
        return ERROR;//要删除的结点不存在
    }
    LNode *s = p->next;//为什么不用开空间：目前理解：插入是新插的结点，是新结点，所以需要申请空间，这里只是定义s就是p的后继结点，原本就有
    *e = s->data;
    p->next = s->next;
    free(s);
    return OK;
}

找到要删除结点的前一个结点p，删除它的后继s即可

  • 定义s就是p的后继结点，原本就有，不需要申请空间

边界情况

  • i < 1：输入i值不合法
  • p->next == NULL：要删除的结点不存在

删除指定结点

int Deletespecial(LNode *p){
    if(p == NULL){
        return ERROR;
    }
    LNode *s = p->next;//4
    p->data = s->data;//p不能是最后一个结点//3变为4
    p->next = s->next;//3的后面是5
    free(s);//删除原本的4
    return OK;
}

按位查找

int GetElem(LinkList L,int i,int *e){
    if(i<0){
        return NULL;
    }
    LNode *p;
    int j = 0;
    p = L;
    while(p!=NULL && j<i){
        p = p->next;
        j++;
    }
    *e = p->data;
    printf("第%d个元素是%d\n",i,*e);
    return OK;
}

循环找到第i个结点返回其值即可

按值查找

int LocateElem(LinkList &L,int e){
    LNode *p;
    int j = 0;
    p = L;
    while(p!=NULL){
        p = p->next;
        j++;
        if(p->data == e){
            break;
        }
    }
    printf("值为%d的结点的位序是%d\n",e,j);
    return j;
}

从第一个结点开始循环，直到p->data == e时结束循环，返回j值

输出

int Print(LinkList L){
    LNode *p = L->next;//p是第一个结点
    while(p!=NULL){
        printf("%d\t",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

主函数

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

int main (){
    LinkList L;
    int e;
    HeadInsert(L);//输入1,2,3
    Delete(L,2,&e);//删除2
    Insert(L,2,4);//在第2位插入4:    3 4 1
    InsertNext(L->next,5);//在第2位后面插入5     3 5 4 1
    InsertPrior(L->next->next,6);//在第2位前面插入6    3 6 5 4 1
    Deletespecial(L->next->next->next->next);//删除第四个结点
    InsertNext(L,9);
    Print(L);
    GetElem(L,2,&e);
    LocateElem(L,5);
}

运行：初始插入1,2,3

封装

不难发现，有一些操作的具体实现可以引用另一个操作，直接举栗子?，插入操作就是先找到插入结点的前一个结点，再在它的后面插一个新的结点，这不就是GetElem + InsertNext，就是先按值查找再后插，所以我们注意到，在后插操作有一个边界条件是

if(p==NULL){
    return ERROR;
}

当时的我一直在想，为什么输入的结点还可以为NULL，但如果把按位查找和后插操作直接拿来放在插入操作中，可以写为：

//使用前需要声明这两个函数
int InsertNext(LNode *p,int e);
LNode *GetElem(LinkList L,int i);

int Insert (LinkList &L,int i,int e){
    if(i<1){
        return ERROR;
    }
    LNode *p = GetElem(L,i-1);//这里需要把函数的返回值改为返回结点类型
	InsertNext(p,e);
}

//把按位查找函数的返回值改为返回结点类型
LNode * GetElem(LinkList L,int i){
    if(i<0){
        return NULL;
    }
    LNode *p;
    int j = 0;
    p = L;
    while(p!=NULL && j<i){
        p = p->next;
        j++;
    }
    return p;
}

那么看一下按位查找函数 ，如果i<0，会返回NULL值，就会出现p==NULL传给后插 操作，那么这个边界条件的作用就会显现。

相关文章