03--双向链表与双向循环链表

[toc]

`

双向链表

双向链表是在单链表的基础上添加了前驱指针。

bf24e4bbbce14f5e458f037d96f6d64d

双向链表创建

* 带头结点
* 不带头结点

为了增删改查的便,使用带头结点的方便.
与单链表区别就是多了前驱指针,创建采用尾插法,让新创建的temp的头指针指向上一个保存的位置,并将当前temp保存为尾指针就行.

21a39f1c3178734b7ae9597eac7d29a3

• 初始化结点及宏

#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 YZNode{
    struct YZNode* prior;
    struct YZNode* next;
    ElemType data;
}YZNode;

typedef struct YZNode* YZNodeList;

• 创建双向结点,并创建10个

Status InitListNode(YZNodeList *L){
    YZNodeList end;
    *L = (YZNodeList)malloc(sizeof(YZNode));
    if (*L == NULL) return ERROR;
    (*L)->next = NULL;
    (*L)->prior = NULL;
    (*L)->data = -1;
    end = *L;
    //假设创建10个
    for (int i=1; i<=10; i++) {
        YZNodeList temp = (YZNodeList)malloc(sizeof(YZNode));
         temp->next = NULL;
         temp->prior = NULL;
         temp->data = i;
        //2.为新增的结点建立双向链表关系
        //temp 的前驱是p
        temp ->prior = end;
        //temp 是p的后继
        end->next = temp;
        //保存尾结点
        end = temp; //end = end->next;
    }
    
    return OK;
}

遍历打印

void disPlay(YZNodeList L){
    YZNodeList p;
    p = L->next;
    if (p == NULL){
        printf("这是一个空表");
        exit(ERROR);
    }
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
}

插入

1.2可以互选 34也可以互换
单链表只有23步骤,这里只是多了一个前驱,操作还是一样的

首先temp的next执行插入位置前一个的next,插入位置的前一个的next的prior等于temp,现在还有一条线就是插入位置前一个指向插入位置的next那个,把那条线next指向temp,temp的prior指向插入位置前一个就行.

1dd74cbf6959d60d7f5894c5178153fb

Status ListInsert(YZNodeList *L, int i, ElemType data){
    if (i<1) return ERROR;
    YZNodeList temp = (YZNodeList)malloc(sizeof(YZNode));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    
    YZNodeList q = *L;
    int j = 1;
    //找到插入前一个 也可以使用for循环 看个人爱好
    while (q && j<i) {
        q = q->next;
        j++;
    }
    //如果插入的位置超过链表本身的长度
    if (q == NULL) return ERROR;
    //如果是最后一个
    if (q->next == NULL){
        q->next = temp;
        temp->prior = q;
    }else{
           q->next->prior = temp;
           temp->next = q->next;
           q->next = temp;
           temp->prior = q;
    }
    
    return OK;
}

删除

delTemp的上一个节点的next指向delTemp的next

delTemp的下一个节点的prior执行delTemp的prior

delTemp->next == NULL 就不必设置prior

释放deltemp指向的堆内存

83c547a80221eb112b3f050abe869c50

Status ListDelete(YZNodeList *L, int i, ElemType *e){
    int k=1;
    YZNodeList q = (*L);
    if (*L == NULL) return ERROR;
    
    while (q && k<i) {
        q = q->next;
        k++;
    }
    //q 删除的上一个指针
    if(k>i || q == NULL) return ERROR;
    
    YZNodeList  delTemp = q->next;
    *e = delTemp->data;
    
    q->next = delTemp->next;
    //如果delTemp->next==NULL 说明最后一个结点
    if (delTemp->next != NULL){
        delTemp->next->prior = q;
    }
    free(delTemp);//释放内存 一点不能忘记 
    return OK;
}

删除指定元素

和指定某个下标一样,这里通过遍历找到delTemp,不用再去创建临时变量指向它

056575c62c9dc90259617529a8bbbb6d

Status LinkListDeletVAL(YZNodeList *L, int data){
    YZNodeList q = (*L);
    while (q) {
        if (q->data == data){
            q->prior->next = q->next;
            if (q->next != NULL){
                q->next->prior = q->prior;
            }
            free(q);
            break;
        }
        q = q->next;
    }
    
    return OK;
    
}

查找指定元素

遍历找到退出,如果有多个只返回第一个

int selectElem(YZNodeList L,ElemType elem){
    if (L == NULL) return -1;
    YZNodeList q = L;
    int k = 1;
    while (q) {
        if (q->data == elem){
            return k;
        }
        k++;
        q = q->next;
    }
    return -1;
   
}

替换指定元素

两种写法,都一样

Status replaceLinkList(YZNodeList *L,int index,ElemType newElem){
    YZNodeList q = (*L);

   // int j = 1;
//    while (q && j<=index) {
//        q = q->next;
//        j++;
//    }
//    q->data = newElem;
    YZNodeList p = (*L)->next;
    int k = 1;
    while (p && k<index) {
        p = p->next;
        k++;
    }
    p->data = newElem;
    return OK;
}

置空链表

单链表一样 只是要把前驱也置空

Status ClearList(YZNodeList *L)
{
    YZNodeList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=(*L)->prior=NULL;        /* 头结点指针域为空 */
    return OK;
}

示例

    YZNodeList L;
    ElemType del;
    InitListNode(&L);
    disPlay(L);
    ListInsert(&L, 5, 100);
    disPlay(L);
    ListDelete(&L, 4, &del);
    disPlay(L);
    printf("%d\n",del);
    LinkListDeletVAL(&L, 100);
    disPlay(L);
   int a =  selectElem(L, 8);
    printf("8的位置%d\n",a);
    replaceLinkList(&L, 5, 11111);
     disPlay(L);
     ClearList(&L);
    disPlay(L);

双向循环链表

双向循环链表

尾结点的next指向头结点
头结点的prior指向尾结点

双向循环链表创建

• 创建

#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 * YZNodeList;

• 初始化 继续尾插法

和双向循环链表一样 这里多了个尾指针的next指向 和 头结点的prior指向
下面的尾指针是指最后一个结点
①保存尾指针p
②尾指针next指向新建数据temp
③temp的prior指向尾指针
④尾指针的prior指向temp
⑤保存尾指针temp p temp

9b9f9d7d117ac629e85f4df8e8e723b3

Status creatLinkList(YZNodeList *L){
    *L = (YZNodeList)malloc(sizeof(Node));
    if (!(*L))  return ERROR;
    (*L)->prior = (*L);
    (*L)->next = (*L);
    YZNodeList q = (*L);
    /*
    for (int i =1; i<=10; i++) {
        YZNodeList temp = (YZNodeList)malloc(sizeof(Node));
        temp->data = i;
        
        q->next = temp;
        temp->prior = q;
        temp->next = (*L);
        q->prior = temp;
        q = temp;//q = q->next
    }
    */
    for(int i=1; i <= MAXSIZE;i++){
        
        //1.创建1个临时的结点
        YZNodeList temp = (YZNodeList)malloc(sizeof(Node));
        temp->data = i;
        
        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        p = p->next;
    }
    //单链表后插入法的形式 
    p->next = (*L);
    (*L)->prior = p;
    
    
   return OK;
}

双向循环链表插入

当插入位置超过链表长度则插入到链表末尾(其他链表也可以这样)
插入在尾结点

• 头结点的prior指向尾结点

插入在中间

• 和双向链表一样
• temp和上一个节点建立关系

• 上一个节点和temp建立关系

  
  d70b649191c05ae1e65ed7fc37db8215

Status LinkListInsert(YZNodeList *L, int index, ElemType e){
    int k = 1;
    if (*L == NULL) return ERROR;
    YZNodeList q = *L;
    while (q->next !=(*L) && k < index) {
        q = q->next;
        k++;
    }
    
    if (k > index ) return ERROR;
    YZNodeList temp = (YZNodeList)malloc(sizeof(Node));
    temp->data = e;
    
    temp->prior = q;
    temp->next = q->next;
    
    q->next = temp;
    //temp还差一条线
    if(q->next != (*L)){
        temp->next->prior = temp;
    }else{
        (*L)->prior = temp;
    }
    
    
    return OK;
}

双向循环链表遍历

注意点 YZNodeList q = L->next; 所以 printf("%d",q->data);
q = q->next;先打印

Status Display(YZNodeList L){
    if(L == NULL){
        printf("这是一个空表");
    }
    YZNodeList q = L->next;
    while (q != L) {
        printf("%d",q->data);
        q = q->next;
    }
    printf("\n");
    
    return OK;
}

双向循环链表删除

和双向表删除相似

当剩下一个头结束直接释放内存置空

修改被删除结点的前驱结点的后继指针(虚线1)

修改被删除结点的后继结点的前驱指针 (虚线2)

删除结点temp

8605ff203f607523fe6cc0760718345a

Status LinkListDelete(YZNodeList *L,int index,ElemType *e){
    
    int i = 1;
    YZNodeList temp = (*L)->next;
    
    if (*L == NULL) {
        return  ERROR;
    }
    
    //①.如果删除到只剩下首元结点了,则直接将*L置空;
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    
    //1.找到要删除的结点
    while (i < index) {
        temp = temp->next;
        i++;
    }

    //2.给e赋值要删除结点的数据域
    *e = temp->data;
    
    //3.修改被删除结点的前驱结点的后继指针 图1️⃣
    temp->prior->next = temp->next;
    //4.修改被删除结点的后继结点的前驱指针 图2️⃣
    temp->next->prior = temp->prior;
    //5. 删除结点temp
    free(temp);
    
    return OK;
    
}