1、?壹開始的思路:把A、B都丟進C裏,然後對C排序。人們壹開始想到的總是最懶的辦法,往往是最沒效率的。
改進:由於A、B是排好序的,先把A丟進C裏,再拿B元素壹個個往裏查找插入。這麽做要頻繁移動元素,如果線性表不是鏈表的話,開銷很大。 再改進:從A、B中各拿壹個元素出來,比較後把小的放進C裏,再從剛才拿出元素的那個表裏再拿個元素出來,再比較,把小的放進C裏,重復這樣的操作,直到A、B其中壹個中的元素拿完為止,再把還有剩的元素全丟進C裏。2、例程:
#include?<stdlib.h>/*順序表存儲空間長度的最小值*/
#define?LISTMINSIZE?10
/*順序表存儲結構類型定義*/
typedef?struct
{
ListDT*base;/*順序表空間基地址*/
intlistsize;/*順序表空間尺寸*/
intlen;?/*順序表長度*/
}SeqList;
/*順序表初始化*/
void?ListInitialize(SeqList?*pL,?int?size)
{
if(size<LISTMINSIZE)
size=LISTMINSIZE;/*限定不能小於最小尺寸*/
pL->listsize=size;
pL->base=(ListDT*)malloc(pL->listsize*sizeof(ListDT));
if(!pL->base)
exit(EXIT_FAILURE);
pL->len=0;/*初始化空表*/
}
/*按給定的下標取順序表元素值*/
BOOL?ListElem(SeqList?L,?int?index,?ListDT?*pelem)
{
BOOLflg=TRUE;
if(index<0||?index>L.len-1?)
flg=FALSE;/*參數越界*/
else
*pelem=L.base[index];
returnflg;
}
/*求順序表長度*/
int?ListLen(SeqList?L)
{
returnL.len;?
}
/*在順序表中指定序號位置插入元素*/
BOOL?ListInsert(SeqList?*pL,?int?pos,?ListDT?d)
{
BOOLflg=TRUE;
inti;
if(pos<0||?pL->len>=pL->listsize?||?pos>pL->len)
flg=FALSE;
else
{
for(i=pL->len-1;i>=pos;?i--)?/*移動數據*/
pL->base[i+1]=pL->base[i];pL->base[pos]=d;?/*寫入數據*/
pL->len++;?/*表長增1*/
}
returnflg;
}
/*把順序表中指定序號的元素刪除*/
BOOL?ListDel(SeqList?*pL,?int?pos)
{
BOOLflg=TRUE;
inti;
if(pos<0||?pos>=pL->len)
flg=FALSE;
else
{
for(i=pos+1;i<pL->len;?i++)/*移動數據*/
pL->base[i-1]=pL->base[i];pL->len--;/*表長增1*/
}
returnflg;
}
/*在順序表中查找元素*/
int?ListLoc(SeqList?L,?ListDT?d,BOOL?(*equal)(ListDT,ListDT))
{
intpos=L.len-1;
while(pos>=0&&?!(*equal)(L.base[pos],d))
pos--;
returnpos;
}
/*取前導元素序號位置*/
BOOL?ListPrior(SeqList?L,?int?pos,?int?*ppriorpos)
{
BOOLflg=TRUE;
if(pos>0&&?pos<L.len)
*ppriorpos=pos-1;
else
flg=FALSE;
returnflg;
}
/*取後繼元素序號位置*/
BOOL?ListNext(SeqList?L,?int?pos,?int?*pnextpos)
{
BOOLflg=TRUE;
if(pos>=0&&?pos<L.len-1)
*pnextpos=pos+1;
else
flg=FALSE;
returnflg;
}
/*銷毀順序表*/
void?ListDestroy(SeqList?L)
{
free(L.base);
}
#endif
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*
建議性測試用程序
*/
typedef?enum?{TRUE=1,FALSE=0}?BOOL;
typedef?int?ListDT;
#include?"seqlist.c"
void?printSeqList(SeqList?L)
{
inti;
ListDTx;
printf("\nList:\n");
for(i=0;i<ListLen(L);?i++)
{
ListElem(L,i,&x);
printf("%3d",x);
}
}
BOOL?dataequal(int?x,?int?y)
{
return(x==y)?TRUE:FALSE;
}
#define?N?5
void?main()
{
inti,prior,next;
ListDTx,test[N]={10,20,30,40,50};
SeqListL;
/*初始化順序表*/
ListInitialize(&L,N);
/*在表頭插入N個元素*/
for(i=0;i<N;?i++)
ListInsert(&L,0,test[i]);
printSeqList(L);
/*刪除元素*/
ListDel(&L,N/2);
printSeqList(L);
printf("\ninputa?key:\n");
scanf("%d",&x);
/*查找x在表中位置*/
i=ListLoc(L,x,dataequal);
/*求x的前導元素*/
if(ListPrior(L,i,&prior))
{
ListElem(L,prior,&x);
printf("Prior:%d\n",x);
}
else
printf("noPrior.\n");
/*求x的後繼*/
if(ListNext(L,i,&next))
{
ListElem(L,next,&x);
printf("Next:%d\n",x);
}
else
printf("noNext.\n");
/*求表長*/
printf("Listlength=%d",ListLen(L));
/*銷毀順序表*/
ListDestroy(L);
}