資料結構——c語言描述 第二章（3） 雙向連結清單

沒什麼好說的直接上代碼吧。

typedef struct Dnode {
    struct Dnode *pre , *next;
    char data;
}Dlinklist;

Dlinklist *createdlinklist_tail () ;
int dlinklistins (Dlinklist *D , int i , Dlinklist *ins) ;
int deldlinklist (Dlinklist *D , int i , char *e) ;
           

這個是頭檔案，主要定義了基本的雙向連結清單的節點資料結構，和聲明函數頭。

#include <stdio.h>
#include "dlinklist.h"
#include <stdlib.h>

Dlinklist *createdlinklist_tail () {
    Dlinklist *D , *s , *pre_node;
    char c;
    int flag = 1;

    D = (Dlinklist *) malloc (sizeof (Dlinklist));
    D->pre = D;
    D->next = D;
    pre_node = D;

    while (flag) {
        c = getchar ();
        if (c == '.')
            flag = 0;
        else {
            s = (Dlinklist *) malloc (sizeof (Dlinklist));
            s->data = c;
            s->pre = pre_node;
            s->next = pre_node->next;
            pre_node->next->pre = s;
            pre_node->next = s;
            pre_node = s;
        }
    }
    return D;
}

int dlinklistins (Dlinklist *D , int i , Dlinklist *ins) {
    int j = 0;
    Dlinklist *temp = D;

    if (i < 1) {
        printf ("arguement i  error!\n");
        return 0;
    }
    if (D == NULL) {
        printf ("arguement D error!\n");
        return 0;
    } 
    if (ins == NULL) {
        printf ("arguement ins error!\n");
        return 0;
    }
    
    if (i == 1 && temp->next == D) {
        temp->next = ins;
        ins->pre = temp;
        temp->pre = ins;
        ins->next = temp;
        return 1;
    }

    while (1) {
        j++;
        temp = temp->next;
        if (j == i && temp != D) {
            ins->pre = temp->pre;
            ins->next = temp;
            temp->pre->next = ins;
            temp->pre = ins;
            return 0;
        }
        else if (temp == D) {
            printf ("arguemrnt i is too big\n");
            return 0;
        }
    }
}

int deldlinklist (Dlinklist *D , int i , char *e) {
    int j = 0;
    Dlinklist *temp = D;

    if (D == NULL) {
        printf ("argument D is NULL\n");
        return 0;
    }
    if (i < 1) {
        printf ("arguement i is too small\n");
        return 0;
    }

    while (1) {
        j++;
        temp = temp->next;
        if (j == i && temp != D) {
            *e = temp->data;
            temp->pre->next = temp->next;
            temp->next->pre = temp->pre;
            free (temp);
            return 1;
        }
        else if (temp == D) {
            printf ("arguement i is too big\n");
            return 0;
        }
    }
}
           

對雙向連結清單的基本操作的實作，主要是尾插法，插入操作和删除操作。

總結：雙向連結清單和單向連結清單相比較是有一定的差別的，但是主要實作的思路還是差不多的，這裡如果實作雙向連結清單的頭插法的還是要進行判斷的，算法上還是有一定的差別的，這次程式設計的過程中沒有再犯低級的錯誤還是想比較于昨天有進步，哈哈哈哈哈，這裡還是比較簡單的，後面的圖論可能會遇見麻煩，到時候筆記的過程中會圖文的形勢進行解決，加油gogogogo!