好贷网好贷款

双链表

发布时间:2016-12-4 7:52:40 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"双链表",主要涉及到双链表方面的内容,对于双链表感兴趣的同学可以参考一下。

双链表 1、双向链表(Double Linked List)      双(向)链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域prior。      注意:      ①双链表由头指针head惟一确定的。      ②带头结点的双链表的某些运算变得方便。      ③将头结点和尾结点链接起来,为双(向)循环链表。 2、双向链表的结点结构和形式描述 ①结点结构(见上图a)        ②形式描述      typedef struct dlistnode{          DataType data;          struct dlistnode *prior,*next;       }DListNode;     typedef DListNode *DLinkList;     DLinkList head; 3、双向链表的前插和删除本结点操作      由于双链表的对称性,在双链表能能方便地完成各种插入、删除操作。 ①双链表的前插操作             void DInsertBefore(DListNode *p,DataType x)       {//在带头结点的双链表中,将值为x的新结点插入*p之前,设p≠NULL         DListNode *s=malloc(sizeof(DListNode));//①         s->data=x;//②         s->prior=p->prior;//③         s->next=p;//④         p->prior->next=s;//⑤         p->prior=s;//⑥        } ②双链表上删除结点*p自身的操作             void DDeleteNode(DListNode *p)       {//在带头结点的双链表中,删除结点*p,设*p为非终端结点           p->prior->next=p->next;//①           p->next->prior=p->prior;//②           free(p);//③       }  注意:      与单链表上的插入和删除操作不同的是,在双链表中插入和删除必须同时修改两个方向上的指针。      上述两个算法的时间复杂度均为O(1)???? 上面说的 O(1)是指的指针已经指向了要删除的节点!! 其实单链表也会是O(1)的!!   在单链表中,NextElem的执行时间为O(),而PriorElem的执行时间为O(n)。为了克服这个单向性的缺点,可利用双向链表。 在双链表的结点中有两个指针域,其一指向直接后继,另一指向直接前驱。 功能: (1)       初始化双链表 InitList(DLinkList *&L); (2)       采用尾插法插入a,b,c,d,e元素 DestroyList(DLinkList  *L); (3)       输出双链表h (4)       输出双链表长度 (5)       判断双链表h是否为空 (6)       输出双链表h的第三个元素 (7)       输出元素a的位置 (8)       在第四个元素位置上插入f元素 (9)       输出双链表h (10)   删除h的第三个元素 (11)   释放双链表h     程序:         #include "stdafx.h"         using namespace std;  typedef  char  ElemType;                                                                                                                                                    //双链表结构体  typedef  struct  LNode  {   char  Name[1024];   struct LNode  *next;   struct LNode  *pre;  }DLinkList, *pDLinkList;  pDLinkList  HeadList;        // (1) 初始化双链表 void InitList(pDLinkList &L)     //加&为引用,为了改变外部传入的参数值 {  L = (pDLinkList)malloc(sizeof(DLinkList));      //创建头结点  ZeroMemory(L->Name,sizeof(L->Name));  L->next=L->pre = NULL; }   // (2) 采用尾插法插入元素 void ListInsert(char* name) {                                       pDLinkList p, newNode;  p = HeadList;  while (p->next != NULL)  {   p = p->next;  }  newNode = (pDLinkList)malloc(sizeof(DLinkList));  ZeroMemory(newNode->Name,sizeof(newNode->Name));  strcpy_s(newNode->Name,name);  newNode->next =NULL;  p->next = newNode;  newNode->pre = p; }   // (3) 输出双链表 void ReadList() {  pDLinkList p;  p = HeadList->next;  while (p != NULL )  {   cout<<"用户名 = "<<p->Name<<endl;   p = p->next;  } }   // (4) 输出双链表长度 int  GetListLength() {  int  length = 0;  pDLinkList p = HeadList;  while (p != NULL)  {   p = p->next;   ++length;  }  return length; }   // (5) 判断双链表h是否为空 int ListEmpty(pDLinkList  L) {  return (L->next == NULL); }   // (8) 在第i个位置上插入元素name bool NumberInsert(pDLinkList L,int i ,char* name) {  int x = 1;  pDLinkList   p = L->next;  while (p != NULL && x<(i-1))  {   p = p->next;   ++x;  }  if (p == NULL)  {   return false;  }  pDLinkList newNode = (pDLinkList)malloc(sizeof(DLinkList));  strcpy_s(newNode->Name,name);  newNode->next = p->next;  newNode->pre = p;  p->next = newNode;  return true; }   // (10) 删除双链表的第i个元素 bool  ListNumberDelete(pDLinkList &List,int i) {  int j = 0;  pDLinkList p = List, DelNode;  while(p!=NULL&&j<i-1)  {   p = p->next;   ++j;  }  if (p == NULL)            //未找到第i-1个结点  {   return false;  }  else  {   DelNode = p->next;         //DelNode指向要删除的结点   if (DelNode == NULL)   {    return false;   }   p->next = DelNode->next;    //从链表中删除DelNode结点   if (DelNode->next != NULL)   {    DelNode->next->pre = p;   }   free(DelNode);                       //释放DelNode结点   return true;  } } int _tmain(int argc, _TCHAR* argv[]) {  InitList(HeadList);  char* buffer1 = "杭州";  char* buffer2 = "下沙";  char* buffer3 = "武汉";  char* buffer4 = "宁波";  char* buffer5 = "南京";  ListInsert(buffer1);  ListInsert(buffer2);  ListInsert(buffer3);  ListInsert(buffer4);  cout<<"原链表"<<endl;  ReadList();  cout<<endl;  cout<<"第三位插入数值后"<<endl;  NumberInsert(HeadList,3 , buffer5);  ReadList();  cout<<endl;  cout<<"第2位删除数值后"<<endl;      ListNumberDelete(HeadList,2);      ReadList();  return 0; } 效果:

上一篇:数据文件和控制文件
下一篇:java使用memcached

相关文章

关键词: 双链表

相关评论