The Double Linknode for Linear table (Continuous updates) | Data

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

Continuous updates

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
}

//1 Initialization Linknode
void InitList(LinkNode*& L) {
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = NULL; //Create Head-inserting, it's next domain set to NULL
}

//2 Destroyed Linknode
void DestroyList(LinkNode*& L) {
    LinkNode *pre = L, * p = L->next;   //pre points to node p's forward node
    while (p != NULL) { //Scan Linknode L
        free(pre);  //Release pre node
        pre = p;    //pre,p sync and move a node
        p = pre->next;
    }
    free(pre);  //At the end of the loop p is NULL, pre points to the end node to release it
}

//3 Determine if a linear table is empty
bool ListEmpty(LinkNode* L) {
    return L->next == NULL;
}

//4 Calculation length of the Linknode
int ListLength(LinkNode* L) {
    int n = 0;
    LinkNode *p = L;    //p point to Head-inserting,set n is 0
    while (p->next != NULL) {   //Not empty, traverse is turn
        n++;
        p = p->next;
    }
    return n;   //return L's length n 
}

//5 Output Linknode
void Display(LinkNode* L) {
    LinkNode* p = L->next;  //p point to Head-inserting
    while (p != NULL) { //Not empty, traverse is turn
        printf("%d ", p->data);
        p = p->next;    //p move to next node
    }
    printf("\n");
}

//6 Find a data element value
bool GetData(LinkNode *L, int i, int &e) {
    int j = 0;
    LinkNode *p = L;  //p point to Head-inserting
    if (i <= 0) {   //If i error return false
        return false;
    }
    while (j < i && p != NULL) {    //find the ith node p
        j++;
        p = p->next;
    }
    if (p == NULL) {    //If doesn't
        return false;
    }
    else {  //If exust return true
        e = p->data;
        return true;
    }
}

//7 Find by element value
int LocateData(LinkNode *L, ElemType e) {
    int i = 1;
    LinkNode* p = L->next;  //p point to Head-insterting
    while (p != NULL && p->data != e) {  //Find for the data value with the serial number i
        p = p->next;
        i++;
    }
    if (p == NULL) {    //If doesn't
        return 0;
    }
    else {  //If exuse return number i
        return i;
    }
}

//8 Insert data elements
bool ListInsert(LinkNode *&L, int i, ElemType e) {
    int j = 0;
    LinkNode *p = L, *s;   //p point to Head-inserting
    if (i <= 0) {   //If i error return false
        return false;
    }
    while (j < i - 1 && p != NULL) {    //find the number i-1 node p
        j++;
        p = p->next;
    }
    if (p == NULL) {    //If not found
        return false;
    } else {  //Find number i-1 node p,insert new node and return true
        s = (LinkNode * )malloc(sizeof(LinkNode));
        s->data = e; //Create new node s, 创建新结点 s,value is data
        s->next = p->next;  //Head-inserting
        p->next = s;
        return true;
    }
}

//9 Delete data elements
bool ListDelete(LinkNode*& L, int i, ElemType &e) {
    LinkNode* p = L, * q;   //p point to Head-inserting
    if (i <= 0) {   //if i error return false
        return false;
    }
    int j = 0;  //set j is 0
    while (j < i - 1 && p != NULL) {    //Find number i node p
        j++;
        p = p->next;
    }
    if (p == NULL) {    //Not found
        return false;
    }
    else {  //Find number i-1 node p
        q = p->next;    //q point to number i th node
        if (q == NULL) {    //If number i node it doesn't
            return false;
        }
        e = q->data;
        p->next = q->next;  //Delete q node,number i-1 node point to number i+1 node
        free(q);    //Release q node
        return true;
    }
}

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