MENU

数据结构 - 单链表

March 10, 2021 • Read: 291 • 数据结构

单链表定义

单链表

定义单链表

struct LNode{  // 节点
    ElemType data;       // 每个节点存放一个数据元素
    struct LNode *next;    // 指针指向下一个节点 指针域
};

/**
 * 增加一个新的节点:在内存中申请一个节点所需要的空间,并用指针p指向这个节点
**/
struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));

C语言:

typedef关键字 -- 数据类型重命名

typedef <数据类型> <别名>

如:typedef int zhengshu

struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));

//可以写为如下:

typedef struct LNode LNode
LNode * p =(LNode *) malloc(sizeof(LNode));

在《数据结构》中定义的单链表代码如下:

typedef struct LNode{
    ELemType data;       // 每一个节点存放一个数据元素
    struct LNode *next; // 每个节点存放一个数据元素
}LNode, *LinkList;

// 以上代码实际上时以下代码的简化

struct LNode{
    ElemType data;      // 每个节点存放一个数据元素
    struct * next         // 指针指向下一个节点
};

typedef struct LNode LNode;
typedef struct *LinkList;

// 要表示一个单链表的时,只需要声明一个头指针L,指向单链表的第一个节点
// LNode * L;  声明一个指向单链表第一个结点指针
// 或:LinkList L;  声明一个指向单链表第一个节点的指针

初始化单链表:

// 不带头节点的单链表
typedef struct LNode{
    ElemType data;
  struct LNode *next;
}LNode,*LinkList;

// 初始化一个空的单链表
bool InitList(LinkList &L){
    L =NULL;  // 空表,暂时没有节点, 防止有脏数据
    return true;
}

void test(){
    LinkList L; // 声明一个单链表的指针
    // 初始化一个单链表
    InitList(L);
    //...后续代码
}
   // 带头节点的单链表

  typedef struct LNode{
      ELemType data;
      struct LNode * next;
  }LNode,*LinkList;
  
  // 初始化一个单链表(带头节点)
  bool InitList(LinkList &L){
      L = (LNode*)malloc(sizeof(LNode)); // 给头节点分配一块内存
      if(L==NULL){ // 内存不足,分配失败
          return false;
      }
      L->= NULL; // 在头节点之后暂时还没有节点
      return true;
  }
  
  void test(){
      
      LinkList L; // 声明一个单链表的指针
      InitList(L) // 初始化单链表
  }

单链表的插入

按位序插入(带头节点)

ListInsert(&L,i,e):插入操作。在表中的第i个位置插上指定元素e。

找到第i - 1 个节点,将新节点插入其后

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct LNode {
    int data;
    struct LNode* next;
}LNode,*LinkList;

// 在第i个位置插入元素e(带头节点)
bool ListInsert(LinkList &L, int i, int e) {
    if (i<1) {
        return false;
    }
    LNode *p; // 指针p指向当前扫面到的节点
    int j = 0; // 当前p指向的是第几个节点
    p = L; // L指向头节点,头节点是第0个节点(不包含数据)
    while (p!=NULL&&j<i-1) { // 循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if (p == NULL) { // i的值不合法
        return false;
    } 
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s; // 将节点s连到p之后
    return true;
}
// 初始化单链表
bool Init(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L==NULL) {
        printf("内存不足,分配失败!");
        return false;
    }
    L->next = NULL; // 后面没有节点了
    printf("分配成功!");
    return true;
}
int main() {

    LinkList L; // 声明一个单链表的指针
    Init(L); // 初始化单链表
    ListInsert(L, 1, 1);
    return 0;
}

平均时间复杂度为O(n)

按位序插入(不带头节点)

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

typedef struct LNode {
    int data;
    struct LNode*next;
}LNode,*LinkList;

bool ListInsert(LinkList &L,int i,int e) {
    if (i<1) { // 插入第1个节点的操作和其他的节点操作不同
        return false;
    }
    if (i == 1) {
        LNode *s = (LNode*)malloc(sizeof(LNode)); // 分配一块内存空间来创建节点
        s->data = e;    //将插入的数据赋值到内存空间中
        s->next = L;    //将新建的内存指针指向头节点
        L = s;            // 头指针指向新节点
        return true;
    }
    LNode *p;            // 指针p指向当前扫描的节点
    int j = 1;            // 当前p指向的是第几个节点
    p = L;                // p指向第1个节点(注意:不是头节点)
    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;
}
// 初始化单链表
bool Init(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L==NULL) {
        printf("内存不足,分配失败!");
        return false;
    }
    L->next = NULL; // 后面没有节点了
    printf("分配成功!");
    return true;
}
int main() {

    LinkList L; // 声明一个单链表的指针
    Init(L); // 初始化单链表
    ListInsert(L, 1, 1);
    return 0;
}

如果不带头节点,则插入、删除第1个元素时,需要更改头指针L

指定节点的后插操作

image-20210209173741960

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

// 后插操作:在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保存数据元素
    s->next = p->next;
    p->next =s;   // 将节点s连到p之后
    return true;
}
typedef struct LNode {
    int data;
    struct LNode*next;
}LNode,*LinkList;

// 在第i个位置插入元素e(带头节点)
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p;    // 指针p指向当前扫描到的节点
    int j = 0;    // 当前p指向的是第几个节点
    p = L;        // 指向头结点,头结点时第0个节点(不保存数据)
    while (p != NULL&&j<i-1) {
        p = p->next;
        j++;
    }
    if (p==NULL) {  // 输入的i值不合法
        return false;
    }
    /*LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;*/

    // 以上注释代码可以用
    return InsertNextNode(p, e);

}

指定节点的前插操作

bool InserPriorNode(LNode *p,ELemType e)

image-20210210122147731

上面那种情况如何能够找到p节点的前驱节点呢?

所以需要传入一个头指针,如下:

bool InsertPriorNode (LinkList L,LNode *p,ElemType e)

image-20210210122547650

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode,*LinkList;

// 前插操作:在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->data = e;
    p->next = s;        //    新节点s连到p之后
    s->data = p->data;  // 将p中元素复制到s中
    p->data = e;        // p中元素覆盖为e    
    return true;

}

image-20210210123645334
在要插入之前的元素中的数据和指针重新指向,如上图所示;

单链表的删除

按位序删除(带头节点)

ListDelete(&L,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值

找到第i-1个节点,将其指针指向第i+1个节点

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

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode,*LinkList;

// 按位序删除(带头节点)
bool ListDelete(LinkList &L, int i, int &e) {
    if (i<1) {
        return false;
    }
    LNode *p;    // 指针p指向当前扫描的节点
    int j = 0;  // 指针p指向的是第几个节点
    p = L;        // 指向头节点,头节点是第0个节点(不保存数据)
    while (p!=NULL&&j<i-1) {    // 循环找到第 i-1个节点
        p = p->next;
        j++;
    }
    if (p==NULL) { // i值不合法
        return false;
    }
    if (p->next==NULL) {    // 第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;        // 令q指向被删除节点
    e = q->data;            // 用e返回元素的值
    p->next = q->next;        // 将*q节点从链中“断开”
    free(q);                // 释放节点的存储空间
    return true;            // 删除成功
}

​ 时间复杂度

​ 最坏、平均的时间复杂度 = O(n)

​ 最好时间复杂度 = O(1)

指定节点删除

bool DeleteNode(LNode *p)

image-20210210125945525

删除节点p:需要修改前驱节点的next指针

  • 方法1:传入头指针,循环寻找p的前驱节点
  • 方法2:偷天换日
bool DeleteNode(LNode *p){
    if (p==NULL){
        return false;
    }
    LNode *q=p->next;         // 令q指向*p的后继节点
    p->data=p->next->data;     // 和后继节点交换数据域
    p->next=q->next;        // 将*q节点从链中"断开"
    free(q);                // 释放后继节点的存储空间
    return true;
}

单链表的查找

按位查找

// 按位查找,返回第i分元素(带头节点)
LNode * GetElemt(LinkList L,int i){
    if(i<0){
        return NULL;
    }
    LNode *p;         // 指针p指向当前扫描到的节点
    int j = 0;         // 指向p指向的是第几个节点
    p = L;            // 指向头节点,头结点时第0个节点(不存数据)
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

image-20210310172418474

按值查找

// 按值查找,找到数据与 == e 的节点
LNode* LocateELem(LinkList L,ElemType e){
    LNode *p = L->next;
    // 从第1个节点开始查找数据域中e的节点
    while(p!=NULL&&p->data!=e){
        p = p->next;
    }
    return p;        // 找到后返回该节点指针,否则返回NULL
}

单链表的长度

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

单链表的建立

如果给你很多元素(ElemType),要把它们存在一个单链表里边,怎么操作?

  • Step1:初始化一个单链表
  • Step2:每次取一个数据元素,插入到表尾/表头

尾插法建立单链表

typedef struct LNode{    // 定义 单链表节点类型
    ElemType data;        // 每一个节点存放一个数据元素
    struct LNode *next; // 指针指向下一个节点
}LNode,*LinkList;

// 初始化一个单链表(带头节点)
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); //    分配一个头节点
    if(L==NULL){
        return false;    // 内存不足分配失败
    }
    L->next =NULl;        // 头节点之后还没有节点
    return true;
}

void test(){
    LinkList L;     // 声明一个指向单链表的指针
    // 初始化一个空表
    InitList(L);
    
   // 后续操作
}

设置length 记录链表的长度

while(){
    // 每次取一个数据元素e;
    ListInsert(L,length+1,e); // 插到尾部
    length++;
}

具体代码如下:

LinkList List_TailInsert(LinkList &L){ // 正向建立单链表
    int x;                               // 设ElemType为整形
    L =(LinkList)malloc(sizeof(LNode));// 建立头节点
    LNode *s,*r=L;                        // r为表尾指针
    scanf("%d",&x);                        // 输入节点的值
    while(X!9999){                        // 输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r = s;                            //  r指向新的表尾点
        scanf("%d"&x);
    }
    r->next =NULL;                        // 表尾节点置空
    return L;
    
}

头插法建立单链表

LinkList List_HeadInsert(LinkList &L){    // 逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));    // 创建头节点
    L->next =NULL;                        // 初始为空表
    scanf("%d",&x);                        // 输出插入的元素
    while(x!9999){                        // 当输入9999表示结束
        s(LNode *)malloc(sizeof(LNode));// 创建新节点
        s->data=x;
        s->next=L->next;
        L->next=s;                        // 将新节点插入到表中,L为头指针
        scanf("%d",&x)
    }
    return L
}

头插法可以用作单链表的逆置

版权声明:文章转载请注明来源,如有侵权请联系删除!

Last Modified: April 12, 2021
Archives QR Code Tip
QR Code for this page
Tipping QR Code