提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

数据结构（4）双链表，循环链表，静态链表

2023-02-18 16:42:48 时间

双链表

双链表和单链表的区别就是，一个结点除了有指向后一个结点的指针域，还有一个指向前一个结点的指针域，所以建表的代码为：

typedef struct DNode{
    int data;
    struct DNode *next;
    struct DNode *prior;
}DNode,*DLinkList;

初始化时，应把后继指针域和前驱指针域都指向NULL ，当然，前驱指针域的值应一直为NULL

int InitList(DLinkList &L){
    L = (DNode *) malloc(sizeof (DNode *));
    if(L == NULL){
        return ERROR;//内存分配失败
    }
    L->next = NULL;
    L->prior = NULL;//头结点的前驱永远是NULL
    return OK;
}

双链表的查找操作和单链表相同，这里就不做讨论。和单链表不同的操作在于插入和删除，不同点是双链表的插入和删除需要同时修改两个方向的指针。

  • 后插操作
int InsertNext(DNode *p,int e){
    if(p == NULL){
        return ERROR;//非法参数
    }
    DNode *s;
    s = (DNode *) malloc(sizeof (DNode *));
    s->next = p->next;
    if(p->next != NULL){
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;

    s->data = e;
    return OK;
}

实现了后插操作，插入操作和前插操作就可以直接引用后插来实现了

  • 插入
int InsertNext(DNode *p,int e);
int Insert(DLinkList &L,int i,int e){
    if(i<1){
        return ERROR;
    }
    DNode *p;
    int j = 0;
    p = L;
    while(p!=NULL && j<i-1){
        p = p->next;
        j++;
    }
    InsertNext(p,e);//调用后插函数即可
    return OK;
}
  • 前插：相当于在对这个结点的前一个结点进行后插
int InsertNext(DNode *p,int e);
int InsertPrior(DNode *p,int e){
    InsertNext(p->prior,e);
    return OK;
}
  • 删除操作
int Delete(DLinkList &L,int i,int *e){
    if(i<0){
        return ERROR;
    }
    DNode *p;
    int j = 0;
    p = L;
    while(p!=NULL & j<i){
        p = p->next;
        j++;
    }
    *e = p->data;

    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}
  • 主函数
#include <stdio.h>
#include <stdlib.h>
#include "L.h"

int main (){
    DLinkList L;
    int e;
    InitList(L);
    HeadInsert(L);
    InsertNext(L->next,9);
    Insert(L,3,10);
    InsertPrior(L->next->next,11);
    Delete(L,5,&e);
    Print(L);
    return 0;
}

还需要注意的点就是：什么时候需要申请空间，什么时候不需要申请空间，最近在写代码的时候总是出错。新建结点 = L 后从头遍历后的不需要申请空间。

循环链表

循环单链表

  • 表尾指向头结点

循环双链表

在什么的双链表的插入和删除操作中，如果p是最后一个结点，那么p->next就是NULL ，但是使用循环链表的话就不会出现那种情况。

静态链表

链表的每个结点在内存中的分布是随机的，静态链表就是建立一个固定的区间，结点在这固定的区间内随机存储。

  • 建表
#define MaxSize 10
typedef struct {
    int data;
    int next;//下一个元素的数组下标
}SLinkList[MaxSize];
  • 初始化：把a[0]的next设为-1即可

关于静态链表的其他操作这里不写了，因为学链表真的有点学麻了，前前后后很多天了，最近睡眠也不太好，学习的精力挺低的。计划从明天开始栈和队列，静态链表这里先大概了解原理，具体实现之后再补。?‍?️

相关文章