資料結構--雙向循環連結清單C實作

雙向連結清單的優點是可以向前後兩個方向周遊，而單連結清單和循環連結清單，如果要對某一個元素進行操作，必須找到該元素的前一結點；而雙連結清單就不需要，因為它可以向前周遊，找到前一結點修改它的字尾，同理可以修改後一結點的字首。

本文代碼沒有使用哨兵結點實作。

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

typedef int Mt;

typedef struct Node{
    Mt data;
    struct Node *next;
    struct Node *prior;

}Dlist;

Dlist *CurPosition;

Dlist* init()
{
    Dlist *head=NULL,*p ,*p1;
    int n;
    printf("輸入資料數量：\n");
    scanf("%d",&n);
    if(n>)
    {
        p = (Dlist*)malloc(sizeof(Dlist));
        if(p == NULL){
            printf("記憶體申請失敗！\n");
            return NULL;
        }
        if(head==NULL)
        {
            head = p;
        }
        scanf("%d",&p->data);
        p->next = p;
        p->prior = p;
        p1 = p;
        while (--n>)
        {
            p= (Dlist*)malloc(sizeof(Dlist));
            scanf("%d",&p->data);
            p1->next = p;
            p->next = p1;
            p->prior = p1;
            p1 = p;
        }
        p1->next = head;
        head->prior = p1;
    }
    CurPosition = head;//傳回目前位置。
    return head;

}

void printDlist(Dlist *head)
{
    Dlist *h;
    h=head;
    if(head == NULL)
    {
        printf("該連結清單為空！\n");
    }else
    {
        while(head!=NULL)
        {
            printf("%d ",head->data);
            head = head->next;
            if(head == h)
               break;
        }
    }

}

Dlist* deleteDlist(Dlist *head)
{
    Dlist *h1,*h2;
    h1 = head;
    while(head!=NULL)
    {
        h2 = head;
        free(head);
        head = h2->next;
        if(h1==head)
        {
            printf("雙向連結清單删除完成！\n");
            break;
        }
    }
    return NULL;
}

int LengthDlist(Dlist *head)
{
    int length =;
    Dlist *h = head;
    while(head!=NULL)
    {
        length++;
        head = head->next;
        if(head == h)
            break;
    }
    return length;
}

Dlist* insertHead(Dlist* head,Mt num)
{
    Dlist *p;
    p = (Dlist*)malloc(sizeof(Dlist));
    if(p == NULL){
        printf("記憶體申請失敗！\n");
        return head;
    }
    p->data = num;
    if(head == NULL)
    {
        p->next = p;
        p->prior = p;
    }else
    {
        p->next = head;
        p->prior = head->prior;
        head->prior->next = p;
        head->prior = p;
    }
    printf("插入成功！\n");
    return CurPosition = p;
}

Dlist *Taildelete(Dlist *head)
{
    Dlist* h;
    if(head==NULL)
    {
        printf("該連結清單為空,删除失敗！\n");
        return NULL;
    }else if(head == head->next)
    {
        free(head);
        return NULL;//如果隻有一個結點，傳回NULL
    }else
    {
        h=head->prior;
        head->prior = h->prior;
        h->prior->next = head;
        free(h);
        printf("删除尾部結點完成！\n");
    }
    CurPosition = head->prior;
    return head;
}

Dlist* insertPosition(Dlist* head,int pos,Mt num)
{
    int i;
    int len = LengthDlist(head);
    Dlist *p,*h=head;
    if(pos>len+)
    {
        printf("插入位置超過連結清單長度！\n");
        return head;
    }else if(head ==NULL)
    {
        p = (Dlist*)malloc(sizeof(Dlist));
        if(p == NULL){
           printf("記憶體申請失敗！\n");
           return head;
        }
        p->data = num;
        p->next = p;
        p->prior = p;
        return p;
    }else
    {
        p = (Dlist*)malloc(sizeof(Dlist));
        if(p == NULL){
           printf("記憶體申請失敗！\n");
           return head;
        }
        p->data =num;
        if(pos==)
        {
            p->next = head;
            p->prior = head->prior;
            head->prior->next = p;
            head->prior = p;
            h = p;
        }else if(pos == LengthDlist(head))
        {
            p->next = head;
            p->prior = head->prior;
            head->prior->next = p;
            head->prior = p;
            h = p;
        }else
        {
            for(i=;i<pos;i++)
            {
                head = head->next;
            }
            p->next = head->next;
            p->prior = head;
            head->next->prior = p;
            head->next = p;

            CurPosition = p;
        }
    }
    return h;
}

Dlist* deletePosition(Dlist* head,int pos)
{
    Dlist* h;
    if(head==NULL)
    {
        printf("該連結清單為空，删除第%d個位置的元素失敗！\n",pos);
        return NULL;
    }else if(pos>LengthDlist(head) || pos<=)
    {
        printf("删除位置超過連結清單長度!\n");
        return head;
    }else if(LengthDlist(head)==)
    {
        free(head);
        return NULL;
    }
    else if(pos == )
    {
        h = head->next;
        head->prior->next = head->next;
        h->prior = head->prior;
        free(head);
    }else if(pos == LengthDlist(head))
    {
        h = head;
        head = head->prior;
        h->prior = head->prior;
        head->prior->next = h;
        free(head);
    }else
    {
        h = head;
        while(--pos)
        {
            head = head->next;
        }
        head->next->prior = head->prior;
        head->prior->next = head->next;

        CurPosition = head->next;
        free(head);
    }
    return h;
}

int getPosElement(Dlist *head) //擷取目前操作的位置
{
    int Pos=;
    if(head == CurPosition)
    {
        Pos = ;
    }else
    {
        while(head!=CurPosition)
        {
            Pos++;
            head = head->next;
        }
    }
    return Pos;
}

int main(int argc, char *argv[]) {
    Dlist *Head=NULL;
    Dlist *CurPosition;
    int Len,Pos;
    Head = init();
    //printDlist(Head);
    //Head = deleteDlist(Head);
    //Len = LengthDlist(Head);
    //printf("該連結清單長度為：%d\n",Len);
    //printf("從頭部插入一個數:\n");
    //Head = insertHead(Head,);
    //printDlist(Head);
    //Head = Taildelete(Head);
    //Head = insertPosition(Head,,);
    Head = deletePosition(Head,);
    printDlist(Head);
    Len = LengthDlist(Head);
    printf("該連結清單長度為：%d\n",Len);
    Pos = getPosElement(Head);
    printf("目前操作位置：%d\n",Pos);
    return ;
}
           

學習總結：

先看下面的代碼：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

char *fuc(char *s)
{
    char str[]="";
    int i,j;
    for(i=strlen(s)-,j=;i>=;i--,j++)
    {
        str[j]=s[i];
    }
    return str;
}

int main(int argc, char *argv[]) {
    char *s = "hello world";
    char *ch;
    ch = fuc(s); //将s指向的字元數組逆序并傳回
    puts(ch);
    printf("\n"); 
    return ;
}
           

看似程式沒有問題，但是總是糾結為什麼得不到正确的結果。深入探讨發現，位址的傳遞并沒有問題，隻是位址指向的資料不見了。還是學藝不精啊0.0。原來str數組定義為局部變量，随着函數fuc的結束而結束。是以ch接收到的字元串的首位址已經沒有指向想要的字元串了。

一朝被蛇咬，十年怕井繩啊！

于是乎我覺得下面的代碼也有問題：

Rlist init(Rlist head) //建立哨兵結點
{
    Rlist p;
    p = (Rlist)malloc(sizeof(struct Node));
    if(errMemory(p))
    {
        head = p;
        p->next =NULL;
        return head;
    }
    return NULL;
}
           

一個連結清單的初始化，沒錯，它是在子函數裡面的進行的。但是為什麼它的記憶體空間沒有杯釋放呢？

原來是malloc函數的原因，該函數主動申請一段記憶體，記憶體就不會被系統顯性地釋放，需要主動調動free函數釋放記憶體0.0。