资源描述：
《数据结构期中测试-算法填空(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1、两个集合A和B的并集，集合A、B分别用线性表LA、LB表示。要求：A＝A∪B。注：∪——并集，属于A或者属于B)思路：1．从线性表LB中依次取得每个数据元素;GetElem(LB,i)→e2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3.若不存在，则插入之。ListInsert(LA,n+1,e)voidunion(List&LA,ListLB){//将所有在线性表Lb中但不在La中的数据元素插入到La中LA_len=ListLength(LA);LB_le
2、n=ListLength(LB);//求线性表的长度for(i=1;i<=LB_len;i++){GetElem(LB,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(LA,e,equal())ListInsert(LA,++LA_len,e);//La中不存在和e相同的数据元素，则插入之}}//union2、线性表的初始化StatusInitList_Sq(SqList&L)、{//构造一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_
3、SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq3、从线性表中查找具有给定值的第一个元素：intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足comp
4、are()的//元素的位序。若找到，则返回其在L中的位序，否则返回0。i=1;//i的初值为第1元素的位序p=L.elem;//p的初值为第1元素的存储位置while(i<=L.length&&L.elem[i-1]!=e)++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq此算法的时间复杂度为:O(ListLength(L))4、在线性表中指定位置前插入一个元素算法思想：1）不合法：①插入位置：检查i值是否超出所允许的范围（1≤i≤n+
5、1），若超出，则进行“超出范围”错误处理；②存储空间满2）将线性表的第i个元素和它后面的所有元素均向后移动一个位置；3）将新元素写入到空出的第i个位置上；4）使线性表的长度增1。StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L的第i个元素之前插入新的元素e//i的合法值为1≤i≤Listlength_Sq(L)+1if(i<1
6、
7、i>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.lists
8、ize){//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存储容量}for(intj=L.length-1;j>=i-1;j--){L.elem[j+1]=L.elem[j]}L.elem[
9、i-1]=e;//元素下标法++length;returnok;}插入算法的时间复杂度为:O(ListLength(L))5、在线性表中删除第i个元素算法思想：1）检查i值是否超出所允许的范围（1≤i≤n），若超出，则进行“超出范围”错误处理；2）将线性表的第i个元素后面的所有元素均向前移动一个位置；3）使线性表的长度减1。StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序线性表L中删除第i个元素，并用e返回其值。//i的合法值为1≤i≤Lis
10、tLength_Sq(L)if((i<1)
11、
12、(i>L.length))returnERROR;//删除位置不合法e=L.elem[i-1];for(intj=i-1;j
