一个做网页的网站,所有网页游戏网址,漫画app软件定制开发,wordpress内容表单http://blog.csdn.net/jw903/article/details/38947753 双向链表其实是单链表的改进。 当我们对单链表进行操作时#xff0c;有时你要对某个结点的直接前驱进行操作时#xff0c;又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后…http://blog.csdn.net/jw903/article/details/38947753 双向链表其实是单链表的改进。 当我们对单链表进行操作时有时你要对某个结点的直接前驱进行操作时又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域那么能不能定义一个既有存储直接后继结点地址的链域又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢这就是双向链表。 在双向链表中结点除含有数据域外还有两个链域一个存储直接后继结点地址一般称之为右链域一个存储直接前驱结点地址一般称之为左链域。 在c语言中双向链表结点类型可以定义为 [cpp] view plain copy typedef struct Node { int item; struct Node *pre; struct Node *next; }DListNode,*DList; 下面的代码就是对双向链表的创建和相关操作 [cpp] view plain copy /*************************************************************************** *name:jae chia * *date:2014.8.29 * *version: 1.0 * **************************************************************************/ #includeiostream #includecassert using namespace std; //双向链表的建立与操作 typedef struct Node { int item; struct Node *pre; struct Node *next; }DListNode,*DList; DList InsertNodeToTail(DList head,int data)//将节点插入到双向链表的尾部 { if(headNULL) { head(DList)malloc(sizeof(DListNode)); assert(head!NULL); head-itemdata; head-nextNULL; head-preNULL; } else { DListNode *newnode(DList)malloc(sizeof(DListNode));//创建新的链表节点 assert(newnode!NULL); newnode-itemdata; newnode-nextNULL; newnode-preNULL; DListNode *phead; while(p-next!NULL) { pp-next; } p-nextnewnode; newnode-prep; } return head; } DList InsertDListByOrder(DList head,int data)//这里的插入操作是按序插入保证双向链表中的节点以递增有序 { DListNode *newnode(DList)malloc(sizeof(DListNode)); assert(newnode); newnode-itemdata; //newnode-nextNULL; //newnode-preNULL; DListNode *phead; DListNode *prenode; for(;p!NULL;pp-next) { prenodep; if(newnode-item p-item) break; } if(pNULL)//如果遍历整个链表结点的值都比要插入的小那么只能在尾端插入 { prenode-nextnewnode; newnode-preprenode; newnode-nextNULL; } else if(phead)//如果链表中的数都比要插入的数大则在头部插入 { newnode-preNULL; newnode-nexthead; headnewnode; } else //在中间插入 { p-pre-nextnewnode; newnode-prep-pre; newnode-nextp; p-prenewnode; } return head; } bool FindNode(DList head,int data)//查找链表中含有某元素的节点是否存在 { if(headNULL) { coutthe Dlist is NULLendl; return false; } DListNode *phead; while(p!NULL) { if(p-itemdata) return true; pp-next; } return false; } DList DeleteNode(DList head,int data)//删除节点 { DListNode *phead; while(p!NULL) { if(p-itemdata) break; pp-next; } if(pNULL) { coutthe node with data is not existed in the Listendl; exit(0); } if(phead)//要删除的结点恰好是双向链表的头结点 { DListNode *tmphead; headhead-next; head-preNULL;//--------------------------------------------------- free(tmp); } else if(p-nextNULL)//如果要删除的节点是链表的最后一个节点 { p-pre-nextNULL; free(p); } else //删除中间节点 { p-pre-nextp-next; p-next-prep-pre; } return head; } void PrintDList(DList head)//打印 { cout现在链表如下:endl; if(headNULL) { coutthe Dlist is NULLendl; return ; } DListNode *phead; while(p!NULL) { coutp-item ; pp-next; } coutendlendl; } void DestroyDList(DList head)//销毁双向链表 { DListNode *phead; while(p!NULL) { DListNode *tmpp; pp-next; free(tmp); } } void Test() { DListNode *headNULL; for(int i0;i10;i) /*利用尾部插入来构造双向链表*/ headInsertNodeToTail(head,i); PrintDList(head); int a; cout输入要查找的结点的值endl; cina; if(FindNode(head,a)) cout结点存在endlendl; else cout结点不存在!endlendl; cout删除结点4...endl; /*删除指定节点*/ headDeleteNode(head,4); PrintDList(head); cout插入结点4...endl; /*按序插入*/ headInsertDListByOrder(head,4); PrintDList(head); cout删除头结点...endl; /*删除指定节点*/ headDeleteNode(head,0); PrintDList(head); cout删除尾结点...endl; headDeleteNode(head,9); PrintDList(head); cout插入头结点...endl; /*按序插入*/ headInsertDListByOrder(head,0); PrintDList(head); cout插入尾结点...endl; /*按序插入*/ headInsertDListByOrder(head,10); PrintDList(head); DestroyDList(head); } int main(void) { Test(); } 运行
