数据结构与算法

数算---线性表（二）

2023-04-23  本文已影响0人  Lcr111

前言

上篇文章数算---线性表（一）我们介绍了线性表中的顺序表和单向链表，这篇文章我们继续将剩余的几种链表一一做个介绍及实现。（代码语言为C语言）

单向循环链表

单向循环链表与单向链表不同的就是尾结点的next指针指向头结点（如果有头结点，否则就是首元结点），而不是指向NULL。这篇文章中单向循环链表我们不用添加头结点，即第一个位置为首元结点（如下图非空表）。

单向循环链表
准备工作

准备工作代码和上篇单向链表一样。

#include <stdio.h>
#include "stdlib.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;
初始化

我们采用Xcode调试框输入结点数据生成结点的方式来构建一个循环链表。此处没有创建头结点。

Status CreateList(LinkList *L){
    int item;
    LinkList temp = 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;//尾结点next指向首元结点
            r->next = temp;//此时temp为尾结点
            
            r = temp;//方便下个数据进来用
        }
    }
    return OK;
}
插入数据

循环链表的数据插入我们需要注意的是插入的位置，如果插入位置是第一个，即插入首元结点，以及插入位置为链表中其他位置，我们分这两种情况分析。


插入首元结点
插入其他位置 
Status ListInsert(LinkList *L, int place, int num){
    LinkList temp, target;
    int i;
    if(place == 1){
        //创建新结点（要插入的结点）
        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{
        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;
}
遍历数据

循环链表适合用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");
    }
}
删除数据

删除结点需要注意的是所删除位置是第一个还是其他位置，删除位置为1是还需要判断是否当前链表只有一个结点的情况，删除后链表就为空表。

Status LinkListDelete(LinkList *L, int place){
    LinkList temp,target;
    int i;
    temp = *L;
    if(temp == NULL) return  ERROR;
    if(place == 1){
        if((*L)->next == (*L)){
            (*L) = NULL;
            return OK;
        }
        //找到尾结点
        for (target = *L; target->next != *L; target = target->next);
        temp = *L;
        //将原来第二个结点作为首元结点
        *L = (*L)->next;
        //重新将尾结点指向首元结点
        target->next = *L;
        free(temp);
    }else{
        //找到要删除的前一个结点
        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;
}
查找数据

查找数据在链表中的位置，需要注意的是循环遍历链表的循环跳出条件，要考虑到链表中找不到的情况。

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;
    }
    //此时 可能 第i个结点p即为要查找的结点，但需要注意p->next != L 也会跳出循环
    //所以需要排除尾结点不满足的情况，也就是此链表没匹配到要找的数据
    if(p->next == L && p->data != value){
        return -1;
    }
    return i;
}

双向链表

不同于单向链表结构，双向链表的结点多个一个指向前驱结点的指针域。这样从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。


双向链表结点
创建链表

准备代码与上方有所差别，结点的结构需要增加一个指针域。

typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;
//创建链表
Status CreateLinkList(LinkList *L){
    *L = (LinkList)malloc(sizeof(Node));
    if(*L == NULL) return  ERROR;
    //头结点
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    
    LinkList p = *L;
    for (int i = 0; i < 10; i ++) {
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        
        p->next = temp;
        temp->prior = p;
        p = p->next;
    }
    return OK;
}
插入数据

双向链表插入数据和单向链表插入的原理是一样的，就是需要判断是否插入链尾和前驱指向的问题。注意点就是先将新结点后驱指向后面的结点，先建立与后面结点的关系，再来处理与前驱结点的关系。


双向链表插入 
Status ListInsert(LinkList *L, int i , ElemType data){
    
    if(i < 1) return ERROR;
    
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->prior = NULL;
    temp->next = NULL;
    temp->data = data;
    
    LinkList p = *L;//带有头结点的
    //找到第i-1个位置的结点
    for (int j = 1; j < i && p; j ++) {
        p = p->next;
    }
    //i 3
    //j 1 2 3
    //p 1 2
    //此时p为i-1 处的结点
    //插入位置大于链表的长度
    if(p == NULL){
        return ERROR;
    }
    //插入到尾部，直接接上去就可以
    if(p->next == NULL){
        p->next = temp;
        temp->prior = p;
    }else{
        //插入到位置为非尾部
        p->next->prior = temp;
        temp->next = p->next;
        p->next = temp;
        temp->prior = p;
    }
    return OK;
}
删除数据

删除数据就是插入的逆向操作，需要先找到删除位置的前一个结点，然后将它与删除位置后一个结点建立联系，最后需要释放所删除结点的内存。


双向链表删除 
Status ListDelete(LinkList *L, int i, ElemType *e){
    int k = 1;
    LinkList p = (*L);
    if(*L == NULL){
        return ERROR;
    }
    //找到第i-1个结点
    while (k < i && p != NULL) {
        p = p->next;
        k ++;
    }
    if(k > i || p == NULL){
        return ERROR;
    }
    
    LinkList delTemp = p->next;
    *e = delTemp->data;
    //将要删除的结点后驱给到前一个结点的后驱，一前一后建立上联系
    p->next = delTemp->next;
    //判断是否删除的是尾结点，不是的话需要设置后一个结点的前驱为前一个结点
    if(delTemp->next != NULL){
        delTemp->next->prior = p;
    }
    free(delTemp);
    return OK;
}

双向循环链表

双向循环链表就是在双向链表基础上，将表尾和表头建立关系。表尾next指向表头，表头prior指向表尾，形成循环结构。所以循环链表的尾结点next是不会为NULL的。


双向循环链表

在创建链表、插入结点、删除结点等操作时，要考虑到需要建立头结点和尾结点之间的关系。

创建链表

注意处理尾结点和头结点的关系。

Status createLinkList(LinkList *L){
    *L = (LinkList)malloc(sizeof(Node));
    if(*L == NULL){
        return ERROR;
    }
    
    (*L)->next = (*L);
    (*L)->prior = (*L);
    
    LinkList p = *L;
    for (int i = 0; i < 10; i ++) {
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->data = i;
        //temp 接在头结点后
        p->next = temp;
        //前驱结点为p
        temp->prior = p;
        //后驱结点为头结点
        temp->next = (*L);
        //头结点的前驱结点为temp
        (*L)->prior = temp;
        //方便后续接上
        p = p->next;
        
    }
    return OK;
}
插入数据

与双向链表不同的是需要处理首尾联系。

Status LinkListInsert(LinkList *L,int index, ElemType e){
    
    LinkList p = (*L);
    int i = 1;
    
    if (*L == NULL) return  ERROR;
    //找到插入位置前一个
    while (i < index && p->next != *L) {
        p = p->next;
        i++;
    }
    
    if(i > index) return ERROR;
    LinkList temp = (LinkList)malloc(sizeof(Node));
    if (temp == NULL) return  ERROR;
    temp->data = e;
    temp->prior = p;
    temp->next = p->next;
    p->next = temp;
    
    if(*L != temp->next){
        //如果插入的不是尾结点，建立后驱结点的前驱关系
        temp->next->prior = temp;
    }else{
        //插入的是尾结点，就建立与头结点的关系
        (*L)->prior = temp;
    }
    return OK;
}
删除数据

由于头结点和尾结点的关系，删除结点时不用考虑尾结点的特殊情况，只需要注意删除当前结点后只剩下头结点的情况，需要置空。

Status LinListDelete(LinkList *L,int index,ElemType *e){
    int i = 1;
    LinkList temp = (*L)->next;
    
    if(*L == NULL){
        return ERROR;
    }
    //即此时删除的是首元结点,删了之后就直接*L置空
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    while (i < index) {
        temp = temp->next;
        i++;
    }
    *e = temp->data;
    //将前一个和后一个关联上
    temp->prior->next = temp->next;
    temp->next->prior = temp->prior;
    free(temp);
    return OK;
}
上一篇下一篇

猜你喜欢

热点阅读