双向链表的操作

2013-08-17 17:57:12
双向链表的操作。
代码（测试通过，暂未发现错误，欢迎交流指正！）：
  1 #include <iostream>
  2 #include <cassert>
  3 using namespace std;
  4 
  5 typedef int DataType;  //链表元素类型
  6 
  7 typedef struct doubleLinkNode    //双向链表结点
  8 {
  9     DataType data;
 10     doubleLinkNode *prior;
 11     doubleLinkNode *next;
 12 }DLNode,*PDLNode;
 13 
 14 //链表初始化
 15 void InitDoubleLink(PDLNode &pHead)
 16 {
 17     pHead = new DLNode;
 18     pHead->data = 0;
 19     pHead->prior = NULL;
 20     pHead->next = NULL;
 21 }
 22 
 23 //创建链表
 24 PDLNode CreatDoubleLink(PDLNode &pHead)
 25 {
 26     DataType dataTmp = 0;
 27     PDLNode pNew = NULL;
 28     //PDLNode pPre = pHead;
 29 
 30     InitDoubleLink(pHead);
 31     PDLNode pPre = pHead;  //在InitDoubleLink之后赋值，而不是在之前赋值
 32 
 33     cout<<"Please enter the elements of the link  ,separate with space,and end with ctrl+z :"<<endl;
 34     while (cin>>dataTmp)
 35     {
 36         pNew = new DLNode;  //new出来的空间需要测试是否为空吗？
 37         pNew->data = dataTmp;
 38         pNew->next = NULL;
 39         pNew->prior = pPre;
 40 
 41         pPre->next = pNew;
 42         pPre = pNew;
 43     }
 44 
 45     return pHead;
 46 }
 47 
 48 //删除链表元素
 49 PDLNode DeleteDoubleLink(PDLNode &pHead,size_t posToDelete)
 50 {
 51     assert(NULL != pHead);
 52 
 53     PDLNode pCur = pHead;
 54     while (posToDelete--)  
 55     {
 56         pCur = pCur->next;
 57         assert(NULL != pCur);
 58     }
 59 
 60     pCur->prior->next = pCur->next;
 61     if (pCur->next != NULL)
 62     {
 63         pCur->next->prior = pCur->prior;
 64     }
 65 
 66     delete pCur;
 67     return pHead;
 68 }
 69 
 70 //链表插入
 71 PDLNode InsertDoubleLink(PDLNode &pHead,size_t posToInsert,const DataType dataToInsert)
 72 {
 73     assert(NULL != pHead);
 74 
 75     PDLNode pNew = new DLNode;  //new出来的空间需要测试是否为空吗？
 76     pNew->data = dataToInsert;
 77     pNew->next = NULL;
 78     pNew->prior = NULL;
 79 
 80     PDLNode pCur = pHead;
 81     while (posToInsert--)  
 82     {
 83         pCur = pCur->next;
 84         assert(NULL != pCur);
 85     }
 86 
 87     pNew->prior = pCur;
 88     pNew->next = pCur->next;
 89     pCur->next = pNew;
 90 
 91     if (pCur->next != NULL)   //对插入到尾部的情况进行处理
 92     {
 93         pCur->next->prior = pNew;
 94     }
 95 
 96     return pHead;
 97 }
 98 
 99 //链表显示
100 void DisplayDoubleLink(const PDLNode &pHead)
101 {
102     assert(NULL != pHead);
103     PDLNode pCur = pHead->next;
104 
105     while (NULL != pCur)
106     {
107         cout<<pCur->data<<"	";
108         pCur = pCur->next;
109     }
110     cout<<endl;
111 }
112 
113 //链表销毁
114 void DestoryDoubleLink(PDLNode &pHead)
115 {
116     assert(NULL != pHead);
117     PDLNode pCur = pHead->next;
118     
119     while (NULL != pCur)
120     {
121         delete pCur->prior;
122         pCur = pCur->next;
123     }
124 }
125 
126 //链表测试
127 void TestDoubleLink()
128 {
129     PDLNode pHead = NULL;
130 
131     //Test CreatDoubleLink...
132     cout<<"Test CreatDoubleLink..."<<endl;
133     pHead = CreatDoubleLink(pHead);
134     cout<<"display the link created by CreatLink : "<<endl;
135     DisplayDoubleLink(pHead);
136     cin.clear();  //清除流状态
137     cin.sync();
138     
139 
140     //Test InsertDoubleLink...
141     //cout<<"Test InsertDoubleLink..."<<endl;
142     //size_t posToInsert = 0;
143     //DataType dataToInsert = 0;
144 
145     //cout<<"Please enter the position and the data to insert,end with ctrl+z :"<<endl;
146     //while (cin>>posToInsert>>dataToInsert)
147     //{
148     //    cout<<"The link before insertion : "<<endl;
149     //    DisplayDoubleLink(pHead);
150 
151     //    pHead = InsertDoubleLink(pHead,posToInsert,dataToInsert);
152 
153     //    cout<<"The link after insertion : "<<endl;
154     //    DisplayDoubleLink(pHead);
155 
156     //    cout<<"Please enter the position to insert,end with ctrl+z :"<<endl;
157     //}
158     //cin.clear();  //清除流状态
159     //cin.sync();
160 
161     //Test DeleteDoubleLink...
162     size_t posToDelete = 0;
163     
164     cout<<"Please enter the position to delete,end with ctrl+z :"<<endl;
165     while (cin>>posToDelete)
166     {
167         cout<<"The link before insertion : "<<endl;
168         DisplayDoubleLink(pHead);
169 
170         pHead = DeleteDoubleLink(pHead,posToDelete);
171 
172         cout<<"The link after delete : "<<endl;
173         DisplayDoubleLink(pHead);
174 
175         cout<<"Please enter the position to delete,end with ctrl+z :"<<endl;
176     }
177 
178     cin.clear();  //清除流状态
179     cin.sync();
180 
181     DestoryDoubleLink(pHead);
182 }
183 
184 //main
185 int main()
186 {
187     TestDoubleLink();
188     return 0;
189 }