您的位置: 首页  >  文章  >  双向链表的创建和相关操作

双向链表的创建和相关操作

分类: 文章 • 2024-08-05 19:13:04

http://blog.****.net/jw903/article/details/38947753

   双向链表其实是单链表的改进。 当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

   在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

   在c语言中双向链表结点类型可以定义为：

[cpp] view plain copy
  1. typedef struct Node  
  2. {  
  3.     int item;  
  4.     struct Node *pre;  
  5.     struct Node *next;  
  6. }DListNode,*DList;  

下面的代码就是对双向链表的创建和相关操作：

[cpp] view plain copy
  1. /*************************************************************************** 
  2.  *name:jae chia                                                            * 
  3.  *date:2014.8.29                                                           * 
  4.  *version: 1.0                                                             * 
  5.  **************************************************************************/  
  6. #include<iostream>  
  7. #include<cassert>  
  8. using namespace std;  
  9.   
  10. //双向链表的建立与操作  
  11. typedef struct Node  
  12. {  
  13.     int item;  
  14.     struct Node *pre;  
  15.     struct Node *next;  
  16. }DListNode,*DList;  
  17. DList InsertNodeToTail(DList head,int data)//将节点插入到双向链表的尾部  
  18. {  
  19.     if(head==NULL)  
  20.     {  
  21.         head=(DList)malloc(sizeof(DListNode));  
  22.         assert(head!=NULL);  
  23.         head->item=data;  
  24.         head->next=NULL;  
  25.         head->pre=NULL;  
  26.     }  
  27.     else  
  28.     {  
  29.         DListNode *newnode=(DList)malloc(sizeof(DListNode));//创建新的链表节点  
  30.         assert(newnode!=NULL);  
  31.         newnode->item=data;  
  32.         newnode->next=NULL;  
  33.         newnode->pre=NULL;  
  34.   
  35.         DListNode *p=head;  
  36.         while(p->next!=NULL)  
  37.         {  
  38.             p=p->next;  
  39.         }  
  40.         p->next=newnode;  
  41.         newnode->pre=p;  
  42.     }  
  43.     return head;  
  44. }  
  45.   
  46. DList InsertDListByOrder(DList head,int data)//这里的插入操作是按序插入（保证双向链表中的节点以递增有序）  
  47. {  
  48.     DListNode *newnode=(DList)malloc(sizeof(DListNode));  
  49.     assert(newnode);  
  50.     newnode->item=data;  
  51.     //newnode->next=NULL;  
  52.     //newnode->pre=NULL;  
  53.   
  54.     DListNode *p=head;  
  55.     DListNode *prenode;  
  56.     for(;p!=NULL;p=p->next)  
  57.     {     
  58.         prenode=p;  
  59.         if(newnode->item <=p->item)  
  60.             break;       
  61.     }  
  62.     if(p==NULL)//如果遍历整个链表，结点的值都比要插入的小，那么只能在尾端插入  
  63.     {  
  64.         prenode->next=newnode;  
  65.         newnode->pre=prenode;  
  66.         newnode->next=NULL;  
  67.     }  
  68.     else if(p==head)//如果链表中的数都比要插入的数大则在头部插入；  
  69.     {  
  70.         newnode->pre=NULL;  
  71.         newnode->next=head;  
  72.         head=newnode;  
  73.     }  
  74.     else   //在中间插入  
  75.     {  
  76.         p->pre->next=newnode;  
  77.         newnode->pre=p->pre;  
  78.   
  79.         newnode->next=p;  
  80.         p->pre=newnode;  
  81.     }  
  82.     return head;  
  83. }  
  84.   
  85. bool FindNode(DList head,int data)//查找链表中含有某元素的节点是否存在  
  86. {  
  87.     if(head==NULL)  
  88.     {  
  89.         cout<<"the Dlist is NULL"<<endl;  
  90.         return false;  
  91.     }  
  92.     DListNode *p=head;  
  93.     while(p!=NULL)  
  94.     {  
  95.         if(p->item==data)  
  96.             return true;  
  97.         p=p->next;  
  98.     }  
  99.     return false;  
  100. }  
  101.   
  102. DList DeleteNode(DList head,int data)//删除节点  
  103. {  
  104.     DListNode *p=head;  
  105.     while(p!=NULL)  
  106.     {  
  107.         if(p->item==data)  
  108.             break;  
  109.         p=p->next;  
  110.           
  111.     }  
  112.     if(p==NULL)  
  113.     {  
  114.         cout<<"the node with data is not existed in the List"<<endl;  
  115.         exit(0);  
  116.     }  
  117.     if(p==head)//要删除的结点恰好是双向链表的头结点  
  118.     {  
  119.         DListNode *tmp=head;  
  120.         head=head->next;  
  121.         head->pre=NULL;//---------------------------------------------------  
  122.         free(tmp);  
  123.     }  
  124.     else if(p->next==NULL)//如果要删除的节点是链表的最后一个节点  
  125.     {  
  126.         p->pre->next=NULL;  
  127.         free(p);  
  128.     }  
  129.     else //删除中间节点  
  130.     {  
  131.         p->pre->next=p->next;  
  132.         p->next->pre=p->pre;  
  133.     }  
  134.     return head;    
  135. }  
  136. void PrintDList(DList head)//打印  
  137. {  
  138.     cout<<"现在，链表如下:"<<endl;  
  139.     if(head==NULL)  
  140.     {  
  141.         cout<<"the Dlist is NULL"<<endl;  
  142.         return ;  
  143.     }  
  144.     DListNode *p=head;  
  145.     while(p!=NULL)  
  146.     {  
  147.         cout<<p->item<<" ";  
  148.         p=p->next;  
  149.     }  
  150.     cout<<endl<<endl;  
  151. }  
  152. void DestroyDList(DList head)//销毁双向链表  
  153. {  
  154.     DListNode *p=head;  
  155.     while(p!=NULL)  
  156.     {  
  157.         DListNode *tmp=p;  
  158.         p=p->next;  
  159.         free(tmp);  
  160.     }  
  161. }  
  162.   
  163. void Test()  
  164. {  
  165.     DListNode *head=NULL;  
  166.   
  167.     for(int i=0;i<10;i++)   /*利用尾部插入来构造双向链表*/  
  168.         head=InsertNodeToTail(head,i);  
  169.     PrintDList(head);  
  170.       
  171.     int a;  
  172.     cout<<"输入要查找的结点的值"<<endl;  
  173.     cin>>a;  
  174.     if(FindNode(head,a))  
  175.         cout<<"结点存在！"<<endl<<endl;  
  176.     else  
  177.         cout<<"结点不存在!"<<endl<<endl;  
  178.   
  179.     cout<<"删除结点4..."<<endl;    /*删除指定节点*/  
  180.     head=DeleteNode(head,4);  
  181.     PrintDList(head);  
  182.   
  183.     cout<<"插入结点4..."<<endl;     /*按序插入*/  
  184.     head=InsertDListByOrder(head,4);  
  185.     PrintDList(head);  
  186.       
  187.     cout<<"删除头结点..."<<endl;    /*删除指定节点*/  
  188.     head=DeleteNode(head,0);  
  189.     PrintDList(head);  
  190.       
  191.     cout<<"删除尾结点..."<<endl;  
  192.     head=DeleteNode(head,9);  
  193.     PrintDList(head);  
  194.       
  195.     cout<<"插入头结点..."<<endl;     /*按序插入*/  
  196.     head=InsertDListByOrder(head,0);  
  197.     PrintDList(head);  
  198.       
  199.     cout<<"插入尾结点..."<<endl;     /*按序插入*/  
  200.     head=InsertDListByOrder(head,10);  
  201.     PrintDList(head);  
  202.   
  203.     DestroyDList(head);  
  204. }  
  205. int main(void)  
  206. {  
  207.     Test();  
  208. }  

运行：

双向链表的创建和相关操作


相关推荐