用C語言完成一個雙向鏈表的創建，插入，刪除

jopen 10年前發布 | 102K 次閱讀雙向鏈表 C/C++開發
/dlist.h/

#ifndef DList_H  
#define DList_H  
typedef  int Item;  
typedef struct Node * PNode;  //節點指針
typedef PNode Position;  //節點位置
/*定義節點類型*/  
typedef struct Node  
{  
    Item data;      /*數據域*/  
    PNode previous; /*指向前驅*/  
    PNode next;     /*指向后繼*/  
}Node;  
/*定義鏈表類型*/  
typedef struct  
{  
    PNode head;     /*指向頭節點*/  
    PNode tail;     /*指向尾節點*/  
    int size; //鏈表長度
}DList;  

/*分配值為i的節點，并返回節點地址*/  
Position MakeNode(Item i);  

/*釋放p所指的節點*/  
void FreeNode(PNode p);  

/*構造一個空的雙向鏈表*/  
DList* InitList();  

/*刪除一個雙向鏈表*/  
void DestroyList(DList *plist);  

/*將一個鏈表置為空表，釋放原鏈表節點空間*/  
void ClearList(DList *plist);  

/*返回頭節點地址*/  
Position GetHead(DList *plist);  

/*返回尾節點地址*/  
Position GetTail(DList *plist);  

/*返回鏈表大小*/  
int GetSize(DList *plist);  

/*返回p的直接后繼位置*/  
Position GetNext(Position p);  

/*返回p的直接前驅位置*/  
Position GetPrevious(Position p);  

/*將pnode所指節點插入第一個節點之前*/  
PNode InsFirst(DList *plist,PNode pnode);  

/*將鏈表第一個節點刪除并返回其地址*/  
PNode DelFirst(DList *plist);  

/*獲得節點的數據項*/  
Item GetItem(Position p);  

/*設置節點的數據項*/  
void SetItem(Position p,Item i);  

/*刪除鏈表中的尾節點并返回其地址，改變鏈表的尾指針指向新的尾節點*/  
PNode Remove(DList *plist);  

/*在鏈表中p位置之前插入新節點S*/  
PNode InsBefore(DList *plist,Position p,PNode s);  

/*在鏈表中p位置之后插入新節點s*/  
PNode InsAfter(DList *plist,Position p,PNode s);  

/*返回在鏈表中第i個節點的位置*/  
PNode LocatePos(DList *plist,int i);  

/*依次對鏈表中每個元素調用函數visit()*/  
void ListTraverse(DList *plist,void (*visit)());
/*打印data*/
void print(Item data);   
#endif  




/dlist.c/

#include"dlist.h"  
#include<malloc.h>  
#include<stdlib.h>  
/*分配值為i的節點，并返回節點地址*/  
Position MakeNode(Item i)  //創建節點，并設置數據i
{  
    PNode p = NULL;   //定義一個節點p指向空
    p = (PNode)malloc(sizeof(Node));  //為該節點分配Ｎode結構體大小的空間
    if(p!=NULL) //分配成功后
    {  
        p->data = i;  //設置數據域為i
        p->previous = NULL;//節點p前繼指針指向空  
        p->next = NULL; //節點p后繼指針指向空
    }     
    return p;  //返回創建好的p節點指針地址
}  
/*釋放p所指的節點*/  
void FreeNode(PNode p)  
{  
     free(p);  
}  
/*構造一個空的雙向鏈表*/  
DList * InitList()  
{  
    DList *plist = (DList *)malloc(sizeof(DList));//為新的雙向鏈表分配DList結構體大小的空間  
    PNode head = MakeNode(0);  //調用上面的MakeNode（）函數創建數據域為0的頭指針指向頭節點
    if(plist!=NULL)//成功分配新鏈表空間后  
    {  
        if(head!=NULL) //頭指針不為空
        {  
            plist->head = head;//新鏈表的頭指針指向頭節點
            plist->tail = head; //先鏈表的尾指針也指向頭節點
            plist->size = 0; //鏈表長度為0
        }  
        else  
            return NULL; //頭指針創建失敗
    }  
    return plist; //返回創建好的空鏈表
}  

/*刪除一個雙向鏈表*/  
void DestroyList(DList *plist)  
{  
    ClearList(plist); //因為 DList *plist = (DList *)malloc(sizeof(DList))為鏈表分配了空間，所以必須調用清空鏈表函數，釋放鏈表節點的空間
    free(GetHead(plist)); //因為 PNode head = MakeNode(0)為頭節點分配了空間，所以必須調用GetHead（）函數獲取當前鏈表的頭節點地址然后進行釋放
    free(plist);  
}  

/*判斷鏈表是否為空表*/  
int IsEmpty(DList *plist)  
{  
    if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist)) //如果調用 GetSize（）函數獲取的鏈表大小為0并且調用GetTail函數獲取的尾節點和調用
                              //GetHead函數獲取的頭節點指向同一個地址，那么就是空表
        return 1;  
    else  
        return 0;  
}  
/*將一個鏈表置為空表，釋放原鏈表節點空間*/  
void ClearList(DList *plist) //清空鏈表
{  
    PNode temp,p;  
    p = GetTail(plist); //將節點指針p指向尾指針指向的節點地址
    while(!IsEmpty(plist))  //如果該鏈表不為空
    {     
        temp = GetPrevious(p); //將節點指針temp指向p指針的前繼指針所指向的地址
        free(p); //將 p指針指向的尾節點釋放
        p = temp; //p指針重新指向剛才釋放的尾節點的前一個節點
        plist->tail = temp; //尾指針重新指向剛才釋放的尾節點的前一個節點
        plist->size--;  //從后往前一個一個釋放節點空間，釋放一個鏈表大小就減1
    }  
}  

/*返回頭節點地址*/  
Position GetHead(DList *plist)  
{  
    return plist->head;  
}  

/*返回尾節點地址*/  
Position GetTail(DList *plist)  
{  
    return plist->tail;  
}  

/*返回鏈表大小*/  
int GetSize(DList *plist)  
{  
    return plist->size;  
}  

/*返回p的直接后繼位置*/  
Position GetNext(Position p)  
{  
    return p->next;  
}  

/*返回p的直接前驅位置*/  
Position GetPrevious(Position p)  
{  
    return p->previous;  
}  

/*在第一個節點前插入新節點pnode*/  
PNode InsFirst(DList *plist,PNode pnode)  
{  
    Position head = GetHead(plist);//獲取頭節點位置

    if(IsEmpty(plist))  //若鏈表為空，鏈表的尾指針就指向pnode節點，直接插入新節點
        plist->tail = pnode;  
    plist->size++;//鏈表大小加1,給新加的pnode節點  
      pnode->next = head->next; //新加的pnode節點的后繼指針指向頭節點指向的第一個節點  
    pnode->previous = head;//新加的pnode節點的前繼指針指向頭節點  
      if(head->next!=NULL)  //如果第一個節點不為空
        head->next->previous = pnode;  //第一個節點的前繼指針就指向新加的pnode節點
    head->next = pnode; //頭節點的后繼指針指向新加的pnode節點
      return pnode;   
}  

/*刪除第一個節點,返回該節點的地址*/  
PNode DelFirst(DList *plist)  
{  
    Position head = GetHead(plist);//獲取頭節點位置  
    Position p=head->next; //獲取第一個節點位置
    if(p!=NULL)  //第一個節點存在
    {  
        if(p==GetTail(plist))  //若第一個節點就是尾節點
            plist->tail = p->previous; //尾指針直接指向第一個節點的前繼節點即頭節點
        head->next = p->next; //頭節點的后繼指針直接指向第一個節點的后一個節點也就是第二個節點
        head->next->previous = head; //第二個節點的前繼指針指向頭節點
        plist->size--;  //刪除第一個節點后鏈表大小減1

    }     
    return p;  
}  

/*獲得節點的數據項*/  
Item GetItem(Position p)  
{  
    return p->data;  
}  

/*設置節點的數據項*/  
void SetItem(Position p,Item i)  
{  
    p->data = i;  
}  

/*刪除鏈表中的尾節點并返回地址，改變鏈表的尾指針指向新的尾節點*/  
PNode Remove(DList *plist)  
{  
    Position p=NULL;  
    if(IsEmpty(plist))  
        return NULL;  
    else  
    {  
        p = GetTail(plist);  //讓p指向尾節點
        p->previous->next = p->next;//p的前一個節點的后繼指針也就是指向尾節點的指針跳過原尾節點指向頭節點  
        plist->tail = p->previous;  //尾指針重新指向原尾節點的前一個節點
        plist->size--;//刪除尾節點后鏈表大小減1  
        return p;  
    }  
}  
/*在鏈表中p位置之前插入新節點s*/  
PNode InsBefore(DList *plist,Position p,PNode s)  
{  
    s->previous = p->previous; //s節點的前繼指針指向 p節點的前一個節點
    s->next = p; //s節點的后繼指針指向p節點
    p->previous->next = s; //原p節點的前一個節點的后繼指針指向s節點     
    p->previous = s; //p節點的前繼指針指向s節點

    plist->size++; //插入新節點s后，鏈表大小加1
    return s;  
}  
/*在鏈表中p位置之后插入新節點s*/  
PNode InsAfter(DList *plist,Position p,PNode s)  
{  
    s->next = p->next;  //s節點的后繼指針原p節點的下一個節點
    s->previous = p;  //s節點的前繼指針指向p節點

    if(p->next != NULL)  //原p節點下一個節點存在
        p->next->previous = s;  //原p節點下一個節點的前繼指針指向新加的s節點
    p->next = s;//原p節點的后繼指針指向s節點  

    if(p = GetTail(plist)) //如果p是尾節點
        plist->tail = s;  //那么尾指針重新指向新加的s節點，讓s節點作為尾節點

    plist->size++; //插入新節點s后，鏈表大小加1  
    return s;  
}  

/*返回在鏈表中第i個節點的位置*/  
PNode LocatePos(DList *plist,int i)  
{  
    int cnt = 0;  
    Position p = GetHead(plist); //p指向頭節點
    if(i>GetSize(plist)||i<1)  //判斷i大小是否在鏈表大小之間
        return NULL;  

    while(++cnt<=i) //p指針位置從頭節點開始往后移動，直至第i個節點的位置
    {  
        p=p->next;  
    }  

    return p;  //p最后指向的位置就是所求的第i個節點的位置
}  

  /*依次對鏈表中每個元素調用函數visit()打印鏈表元素值*/  
void ListTraverse(DList *plist,void (*visit)())  
{  
    Position p = GetHead(plist);//p指向頭節點   
    if(IsEmpty(plist))  //空鏈表無數據就退出
        printf("NULL");  
    else  
    {  

        while(p->next!=NULL)  //p不斷往下遍歷輸出元素值
        {  
            p = p->next;  
            visit(p->data);            
        }         
    }  
}
 /*打印data*/
void print(Item data)
{
    printf("%d ",data);
}



/test.c/
include"dlist.h"

#include"dlist.c"  
#include<stdio.h>
#include<stdlib.h>   
main()  
{  
    int i,n;
    int select;
    DList *plist = NULL;  
    PNode p = NULL;  
    printf("開始創建空雙向鏈表。。。。。\n");
    plist = InitList();  //創建雙向鏈表
    system("sleep 2");
    printf("創建空雙向鏈表完成！\n");
    printf("請輸入你想創建的節點數目:");
    scanf("%d",&n);
    if(n==0)
    {
        printf("空表不能進行任何操作！\n");
        exit(0);
    }
    int a[n];
    printf("開始創建頭節點。。。。。。\n");
    printf("請輸入頭節點的數據（空頭節點請寫0繼續）:");
    scanf("%d",&a[0]);
    printf("正在創建頭節點。。。。。。\n");
    p = InsFirst(plist,MakeNode(a[0]));
    printf("頭節點創建完成！數據為：%d\n",a[0]);  
       for(i=1;i<n;i++)
    {
        printf("開始創建第%d個節點。。。。。。\n",i);
        printf("請輸入第%d個節點的數據:",i);
        scanf("%d",&a[i]);
        printf("正在創建第%d個節點。。。\n",i);
        p = InsAfter(plist,p,MakeNode(a[i]));
        system("sleep 1");
        printf("創建第%d個節點完成\n",i);
    }
    printf("%d個節點創建完成！",n);
    printf("遍歷輸出各節點數據項:");  
    ListTraverse(plist,print);  
     printf("\n");
    printf("該鏈表共有%d個節點\n",GetSize(plist));
    while(1)
    {
    printf("請選擇您想要做的操作：\n1.在鏈表中p位置之前插入新節點s \n2.刪除第一個節點 \n3.將鏈表置空 \n4.刪除鏈表\n5.退出：\n");
    scanf("%d",&select);
    switch(select)
        {
            case 1:printf("p位置的值為:%d\n",GetItem(p));
            printf("開始創建新節點s。。。。。。\n");
            printf("請輸入新節點s的數據:");
            scanf("%d",&a[n+1]);
            printf("正在創建新節點s。。。\n");
            p = InsBefore(plist,p,MakeNode(a[n+1]));
            system("sleep 1");
            printf("創建新節點s完成！數據為:%d\n",a[n+1]);
            printf("遍歷輸出各節點數據項:");ListTraverse(plist,print);printf("\n");break;
            case 2:DelFirst(plist);system("sleep 1");printf("刪除完成\n"); printf("遍歷輸出各節點數據項:");ListTraverse(plist,print);printf("\n");break;
            case 3:ClearList(plist);system("sleep 1");printf("清空完成\n"); printf("遍歷輸出各節點數據項:");ListTraverse(plist,print);printf("\n");exit(0);
            case 4:DestroyList(plist); printf("鏈表已被銷毀\n");printf("\n");exit(0);
            case 5:exit(0);
            default:printf("您的輸入有誤!\n");
            }
    }

}
         </pre>
本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
本文地址：http://www.baiduhome.net/lib/view/open1410699307711.html
雙向鏈表 C/C++開發
用C語言完成一個雙向鏈表的創建，插入，刪除

相關經驗

相關資訊

相關文檔

目錄
