线性表 - 循环链表

555 阅读11分钟

1. 单向循环链表

对于单链表,每个结点只存储了向后的指针,这样当中某一结点就无法找到它的前驱结点。

将单链表中终端结点的指针由空指针改为指向头结点,就使整个单链表形成一个环, 这种头尾相接的单链表称为单循环链表,简称循环链表。循环链表解决了一个很麻烦的问题:如何从当中一个结点出发,访问到链表的全部结点。

循环链表和单链表的主要差异就是在于循环的判断条件上,原来是判断p->next是否为空,现在则是p->next不等于头结点,则循环未结束。

1.1 单向循环链表的创建

单向循环链表的创建分为两种情况:

  1. 链表第一次创建: 创建一个新的结点 新结点的next指向自身(L)->next = (L);
  2. 链表已经创建,直接插入数据: 找到链表的尾结点,将尾结点的next指向新结点 ,新结点的next指向(*L)
#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;

// 单向循环链表初始化
Status CreateList (LinkList *L) {
    
    int item;
    LinkList temp = NULL;
    LinkList r = NULL; // 记录最后一个节点
    
    printf("请输入新的结点, 当输入0时结束!\n");
    while (1) {
        
        scanf("%d",&item);
        
        if (*L == NULL) {
            // 如果输入的链表是空。则创建一个新的节点,使其next指针指向自己  (*head)->next=*head;
            *L = (LinkList)malloc(sizeof(Node));
            if(!*L) return ERROR;
            
            (*L)->data = item;
            (*L)->next = *L;
            r = *L;
            
        } else {
            // 输入的链表不是空的,寻找链表的尾节点,使尾节点的next=新节点。新节点的next指向头节点(插入操作)
            temp = (LinkList)malloc(sizeof(Node));
            if (!temp) return ERROR;
            temp->data = item;     // 创建新的节点
            
            temp->next = *L;
            r->next = temp;
            
            r = temp;
        }
    }
    return OK;
}

1.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);
        
    }
}

1.3 单向循环链表的插入

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

1.4 单向循环链表的删除

  1. 如果删除首元节点
    1. 如果删除到只剩下首元结点了,则直接将*L置空;
    1. 链表还有很多数据,但是删除的是首结点;
  • 2.1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
  • 2.2. 新结点做为头结点,则释放原来的头结点
  1. 如果删除其他结点
  • 找到删除结点前一个结点target
  • 使得target->next 指向下一个结点
  • 释放需要删除的结点temp
// 单向循环链表删除元素
Status LinkListDelete(LinkList *L,int place) {
    
    LinkList temp, target;
    int i;
    temp = *L;      // temp 指向链表首元结点
    if(!temp) return ERROR;
    
    if (place == 1) {
        // 如果删除首元节点
        // 1.如果删除到只剩下首元结点了,则直接将*L置空;
        if((*L)->next == (*L)){
            (*L) = NULL;
            return OK;
        }
        
        // 2.链表还有很多数据,但是删除的是首结点;
        // 2.1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
        // 2.2. 新结点做为头结点,则释放原来的头结点
        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++);       //1. 找到删除结点前一个结点target
            temp = target->next;
        
            target->next = temp->next;  // 2. 使得target->next 指向下一个结点
            free(temp);                 // 3. 释放需要删除的结点temp
        }
    
    return OK;
    
}

1.5 单向循环链表的查询

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

2. 双向链表

单链表访问一个结点的后续结点,而无法直接访问其前驱结点。 为此我们在单链表结点结构中新增加一个前驱指针域,指向前驱结点的数据域,使其不但能够访问其后续结点,也可以方便的访问其前驱结点,这种节点结构叫做双向链表的结点结构

2.1 双向链表的创建

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 *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

// 创建双向链接
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++){
        
        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        
        //2.为新增的结点建立双向链表关系
        p->next = temp;         // 2.1. temp 是p的后继
        temp->prior = p;        // 2.2. temp 的前驱是p
        p = p->next;            // 3.2. 记录最后的结点的位置,方便下一次插入
        
    }
    
    return OK;
}

2.2 双向链表的插入

双向链表插入元素
Status ListInsert(LinkList *L, int i, ElemType data) {
    
    if (i < 1) return ERROR;                            // 1.插入的位置不合法 为0或者为负数
    
    LinkList temp = (LinkList)malloc(sizeof(Node));     // 2.新建结点
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    
    LinkList p = *L;                                    // 3.将p指向头结点!
    
    for(int j = 1; j < i && p;j++)                      // 4.找到插入位置i直接的结点
        p = p->next;
    
    if(!p) return  ERROR;                               // 5.如果插入的位置超过链表本身的长度
    
    if (p->next == NULL) {                              // 6.判断插入位置是否为链表尾部;
        
        p->next = temp;
        temp->prior = p;
        
    } else {
        //1️⃣ 将p->next 结点的前驱prior = temp
        p->next->prior = temp;
        //2️⃣ 将temp->next 指向原来的p->next
        temp->next = p->next;
        //3️⃣ p->next 更新成新创建的temp
        p->next = temp;
        //4️⃣ 新创建的temp前驱 = p
        temp->prior = p;
    }
    
    return  OK;
}

2.3 双向链表的删除

删除双向链表指定位置上的结点
Status ListDelete(LinkList *L, int i, ElemType *e) {
    
    int k = 1;
    LinkList p = (*L);
    
    //1.判断双向链表是否为空,如果为空则返回ERROR;
    if (*L == NULL) {
        return ERROR;
    }
    
  
    //2. 将指针p移动到删除元素位置前一个
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    
    //3.如果k>i 或者 p == NULL 则返回ERROR
    if (k>i || p == NULL) {
        return  ERROR;
    }
    
    //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
    LinkList delTemp = p->next;
    *e = delTemp->data;
    
    //5. p->next 等于要删除的结点的下一个结点
    p->next = delTemp->next;
    
    //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }
    
    //7.删除delTemp结点
    free(delTemp);
    
    return OK;
    
}

2.4 双向链表的查询

int selectElem(LinkList L,ElemType elem) {
    
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == elem) {
            return i;
        }
        
        i++;
        p = p->next;
    }
    
    return  -1;
}

2.5 双向链表的更新节点

// 在双向链表中更新结点
Status replaceLinkList(LinkList *L,int index,ElemType newElem) {

    LinkList p = (*L)->next;
    
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    
    p->data = newElem;
    return OK;
}

3. 双向循环链表

3.1 双向循环链表的创建

// 双向循环链表初始化
Status creatLinkList(LinkList *L) {
    
    *L = (LinkList)malloc(sizeof(Node));
    if (!*L)  return ERROR;
    
    (*L)->next = (*L);
    (*L)->prior = (*L);
    
    //新增数据
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        
        LinkList temp = (LinkList)malloc(sizeof(Node));  // 1.创建1个临时的结点
        temp->data = i;
        
                                                         // 2.为新增的结点建立双向链表关系
        p->next = temp;                                  // 2.1.temp 是p的后继
        temp->prior = p;                                 // 2.2.temp 的前驱是p
        temp->next = (*L);                               // 2.3.emp的后继是*L
        p->prior = temp;                                 // 2.4. 的前驱是新建的temp
        p = p->next;                                     // 2.5. 要记录最后的结点的位置,方便下一次插入
        
    }
    
    return OK;
}

3.2 双向循环链表的插入

双向循环链表插入元素
/*当插入位置超过链表长度则插入到链表末尾*/
Status LinkListInsert(LinkList *L, int index, ElemType e) {
   
    LinkList p = (*L);                              // 1.创建指针p,指向双向链表头
    int i = 1;
    
    if(!*L) return ERROR;                           // 2.双向循环链表为空,则返回error
   
    while (i < index && p->next != *L) {            // 3.找到插入前一个位置上的结点p
        p = p->next;
        i++;
    }
    
    if (i > index)  return ERROR;                   // 4.如果i>index 则返回error
    
    LinkList temp = (LinkList)malloc(sizeof(Node)); // 5.创建新结点temp
    if (temp == NULL) return ERROR;                 // 6.temp 结点为空,则返回error
    temp->data = e;                                 // 7.将生成的新结点temp数据域赋值e.
    
    temp->prior = p;                                // 8.将结点temp 的前驱结点为p;
    temp->next = p->next;                           // 9.temp的后继结点指向p->next;
    p->next = temp;                                 // 10.p的后继结点为新结点temp;

    if (*L != temp->next) {
        temp->next->prior = temp; // 11.如果temp 结点不是最后一个结点,temp节点的下一个结点的前驱为temp结点
    } else {
        (*L)->prior = temp;
    }
    
    return OK;
}

3.3 双向循环链表的删除

// 双向循环链表删除结点
Status LinkListDelete(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) {                         // 1.找到要删除的结点
        temp = temp->next;
        i++;
    }
    
    *e = temp->data;                            // 2.给e赋值要删除结点的数据域
    
    temp->prior->next = temp->next;             // 3.修改被删除结点的前驱结点的后继指针 
    temp->next->prior = temp->prior;            // 4.修改被删除结点的后继结点的前驱指针
    free(temp);                                 // 5.删除结点temp
    
    return OK;
}

4. 顺序存储结构与链式存储结构总结

  1. 存储分配方式:
  • 顺序存储结构用一段连续的存储单元依然存储线性表的数据元素。
  • 链式存储结构用一组任意的存储单元存放线性表的玩意。
  1. 时间性能:
  • 查找:顺序存储结构O(1),单链表O(n)。
  • 插入与删除:顺序存储结构O(n),链式存储结构为O(1)。
  1. 空间性能
  • 顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢。
  • 链式存储结构不需要分配存储空间,只要有就可以分配,元素个数也不受限制。
  1. 结论
  • 若线性表需要频繁查找,很少进入插入和删除操作时,宜采用顺序存储结构。
  • 若需要频繁插入和删除时,宜采用链式存储结构。
  • 当线性表中的元素个数变化较大或者根本不知道有多大时,最好用链式存储结构,这样可以不用考虑存储空间大小问题。
  • 而如果事先知道线性表的大致长度,比如一年12个月,这种用顺序存储结构效率会高很多。