数据结构和算法（二）单链表与单向循环链表的实现

孔雨露
2,245 阅读16分钟

数据结构和算法（1）线性表实现

数据结构和算法（2）单向循环链表的创建插入删除实现

数据结构和算法（3）双向链表与双向循环链表的实现

数据结构和算法（4）链表相关面试题

数据结构和算法（5）栈和队列的操作和实现

数据结构和算法（6）队列的操作和实现

@TOC

上一篇博客“线性表” 详细讲解了顺序表和单链表的基本操作。本篇博客主要讲解对于循环链表的基本操作。

线性表汇总

1. 线性表概要

我们先来总的看一下线性表主要有哪些操作，如下图：

线性表的主要操作

红框里面的内容是本篇博客主要讲解的内容，后面的博客会继续讲解双向链表，循环双向链表等。

先回顾一下单链表

链表是一种线性表, 也是一种存储数据的数据结构.如下图：这种的一个节点中包含自身数据以及指向下一个节点的位置,一个嵌套着下一个. 这中结构就称之为链表.

链表结构
链表

2. 单向循环链表

本篇博客demo点击这里下载：单向循环链表demo

单向循环链表结点的定义跟单链表一样，区别就是尾结点执行头结点，形成一个环。 如下图（1）表示一个单向循环链表，由尾结点指向头结点：

图1：单向循环链表

我们再来回顾一下单向链表的结构图：如下图：图2

图2：单向链表

我们对比看，可以明显的看出，单向循环链表和单向链表的区别，仅仅是多了一个尾结点指针指向头结点的过程，他们的结点定义是一样的。

  • 单向循环链表结点定义如下：
typedef int KStatus;
typedef int KElementType;
typedef struct KNode {
    KElementType data;//用来存储一个int数据(具体数据类型根据开发实际情况而定,此处使用int)
    struct KNode *next;//指向下一个节点的指针
} Node;
typedef struct KNode * LinkList;

2.1 建表

单向循环链表的建表过程跟单链表非常相似。我们一般都采用尾部插入法，这样比较符合我们的业务逻辑，尾部插入法的得到的数据和我们定义的顺序是一样的，如果采用头部插入法，则得到的是一个逆序的表。

如我们初始化链表时，只是有一个头结点，它的next指针指向它自己，如下图3是一个空链表：

图3：空链表

我们采用尾部插入法，分别插入数据9，16，18，20 就得到了下面的链表，如图4：

图4：非空单向循环链表

我们插入建表的过程如下：

分为两种情况：① 第一次开始创建; ②已经创建,往里面新增数据

判断是否第一次创建链表：

YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L); NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);

我们细分一下过程如下：

  1. 我们先初始化得到一个空链表如下：
    图3：空链表
  2. 插入1个结点后如下：

第二步：插入一个结点
3. 插入2个结点后如下：
第三步：插入2个结点

代码实现如下：

  • 方式1：
//1. 创建循环链表
//2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
/* 1. 判断是否第一次创建链表
   YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
   NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
 */
KStatus createCircleList(LinkList *L) {

    int item;
    LinkList temp = NULL;
    LinkList target = NULL;

    printf("输入节点的值，输入0结束\n");
    while (1) {
        scanf("%d",&item);

        if(item == 0) break;

        //判断，如果输入的链表是空，则创建一个新结点，并且使其next指针指向自己  (*head)->next=*head;
        if(NULL == *L) {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
        } else {
            //如果输入的链表不为空，则寻找链表的尾结点，是尾结点的next=新节点。新节点的next指向头节点
            for (target = *L; target->next != *L; target = target->next);

            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return ERROR;

            //结点赋值，并插入尾部
            temp->data = item;
            //1.新节点指向头节点
            temp->next = *L;
            //2.尾节点指向新节点
            target->next = temp;

        }
    }

    return OK;
}

上面的代码我们通过一个for循环来查找到链表的尾部结点，实际上我们初始化链表的时候，可以用一个指针r专门指向尾结点，这样我们就没有必要循环遍历去查找尾结点了，修改后的代码如下：

  • 方式2：
KStatus createCircleList2(LinkList *L) {

    int item;
    LinkList temp = NULL;
    //LinkList target = NULL;
    //增加一个赋值指针，指向尾结点
    LinkList r = *L;

    printf("输入节点的值，输入0结束\n");
    while (1) {
        scanf("%d",&item);

        if(item == 0) break;

        //判断，如果输入的链表是空，则创建一个新结点，并且使其next指针指向自己  (*head)->next=*head;
        if(NULL == *L) {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            //记录尾结点
            r = *L;
        } else {
            //如果输入的链表不为空，则寻找链表的尾结点，是尾结点的next=新节点。新节点的next指向头节点
            //for (target = *L; target->next != *L; target = target->next);
            //这里已经用r指向了尾结点，不需要查找了。

            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return ERROR;

            //结点赋值，并插入尾部
            temp->data = item;
            //1.新节点指向头节点
            temp->next = *L;
            //2.尾节点指向新节点
            r->next = temp;

            //移动r指针，保存r指针一直指向尾结点
            r = temp;

        }
    }

    return OK;
}

2.2 遍历

循环链表的遍历很简单，一个do while 语句就做完了，如下遍历代码:

// 2.遍历循环链表
void traverseCircleList(LinkList L) {
    //判断链表是否为空
    if(!L) {
        printf("链表为空！\n");
        return;
    }

    LinkList temp;
    temp = L;
    do {
        printf("%6d", temp->data);
        temp = temp->next;
    }while (temp != L) ;
    printf("\n");
}

2.3 插入

单向循环链表的插入也跟单向链表插入相似，只是多了尾部结点指针特殊处理。

单向循环链表的插入又分为两种情况：

  • 第一种情况：插入位置在首结点，需要单独特殊处理
  • 第二种情况: 其他位置（非首结点）可以统一处理

为了更好的理解，下面我们通过图来区分两种情况的插入。

第一种情况：插入位置在首结点，如下图（图2.3.1）：

图2.3.1：情况1 插入位置在首结点

根据上图，我们来分析一下第一种情况的插入过程大致如下： 首先我们创建一个新结点，赋值为2， 然后，我们用下面三步完成结点2的插入 1、将新创建的结点 next 指向原来的首元结点。（上图对应标号2，我们用结点X的next指针指向结点A） 2、将尾结点 next 指向新创建的结点。（上图对应标号3，将尾结点C的next指针指向新的头结点X） 3、将L指针指向新创建的结点。（上图对应标号4 ，将L指向新的首结点X）

完成插入后得到：

图2.3.2：情况1 插入位置在首结点，插入完成

注意：这里步骤1，2的顺序不能更换，假设我们先指向步骤2，再执行步骤1，那么我们原来的首节点1，就会丢失，找不到了。我们链表插入的最重要的原则就是，保证链表不要丢失结点。断开结点前必须有指针指向即将要断开的结点，这样才能保证不丢失结点。

第二种情况: 其他位置（非首结点），如下图：

图2.3.3：情况3 插入位置在非首结点

如上图表示的第二种情况，在非首节点插入新创建的结点X 如上图所示，我们同样先新建一个结点X，假设我们要插入在B和C之间，那么我们首先需要找到C结点的前一个结点B，然后再用同样的3步完成插入操作。 插入过程： 1、找到插入结点前一个结点(B结点)，（我们用target指针指向B.） 2、将新创建结点X的next 指向插入位置后面的结点(X->next = C) 3、然后再把插入位置前面的结点next 指向新创建的结点（B->next= X）

完成插入后我们得到如下：

图2.3.3：情况3 插入位置在非首结点，插入完成

插入结点的实现代码如下：

// 3. 循环链表插入元素
// L : 链表指针
// place: 要插入的位置
// data : 要插入的数据
KStatus insertElement(LinkList *L, int place, int data) {

    LinkList temp, target;
    int I;

    //先判断位置是否为首结点，在首结点需要单独处理
    if (place == 1) {
        //1. 创建一个新结点
        temp = (LinkList)malloc(sizeof(Node));
        //判断内存是否分配成功
        if (! temp) return ERROR;
        //赋值
        temp->data = data;

        //2. 找到链表的最后一个结点，尾结点
        for(target = *L; target->next != *L ; target = target->next);

        //3.找到尾结点，插入到尾结点后面
        //3.1 让新结点的next,指向新的头结点
        temp->next = *L;
        //3.2 让尾结点的next指向新的结点，这样新的结点成了新的尾结点。
        target->next = temp;
        //3.3 让头指针指向新的尾结点
        *L = temp;

    } else { //其他位置
        //1. 创建一个新结点
        temp = (LinkList)malloc(sizeof(Node));
        //判断内存是否分配成功
        if (! temp) return ERROR;
        //赋值
        temp->data = data;

        //2. 找到链表的第place - 1 的位置
        for(i = 1, target = *L; target->next != *L && i != place - 1 ; target = target->next, i++);

        //3. 指向插入操作，将新结点插入到place位置
        //3.1 新结点的next 指向target原来的next位置 ;
        temp->next = target->next;
        //3.2 插入结点的前驱指向新结点
        target->next = temp;
    }
    return OK;
}

2.4 删除

删除跟插入一样，也是分为两种情况：

  • 第一种情况：删除首结点，需要特殊处理。
  • 第二种情况：删除其他结点，非首结点，可以统一处理。

对于第一种情况（删除首结点）：

图2.4.1：删除首结点

我们来分析一下过程： 如上图，我们要删除首结点A，我们先要找到尾结点C。 然后，将尾结点C的next,指向新的首结点B。（C->next = B） 然后，将L指向新的首结点B。(*L = B) 最后释放A结点的内存。

第二种情况删除非首结点：

图2.4.2：删除非首结点

我们删除非首结点的话就可以统一处理，如上图，假设我们删除结点X, 那我们先要找到X的上一个结点B。 然后，将X的上一个结点也就是B的next执行 X的下一个结点也就是C。 （B->next = C 或者 B->next = B->next->next） 最后我们释放X结点的内存。

实现代码如下：

// 4. 循环链表删除元素
// 删除第place位置的元素
// L : 链表指针
// place: 要删除的位置
KStatus deleteElement(LinkList *L, int place) {

    LinkList temp, target;
    int I;
    //temp 指向链表首元结点
    temp = *L;
    //如果为空链表，则结束
    if (!temp) return ERROR;

    //判断是否是首节点，如果是首结点需要单独特殊处理
    if (place == 1) {
         //①.如果删除到只剩下首元结点了,则直接将*L置空;
        if((*L)->next == (*L)) {
            *L = NULL;
            return OK;
        }

        //②.链表还有很多数据,但是删除的是首结点;
        // 2.1 先要找到尾结点，
        for (target = *L; target->next != *L; target = target->next) ;
        // 2.2 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
        temp = *L;
        *L = (*L)->next;
        // 2.3 新结点做为头结点,则释放原来的头结点
        target->next = *L;
        //释放资源
        free(temp);
    } else { //其他位置，统一处理
        //遍历找到第place-1个位置
        for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) {
            //找到删除结点前一个结点target
            //用temp指向要删除的元素，第place位置
            temp = target->next;
            //使得target->next 指向下一个结点
            target->next = temp->next;

            //释放内存
            free(temp);
        }
    }
    return OK;
}

2.5 查询

查询非常结点，一个while循环就弄完了，实现代码如下：

//5. 循环列表查询
// 返回位置的索引值
int queryValue(LinkList L , int value) {
    int i = 1;
    LinkList p = L;

    //寻找链表中的结点 data == value
    while (p->data != value) {
        I++;
        p = p->next;
    }
    //当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
    if (p->next == L && p->data != value) return -1; //没有找到
    //找到了元素，返回下标
    return I;
}

2.6 单元测试

// 6. 单元测试
void test() {
       LinkList head;
        int place,num;
        int iStatus;

        iStatus = createCircleList(&head);
        //iStatus = createCircleList2(&head);
        printf("原始的链表：\n");
        traverseCircleList(head);

    //    printf("输入要插入的位置和数据用空格隔开：");
    //    scanf("%d %d",&place,&num);
    //    iStatus = insertElement(&head,place,num);
    //    traverseCircleList(head);

        printf("输入要删除的位置：");
        scanf("%d",&place);
        deleteElement(&head,place);
        traverseCircleList(head);


        printf("输入你想查找的值:");
        scanf("%d",&num);
        place = queryValue(head,num);
        if(place!=-1)
            printf("找到的值的位置是place = %d\n",place);
        else
            printf("没找到值\n");
}

2.7 完整代码实现

//
//  main.c
//  004_CircularLinedList
//
//  Created by 孔雨露 on 2020/4/5.
//  Copyright © 2020 Apple. All rights reserved.
//

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

/*
 4.1 循环链表创建!
 2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
 
 1. 判断是否第一次创建链表
    YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
    NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
 */
Status CreateList(LinkList *L){

    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while(1)
    {
        scanf("%d",&item);
        if(item==0) break;
        
          //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己  (*head)->next=*head;
        if(*L==NULL)
        {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L)exit(0);
            (*L)->data=item;
            (*L)->next=*L;
        }
        else
        {
           //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
            
            for (target = *L; target->next != *L; target = target->next);
            
            temp=(LinkList)malloc(sizeof(Node));
            
            if(!temp) return ERROR;
            
            temp->data=item;
            temp->next=*L;  //新节点指向头节点
            target->next=temp;//尾节点指向新节点
        }
    }
    
    return OK;
}

Status CreateList2(LinkList *L){
    
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    LinkList r = NULL;
    printf("请输入新的结点, 当输入0时结束!\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) {
            break;
        }
        
        //第一次创建
        if(*L == NULL){
            
            *L = (LinkList)malloc(sizeof(Node));
            if(!*L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            r = *L;
        }else{
            
            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return  ERROR;
            temp->data = item;
            temp->next = *L;
            r->next = temp;
            
            r = temp;
        }
        
    }
    
    return OK;
}



//4.2 遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值
void show(LinkList p)
{
    //如果链表是空
    if(p == NULL){
        printf("打印的链表为空!\n");
        return;
        
    }else{
        LinkList temp;
        temp = p;
        do{
            printf("%5d",temp->data);
            temp = temp->next;
        }while (temp != p);
        printf("\n");
    }
    
}

//4.3 循环链表插入数据
Status ListInsert(LinkList *L, int place, int num){
    
    LinkList temp ,target;
    int I;
    if (place == 1) {
        
        //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 找到链表最后的结点_尾结点,
        //3. 让新结点的next 执行头结点.
        //4. 尾结点的next 指向新的头结点;
        //5. 让头指针指向temp(临时的新结点)
        
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        
        for (target = *L; target->next != *L; target = target->next);
        
        temp->next = *L;
        target->next = temp;
        *L = temp;
        
    }else
    {
        
        //如果插入的位置在其他位置;
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
        //3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
        //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
        
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        
        for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
        
        temp->next = target->next;
        target->next = temp;
    }
    
    return OK;
}

//4.4 循环链表删除元素
Status  LinkListDelete(LinkList *L,int place){
    
    LinkList temp,target;
    int I;
    //temp 指向链表首元结点
    temp = *L;
    if(temp == NULL) return ERROR;
    
    
    if (place == 1) {
        
        //①.如果删除到只剩下首元结点了,则直接将*L置空;
        if((*L)->next == (*L)){
            (*L) = NULL;
            return OK;
        }
        
        
        //②.链表还有很多数据,但是删除的是首结点;
        //1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
        //2. 新结点做为头结点,则释放原来的头结点
        
        for (target = *L; target->next != *L; target = target->next);
        temp = *L;
        
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    }else
    {

        //如果删除其他结点--其他结点
        //1. 找到删除结点前一个结点target
        //2. 使得target->next 指向下一个结点
        //3. 释放需要删除的结点temp
        for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;

            temp = target->next;
            target->next = temp->next;
            free(temp);
        }
    
    return OK;
    
}


//4.5 循环链表查询值
int findValue(LinkList L,int value){
    
    int i = 1;
    LinkList p;
    p = L;
    
    //寻找链表中的结点 data == value
    while (p->data != value && p->next != L) {
        I++;
        p = p->next;
    }
    
    //当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
    if (p->next == L && p->data != value) {
        return  -1;
    }
    
    return I;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    LinkList head;
    int place,num;
    int iStatus;
    
    //iStatus = CreateList(&head);
    iStatus = CreateList2(&head);
    printf("原始的链表：\n");
    show(head);
    
//    printf("输入要插入的位置和数据用空格隔开：");
//    scanf("%d %d",&place,&num);
//    iStatus = ListInsert(&head,place,num);
//    show(head);

    printf("输入要删除的位置：");
    scanf("%d",&place);
    LinkListDelete(&head,place);
    show(head);
    
    
    printf("输入你想查找的值:");
    scanf("%d",&num);
    place=findValue(head,num);
    if(place!=-1)
        printf("找到的值的位置是place = %d\n",place);
    else
        printf("没找到值\n");
    
    return 0;
}

输出结果：

Hello, kongyulu!
请输入新的结点, 当输入0时结束!
1
2
3
4
5
6
0
原始的链表：
    1    2    3    4    5    6
输入要删除的位置：1
    2    3    4    5    6
输入你想查找的值:4
找到的值的位置是place = 3
Program ended with exit code: 0

avatar
文章
阅读
粉丝

友情链接：