1雙向鏈表
單鏈表只能從頭結(jié)點開始訪問鏈表中的數(shù)據(jù)元素硕旗，如果需要逆序訪問單鏈表中的數(shù)據(jù)元素將極其低效缺谴。
雙鏈表是鏈表的一種但惶，由節(jié)點組成，每個數(shù)據(jù)結(jié)點中都有兩個指針湿蛔，分別指向直接后繼和直接前驅(qū)膀曾。
雙鏈表（雙向鏈表）：雙鏈表和單鏈表相比，多了一個指向尾指針（tail）阳啥，雙鏈表的每個結(jié)點都有一個頭指針head和尾指針tail,雙鏈表相比單鏈表更容易操作添谊，雙鏈表結(jié)點的首結(jié)點的head指向為null，tail指向下一個節(jié)點的tail;尾結(jié)點的head指向前一個結(jié)點的head苫纤，tail 指向為null碉钠，是雙向的關(guān)系；
指針域 prior：用于指向當(dāng)前節(jié)點的直接前驅(qū)節(jié)點卷拘；
數(shù)據(jù)域 data：用于存儲數(shù)據(jù)元素喊废。
指針域 next：用于指向當(dāng)前節(jié)點的直接后繼節(jié)點；
雙向鏈表的結(jié)構(gòu)如圖
增加頭節(jié)點便于首元節(jié)點處理
1.1雙向鏈表實現(xiàn)
定義變量
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼栗弟，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實際情況而定污筷，這里假設(shè)為int */
//定義結(jié)點
typedef struct Node{
ElemType data;
struct Node *prior;
struct Node *next;
}Node;
typedef struct Node * LinkList;
2創(chuàng)建雙向鏈表
Status createLinkList(LinkList *L){
//*L 指向頭結(jié)點
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) return ERROR;
(*L)->prior = NULL;
(*L)->next = NULL;
(*L)->data = -1;
//新增數(shù)據(jù)
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.創(chuàng)建1個臨時的結(jié)點
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->prior = NULL;
temp->next = NULL;
temp->data = I;
//2.為新增的結(jié)點建立雙向鏈表關(guān)系
//① temp 是p的后繼
p->next = temp;
//② temp 的前驅(qū)是p
temp->prior = p;
//③ p 要記錄最后的結(jié)點的位置,方便下一次插入
p = p->next;
}
return OK;
}
3.打印循環(huán)鏈表的元素
void display(LinkList L){
LinkList temp = L->next;
if(temp == NULL){
printf("打印的雙向鏈表為空!\n");
return;
}
while (temp) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
4.雙向鏈表插入元素
將priorNode->next節(jié)點的prior指向新節(jié)點；
將新節(jié)點->next指向原來的priorNode->next乍赫；
將priorNode->next指向新節(jié)點瓣蛀；
新節(jié)點的prior指向priorNode。
Status ListInsert(LinkList *L, int i, ElemType data){
//1. 插入的位置不合法 為0或者為負(fù)數(shù)
if(i < 1) return ERROR;
//2. 新建結(jié)點
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
//3.將p指向頭結(jié)點!
LinkList p = *L;
//4. 找到插入位置i直接的結(jié)點
for(int j = 1; j < i && p;j++)
p = p->next;
//5. 如果插入的位置超過鏈表本身的長度
if(p == NULL){
return ERROR;
}
//6. 判斷插入位置是否為鏈表尾部;
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
}else
{
//1?? 將p->next 結(jié)點的前驅(qū)prior = temp
p->next->prior = temp;
//2?? 將temp->next 指向原來的p->next
temp->next = p->next;
//3?? p->next 更新成新創(chuàng)建的temp
p->next = temp;
//4?? 新創(chuàng)建的temp前驅(qū) = p
temp->prior = p;
}
return OK;
}
5.刪除雙向鏈表指定位置上的結(jié)點
遍歷找到要刪除的節(jié)點雷厂，更改前驅(qū)節(jié)點的next指針和后繼節(jié)點的prior指針
Status ListDelete(LinkList *L, int i, ElemType *e){
int k = 1;
LinkList p = (*L);
//1.判斷雙向鏈表是否為空,如果為空則返回ERROR;
if (*L == NULL) {
return ERROR;
}
//2. 將指針p移動到刪除元素位置前一個
while (k < i && p != NULL) {
p = p->next;
k++;
}
//3.如果k>i 或者 p == NULL 則返回ERROR
if (k>i || p == NULL) {
return ERROR;
}
//4.創(chuàng)建臨時指針delTemp 指向要刪除的結(jié)點,并將要刪除的結(jié)點的data 賦值給*e,帶回到main函數(shù)
LinkList delTemp = p->next;
*e = delTemp->data;
//5. p->next 等于要刪除的結(jié)點的下一個結(jié)點
p->next = delTemp->next;
//6. 如果刪除結(jié)點的下一個結(jié)點不為空,則將將要刪除的下一個結(jié)點的前驅(qū)指針賦值p;
if (delTemp->next != NULL) {
delTemp->next->prior = p;
}
//7.刪除delTemp結(jié)點
free(delTemp);
return OK;
}
刪除雙向鏈表指定的元素
Status LinkListDeletVAL(LinkList *L, int data){
LinkList p = *L;
//1.遍歷雙向循環(huán)鏈表
while (p) {
//2.判斷當(dāng)前結(jié)點的數(shù)據(jù)域和data是否相等,若相等則刪除該結(jié)點
if (p->data == data) {
//修改被刪除結(jié)點的前驅(qū)結(jié)點的后繼指針,參考圖上步驟1??
p->prior->next = p->next;
//修改被刪除結(jié)點的后繼結(jié)點的前驅(qū)指針,參考圖上步驟2??
if(p->next != NULL){
p->next->prior = p->prior;
}
//釋放被刪除結(jié)點p
free(p);
//退出循環(huán)
break;
}
//沒有找到該結(jié)點,則繼續(xù)移動指針p
p = p->next;
}
return OK;
}
6.在雙向鏈表中查找元素
int selectElem(LinkList L,ElemType elem){
LinkList p = L->next;
int i = 1;
while (p) {
if (p->data == elem) {
return I;
}
I++;
p = p->next;
}
return -1;
}
7.在雙向鏈表中更新結(jié)點
Status replaceLinkList(LinkList *L,int index,ElemType newElem){
LinkList p = (*L)->next;
for (int i = 1; i < index; i++) {
p = p->next;
}
p->data = newElem;
return OK;
}
調(diào)用
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
Status iStatus = 0;
LinkList L;
int temp,item,e;
iStatus = createLinkList(&L);
printf("iStatus = %d\n",iStatus);
printf("鏈表創(chuàng)建成功,打印鏈表:\n");
display(L);
printf("請輸入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入數(shù)據(jù),打印鏈表:\n");
display(L);
printf("請輸入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入數(shù)據(jù),打印鏈表:\n");
display(L);
printf("請輸入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入數(shù)據(jù),打印鏈表:\n");
display(L);
printf("請輸入刪除的位置\n");
scanf("%d",&temp);
iStatus = ListDelete(&L, temp, &e);
printf("刪除元素: 刪除位置為%d,data = %d\n",temp,e);
printf("刪除操作之后的,雙向鏈表:\n");
display(L);
printf("請輸入你要刪除的內(nèi)容\n");
scanf("%d",&temp);
iStatus = LinkListDeletVAL(&L, temp);
printf("刪除指定data域等于%d的結(jié)點,雙向鏈表:\n",temp);
display(L);
printf("請輸入你要查找的內(nèi)容\n");
scanf("%d",&temp);
ElemType index = selectElem(L, temp);
printf("在雙向鏈表中查找到數(shù)據(jù)域為%d的結(jié)點,位置是:%d\n",temp,index);
printf("請輸入你要更新的結(jié)點以及內(nèi)容\n");
scanf("%d %d",&temp,&item);
iStatus = replaceLinkList(&L, temp, item);
printf("更新結(jié)點數(shù)據(jù)后的雙向鏈表:\n");
display(L);
return 0;
}
2.雙向循環(huán)列表
雙向循環(huán)列表與雙向列表的區(qū)別在于雙向循環(huán)列表的頭節(jié)點的prior指針指向尾節(jié)點惋增，尾節(jié)點的next指針指向頭節(jié)點構(gòu)成一個循環(huán)。
結(jié)構(gòu)如圖
1.雙向循環(huán)列表初始化
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存儲空間初始分配量 */
typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼改鲫，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實際情況而定诈皿，這里假設(shè)為int */
//定義結(jié)點
typedef struct Node{
ElemType data;
struct Node *prior;
struct Node *next;
}Node;
typedef struct Node * LinkList;
//6.1 雙向循環(huán)鏈表初始化
Status creatLinkList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) {
return ERROR;
}
(*L)->next = (*L);
(*L)->prior = (*L);
//新增數(shù)據(jù)
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.創(chuàng)建1個臨時的結(jié)點
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data = i;
//2.為新增的結(jié)點建立雙向鏈表關(guān)系
//① temp 是p的后繼
p->next = temp;
//② temp 的前驅(qū)是p
temp->prior = p;
//③ temp的后繼是*L
temp->next = (*L);
//④ p 的前驅(qū)是新建的temp
p->prior = temp;
//⑤ p 要記錄最后的結(jié)點的位置,方便下一次插入
p = p->next;
}
return OK;
}
2.雙向循環(huán)鏈表遍歷
Status Display(LinkList L){
if (L == NULL) {
printf("打印的雙向循環(huán)鏈表為空!\n\n");
return ERROR;
}
printf("雙向循環(huán)鏈表內(nèi)容: ");
LinkList p = L->next;
while (p != L) {
printf("%d ",p->data);
p = p->next;
}
printf("\n\n");
return OK;
}
3.雙向循環(huán)鏈表插入元素
/*當(dāng)插入位置超過鏈表長度則插入到鏈表末尾*/
Status LinkListInsert(LinkList *L, int index, ElemType e){
//1. 創(chuàng)建指針p,指向雙向鏈表頭
LinkList p = (*L);
int i = 1;
//2.雙向循環(huán)鏈表為空,則返回error
if(*L == NULL) return ERROR;
//3.找到插入前一個位置上的結(jié)點p
while (i < index && p->next != *L) {
p = p->next;
i++;
}
//4.如果i>index 則返回error
if (i > index) return ERROR;
//5.創(chuàng)建新結(jié)點temp
LinkList temp = (LinkList)malloc(sizeof(Node));
//6.temp 結(jié)點為空,則返回error
if (temp == NULL) return ERROR;
//7.將生成的新結(jié)點temp數(shù)據(jù)域賦值e.
temp->data = e;
//8.將結(jié)點temp 的前驅(qū)結(jié)點為p;
temp->prior = p;
//9.temp的后繼結(jié)點指向p->next;
temp->next = p->next;
//10.p的后繼結(jié)點為新結(jié)點temp;
p->next = temp;
//如果temp 結(jié)點不是最后一個結(jié)點
if (*L != temp->next) {
//11.temp節(jié)點的下一個結(jié)點的前驅(qū)為temp 結(jié)點
temp->next->prior = temp;
}else{
(*L)->prior = temp;
}
return OK;
}
4.雙向循環(huán)鏈表刪除結(jié)點
Status LinkListDelete(LinkList *L,int index,ElemType *e){
int i = 1;
LinkList temp = (*L)->next;
if (*L == NULL) {
return ERROR;
}
//①.如果刪除到只剩下首元結(jié)點了,則直接將*L置空;
if(temp->next == *L){
free(*L);
(*L) = NULL;
return OK;
}
//1.找到要刪除的結(jié)點
while (i < index) {
temp = temp->next;
i++;
}
//2.給e賦值要刪除結(jié)點的數(shù)據(jù)域
*e = temp->data;
//3.修改被刪除結(jié)點的前驅(qū)結(jié)點的后繼指針 圖1??
temp->prior->next = temp->next;
//4.修改被刪除結(jié)點的后繼結(jié)點的前驅(qū)指針 圖2??
temp->next->prior = temp->prior;
//5. 刪除結(jié)點temp
free(temp);
return OK;
}
調(diào)用
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
LinkList L;
Status iStatus;
ElemType temp,item;
iStatus = creatLinkList(&L);
printf("雙向循環(huán)鏈表初始化是否成功(1->YES)/ (0->NO): %d\n\n",iStatus);
Display(L);
printf("輸入要插入的位置和數(shù)據(jù)用空格隔開：");
scanf("%d %d",&temp,&item);
iStatus = LinkListInsert(&L,temp,item);
Display(L);
printf("輸入要刪除位置：");
scanf("%d",&temp);
iStatus = LinkListDelete(&L, temp, &item);
printf("刪除鏈表位置為%d,結(jié)點數(shù)據(jù)域為:%d\n",temp,item);
Display(L);
return 0;
}
