单链表基本算法

单链表基本算法

写在前面

代码语法说明:在C语言语法的基础上使用了C++的 “引用”(&) 特性,后缀名为 .cpp

数据结构

定义单链表的数据结构为:

// 数据结构
typedef struct LNode
{

    int data;
    struct LNode *next;
} LinkList;

几个算法

  1. 已知节点 p,在节点 p 之前插入值。一般在单链表中的插入,都是先获取插入位置之前的一个节点,然后在这个节点之后插入新的节点。但这里是说在一个节点的前面插入新的值,所以本质上还是先在这个节点的后面插入一个新节点,然后做的一个操作是:将新节点的值和这个节点的值作交换。以此达到在前面插入的效果。
   /* 已知p,在p前插入值
   1. p 指向第 idx(idx>=0) 个节点
   2. 构建新节点 s,值为 x,要在 p 之前插入节点s
   3. 在 p 之后插入 s
   4. 交换节点 p 和节点 s 的值即达到效果
   */

   void InsertBefore(LinkList *L, int idx, int x) {
       // p 指向第 idx 个节点
       LinkList *p = L;
       for (; idx>=0; idx--) {
           p = p->next;
       }
       // s 为新建节点
       LinkList *s = (LinkList *) malloc(sizeof(LinkList));
       s->data = x;
       // 将 s 插入到 p 之后
       s->next = p->next;
       p->next = s;
       // 交换 p 和 s 的值
       int temp = p->data;
       p->data = s->data;
       s->data = temp;
   }

  1. 已知 p,删除 p 节点的值。和上一个方法同理,本质上还是删除 p 之后的一个节点,但是先把后面节点的值复制到当前节点,然后再删除,这样就达到了删除当前位置值的效果。
   /* 已知p,删除p
   1. p 指向第 idx(idx>=0) 个节点
   2. 要删除p本身
   3. 将 p 随后一个节点的值复制到 p 中
   4. 删除 p 之后的一个节点
   */

   void DeleteInplace(LinkList *L, int idx) {
       // p 指向第 idx 个节点
       LinkList *p = L;
       for (; idx>=0; idx--) {
           p = p->next;
       }
       // 将 p 随后一个节点的值复制到 p 中
       p->data = p->next->data;
       // 删除 p 随后的一个节点
       p->next = p->next->next;
   }

  1. 链表就地逆置1:更换节点指针域方向。将每一个节点的 next 域指向前一个节点,以此达到转置的效果。
   /* 链表就地逆置1:更换节点指针域方向
   1. 第一个节点(除头节点外)的 next 域置空
   2. 每个节点的 next 域指向前一个节点
   3. 头节点 next 域指向尾节点
   */

   void Reverse1(LinkList *&L) {
       LinkList *p = L->next;
       LinkList *q = p->next;
       LinkList *s;
       p->next = NULL;  // 第一个节点变尾节点
       while (q != NULL) {
           s = q->next;  // 保留下一个节点地址
           q->next = p;
           p = q;
           q = s;
       }
       L->next = p;  // 头节点接原来的尾节点
   }

  1. 链表就地逆置2:头插法逆置。将每一个节点插入到链表的最前面,以此达到转置的效果。
   /* 链表就地逆置2:头插法逆置
   1. 第一个节点(除头节点之外)的 next 域置空
   2. 每个节点插入到头节点后面
   */

   void Reverse2(LinkList *&L) {
       LinkList *p = L->next->next;  // 第二个节点(除头节点外)
       L->next->next = NULL;  // 第一个节点(除头节点外)的 next 域名置空
       LinkList *s;
       while (p != NULL) {
           s = p->next;  // 保留下一个节点地址
           p->next = L->next;
           L->next = p;
           p = s;
       }
   }

  1. 对于递增单链表 L,删除大于等于min,小于等于max之间的节点。
   /* 对于递增单链表 L,删除大于等于min,小于等于max之间的节点
   1. 找到小于 min 的节点 p
   2. 找到大于 max 的节点 q
   3. 释放 p->next 至 q(不包含q) 之间的所有节点的空间
   4. 令 p->next 指向 q
   */

   void delnodes(LinkList *&L, int min, int max) {
       LinkList *p = L->next;
       while (p->next->data < min) {  // 找前边界
           p = p->next;
       }
       LinkList *q = p;
       while (q->next->data <= max) {  // 找后边界
           q = q->next;
       }
       q = q->next;

       LinkList *t = p->next;
       while (t != q) {  // 释放中间所有节点的空间
           LinkList *next = t->next;
           free(t);
           t = next;
       }
       p->next = q;  // 将 p 的 next 指向 q
   }

  1. 对于递增单链表,删除所有值域重复的节点。
   /* 对于递增单链表,删除所有值域重复的节点
   1. 发现一个,删除一个的原则
   2. 在递增单链表中,重复的值肯定都是紧挨着的
   3. p 遍历链表,若 p->next 和 p 的值域相等,则删除 p->next 并释放空间
   */

   void dels(LinkList *&L) {
       LinkList *p = L->next;
       while (p != NULL) {
           if (p->next != NULL && p->data == p->next->data) {  // 删除值域相同的下一个节点
               LinkList *next = p->next->next;
               free(p->next);
               p->next = next;
           }
           else p = p->next;  // 要加入 else 条件,因为删除下一个节点后,当前节点可能和下下个节点是相同的
       }
   }

测试代码

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

// 数据结构
typedef struct LNode
{

    int data;
    struct LNode *next;
} LinkList;

// tools 功能函数
void Print(LinkList *L, char *s) {
    LinkList *p = L->next;  // 这是有头节点的链表
    printf("%s: ", s);
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    putchar('\n');
}
void CreateListR(LinkList *&L, int data[], int n) {
    L = (LinkList *) malloc(sizeof(LinkList));  // 头节点
    LinkList *tail = L;
    for (int i=0; i<n; i++) {
        // 创建新节点
        LinkList *p = (LinkList *) malloc(sizeof(LinkList));
        p->data = data[i];
        p->next = NULL;
        // 节点添加到末尾
        tail->next = p;
        tail = tail->next;
    }
}

// 基本算法(开始)
//...
// 基本算法(结束)

int main(void) {
    // 初始化链表
    // int data[10] = {0,1,2,3,4,5,6,7,8,9};
    int data[10] = {0,1,2,2,2,5,6,6,8,9};
    LinkList *L;
    CreateListR(L, data, 10);
    Print(L, "操作前");

    // InsertBefore(L, 3, 100);
    // DeleteInplace(L, 3);
    // Reverse1(L);
    // Reverse2(L);
    // delnodes(L, 2, 6);
    // dels(L);

    Print(L, "操作后");
    return 0;
}

参考资料

《新编数据结构习题与解析》(李春葆等编著)

发表评论

电子邮件地址不会被公开。 必填项已用*标注