考研数据结构算法经典

数据结构算法背诵一、线性表1.逆转顺序表中的所有元素算法思想：第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，……，依此类推。voidReverse(intA[],intn){inti,t;for(i=0;in/2;i++){t=A[i];A[i]=A[n-i-1];A[n-i-1]=t;}}2.删除线性链表中数据域为item的所有结点算法思想：先从链表的第2个结点开始，从前往后依次判断链表中的所有结点是否满足条件，若某个结点的数据域为item，则删除该结点。最后再回过头来判断链表中的第1个结点是否满足条件，若满足则将其删除。voidPurgeItem(LinkList&list){LinkListp,q=list;p=list-next;while(p!=NULL){if(p-data==item){q-next=p-next;free(p);p=q-next;}else{q=p;p=p-next;}}if(list-data==item){q=list;list=list-next;free(q);}}3.逆转线性链表voidReverse(LinkList&list){LinkListp,q,r;p=list;q=NULL;while(p!=NULL){r=q;q=p;p=p-next;q-next=r;}list=q;}4.复制线性链表（递归）LinkListCopy(LinkListlista){LinkListlistb;if(lista==NULL)returnNULL;else{listb=(LinkList)malloc(sizeof(LNode));listb-data=lista-data;listb-next=Copy(lista-next);returnlistb;}}5.将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表LinkListMergeList(LinkListlista,LinkListlistb){LinkListlistc,p=lista,q=listb,r;//listc指向lista和listb所指结点中较小者if(lista-data=listb-data){listc=lista;r=lista;p=lista-next;}else{listc=listb;r=listb;q=listb-next;}while(p!=NULL&&q!=NULL){if(p-data=q-data){r-next=p;r=p;p=p-next;}else{r-next=q;r=q;q=q-next;}}//将剩余结点（即未参加比较的且已按升序排列的结点）链接到整个链表后面r-next=(p!=NULL)?p:q;returnlistc;}二、树1.二叉树的先序遍历（非递归算法）算法思想：若p所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将p指向其左孩子结点；若p所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址），将p指向其右孩子结点。重复上述过程，直到p=NULL且堆栈为空，遍历结束。#defineMAX_STACK50voidPreOrderTraverse(BTreeT){BTreeSTACK[MAX_STACK],p=T;inttop=-1;while(p!=NULL||top!=-1){while(p!=NULL){VISIT(p);STACK[++top]=p;p=p-lchild;}p=STACK[top--];p=p-rchild;}}2.二叉树的中序遍历（非递归算法）算法思想：若p所指结点不为空，则将该结点的地址p入栈，然后再将p指向其左孩子结点；若p所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址）送p，并访问该结点，然后再将p指向该结点的右孩子结点。重复上述过程，直到p=NULL且堆栈为空，遍历结束。#defineMAX_STACK50voidInOrderTraverse(BTreeT){BTreeSTACK[MAX_STACK],p=T;inttop=-1;while(p!=NULL||top!=-1);{while(p!=NULL){STACK[++top]=p;p=p-lchild;}p=STACK[top--];VISIT(p);p=p-rchild;}}3.二叉树的后序遍历（非递归算法）算法思想：当p指向某一结点时，不能马上对它进行访问，而要先访问它的左子树，因而要将此结点的地址入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到），还不能对它进行访问，还需要先访问它的右子树，所以，再一次将该结点的地址入栈。只有当该结点的右子树访问完毕后回到该结点时，才能访问该结点。为了标明某结点是否可以访问，引入一个标志变量flag，当flag=0时表示该结点暂不访问，flag=1时表示该结点可以访问。flag的值随同该结点的地址一起入栈和出栈。因此，算法中设置了两个堆栈，其中STACK1存放结点的地址，STACK2存放标志变量flag，两个堆栈使用同一栈顶指针top，且top的初始值为.1。#defineMAX_STACK50voidPostOrderTraverse(BTreeT){BTreeSTACK1[MAX_STACK],p=T;intSTACK2[MAX_STACK],flag,top=-1;while(p!=NULL||top!=-1){while(p!=NULL){STACK1[++top]=p;STACK2[top]=0;p=p-lchild;}p=STACK1[top];flag=STACK2[top--];if(flag==0){STACK1[++top]=p;STACK2[top]=1;p=p-rchild;}else{VISIT(p);p=NULL;}}}4.二叉树的按层次遍历算法思想：设置一个队列，首先将根结点（的地址）入队列，然后依次从队列中退出一个元素，每退出一个元素，先访问该元素所指的结点，然后依次将该结点的左孩子结点（若存在的话）和右孩子结点（若存在的话）入队列。如此重复下去，直到队列为空。#defineMAX_QUEUE50voidLayeredOrderTraverse(BTreeT){BTreeQUEUE[MAX_QUEUE],p;intfront,rear;if(T!=NULL){QUEUE[0]=T;front=-1;rear=0;while(frontrear){p=QUEUE[++front];VISIT(P);if(p-lchild!=NULL)QUEUE[++rear]=p-lchild;if(p-rchild!=NULL)QUEUE[++rear]=p-rchild;}}}5.建立二叉树（从键盘输入数据，先序遍历递归算法）BTreeCreateBT(){charch;BTreeT;sacnf(%c,&ch);if(ch=='')returnNULL;else{T=(BTree)malloc(sizeof(BTNode));T-data=ch;T-lchild=CreateBT();T-rchild=CreateBT();returnT;}}6.建立二叉树（从数组获取数据）BTreeCreateBT(intA[],inti,intn){BTreep;if(in)returnNULL;else{p=(BTree)malloc(sizeof(BTNode));p-data=A[i];p-lchild=CreateBT(A,2*i,n);p-rchild=CreateBT(A,2*i+1,n);returnp;}}T=CreateBT(A,1,n);BTreeCreateBT(intA[],intn){inti;BTree*pT;//对应n个结点申请可容纳n个指针变量的内存空间pT=(BTree*)malloc(sizeof(BTree)*n);//若数组中的某个元素不等于零，则申请相应的结点空间并进行赋值for(i=1;i=n;i++){if(A[i]!=0){pT[i]=(BTree)malloc(sizeof(BTNode));pT[i]-data=A[i];}else{pT[i]=NULL;}}//修改结点的指针域的内容，使父结点指向左、右孩子结点for(i=1;i=n;i++){if(pT[i]!=NULL){pT[i]-lchild=pT[2*i];pT[i]-rchild=pT[2*i+1];}}}7.求二叉树的深度（递归算法）intDepth(BTreeT){intldepth,rdepth;if(T==NULL)return0;else{ldepth=Depth(T-lchild);rdepth=Depth(T-rchild);if(ldepthrdepth)returnldepth+1;elsereturnrdepth+1;}}8.求二叉树的深度（非递归算法）算法思想：对二叉树进行遍历，遍历过程中依次记录各个结点所处的层次数以及当前已经访问过的结点所处的最大层次数。每当访问到某个叶子结点时，将该叶子结点所处的层次数与最大层次数进行比较，若前者大于后者，则修改最大层次数为该叶子结点的层次数，否则不作修改。遍历结束时，所记录的最大层次数即为该二叉树的深度。本算法使用的是非递归的中序遍历算法（其它遍历顺序也可以）。#defineMAX_STACK50intDepth(BTreeT){BTreeSTACK1[MAX_STACK],p=T;intSTACK2[MAX_STACK];intcurdepth,maxdepth=0,top=-1;if(T!=NULL){curdepth=1;while(p!=NULL||top!=-){while(p!=NULL){STACK1[++top]=p;STACK2[top]=curdepth;p=p-lchild;curdepth++;}p=STACK1[top];curdepth=STACK2[top--];if(p-lchild==NULL&&p-rchild==NULL)if(curdepthmaxdepth)maxdepth=curdepth;p=p-rchild;curdepth++;}}returnmaxdepth;}9.求结点所在层次算法思想：采用后序遍历的非递归算法对二叉树进行遍历，遍历过程中对每一个结点判断其是否为满足条件的结点，若是满足条件的结点，则此时堆栈中保存的元素个数再加1即为该结点所在的层次。#defineMAX_STACK50intLayerNode(BTreeT,intitem){BTreeSTACK1[MAX_STACK],p=T;intSTACK2[MAX_STACK],flag,top=-1;while(p!=NULL||top!=-1){while(p!=NULL){STACK1[++top]=p;STACK2[top]=0;p=p-lchild;}p=STACK1[top];flag=STACK2[top--];if(flag==0){STACK1[++top]=p;STACK2[top]=1;p=p-rchild;}else{if(p-data==item)returntop+2;p=NULL;}}}10.交换二叉树中所有结点的左右子树的位置算法思想：按层次遍历二叉树，遍历过程中每当访问一个结点时，就将该结点的左右子树的位置对调。#defineMAX_QUEUE50voidExchangeBT(BTreeT){BTreeQUEUE[MAX_QUEUE],temp,p=T;intfront,rear;if(T!=NULL){QUEUE[0]=T;front=-1;rear=0;while(frontrear){p=QUEUE[