【数据结构作业二】写出单链表结点的结构体类型定义及查找、插入、删除算法，并以单链表作存储结构，实现有序表的合并

一时失言乱红尘 2022-06-07 08:51 121阅读 0赞

#include <iostream>
    using namespace std;
    
    typedef int elementType;
    typedef struct lnode
    { elementType data; 
      struct lnode *next;
     }Lnode,*LinkList;
     
    void create(LinkList &L)
    { LinkList r,p; 
      int n,i;
      L=new Lnode; 
      r=L;
      cout<<"请输入表长：";  cin>>n; 
      cout<<"请输入表中元素（有序）："; 
      for(i=1;i<=n;i++)
      { p=new Lnode;  cin>>p->data;    
        r->next=p; r=p;
      }
      r->next=NULL;
    }
    void insert(LinkList L,elementType x)
    { LinkList pre=L,p=L->next,s;
      while(p&&p->data<x)
       { pre=p;  p=p->next; }
      s=new Lnode;  s->data=x;
      s->next=p;  pre->next=s;
    }
    void print(LinkList L)
    { LinkList p; 
      p=L->next;
      while (p)
      {  cout<<' '<<p->data;
         p=p->next;
      }
    }
    void Union(LinkList &La,LinkList &Lb, LinkList &Lc)
    { LinkList pa,pb,pc;
      pa=La->next;
      pb=Lb->next;
      Lc=La;
      pc=Lc;
      while(pa&&pb)
      { if(pa->data>=pb->data)
        {
      	 pc->next=pb;
      	 pc=pb;
      	 pb=pb->next;
        }
        else
    	{
    	 pc->next=pa;
      	 pc=pa;
      	 pa=pa->next;
        }
      }
        pc->next=pb?pb:pa;
        delete Lb; 
    }
    
    int main()
    { LinkList La,Lb,Lc; elementType x;
      create(La);
      print(La);
      create(Lb);
      print(Lb);
      create(Lc);
      Union(La,Lb,Lc);
      //insert(L,x);
      cout<<"合并后的表：";
      print(Lc);
      return 0;
    }