The Double Linknode for Linear table | Data

The some code in Data book (5th Edition) from the 54 page to 55 page

typedef int ElemType;
typedef struct DNode {
    ElemType data; //Data fields
    struct DNode *prior; //Point to the precursor node
    struct DNode *next; //Point to the successor node
}DLinkNode;//Declare the circular DLinknode type

//Create DLinknode using Head-inserting
static void CreateListF(DLinkNode *&L, ElemType a[], int n) { //Reference to pointer
    DLinkNode *s;
    L = (DLinkNode *)malloc(sizeof(DLinkNode)); //Create Head-inserting
    L->prior = L->next = NULL;
    for(int i = 0; i < n; i++) {
        s = (DLinkNode *)malloc(sizeof(DLinkNode)); //Create new node
        s->data = a[i];
        s->next = L->next; //Insert nodes before the original start node, after the head node
        if(L->next != NULL)
            L->next->prior = s;
        L->next = s;
        s->prior = L;
    }
    s = L->next;
    while(s->next != NULL) //Find the end node, which is pointed at by s
        s = s->next;
    s->next = L;
    L->prior = s; //Head-inserting point next domain points to head node
}

//Create DLinknode using Tail-insertion
static void CreateListR(DLinkNode *&L, ElemType a[], int n) {
    DLinkNode *s, *r;
    L = (DLinkNode *)malloc(sizeof(DLinkNode)); //Create Head-inserting
    r = L; //r always point to Tail-insertion
    for(int i = 0; i < n; i++) {
        //Create new node
        s = (DLinkNode *)malloc(sizeof(DLinkNode));
        s->data = a[i];
        r->next = s; //Insert new nodes s after node r
        s->prior = r;
        r = s;
    }
    r->next = NULL; //Tail knot point next domain points to head node
}

//Initialization Linknode
static void InitList(DLinkNode *&L) { //Reference pointer
    L = (DLinkNode *)malloc(sizeof(DLinkNode)); //Create Head-inserting
    L->prior = L->next = L;
}

//Destroyed Linknode
static void DestroyList(DLinkNode *&L) { //Reference pointer
    DLinkNode *pre = L, *p = pre->next;
    while(p != L) {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);//Release pre
}

//Determine if a linear table is empty
static bool list_empty(DLinkNode *L) {
    return (L->next == L);
}

//Calculation length of the Linknode
static int list_length(DLinkNode *L) {
    int i = 0;
    DLinkNode *p = L;
    while(p->next != L) {
        i++;
        p = p->next; //p point to Tail-inserting
    }
    return i;
}

//Output Linknode
static void display_list(DLinkNode *L)
{
    DLinkNode *p = L->next;
    while(p != L) {
        printf("%c ", p->data);
        p = p->next;
    }
    printf("\n");
}


//Find a data element value
static bool get_elem(DLinkNode *L, int i, ElemType &e)
{
    int j = 1;
    DLinkNode *p = L->next; //p point to first node
    if(i <= 0 || L->next == L) //When i wrong or L is null return false
        return false;
    if(i == 1) {
        e = L->next->data;//Get data
        return true;
    } else {
        while(j <= i - 1 && p != L) { //Find node p for i 
            j++;
            p = p->next;
        }
        if(p == L)
            return false;
        else {
            e = p->data; //Get data
            return true;
        }
    }
}

//Find by element value
static int locate_elem(DLinkNode *L, ElemType e)
{
    int i = 1;
    DLinkNode *p = L->next;
    while(p != NULL && p->data != e) {
        i++;
        p = p->next;
    }
    if(p == NULL) //When node e not exist, return 0
        return 0;
    else //When exist node e of value is 1, return logic number i
        return i;
}

如有侵权，请联系作者删除