数据结构C语言第二版（53页作业）

约定不等于承诺〃 2022-04-22 01:20 215阅读 0赞

#include<iostream>
    using namespace std;
    typedef struct //定义顺序表 
    {
    	int *elem;
    	int length;
    }SqList;
    typedef struct LNode  //定义单向链表 
    {
    	int date;
    	struct LNode *next;
    }LNode,*Linklist;
    typedef struct DuLNode  //定义双向链表 
    {
    	int date;
    	struct DuLNode *prior;
    	struct DuLNode *next;
    }DuLNode,*DuLinklist;
    void creatlist_d(Linklist &L,int n)//尾插法单链表 
    {
    	L=new LNode;   //建立头结点 
    	L->next=NULL;  //头结点后继置空 
    	LNode *p;       
    	Linklist r;    
    	r=L;
    	for(int i=0;i<n;i++)
    	{
    		p=new LNode;
            cin>>p->date;   //输入数据 
    		p->next=NULL;  //后继置空 
    		r->next=p;     //插入 
    		r=p;           //指针后移 
    	}
    }
    void creatlist_du(DuLinklist &LA,int n) //尾插法双向链表
    {
    	LA=new DuLNode;
    	LA->next =NULL;
    	DuLinklist r;
    	DuLNode *p;
    	r=LA;
    	for(int i=0;i<n;i++)
    	{
    		p=new DuLNode;
    		cin>>p->date ;
    		p->next =NULL;
    		p->prior =r;
    		r->next=p;
    		r=p;
    	}
    } 
    void traverse(Linklist L)//遍历单链表
    {
    	if(L->next ==NULL)
    	{
    		cout<<" 该链表已无数据 "<<endl;
    		return ; 
    	}
    	cout<<"结果为：";
         LNode *p=L->next;
    	
    	while(p)
    	{
    		cout<<p->date<<" ";
    		p=p->next;
    	}
    	cout<<endl;
    }
    void traverse_d(DuLinklist L)//遍历双向链表
    {
    	if(L->next ==NULL)
    	{
    		cout<<" 该链表已无数据 "<<endl;
    		return ; 
    	}
    	cout<<"结果为：";
         DuLNode *p=L->next;
    	
    	while(p)
    	{
    		cout<<p->date<<" ";
    		p=p->next;
    	}
    	cout<<endl;
    }
    //第一题：合并两个递增的有序链表 时间复杂度O（length(LA)+length(LB)）
    void   mergelist_1(Linklist &LA,Linklist &LB,Linklist &LC)
    {
    	Linklist pa=LA->next;
    	Linklist pb=LB->next;
        LC=LA;
    	Linklist pc=LA;
    	while(pa&&pb)
    	{
    		if(pa->date < pb->date)
    		{
    			pc->next=pa;
    			pc=pa;
    			pa=pa->next;
    		}
    		else if(pa->date == pb->date)
    		{
    			pc->next=pa;
    			pc=pa;
    			pa=pa->next;
    			pb=pb->next;
    	    }
    	    else
    	    {
    	    	pc->next=pb;
    	    	pc=pb;
    	    	pb=pb->next;
    		}
    	}	
    	    pc->next=pa?pa:pb;
    		delete LB; 
          traverse(LC);	 
     } 
     //第二题：将两个非递减的有序链表合并过程一个非递增的有序链表  时间复杂度O（length(LA)+length(LB) 头插法）
     void mergelist_2(Linklist &LA,Linklist &LB,Linklist &LC)
     {
     	Linklist pa=LA->next;
     	Linklist pb=LB->next;
     	LC=LA;
     	Linklist pc=LC;
     	LC->next =NULL;
     	while(pa&&pb)
     	{
     		if(pa->date<=pb->date)
     		{
     			LNode *p;
     			p=new LNode;
     			p->date  =pa->date;
     			p->next  =LC->next ;
     			LC->next =p;
     			pa=pa->next;
    		 }
    		 else
    		 {
     			LNode *p;
     			p=new LNode;
     			p->date  =pb->date;
     			p->next  =LC->next ;
     			LC->next =p;
     			pb=pb->next;
    		 }
    	 }
    	 while(pa) //链LA还有数据 
    	 {
    	 	LNode *p;
    	 	p=new LNode;
    	 	p->date =pa->date ;
    	 	p->next =LC->next ;
    	 	LC->next =p;
    	 	pa=pa->next ;
    	 }
    	while(pb)  //链LB还有数据 
    	 {
    	 	LNode *p;
    	 	p=new LNode;
    	 	p->date =pb->date ;
    	 	p->next =LC->next ;
    	 	LC->next =p;
    	 	pb=pb->next ;
    	 }
    
    	 delete LB;
         traverse(LC);
      } 
    //第三题：C=A∩B    时间复杂度O（length(LA)）
    void  aggergate_3(Linklist &LA,Linklist &LB,Linklist &LC)
    {
    	Linklist pa=LA->next;
    	Linklist pb=LB->next;
    	LC=LA;
    	Linklist pc=LC;
    	pc->next =NULL;
    	while(pa)
    	{
    		int flag=0;
    		while(pb)
    		{
    			if(pa->date == pb->date)
    		   {
    		   	flag=1;
    		   	break;	
    		   }
    		   else
    		    pb=pb->next ;
    	    }
    	    if(flag==1)
    	    {
    	    	pc->next=pa;
    		    pc=pa;	
    		}
            	pa=pa->next;
            	pb=LB->next;
    	} 
    	pc->next =NULL;
    	delete LB,LA;
    }
    //第四题：在集合A中出现而不在集合B中出现 时间复杂度O（length(LA)*length(LB)）
    void mergelist_4(Linklist &LA,Linklist &LB,Linklist &LC,int &s1)
    {    //设两个指针  一个pa 一个pb    pa移动一次pb跑一整趟，所以循环完记得还要把pa指到第一个节点上 
    	s1=0;
    	Linklist pa=LA;
    	Linklist pb=LB;
        LC=LA;
        Linklist pc=LC;
        
    	while(pa)
    	{   
    	    int p=0;
    	    while(pb)
    	    {
    			if(pb->date==pa->date)
    			{
    			  pc->next=pa->next ;
    			  p=1;
    			} 
    			pb=pb->next ;
    		}
    		if(p==0)  {
    		    pc=pa ; 
    		    s1++;
    		}  
    		pa=pa->next ;
    		
    		pb=LB->next ;
    		
    	}
        s1--;
    	delete LB;
    }
    //第五题：拆分表A    时间复杂度O（length(LA)）
    void splitlist_5(Linklist &LA,Linklist &LB,Linklist &LC)
    {    //坑 需另设两个头结点 
    	Linklist pa=LA->next ;
    	
    	Linklist pb=LB;
        
        Linklist pc=LC;
        while(pa)
        { 
        	if(pa->date >0)
        	{
    			LNode *p;
    			p=new LNode;
    			p->date=pa->date;
    			p->next=NULL;
    			pb->next=p;
    			pb=p;
        		pa=pa->next;
    		}
    		else if(pa->date <0)
    		{
                LNode *p;
    			p=new LNode;
    			p->date=pa->date;
    			p->next=NULL;
    			pc->next=p;
    			pc=p;
    			pa=pa->next;
    		}
    	}
     } 
     //第六题： 求链A中最大值   时间复杂度O（length(LA)）
    void Maxlist(Linklist L) 
    {    //遍历 
    	LNode *p;
    	p=L->next->next;
    	int max=L->next->date;
    	
    	while(p)
    	{
    		max=max>p->date?max:p->date;
    		p=p->next;
    	}
    	cout<<"该链表中的最大值为："<<max<<endl<<endl; 
    } 
    //第七题： 逆转链表   时间复杂度O（length(LA)）
    void reversal_7(Linklist &LA,Linklist &LB)
    {   //设两个指针一个向后跑一个用来前插法定位  
    	Linklist pa=LA->next->next  ;
    	LB=LA;
    	Linklist pb=LB->next ;
    	pb->next=NULL;  //要记得先把尾断了 不然结果会出现 123321 
    	while(pa)
    	{   
    	    LNode *p;
    	    p=new LNode;
    		p->date =pa->date ;
    		p->next =pb ;
    		LB->next =p;
    		pb=p;
    		pa=pa->next ;
    	
    	}
    	
     } 
    //第八题： 删除链A中（mink,maxk) 范围内的数据  时间复杂度O（length(LA)）
    void list_8(Linklist &LA,Linklist &LB,int a,int b)
    {     //遍历 
    	Linklist pa=LA->next ;
    	LB=LA;
    	Linklist pb=LB;
    	while(pa)
    	{
    		if(pa->date>a && pa->date<b)
    		{
    			pb->next =pa->next;
    			pa=pa->next ;
    		    
    		}
    		else
    		{
    			pb->next =pa;
    			pb=pa;
    			pa=pa->next ;
    			
    		}
    	}
     } 
     //第九题： 交换双向链表中a数据和它之前的元素 
     void change_9(DuLinklist &LA,int a)
     {  //a数据结点的前驱取出 插入到a之后 
     	DuLinklist p;
     	p=LA->next;
     	while(p->date!=a)
     	  p=p->next ;
     	
    	     
     			DuLNode *q;
    			q=new DuLNode;
     			q->date =p->prior->date;
     			q->next =NULL ;
     			
                p->prior->prior->next =p;
     			p->prior =p->prior->prior;
     			
     		if(p->next)	
    		{
     			q->next =p->next ;
     			q->prior=p;
     			p->next=q;
     			q->next->prior=q;
    		}
    		else
    		{
    			p->next =q;
    		}
    	 
    	 
     }
     //第十题： 删除顺序表中为a的数  时间复杂度O（length(LA)）
    void delete_10(SqList L,int a)
    {      //定义两个下标值在同一数组空间一起跑 
    	int p;
    	p=0;
    	for(int i=0;i<L.length ;i++)
    	{
    	    if(L.elem[i]!=a)
    		  L.elem[p++]=L.elem[i];	
    	 } 
    	cout<<"结果为："; 
    	for(int i=0;i<p;i++)
    	{
    		cout<<L.elem [i]<<" ";
    	}
    	cout<<endl;
    }
    int main()
    {
    
    	cout<<"-------53页课本习题-------"<<endl;	
    	cout<<"1,第一题；"<<endl;
    	cout<<"2,第二题；"<<endl;
    	cout<<"3,第三题；"<<endl;
    	cout<<"4,第四题；"<<endl;
    	cout<<"5,第五题；"<<endl;
    	cout<<"6,第六题；"<<endl;
    	cout<<"7,第七题；"<<endl;
    	cout<<"8,第八题；"<<endl; 
    	cout<<"9,第九题；"<<endl; 
    	cout<<"10,第十题；"<<endl; 
    	cout<<"0,退出。"<<endl<<endl;
    	int n;
    	cout<<"请输入需要验证题目编号:";
    	cin>>n;
    	while(n)
    	{	
              if(n==1)
              	  {
              	  	Linklist LA,LB; 
    	            int LA_length,LB_length;
              	  	cout<<"请先创建两个单链表！！！"<<endl;
                    cout<<"请分别输入单链表的长度：";
    	            cin>>LA_length>>LB_length;
    	            cout<<"请输入第一个单链表的内容：";
                    creatlist_d(LA,LA_length);
    	            cout<<"请输入第二个单链表的内容：";
                    creatlist_d(LB,LB_length); 
              	  	Linklist LC;
              		mergelist_1(LA,LB,LC);
              		cout<<endl;
              		delete LA,LB,LC;
    			  }
    		   else if(n==2)
    		   	   {
    		   	   	Linklist LA,LB; 
    	            int LA_length,LB_length;
              	  	cout<<"请先创建两个单链表！！！"<<endl;
                    cout<<"请分别输入单链表的长度：";
    	            cin>>LA_length>>LB_length;
    	            cout<<"请输入第一个单链表的内容：";
                    creatlist_d(LA,LA_length);
    	            cout<<"请输入第二个单链表的内容：";
                    creatlist_d(LB,LB_length);
    		   	   	Linklist LC;
    		   		mergelist_2(LA,LB,LC);
    		   		cout<<endl; 
    		   		delete LA,LB;
    			   }
    			else if(n==3)
    				{
    				Linklist LA,LB; 
    	            int LA_length,LB_length;
              	  	cout<<"请先创建两个单链表！！！"<<endl;
                    cout<<"请分别输入单链表的长度：";
    	            cin>>LA_length>>LB_length;
    	            cout<<"请输入第一个单链表的内容：";
                    creatlist_d(LA,LA_length);
    	            cout<<"请输入第二个单链表的内容：";
                    creatlist_d(LB,LB_length);
    				Linklist LC;
    				aggergate_3(LA,LB,LC);
    				traverse(LC);
    				cout<<endl;
    				delete LA,LB;
    			   }
    			else if(n==4)
    				{
    				Linklist LA,LB,pa=LA,pb=LB; 
    	            int LA_length,LB_length;
              	  	cout<<"请先创建两个单链表！！！"<<endl;
                    cout<<"请分别输入单链表的长度：";
    	            cin>>LA_length>>LB_length;
    	            cout<<"请输入第一个单链表的内容：";
                    creatlist_d(LA,LA_length);
    	            cout<<"请输入第二个单链表的内容：";
                    creatlist_d(LB,LB_length);
    			   	 Linklist LC;
    			   	 int s1=0;
    			     mergelist_4(LA,LB,LC,s1);
    			     traverse(LC);
    			     cout<<"该链表的长度为："<<s1<<endl; 
    			     cout<<endl;
    			     delete LA,LB;
    				}
    			else if(n==5)
    			   {
    			 	Linklist LA;
    				LNode *LB,*LC; 
    				LB=new LNode;
    				LC=new LNode;
    				LB->next=NULL;
    				LC->next=NULL;
    	            int LA_length;
    	            cout<<"请先创建一个单链表！！！"<<endl;
                    cout<<"请输入单链表的长度：";
    	            cin>>LA_length;
    	            cout<<"请输入单链表的内容：";
                    creatlist_d(LA,LA_length);
    	            splitlist_5(LA,LB,LC);
    	            traverse(LB);
    	            traverse(LC);
    				delete LA,LB,LC;
    			   }
    			 else if(n==6)
    			   {
    			   	Linklist LA; 
    	            int LA_length;
    	            cout<<"请先创建一个单链表！！！"<<endl;
                    cout<<"请输入单链表的长度：";
    	            cin>>LA_length;
    	            cout<<"请输入单链表的内容：";
                    creatlist_d(LA,LA_length); 
    			   	Maxlist( LA) ;
    			   	delete LA;
    				 } 
    			 else if(n==7)
    			   {
    			 	Linklist LA,LB; 
    	            int LA_length;
    	            cout<<"请先创建一个单链表！！！"<<endl;
                    cout<<"请输入单链表的长度：";
    	            cin>>LA_length;
    	            cout<<"请输入单链表的内容：";
                    creatlist_d(LA,LA_length); 
                    reversal_7( LA, LB);
                    traverse(LB);
                    cout<<endl;
                    delete LA;
    				}
    			else if(n==8)
    			{
    				Linklist LA,LB; 
    	            int LA_length;
    	            cout<<"请先创建一个单链表！！！"<<endl;
                    cout<<"请输入单链表的长度：";
    	            cin>>LA_length;
    	            cout<<"请输入单链表的内容：";
                    creatlist_d(LA,LA_length); 
                    cout<<"请输入删除数据范围：";
                    int a,b;
                    cin>>a>>b;
                    list_8(LA,LB,a,b);
                    traverse(LB);
                    cout<<endl;
                    delete LA,LB;
    				 }	
    			else if(n==9)
    			  {
    				DuLinklist LA;
    				int LA_length;
    	            cout<<"请先创建一个单链表！！！"<<endl;
                    cout<<"请输入单链表的长度：";
    	            cin>>LA_length;
    	            cout<<"请输入单链表的内容：";
    				creatlist_du( LA, LA_length) ;
    				cout<<"请输入要交换的后一个数据：";
    				int a;
    				cin>>a; 
    				change_9(LA,a);
    				traverse_d(LA);
    			   } 
    			else if(n==10)
    			  {
    			  	SqList LA;
                    
    				int LA_length;
    				  
    			 	cout<<"请先创建一个顺序表！！！"<<endl;
                    cout<<"请输入顺序表的长度：";
    	            cin>>LA_length;
    	            LA.length=LA_length;
    	            cout<<"请输入单链表的内容：";
    	            for(int i=0;i<LA.length ;i++)
    	            {
    	            	cin>>LA.elem [i];
    				}
    				cout<<"请输入需要删除的数据：" ;
    			    int a;
    			    cin>>a;
    			    delete_10(LA,a);
    			    cout<<endl; 
    			  } 
    	cout<<"1,第一题；"<<endl;
    	cout<<"2,第二题；"<<endl;
    	cout<<"3,第三题；"<<endl;
    	cout<<"4,第四题；"<<endl;
    	cout<<"5,第五题；"<<endl;
    	cout<<"6,第六题；"<<endl;
    	cout<<"7,第七题；"<<endl;
    	cout<<"8,第八题；"<<endl;
    	cout<<"9,第九题；"<<endl; 
    	cout<<"10,第十题；"<<endl; 
    	cout<<"0,退出。"<<endl<<endl;
    	//int n;
    	cout<<"请输入需要验证题目编号:";
    	cin>>n;	   
    	} 
    	 return 0;
    }