注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zjushuiping

追求的只是心中的那一份宁静!

 
 
 

日志

 
 

实验三 链式存储结构(二)双向链表的有关操作  

2010-04-10 21:10:09|  分类: 数据结构试验 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
⑴利用尾插法建立一个双向链表。
⑵遍历双向链表。
⑶实现双向链表中删除一个指定元素。
⑷在非递减有序双向链表中实现插入元素e仍有序算法。
⑸判断双向链表中元素是否对称若对称返回1否则返回0。
⑹设元素为正整型,实现算法把所有奇数排列在偶数之前。
⑺在主函数中设计一个简单的菜单调试上述算法。
(4)实验四  栈和队列的有关操作
⑴采用链式存储实现栈的初始化、入栈、出栈操作。
⑵采用顺序存储实现栈的初始化、入栈、出栈操作。
⑶采用链式存储实现队列的初始化、入队、出队操作。
⑷采用顺序存储实现循环队列的初始化、入队、出队操作。
⑸在主函数中设计一个简单的菜单,分别测试上述算法。
#include <cstdlib>
#include <iostream>
using namespace std;
typedef struct Dulnode{
        int data;
        struct Dulnode *prior;
        struct Dulnode *next;
        }Dulnode,*Dullinklist;
        
bool init(Dullinklist &headlist)//初始化; 
{
     Dullinklist p;
     p=(Dulnode *)malloc(sizeof(Dullinklist));
     if(p==NULL)
     {cout<<"初始化失败\n";return false;} 
                p->next=p;
                p->prior=p;
                headlist=p;
                return true;
}
                
bool input(Dullinklist headlist)//输入; 
{ cout<<"请输入元素,以^Z结束输入\n";
 Dullinklist p1,p2;
 int i,j,k;
 int a;
 while(scanf("%d",&a)!=EOF)
 {
                           p1=(Dulnode *)malloc(sizeof(Dulnode));
                           if(p1==NULL)
                           {cout<<"内存申请失败,结束输入\n";return false;}
                           p1->data=a;
                           headlist->prior->next=p1;
                           p1->next=headlist;
                           p1->prior=headlist->prior;
                           headlist->prior=p1;
 }
 cout<<"输入完成\n"; 
 return true;
}
bool output(Dullinklist headlist)//元素的输出; 
{if(headlist->next==headlist->prior)
{cout<<"该表为空表\n";return false;}
 
     cout<<"该表元素为:\n";
     Dullinklist p1,p2;
     p1=headlist->next;
     
     while(p1!=headlist)
     {
                        cout<<p1->data<<' ';
                        p1=p1->next;
     }
     return true;
 }
 
 
 bool delete_node(Dullinklist headlist,int e)//删除第e个元素; 
 {
      Dullinklist p1,p2;
      if(headlist->next==headlist->prior)
      {cout<<"该表为空表\n";return false;}
      
      
      int i;
      p1=headlist->next;
      for(i=1;i<=e;i++)
      {
                if(p1==headlist)
                {cout<<"第"<<e<<"个元素不存在\n";return false;}
                p1=p1->next;
      }
      p1=p1->prior;
      p1->prior=p1->next;
      p1->next->prior=p1->prior;
      cout<<"删除的第"<<e<<"个元素为:"<<p1->data<<endl;
      free(p1);
      return true;
 } 
 
bool free_Dullink(Dullinklist headlist)//删除链表; 
{Dullinklist p1,p2;
p1=headlist;
p2=headlist;
p1=p1->next;
while(p1!=p2)
{
                   free(p1);
                   p1=p1->next;
}
//free(p2);
p2->next=headlist;
p2->prior=headlist;
return true;

 
 bool insert(Dullinklist headlist,int e)//元素的插入; 
 {
      Dullinklist p1,p2,p3;
      p3=(Dulnode *)malloc(sizeof(Dulnode));
      if(p3==NULL)
      {cout<<"内存申请失败\n";return false;}
      p3->data=e;
      
      
      p1=headlist->next;
      while(p1!=headlist)
      {
                         if(p1->data>e)
                         break;
                         p1=p1->next;
                         
      
      }
      
      p2=p1->prior;
      p2->next=p3;
      p3->prior=p2;
      p3->next=p1;
      p1->prior=p3;
      return true;
 }
 
 
 bool judge(Dullinklist headlist)//判断; 
 {
      Dullinklist p1,p2;
      if(headlist->next==headlist->prior)
      {cout<<"链表是空表\n";return false;}
      p1=headlist->next;
      p2=headlist->prior;
      while(p1!=p2)
      {
                   if(p1->data!=p2->data)
                   return false;
                   p1=p1->next;
                   p2=p2->prior;
      }
      return true;
 } 
 
 
 
 int fz(Dullinklist headlist)//奇数排在偶数前面; 
 {if(headlist->next==headlist->prior)
 {cout<<"链表是空表\n";return false;}
     Dullinklist p1,p2,p3;
     int t;
     for(p1=headlist->next;p1!=headlist->prior;p1=p1->next)
     {p3=p1;
      for(p2=p1->next;p2!=headlist;p2=p2->next)
      {if(p3->data%2==0)
        p3=p2;
        }
        if(p3!=p1)
        {t=p3->data;p3->data=p1->data;p1->data=t;}
      }
        return true;
 }
      
      
      
  
      
       
                
                
       
      
      
                           
                            
        
int main(int argc, char *argv[])
{
     int e; 
    Dullinklist headlist;
    init(headlist);
    input(headlist);
    output(headlist);
    cout<<"请输入要删除链表中的第几个元素\n";
    scanf("%d",&e);
    delete_node(headlist,e);
    free_Dullink(headlist);
    cout<<"非降序列的输入\n";
    
  input(headlist);
  cout<<"请输入要插入的元素\n"; 
  scanf("%d",&e);
  cout<<"插入元素后的序列为:\n";
  
  insert(headlist,e);
  output(headlist); 
  if(!judge(headlist))
  cout<<"不对称\n";
  else
  cout<<"对称\n";
  fz(headlist);
  cout<<"奇数排在偶数前面\n";
  output(headlist);
   
  
    
     
    
    
    
    
    
    
    system("PAUSE");
    return EXIT_SUCCESS;
}
  评论这张
 
阅读(106)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017