程序员面试宝典——数据结构之双链表

  1 #include<stdlib.h>
  2 #include<iostream>
  3 #include<stdio.h>
  4 #include<string>
  5 using namespace std;
  6 typedef struct Node{
  7 int data;
  8 struct Node* next;
  9 struct Node* pre;
 10 }dnode;
 11 
 12 dnode *create()
 13 {
 14     dnode*head,*p,*s;
 15     int x,cycle=1;
 16     head=(dnode*)malloc(sizeof(dnode));
 17     p=head;
 18      cout<<"
Please input the data:"<<endl;
 19     while(cycle)
 20     {
 21         cin>>x;
 22         if(x!=0)
 23         {
 24             s=(dnode*)malloc(sizeof(dnode));
 25             s->data=x;
 26             p->next=s;
 27             s->pre=p;
 28             p=s;
 29         }
 30         else cycle=0;
 31     }
 32     head=head->next;
 33     head->pre=NULL;
 34     p->next=NULL;
 35     cout<<"
The head data is"<<head->data<<endl;
 36     return head;
 37 }
 38 
 39 dnode* del(dnode* head,int num)
 40 {    
 41     dnode *p1,*p2;
 42     p1=head;
 43     while(num!=p1->data&&p1->next!=NULL)
 44     {
 45         p1=p1->next;
 46     }    
 47     if(num==p1->data)
 48     {
 49         if(p1==head)
 50         {
 51             head=head->next;
 52             head->pre=NULL;
 53             free(p1);
 54         }
 55         else if(p1->next==NULL)
 56         {
 57             p1->pre->next=NULL;
 58             free(p1);
 59         }
 60         else
 61         {
 62             p1->next->pre=p1->pre;
 63             p1->pre->next=p1->next;
 64             free(p1);
 65         }
 66     }
 67     else
 68         cout<<"could not been found "<<num<<endl;
 69     return head;
 70 }
 71 
 72 dnode* insert(dnode* head,int num)
 73 {
 74     dnode *p0,*p1;
 75     p1=head;
 76     p0=(dnode*)malloc(sizeof(dnode));
 77     p0->data=num;
 78     while(p0->data>p1->data&&p1->next!=NULL)
 79     {
 80         p1=p1->next;
 81     }
 82     if(p0->data<=p1->data)
 83     {
 84         if(head==p1)
 85         {
 86             p0->next=p1->next;
 87             p1->pre=p0;
 88             head=p0;
 89         }
 90         else
 91         {
 92             p0->next=p1;
 93             p1->pre->next=p0;
 94             p0->pre=p1->pre;
 95             p1->pre=p0;
 96         }
 97     }
 98     else
 99     {
100         p1->next=p0;
101         p0->pre=p1;
102         p0->next=NULL;
103     }
104     return head;
105 }
106 
107 void print(dnode* head)
108 {    
109     dnode* p=head;
110     while(p->next!=NULL)
111     {
112         cout<<p->data<<"->";
113         p=p->next;
114     }
115     cout<<endl;
116 }
117 int main()
118 {
119     dnode *head,stud;
120     int n,del_num,insert_num;
121     head=create();
122     print(head);
123     cout<<"input delete number:";
124     cin>>del_num;
125     head=del(head,del_num);
126     print(head);
127     cout<<"please input the insert data:";
128     cin>>insert_num;
129     head=insert(head,insert_num);
130     print(head);
131     return 0;
132 }