1.雙向鏈表

雙向鏈表的節(jié)點(diǎn)分為3個(gè)部分：前驅(qū)指針域、數(shù)據(jù)域和后繼指針域，可以用下圖表示：

雙向鏈表節(jié)點(diǎn)@2x.png

• 前驅(qū)指針域：用于存儲(chǔ)該節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)的存儲(chǔ)地址；
• 數(shù)據(jù)域：用于存儲(chǔ)該節(jié)點(diǎn)的數(shù)據(jù)
• 后繼指針域：用于存儲(chǔ)該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)存儲(chǔ)地址；

雙向鏈表的代碼實(shí)現(xiàn)

1.1代碼準(zhǔn)備

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

typedef int Status;
typedef int ElemType;

//定義結(jié)點(diǎn)
typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

1.2雙向鏈表的創(chuàng)建

Status createLinkList(LinkList *L){
    
    //*L 指向頭結(jié)點(diǎn)
    *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;
}

1.3雙向鏈表的遍歷

void display(LinkList L){
    
    LinkList temp = L->next;
    
    if(temp == NULL){
        printf("打印的雙向鏈表為空!\n");
        return;
    }
    
    while (temp) {
        printf("%d  ",temp->data);
        temp = temp->next;
    }
    printf("\n");
    
}

1.4雙向鏈表的插入

Status LinkListInsert(LinkList *L, int place, int num) {
    if (place < 1) return ERROR;
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->prior = NULL;
    temp->next = NULL;
    temp->data = num;
    
    LinkList p = *L;
    for (int i = 1; i < place && p != NULL; i++) {
        p = p->next;
    }
    
    if (p == NULL) return ERROR;
    
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    } else {
        temp->next = p->next;
        p->next->prior = temp;
        p->next = temp;
        temp->prior = p;
    }
    
    return OK;
}

1.5雙向鏈表的刪除

1.5.1 刪除指定位置節(jié)點(diǎn)

Status ListDelete(LinkList *L, int i, ElemType *e){
    
    int k = 1;
    LinkList p = (*L);
    
    if (*L == NULL) {
        return ERROR;
    }
   
    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;
    }
    
    //7.刪除delTemp結(jié)點(diǎn)
    free(delTemp);
    
    return OK;
    
}

1.5.2 刪除指定內(nèi)容節(jié)點(diǎn)

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

1.6雙向鏈表中查找元素

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;
}

1.7雙向鏈表中更新節(jié)點(diǎn)

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;
}

2.雙向循環(huán)列表

雙向循環(huán)列表的特點(diǎn)是，列表頭節(jié)點(diǎn)的前驅(qū)指針指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的后繼指針指向頭節(jié)點(diǎn)。

雙向循環(huán)鏈表@2x.png

2.1雙向循環(huán)鏈表的創(chuàng)建

Status creatLinkList(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;
        p->next = temp;
        temp->prior = p;
        temp->next = (*L);
        p->prior = temp;
        p = p->next;  
    }
    return OK; 
}

2.2雙向循環(huán)鏈表的遍歷

Status Display(LinkList L){
    
    if (L == NULL) {
        printf("打印的雙向循環(huán)鏈表為空!\n\n");
        return ERROR;
    }
    printf("雙向循環(huán)鏈表內(nèi)容:  ");
    
    LinkList p = L->next;
    while (p != L) {

        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n\n");
    return OK;
}

2.3雙向循環(huán)鏈表的插入

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;
}

2.4雙向循環(huán)鏈表的刪除

Status LinkListDelete(LinkList *L,int index,ElemType *e){
    
    int i = 1;
    LinkList temp = (*L)->next;    
    if (*L == NULL) {
        return  ERROR;
    }
    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; 
}