基本数据结构实现--双链表
基本数据结构实现–双链表
*概述
单链表节点中只有一个指向其后记的指针，使得单链表只能从头节点依次顺序地向后遍历。要访问某个节点的前驱节点，只能从头
开始遍历，在拿到某节点指针p后，访问p的后继节点的时间复杂度为O(1)，访问前驱节点的时间复杂度依旧是O(N)。
为了解决这个问题，引入了双链表。在原本的单链表每个节点中加入了一个指向其前驱的节点prior。因此，在我们拿到某节点指针p
的前提下，想要对这个节点的前驱进行操作就可以在O(1)的时间内完成。请注意：一般情况下我们并没有链表中所有节点的指针信息，
而是仅仅保存类似头节点、尾节点的标志性节点。
对于单链表，拿到某节点指针p后，其后所有节点都可以找到，而想要访问前面的节点只能从头节点开始一一查找。而对于双链表来说，
拿到某节点指针后既可以向后查找，也可以向前查找。
*双链表结构类型的定义
一个双链表的类型可以定义如下：
1 typedef struct DNode { 2 ElemType data; //节点数据域 3 DNode* next,* prior; //后继指针、前驱指针 4 } * DLinkList;
此处，DNode 定义了一个双链表的节点类型，DLinkList便定义了一个双链表。DLinkList即是头结点指针。请注意：要标记一个链表，只需
要保存链表的头节点指针就可以了(当然根据需求不同也可以保存尾指针，甚至第i个节点的指针)。因此这里DLinkList既是双链表的头指针，又
代表了“双链表”这一数据类型。
*双链表基本操作及其实现
(1) 初始化一个双链表
1 void InitDLinkList(DLinkList& L) 2 { 3 L = new DNode; //C语言版:L = (DNode*)malloc(sizeof(DNode)); 4 L->data = 0; 5 L->next = NULL; 6 L->prior = NULL; 7 }
由于L指向的是链表的头节点，这个数据域是不属于链表的有效元素的，如果没有他用，可以随意赋值（这里赋值0）.
(2) 后插操作,在p指向的节点之后插入s指向的节点。插入成功返回true，失败(如p不合法等)返回false。
1 bool InsertNextDNode( DNode* p,DNode* s ) 2 { 3 if( p == NULL || s == NULL ) 4 return false; 5 s->next = p->next; 6 //如果p是最后一个节点，p没有下一个节点，自然不需要修改下一个结点的前驱指针 7 if( p->next != NULL ) 8 p->next->prior = s; 9 s->prior = p; 10 p->next = s; 11 return true; 12 }
注意这里与单链表的不同。双链表在插入、删除操作时不仅要修改next指针，还要修改节点的prior指针。在后插时，
如果p是最后一个节点，则不需要修改p->next->prior：因为p没有next。其他情况时需要修改p->next->prior为s。
(3) 删除操作：删除p的后继节点。成功删除返回true，失败（如p不合法，或p没有后继节点等）返回false。
1 bool DeleteNextDNode( DNode* p ) 2 { 3 if( p == NULL ) 4 return false; 5 if( p->next == NULL ) 6 return false; 7 DNode* q = p->next; //q是p的后继节点 8 //需要修改两个指针：p的next以及q的后继的prior 9 if( q->next != NULL ) 10 q->next->prior = p; 11 p->next = q->next; 12 delete q; //C语言版: free(q); 13 return true; 14 }
要注意：p是否是最后一个节点？p的下一个节点是否是最后一个节点?
(4) 按值查找
1 DNode* LocateElem( DLinkList DL,ElemType e ) 2 { 3 DNode* p = DL->next; 4 while( p != NULL && p->data != e ) { 5 p = p->next; 6 } 7 return p; 8 }
(5) 按位序查找
1 DNode* GetElem( DLinkList L, int i ) 2 { 3 if( i < 0 ) //认为头节点是第0个节点，如果输入i为0则返回头结点的指针 4 return NULL; 5 int j = 0; 6 DNode* p = L; 7 while( j != i && p != NULL ) { 8 j++; 9 p = p->next; 10 } 11 return p; 12 }
按值查找与按位序查找在仅有头指针的前提下和单链表中的实现没有任何区别。
(6) 销毁整个链表
在实现了删除后继节点的操作后，我们就可以使用这个操作，逐一删除头节点的后继节点，从而达成销毁整个
链表的目的。请注意：把头结点看成第0个节点的话，每执行一次，相当于删除了链表中的第一个节点，而删
除前的第二个节点成为了新的第一个节点。实现代码如下：
1 void DestroyList( DLinkList& DL ) 2 { 3 while( DL->next != NULL ) 4 DeleteNextDNode(DL); 5 delete DL; 6 DL = NULL; 7 }
* 代码测试
以下测试先将0,2,4,6,8,10,12,14,16,18这10个数以后插的方式建立链表，然后尝试找到值为18的节点并
将其删除；接下来测试查找不存在的，值为200的节点。然后尝试用后插操作实现一个前插操作。（思想：
在p前插入s，先通过prior指针拿到p的前驱节点pp，这样，就相当于对pp执行后插操作）。
1 /* 带头节点的双链表 2 3 实现操作： 4 *1 删除p的后继节点 5 *2 后插操作：在p后插入s 6 *3 前插操作：在p前插入s 7 *4 按值查找 8 *5 按位序查找 9 *6 销毁整个链表 10 */ 11 #include <iostream> 12 #include <cstdio> 13 using namespace std; 14 15 typedef int ElemType; 16 17 typedef struct DNode { 18 ElemType data; //节点数据域 19 DNode* next,* prior; //后继指针、前驱指针 20 } * DLinkList; 21 22 //初始化一个双链表 23 void InitDLinkList(DLinkList& L) 24 { 25 L = new DNode; //C语言版:L = (DNode*)malloc(sizeof(DNode)); 26 L->data = 0; 27 L->next = NULL; 28 L->prior = NULL; 29 } 30 31 //后插操作,在p指向的节点之后插入s指向的节点 32 bool InsertNextDNode( DNode* p,DNode* s ) 33 { 34 if( p == NULL || s == NULL ) 35 return false; 36 s->next = p->next; 37 //如果p是最后一个节点，p没有下一个节点，自然不需要修改下一个结点的前驱指针 38 if( p->next != NULL ) 39 p->next->prior = s; 40 s->prior = p; 41 p->next = s; 42 return true; 43 } 44 45 //删除操作：删除p节点的后继节点 46 //由于链表是带头结点的，因此使用这个函数也可以删除表的第一个数据节点 47 bool DeleteNextDNode( DNode* p ) 48 { 49 if( p == NULL ) 50 return false; 51 if( p->next == NULL ) 52 return false; 53 DNode* q = p->next; //q是p的后继节点 54 //需要修改两个指针：p的next以及q的后继的prior 55 if( q->next != NULL ) 56 q->next->prior = p; 57 p->next = q->next; 58 delete q; //C语言版: free(q); 59 return true; 60 } 61 62 //销毁整个链表 63 void DestroyList( DLinkList& DL ) 64 { 65 while( DL->next != NULL ) 66 DeleteNextDNode(DL); 67 delete DL; 68 DL = NULL; 69 } 70 71 //打印整个链表 72 void Print( DLinkList DL ) 73 { 74 if( DL == NULL ) 75 return ; 76 DNode* p = DL->next; 77 while( p != NULL ) { 78 cout << p->data << endl; 79 p = p->next; 80 } 81 82 } 83 84 //按值查找：找到表中第一个值等于e的元素，返回其指针，如果 85 //不存在值等于e的，返回NULL 86 DNode* LocateElem( DLinkList DL,ElemType e ) 87 { 88 DNode* p = DL->next; 89 while( p != NULL && p->data != e ) { 90 p = p->next; 91 } 92 return p; 93 } 94 95 //按位序查找,找到表中第i个元素，返回其指针 96 DNode* GetElem( DLinkList L, int i ) 97 { 98 if( i < 0 ) //认为头节点是第0个节点，如果输入i为0则返回头结点的指针 99 return NULL; 100 int j = 0; 101 DNode* p = L; 102 while( j != i && p != NULL ) { 103 j++; 104 p = p->next; 105 } 106 return p; 107 } 108 109 //尝试使用后插操作实现一个前插操作：要在p指向的节点前插入s指向的节点， 110 //先拿到p的前驱节点的指针pp，在pp后插入s 111 bool InsertPriorNode( DNode* p,DNode* s ) 112 { 113 if( p == NULL || s == NULL ) 114 return false ; 115 //如果p的前驱为空，说明p是头节点，显然不能在头节点前插入数据 116 if( p->prior == NULL ) 117 return false; 118 DNode* pp = p->prior; 119 InsertNextDNode(pp,s); 120 return true; 121 } 122 123 124 void test1() 125 { 126 //初始化 127 DLinkList DL; 128 InitDLinkList(DL); 129 //测试后插 130 for( int i=0; i<10; i++ ) { 131 DNode* temp = new DNode; 132 temp->data = 2*i; 133 temp->next = temp->prior = NULL; 134 InsertNextDNode(DL,temp); 135 } 136 Print(DL); 137 cout << "-------------------------" << endl; 138 //测试按值查找和删除 139 { 140 //尝试找到值为18的节点并将其删除 141 DNode* temp = LocateElem(DL,18); 142 if( temp != NULL ) 143 DeleteNextDNode(temp); 144 145 //尝试查找不存在的节点 146 temp = LocateElem(DL,200); 147 if( temp == NULL ) { 148 cout << "200不存在" << endl; 149 } 150 } 151 Print(DL); 152 cout << "--------------------------" << endl; 153 //测试前插操作 154 { 155 //尝试在第一个元素及最后一个元素前插入值为985的元素 156 DNode* temp1 = GetElem(DL,1); 157 DNode* temp2 = GetElem(DL,9); //表中现在只有9个元素 158 cout << temp2->data << endl; 159 DNode* _9851 = new DNode; 160 _9851->data = 985; 161 _9851->next = _9851->prior = NULL; 162 DNode* _9852 = new DNode; 163 _9852->data = 985; 164 _9852->next = _9852->prior = NULL; 165 if( InsertPriorNode(temp1,_9851) && InsertPriorNode(temp2,_9852) ) 166 Print(DL); 167 } 168 //测试销毁 169 { 170 DestroyList(DL); 171 cout << "123456" << endl; 172 Print(DL); 173 cout << "123456" << endl; 174 } 175 } 176 177 int main() 178 { 179 test1(); 180 return 0; 181 }