The NoteBook of EricKong

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  610 Posts :: 1 Stories :: 190 Comments :: 0 Trackbacks
原文题是严蔚敏同志的数据结构习题中第二章线性表中提出的问题。

原问如下:

2.24 假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请编写算法将A表与B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元表)排列的线性表C,并要求利用原表(即A表与B表)的结点空间构造C表。

分析:对两个或两个以上,结点按元素值递增/减排列的单链表进行操作时,应采用"指针平行移动、一次扫描完成"的策略。且链表A与链表B的长度大小不一定相等。

代码:

#include<iostream>   
using namespace std;  
typedef 
int ElemType;  
  
//两个递增的链表合并成递增的链表。   
typedef struct LNode  
{  
    ElemType data;  
    
struct LNode *next;  
}
  
LNode;  
typedef LNode 
*LinkList;  
void CreatList(LinkList &L,int n)  
{  
    LinkList p,q;  
    L
=new LNode;  
    L
->next=NULL;  
    q
=L;  
    cout
<<"请从小到大输入链表的元素:";  
    
for (int i=1;i<=n;i++)  
    
{  
        p
=new LNode;  
        cin
>>p->data;  
        p
->next=q->next;  
        q
->next=p;  
        q
=q->next;  
    }
  
    cout
<<"所创建得的递增有序链表为:";  
    p
=L->next;  
    
for (int j=1;j<=n;j++)  
    
{  
        cout
<<p->data<<" ";  
        p
=p->next;  
    }
  
    cout
<<endl;  
}
  
void CreatC(LinkList &A,LinkList &B,LinkList &C,int n)  
{  
    LinkList pa,pb,pc,pre
=NULL/*C结点的上一个结点*/,q/*t*/;  
    pa
=A->next;  
    pb
=B->next;  
  
//  C=t=A;// A   
    while (pa||pb)  
    
{  
        
if (!pb||((pa&&pb)&&(pa->data<pb->data)))  
        
{  
            
////将A的元素插入新表   
            pc=pa;  
            q
=pa->next;  
            pa
->next=pre;  
            pa
=q;  
        }
  
        
else  
        
{  
            pc
=pb;  
            q
=pb->next;  
            pb
->next=pre;  
            pb
=q; //将B的元素插入新表   
        }
  
        pre
=pc;  
    }
  
    cout
<<"合并后的递减有序链表为:";  
    C
=A;  
    A
->next=pc;  
    pa
=pc;  
    
for (int j=1;j<=n;j++)  
    
{  
        cout
<<pa->data<<" ";  
        pa
=pa->next;  
    }
  
    cout
<<endl;  
    getchar();  
}
  
void main()  
{  
    LinkList A,B,C;  
    
int n,m,k;  
    cout
<<"请输入链表***A***的长度:";  
    cin
>>n;  
    CreatList(A,n);  
    cout
<<"请输入链表***B***的长度:";  
    cin
>>m;  
    CreatList(B,m);  
    k
=m+n;  
    CreatC(A,B,C,k);  
    system(
0);  
    getchar();  
}
  


posted on 2012-06-04 09:44 Eric_jiang 阅读(1966) 评论(2)  编辑  收藏 所属分类: C/C++

Feedback

# re: 把两个递增的单链表La,Lb,合并成一个递减的单链表Lc 2012-06-04 12:17 葡语翻译公司
 ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。
  回复  更多评论
  

# re: 把两个递增的单链表La,Lb,合并成一个递减的单链表Lc 2012-11-05 20:39 566
算法很巧妙!谢谢分享!
还想问一下算法的时间复杂度是多少呢?  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: