溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
數據結構 雙向鏈表的實現
雙向鏈表中的每一個結點都含有兩個指針域，一個指針域存放其后繼結點的存儲地址，另一個指針域則存放其前驅結點的存儲地址。
雙向鏈表結點的類型描述：
//雙向鏈表的類型描述
typedef int ElemType;
typedef struct node{
ElemType data;
struct node *prior,*next;
}DuLNode,*DuLinkList;
其中，prior域存放的是其前驅結點的存儲地址，next域存放的是其后繼結點的存儲地址。
雙向鏈表有兩個特點：
一是可以從兩個方向搜索某個結點，這使得鏈表的某些操作（如插入和刪除）變得比較簡單； 二是無論利用前鏈還是后鏈都可以遍歷整個雙向鏈表。
雙向鏈表的操作基本和單鏈表的操作相同；
1. 頭插法創建帶頭結點的雙向鏈表Create_DLinkListF(int n)
//頭插法創建帶頭結點的雙向鏈表
DuLinkList Create_DLinkListF(int n){
DuLinkList L,p;
int i = n - 1;
ElemType x;
//新建頭結點
L = (DuLinkList)malloc(sizeof(DuLNode));
L->prior = NULL;
L->next = NULL;
//添加第一個結點
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
L->next = p;
p->prior = L;
p->next = NULL;
//加入其他結點
while(i > 0){
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
p->next = L->next;
L->next->prior = p;
p->prior = L;
L->next = p;
i--;
}
return L;
}
2. 尾插法創建帶頭結點的雙向鏈表Create_DLinkListR(int n)
//尾插法創建帶頭結點的雙向鏈表
DuLinkList Create_DLinkListR(int n){
DuLinkList L,p,lastNode;
int i = n - 1;
ElemType x;
//新建頭結點
L = (DuLinkList)malloc(sizeof(DuLNode));
L->prior = NULL;
L->next = NULL;
//添加第一個結點
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
L->next = p;
p->prior = L;
p->next = NULL;
lastNode = p;
//加入其他結點
while(i > 0){
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
lastNode->next = p;
p->prior = lastNode;
p->next = NULL;
lastNode = p;
i--;
}
return L;
}
3. 在指定結點之前插入新結點Insert_DLinkListBefore(DuLinkList p,ElemType x)
//在指定結點之前插入新結點
void Insert_DLinkListBefore(DuLinkList p,ElemType x){
DuLinkList newNode;
//判斷結點p之前的結點的合法性：
if(p->prior == NULL)
printf("結點不合法，不能在該結點之前插入結點\n");
else{
newNode = (DuLinkList)malloc(sizeof(DuLNode));
newNode->data = x;
newNode->next = p;
p->prior->next = newNode;
newNode->prior = p->prior;
p->prior = newNode;
}
}
4. 在指定結點之后插入新結點Insert_DLinkListAfter(DuLinkList p,ElemType x)
//在指定結點之后插入新結點
void Insert_DLinkListAfter(DuLinkList p,ElemType x){
DuLinkList newNode;
newNode = (DuLinkList)malloc(sizeof(DuLNode));
newNode->data = x;
//當插入位置是最后一個結點之后時
if(p->next == NULL){
p->next = newNode;
newNode->prior = p;
newNode->next = NULL;
}
else{
newNode->next = p->next;
p->next->prior = newNode;
p->next = newNode;
newNode->prior = p;
}
}
5. 刪除指定結點Delete_DLinkList(DuLinkList p)
//刪除指定結點
void Delete_DLinkList(DuLinkList p){
//如果刪除的是最后一個元素
if(p->next == NULL)
p->prior->next = NULL;
else{
p->prior->next = p->next;
p->next->prior = p->prior;
}
free(p);
}
6. 后鏈輸出雙向鏈表Print_DLinkListN(DuLinkList L)
//后鏈輸出雙向鏈表
void Print_DLinkListN(DuLinkList p){
while(p != NULL){
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}
7.前鏈輸出雙向鏈表Print_DLinkListP(DuLinkList p)
//前鏈輸出雙向鏈表
void Print_DLinkListP(DuLinkList p){
while(p != NULL){
printf("%d\t",p->data);
p = p-prior;
}
printf("\n");
}
至于雙向鏈表的其他操作，如定位，和單鏈表的操作類同，不再贅述。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
