用C++编写的双向链表程序示例

1、/*用C+阕写一个双链表的程序*/*本文可以帮助大家快速的学习如何建立双向链表，以及对双向链表进行的相关操作，比如删除节点、插入节点、链表排序、计算链表长度、打印双向链表等操作*/#include<iostream>usingnamespacestd;/定义双向链表的节点typedefstructstudentintdata;structstudent*pre;structstudent*next;dnode;/建立双向链表dnode*creat()intcycle=1;intx;dnode*head,*t,*s=NULL;head=newdnode;t=head;while(cy

2、cle)cout<<"Pleaseinputa'int'typenumber:"<<endl;cin>>x;if(x!=0)s=newdnode;s->data=x;t->next=s;s->pre=t;t=s;elsecycle=0;head=head->next;head->pre=NULL;t->next=NULL;cout<<"第一个节点的值："<<endl;cout<<head->data<<endl&l

3、t;<endl;returnhead;/计算双向链表的长度intlength(dnode*head)intn=0;dnode*p;p=head;while(p!=NULL)n+;p=p->next;returnn;/打印双向链表并计算链表的长度intprint(dnode*head)intn=0;dnode*p;p=head;while(p!=NULL)n+;cout<<p->data<<endl;p=p->next;cout<<"Length="<<n<<endl;returnn;/实现双

4、向链表中节点的删除dnode*del(dnode*head)dnode*p;intnum;p=newdnode;p=head;/输入要删除的节点上的值cout<<"Pleaseinputthedeletatingvalue:"<<endl;cin>>num;while(num!=p->data&&p->next!=NULL)p=p->next;if(num=p->data)if(p=head)head=head->next;head->pre=NULL;delete(p);elseif(

5、p->next=NULL)p->pre->next=NULL;delete(p);elsep->pre->next=p->next;p->next->pre=p->pre;elsecout<<"Don'tfindthe'num':"<<endl;returnhead;/双向链表中插入节点dnode*insert(dnode*head)intnum;p=head;p0=newdnode;cout<<"Pleaseinputtheinsertingvalu

6、e:"<<endl;cin>>num;p0->data=num;while(p0->data>p->data&&p->next!=NULL)p=p->next;if(p0->data<=p->data)if(p=head)head=p0;p0->pre=NULL;p0->next=p;p->pre=p0;elsep->pre->next=p0;p0->pre=p->pre;p0->next=p;p->pre=p0;/*p->next

7、=p0;p0->pre=p;p0->next=p->next;p->next->pre=p0;*/elsep->next=p0;p0->pre=p;p0->next=NULL;returnhead;/对双向链表进行排序dnode *sort(dnode *head)dnode*p;intt,n;p=head;n=length(p);for(inti=0;i<n-1;i+)p=head;for(intj=0;j<n-1-i;j+)if(p->data>p->next->data)t=p->data;p-&g

8、t;data=p->next->data;p->next->data=t;p=p->next;returnhead;intmain()dnode*head;head=creat();cout<<"创建的双向链表为："<<endl;print(head);cout<<"head="<<head<<endl<<endl;head=del(head);cout<<"删除节点之后的双向链表为："<<endl;print

9、(head);head=insert(head);cout<<"插入节点之后的双向链表为："<<endl;print(head);head=sort(head);cout<<"排序之后的双向链表为："<<endl;print(head);/*备注：在进行链表插入时要注意，链表中的值，、从头节点向后默认是增加的，所以插入的节点位于两个节点中间时，插入节点的位置应该是在p节点之前。如下图所示：*/实验验证:创建链表输入：1,2,3,65,12,11,70删除：12插入：68最后按照冒泡排序发进行排序。hiiiput*inttypeiuimL&r二P1qi£oinput,i'nmter：Fleas«himput改sinf1typodjlitL&t:lJPl则时4Plnp31iWiJHT-fiSPiggiEiut<"int'tyj?enjurteT：12PlqaMIllp