/*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
#include
/*分配值為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
#include
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
