算法与数据结构--实现线性表的合并操作（合并后按非递减排列）--算法2.6
/* (程序头部注释开始)* 程序的版权和版本声明部分* Copyright (c) 2011, 烟台大学计算机学院学生 * All rights reserved.* 文件名称：顺序表的合并 * 作 者： 雷恒鑫 * 完成日期： 2012 年 09 月 18 日 * 版 本 号： V1.0 * 对任务及求解方法的描述部分 * 输入描述：（1）已知顺序线性表La和Lb的元素按值非递减排列。（2）归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。 * 问题描述： * 程序输出： * 程序头部的注释结束*/#include <iostream>using namespace std;#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量#define LISTINCREMENT 10//线性表存储空间的分配增量typedef int ElemType; //定义别名typedef int Status; //定义别名typedef struct{ElemType *elem;//存储空间基址int length;//当前长度int listsize;//当前分配的存储容量（以sizeof(ElemType)为单位）}SqList;Status InitList_Sq(SqList &L){//构造一个空的线性表LL.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));if(!L.elem)exit(1);//存储分配失败,z正常退出L.length = 0;//空表长度为0L.listsize = LIST_INIT_SIZE;//初始存储容量return true;}Status ListInsert_Sq(SqList &L,int i,ElemType e){//在顺序线性表L中第i个位置之前插入新的元素e//i的合法值为1<=i<=ListLength_Sq(L)+1if(i <1 || i> L.length + 1)return false;//i值不合法if(L.length >= L.listsize)//当前存储空间已满，增加分配{ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT )* sizeof(ElemType));if(!newbase)exit(1);//存储分配失败L.elem = newbase;//新基址L.listsize += LISTINCREMENT;//增加存储容量}ElemType *q = &(L.elem[i-1]);//q为插入位置for(ElemType *p = &(L.elem[L.length-1]);p>=q;--p)*(p+1) = *p;//插入位置及之后的元素右移*q = e;//插入e++L.length;//表长增1return true;}Status ListDelete_Sq(SqList &L,int i){//在顺序线性表L中删除第i个元素，并用e返回其值//i的合法值为 1<= i<=ListLength_Sq(L)if((i<1)||(i>L.length))return false;//i值不合法ElemType *p = &(L.elem[i-1]);//p为被删除元素的位置ElemType e = *p;//被删除元素的值赋值给eElemType *q = L.elem + L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1) = *p;//被删除元素之后的元素左移--L.length;//表长减1return e;}Status compare(ElemType e1,ElemType e2){if(e1==e2)return true;return false;}int LocateElem_sq(SqList L,ElemType e,Status (*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()的元素的为序//若找到，则返回其在L中的位序，否则返回0inti = 1;//i的初值为第1个元素的位序ElemType *p = L.elem;//p的初值为为第1个元素的存储位置while(i<=L.length &&!(*compare)(*p++,e)){++i;}if(i<=L.length){return i;}else {return 0;}}void input(SqList L){inti = 1;//i的初值为第1个元素的位序ElemType *p = L.elem;//p的初值为为第1个元素的存储位置while(i<=L.length){cout<<*(p++)<<" ";++i;}cout<<endl;}void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){//已知顺序线性表La和Lb的元素按值非递减排列//归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列ElemType *pa = La.elem;ElemType *pb = Lb.elem;Lc.listsize = Lc.length = La.length + Lb.length;ElemType *pc = Lc.elem = (ElemType *)malloc(Lc.listsize * sizeof(ElemType));if(!Lc.elem)exit(1);//存储分配失败，非正常退出ElemType *pa_last = (La.elem + La.length -1);ElemType *pb_last = (Lb.elem + Lb.length -1);while(pa<=pa_last&&pb<=pb_last)//归并{if(*pa<=*pb){*pc++=*pa++;}else{*pc++=*pb++;}}while(pa<=pa_last)//插入La的剩余元素{*pc++=*pa++;}while(pb<=pb_last)//插入Lb的剩余元素{*pc++=*pb++;}}void main(){SqList La,Lb,Lc;InitList_Sq(La);InitList_Sq(Lb);InitList_Sq(Lc);ListInsert_Sq(La,1,2);//在顺序线性表L中第i个位置之前插入新的元素eListInsert_Sq(La,2,3);//在顺序线性表L中第i个位置之前插入新的元素eListInsert_Sq(La,3,4);//在顺序线性表L中第i个位置之前插入新的元素eListInsert_Sq(La,4,5);//在顺序线性表L中第i个位置之前插入新的元素eListInsert_Sq(Lb,1,6);//在顺序线性表L中第i个位置之前插入新的元素eListInsert_Sq(Lb,2,7);//在顺序线性表L中第i个位置之前插入新的元素eListInsert_Sq(Lb,3,8);//在顺序线性表L中第i个位置之前插入新的元素eListInsert_Sq(Lb,4,9);//在顺序线性表L中第i个位置之前插入新的元素e//ListInsert_Sq(Lc,1,2);//在顺序线性表L中第i个位置之前插入新的元素e//ListInsert_Sq(Lc,2,3);//在顺序线性表L中第i个位置之前插入新的元素e//ListInsert_Sq(Lc,3,4);//在顺序线性表L中第i个位置之前插入新的元素e//ListInsert_Sq(Lc,4,5);//在顺序线性表L中第i个位置之前插入新的元素e//ElemType e = ListDelete_Sq(La,1);cout<<"线性表中La的所有元素为：";input(La);cout<<"线性表中Lb的所有元素为：";input(Lb);//int e = LocateElem_sq(La,3,(*compare));//在顺序线性表L中查找第1个值与e满足compare()的元素的为序//cout<<"线性表中与3相等的元素的位序为："<<e<<endl;cout<<"La与Lb合并后，线性表中Lc的所有元素为："<<endl;MergeList_Sq(La,Lb,Lc);input(Lc);system("PAUSE");return;}
运行结果：
