数据结构算法

1.顺序表插入算法2.6(P19)voidListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L的第i个元素之前插入新的元素e，i的合法值为//1≤i≤L.length+1,若表中容量不足，则按预定义增量扩容if(i<1||i>L.length+1)ErrorMessage("i值不合法");if(L.length>=L.listsize)increment(L,L.incrementsize);//当前存储空间已满，为L增加分配L.incrementsize个元素空间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个元素，并用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结点插入到p结点之前（算法2.16）voidListInsert(LinkList&L,LNode*p,LNode*s)//不带头结点{if(p==L){s->next=L;L=s;}//将s结点插入在链表的第一个结点之前else{q=L;while(q->next!=p)q=q->next;//查找p的前驱qq->next=s;s->next=p;//在q结点之后插入s结点}}voidListInsert(LinkList&L,LNode*p,LNode*s)//带头结点{q=L;while(q->next!=p)q=q->next;//查找p的前驱qq->next=s;s->next=p;//在q结点之后插入s结点}//将对首元结点的操作和其他结点的操作统一起来5.逆序创建链表（算法2.18）voidCreateList_H(LinkList&L,ElemTypeA[],intn)//带头结点{L=newLNode;L->next=NULL;//先建立一个空的单链表for(i=n-1;i>=0;--i){s=newLNode;//生成新结点s->data=A[i];//赋元素值s->next=L->next;L->next=s;//插入在第一个结点之前}voidCreateList_H(LinkList&L,ElemTypeA[],intn)//不带头结点{L=NULL;//先建立一个空的单链表for(i=n-1;i>=0;--i){s=newLNode;//生成新结点s->data=A[i];//赋元素值s->next=L;L=s;//插入在第一个结点之前}}6.指向尾结点的循环有序链表求并集（带头结点）voidunion_OL(LinkList&La，LinkList&Lb){//La和Lb分别为表示集合A和B的循环链表的头指针，求C=A∪B，操作完成之后，La为表示集合C的循环链表的头指针，集合A和B的链表不再存在pa=La->next->next;//pa指向A中当前考察的结点pb=Lb->next->next;//pb指向B中当前考察的结点rc=La->next;//rc指向C当前的表尾结点while(pa!=La->next&&pb!=Lb->next){if(pa->data<pb->data){//链接A的结点，pa指向A中下一结点rc->next=pa;rc=pa;pa=pa->next;}//ifelseif(pa->data>pb->data){//链接B的结点，pb指向B中下一结点rc->next=pb;rc=pb;pb=pb->next;}else{//链接A的元素，释放B的结点，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的头结点Lb->next=La->next;La=Lb;//构成C的循环链}//elsedeletepb;//释放B表的表头}//union_OL7.算法6.2voidInOrder_iter(BiTreeBT,void(*visit)(BiTree)){//利用栈实现中序遍历二叉树，BT为指向二叉树的根结//点的头指针InitStack(S);e.ptr=BT;e.task=Travel;//e为栈元素if(BT)Push(S,e);//布置初始任务while(!StackEmpty(S))//每次处理一项任务{Pop(S,e);if(e.task==Visit)visit(e.ptr);//处理访问任务elseif(e.ptr)//处理非空树的遍历任务{p=e.ptr;e.ptr=p->rchild;e.task=Travel;Push(S,e);