⑴利用尾插法建立一个双向链表。

⑵遍历双向链表。

⑶实现双向链表中删除一个指定元素。

⑷在非递减有序双向链表中实现插入元素e仍有序算法。

⑸判断双向链表中元素是否对称若对称返回1否则返回0。

⑹设元素为正整型，实现算法把所有奇数排列在偶数之前。

⑺在主函数中设计一个简单的菜单调试上述算法。

（4）实验四  栈和队列的有关操作

⑴采用链式存储实现栈的初始化、入栈、出栈操作。

⑵采用顺序存储实现栈的初始化、入栈、出栈操作。

⑶采用链式存储实现队列的初始化、入队、出队操作。

⑷采用顺序存储实现循环队列的初始化、入队、出队操作。

⑸在主函数中设计一个简单的菜单，分别测试上述算法。

 

 

1 #include 
     
        2 #include 
      
         3   4 using namespace std;  5 typedef struct Dulnode{  6         int data;  7         struct Dulnode *prior;  8         struct Dulnode *next;  9         }Dulnode,*Dullinklist; 10         11 bool init(Dullinklist &headlist)//初始化； 12 { 13      Dullinklist p; 14      p=(Dulnode *)malloc(sizeof(Dullinklist)); 15      if(p==NULL) 16      {cout<<"初始化失败\n";return false;} 17                 p->next=p; 18                 p->prior=p; 19                 headlist=p; 20                 return true; 21 } 22                 23 bool input(Dullinklist headlist)//输入； 24 { cout<<"请输入元素,以^Z结束输入\n"; 25  Dullinklist p1,p2; 26  int i,j,k; 27  int a; 28  while(scanf("%d",&a)!=EOF) 29  { 30                            p1=(Dulnode *)malloc(sizeof(Dulnode)); 31                            if(p1==NULL) 32                            {cout<<"内存申请失败，结束输入\n";return false;} 33                            p1->data=a; 34                            headlist->prior->next=p1; 35                            p1->next=headlist; 36                            p1->prior=headlist->prior; 37                            headlist->prior=p1; 38  } 39  cout<<"输入完成\n"; 40  return true; 41 } 42  43 bool output(Dullinklist headlist)//元素的输出； 44 {
   if(headlist->next==headlist->prior) 45 {cout<<"该表为空表\n";return false;} 46   47      cout<<"该表元素为:\n"; 48      Dullinklist p1,p2; 49      p1=headlist->next; 50      51      while(p1!=headlist) 52      { 53                         cout<
       
        data<<' '; 54                         p1=p1->next; 55      } 56      return true; 57  } 58   59   60  bool delete_node(Dullinklist headlist,int e)//删除第e个元素； 61  { 62       Dullinklist p1,p2; 63       if(headlist->next==headlist->prior) 64       {cout<<"该表为空表\n";return false;} 65       66       67       int i; 68       p1=headlist->next; 69       for(i=1;i<=e;i++) 70       { 71                 if(p1==headlist) 72                 {cout<<"第"<
        
         <<"个元素不存在\n";return false;} 73                 p1=p1->next; 74       } 75       p1=p1->prior; 76       p1->prior=p1->next; 77       p1->next->prior=p1->prior; 78       cout<<"删除的第"<
         
          <<"个元素为："<
          
           data<
           
            next; 88 while(p1!=p2) 89 { 90 free(p1); 91 p1=p1->next; 92 } 93 //free(p2); 94 p2->next=headlist; 95 p2->prior=headlist; 96 return true; 97 } 98 99 bool insert(Dullinklist headlist,int e)//元素的插入；100 {101 Dullinklist p1,p2,p3;102 p3=(Dulnode *)malloc(sizeof(Dulnode));103 if(p3==NULL)104 {cout<<"内存申请失败\n";return false;}105 p3->data=e;106 107 108 p1=headlist->next;109 while(p1!=headlist)110 {111 if(p1->data>e)112 break;113 p1=p1->next;114 115 116 }117 118 p2=p1->prior;119 p2->next=p3;120 p3->prior=p2;121 p3->next=p1;122 p1->prior=p3;123 return true;124 }125 126 127 bool judge(Dullinklist headlist)//判断；128 {129 Dullinklist p1,p2;130 if(headlist->next==headlist->prior)131 {cout<<"链表是空表\n";return false;}132 p1=headlist->next;133 p2=headlist->prior;134 while(p1!=p2)135 {136 if(p1->data!=p2->data)137 return false;138 p1=p1->next;139 p2=p2->prior;140 }141 return true;142 }143 144 145 146 int fz(Dullinklist headlist)//奇数排在偶数前面；147 { if(headlist->next==headlist->prior)148 {cout<<"链表是空表\n";return false;}149 Dullinklist p1,p2,p3;150 int t;151 for(p1=headlist->next;p1!=headlist->prior;p1=p1->next)152 {p3=p1;153 for(p2=p1->next;p2!=headlist;p2=p2->next)154 { if(p3->data%2==0)155 p3=p2;156 }157 if(p3!=p1)158 {t=p3->data;p3->data=p1->data;p1->data=t;}159 }160 return true;161 }162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 int main(int argc, char *argv[])177 {178 int e;179 Dullinklist headlist;180 init(headlist);181 input(headlist);182 output(headlist);183 cout<<"请输入要删除链表中的第几个元素\n";184 scanf("%d",&e);185 delete_node(headlist,e);186 free_Dullink(headlist);187 cout<<"非降序列的输入\n";188 189 input(headlist);190 cout<<"请输入要插入的元素\n";191 scanf("%d",&e);192 cout<<"插入元素后的序列为:\n";193 194 insert(headlist,e);195 output(headlist);196 if(!judge(headlist))197 cout<<"不对称\n";198 else199 cout<<"对称\n";200 fz(headlist);201 cout<<"奇数排在偶数前面\n";202 output(headlist);203 204 205 206 207 208 209 210 211 212 213 system("PAUSE");214 return EXIT_SUCCESS;215 }