12数据结构算法总结

1算法总结2.1voidUnion(List&La,ListLb){//算法2.1//将所有在线性表Lb中但不在La中的数据元素插入到La中intLa_len,Lb_len,i;ElemTypee;La_len=ListLength(La);//求线性表的长度Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal))//La中不存在和e相同的数据元素ListInsert(La,++La_len,e);//插入}}//union2.2voidMergeList(ListLa,ListLb,List&Lc){//算法2.2//已知线性表La和Lb中的元素按值非递减排列。//归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。intLa_len,Lb_len;ElemTypeai,bj;inti=1,j=1,k=0;InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);while((i=La_len)&&(j=Lb_len)){//La和Lb均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList2.3StatusInitList_Sq(SqList&L){//算法2.32//构造一个空的线性表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)returnOK;//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq2.4StatusListInsert_Sq(SqList&L,inti,ElemTypee){//算法2.4//在顺序线性表L的第i个元素之前插入新的元素e，//i的合法值为1≤i≤ListLength_Sq(L)+1ElemType*p;if(i1||iL.length+1)returnERROR;//i值不合法if(L.length=L.listsize){//当前存储空间已满，增加容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)returnERROR;//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存储容量}ElemType*q=&(L.elem[i-1]);//q为插入位置for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;}//ListInsert_Sq2.5StatusListDelete_Sq(SqList&L,inti,ElemType&e){//算法2.5//在顺序线性表L中删除第i个元素，并用e返回其值。//i的合法值为1≤i≤ListLength_Sq(L)。ElemType*p,*q;if(i1||iL.length)returnERROR;//i值不合法p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p=q;++p)*(p-1)=*p;//被删除元素之后的元素左移--L.length;//表长减1returnOK;}//ListDelete_Sq2.6intLocateElem_Sq(SqListL,ElemTypee,3Status(*compare)(ElemType,ElemType)){//算法2.6//在顺序线性表L中查找第1个值与e满足compare()的元素的位序。//若找到，则返回其在L中的位序，否则返回0。inti;ElemType*p;i=1;//i的初值为第1个元素的位序p=L.elem;//p的初值为第1个元素的存储位置while(i=L.length&&!(*compare)(*p++,e))++i;if(i=L.length)returni;elsereturn0;}//LocateElem_Sq2.7voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){//算法2.7//已知顺序线性表La和Lb的元素按值非递减排列。//归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存储分配失败pa_last=La.elem+La.length-1;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)*pc++=*pa++;//插入La的剩余元素while(pb=pb_last)*pc++=*pb++;//插入Lb的剩余元素}//MergeList2.8StatusGetElem_L(LinkList&L,inti,ElemType&e){//算法2.8//L为带头结点的单链表的头指针。//当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORLinkListp;p=L-next;intj=1;//初始化，p指向第一个结点，j为计数器while(p&&ji){//顺指针向后查找，直到p指向第i个元素或p为空p=p-next;++j;}if(!p||ji)returnERROR;//第i个元素不存在4e=p-data;//取第i个元素returnOK;}//GetElem_L2.9StatusListInsert_L(LinkList&L,inti,ElemTypee){//算法2.9//在带头结点的单链线性表L的第i个元素之前插入元素eLinkListp,s;p=L;intj=0;while(p&&ji-1){//寻找第i-1个结点p=p-next;++j;}if(!p||ji-1)returnERROR;//i小于1或者大于表长s=(LinkList)malloc(sizeof(LNode));//生成新结点s-data=e;s-next=p-next;//插入L中p-next=s;returnOK;}//LinstInsert_L2.10StatusListDelete_L(LinkList&L,inti,ElemType&e){//算法2.10//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkListp,q;p=L;intj=0;while(p-next&&ji-1){//寻找第i个结点，并令p指向其前趋p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;//删除并释放结点e=q-data;free(q);returnOK;}//ListDelete_L2.11voidCreateList_L(LinkList&L,intn){//算法2.11//逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表LLinkListp;inti;5L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//先建立一个带头结点的单链表for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点p-data=random(200);//改为一个随机生成的数字(200以内)p-next=L-next;L-next=p;//插入到表头}}//CreateList_L2.12voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//算法2.12//已知单链线性表La和Lb的元素按值非递减排列。//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。LinkListpa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;//插入剩余段free(Lb);//释放Lb的头结点}//MergeList_L2.13intLocateElem_SL(SLinkListS,ElemTypee){//算法2.13//在静态单链线性表L中查找第1个值为e的元素。//若找到，则返回它在L中的位序，否则返回0。inti;i=S[0].cur;//i指示表中第一个结点while(i&&S[i].data!=e)i=S[i].cur;//在表中顺链查找returni;}//LocateElem_SL2.14voidInitSpace_SL(SLinkListspace){//算法2.14//将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，//0表示空指针for(inti=0;iMAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1].cur=0;}//InitSpace_SL2.156intMalloc_SL(SLinkList&space){//算法2.15//若备用空间链表非空，则返回分配的结点下标，否则返回0inti=space[0].cur;if(space[0].cur)space[0].cur=space[space[0].cur].cur;returni;}//Malloc_SL2.16voidFree_SL(SLinkList&space,intk){//算法2.16//将下标为k的空闲结点回收到备用链表space[k].cur=space[0].cur;space[0].cur=k;}//Free_SL2.17voiddifference(SLinkList&space,int&S){//算法2.17//依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)∪(B-A)//的静态链表,S为头指针。假设备用空间足够大，space[0].cur为头指针。inti,j,k,m,n,p,r;ElemTypeb;InitSpac