數(shù)據(jù)結(jié)構(gòu)算法

1.順序表插入算法2.6(P19)voidListInsert_Sq(SqList&L,inti,ElemTypee){//在順序線性表L的第i個(gè)元素之前插入新的元素e，i的合法值為//1≤i≤L.length+1,若表中容量不足，則按預(yù)定義增量擴(kuò)容if(i<1||i>L.length+1)ErrorMessage("i值不合法");if(L.length>=L.listsize)increment(L,L.incrementsize);//當(dāng)前存儲空間已滿，為L增加分配L.incrementsize個(gè)元素空間q=&(L.elem[i-1]);//q為插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長增1}//ListInsert_Sq2.刪除元素操作(算法2.7)voidListDelete_Sq(SqList&L,inti,ElemType&e){//在順序線性表L中刪除第i個(gè)元素，并用e返回其值。//i的合法值為1≤i≤L.length。if((i<1)||(i>L.length))ErrorMessage("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;//表長減1}//ListDelete_Sq3.算法2.10voidexchang1(SqList&A,intm,intn){intk,j;for(k=1;k<=n;k++){w=A.elem[m+k-1];for(j=m+k-1;j>=k;j--)A.elem[j]=A.elem[j-1];A.elem[k-1]=w;}//for}//exchang14.在鏈表中將s結(jié)點(diǎn)插入到p結(jié)點(diǎn)之前（算法2.16）voidListInsert(LinkList&L,LNode*p,LNode*s)//不帶頭結(jié)點(diǎn){if(p==L){s->next=L;L=s;}//將s結(jié)點(diǎn)插入在鏈表的第一個(gè)結(jié)點(diǎn)之前else{q=L;while(q->next!=p)q=q->next;//查找p的前驅(qū)qq->next=s;s->next=p;//在q結(jié)點(diǎn)之后插入s結(jié)點(diǎn)}}voidListInsert(LinkList&L,LNode*p,LNode*s)//帶頭結(jié)點(diǎn){q=L;while(q->next!=p)q=q->next;//查找p的前驅(qū)qq->next=s;s->next=p;//在q結(jié)點(diǎn)之后插入s結(jié)點(diǎn)}//將對首元結(jié)點(diǎn)的操作和其他結(jié)點(diǎn)的操作統(tǒng)一起來5.逆序創(chuàng)建鏈表（算法2.18）voidCreateList_H(LinkList&L,ElemTypeA[],intn)//帶頭結(jié)點(diǎn){L=newLNode;L->next=NULL;//先建立一個(gè)空的單鏈表for(i=n-1;i>=0;--i){s=newLNode;//生成新結(jié)點(diǎn)s->data=A[i];//賦元素值s->next=L->next;L->next=s;//插入在第一個(gè)結(jié)點(diǎn)之前}voidCreateList_H(LinkList&L,ElemTypeA[],intn)//不帶頭結(jié)點(diǎn){L=NULL;//先建立一個(gè)空的單鏈表for(i=n-1;i>=0;--i){s=newLNode;//生成新結(jié)點(diǎn)s->data=A[i];//賦元素值s->next=L;L=s;//插入在第一個(gè)結(jié)點(diǎn)之前}}6.指向尾結(jié)點(diǎn)的循環(huán)有序鏈表求并集（帶頭結(jié)點(diǎn)）voidunion_OL(LinkList&La，LinkList&Lb){//La和Lb分別為表示集合A和B的循環(huán)鏈表的頭指針，求C=A∪B，操作完成之后，La為表示集合C的循環(huán)鏈表的頭指針，集合A和B的鏈表不再存在pa=La->next->next;//pa指向A中當(dāng)前考察的結(jié)點(diǎn)pb=Lb->next->next;//pb指向B中當(dāng)前考察的結(jié)點(diǎn)rc=La->next;//rc指向C當(dāng)前的表尾結(jié)點(diǎn)while(pa!=La->next&&pb!=Lb->next){if(pa->data<pb->data){//鏈接A的結(jié)點(diǎn)，pa指向A中下一結(jié)點(diǎn)rc->next=pa;rc=pa;pa=pa->next;}//ifelseif(pa->data>pb->data){//鏈接B的結(jié)點(diǎn)，pb指向B中下一結(jié)點(diǎn)rc->next=pb;rc=pb;pb=pb->next;}else{//鏈接A的元素，釋放B的結(jié)點(diǎn)，pa、pb分別指//向各自下一元素rc->next=pa;rc=pa;pa=pa->next;qb=pb;pb=pb->next;deleteqb;}//else}//whileif(pb==Lb->next)rc->next=pa;//鏈接A的剩余段else{//鏈接B的剩余段rc->next=pb;pb=Lb->next;//pb指向B的頭結(jié)點(diǎn)Lb->next=La->next;La=Lb;//構(gòu)成C的循環(huán)鏈}//elsedeletepb;//釋放B表的表頭}//union_OL7.算法6.2voidInOrder_iter(BiTreeBT,void(*visit)(BiTree)){//利用棧實(shí)現(xiàn)中序遍歷二叉樹，BT為指向二叉樹的根結(jié)//點(diǎn)的頭指針I(yè)nitStack(S);e.ptr=BT;e.task=Travel;//e為棧元素if(BT)Push(S,e);//布置初始任務(wù)while(!StackEmpty(S))//每次處理一項(xiàng)任務(wù){(diào)Pop(S,e);if(e.task==Visit)visit(e.ptr);//處理訪問任務(wù)elseif(e.ptr)//處理非空樹的遍歷任務(wù){(diào)p=e.ptr;e.ptr=p->rchild;e.task=Travel;Push(S,e);