《数据结构算法背诵版》由会员分享，可在线阅读，更多相关《数据结构算法背诵版（59页珍藏版）》请在金锄头文库上搜索。
1、数据构造算法背诵一、线性表逆转顺序表中的所有元素算法思想:第一种元素和最后一种元素对调，第二个元素和倒数第二个元素对调,依此类推。 oid Reerse(it A, int n） n i, t;for (=0; next；while ( !=LL) (p-da= item) -t p-ne；f(p);p = qnext; ese q=p;p=p-ex;f（ist-ta item) q =lst；ist listext；free(q); 3.逆转线性链表 vodReverse(inkLst st) inkist ， q, ; = lit;q NL;while (！= UL) r ；q ；p =
2、pne;q-nxt = r;list = q; 4.复制线性链表（递归）LinkList Cpy(LinkList lista) LiLi lisb; if （lisa = NL）eunNULL;elslistb (LinkLt)maloc(szof（LNo）;listb-data= ista-d;lib-next= Cy(lista-next）;return lsb; .将两个按值有序排列的非空线性链表合并为一种按值有序的线性链表 ikList MgList（LinkLi ista, inkLitlistb) ikLilitc, p = lia，q lstb,r;/ istc 指向lsta和
3、 listb 所指结点中较小者if (lta-datadaa) lisc= lista;r = lita；p = lia-nx; lslistc lstb;lstb；q = listnext; whe (p!=UL & !=ULL) if(pdatda) r-nep; = p;pp-next; l re =;r = q；= q-next； / 将剩余结点（即未参与比较的且已按升序排列的结点）链接到整个链表背面 r-nex = (p != NULL) ? p: q;rtun litc; 二、树 二叉树的先序遍历（非递归算法）算法思想:若 p所指结点不为空，则访问该结点，然后将该结点的地址入栈，然
4、后再将 指向其左孩子结点;若 p所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址）,将p指向其右孩子结点。反复上述过程，直到 p ULL且堆栈为空,遍历结束。 dfineMA_STACK50 vod PreOrderTravrs(Bee T） Tree STACASTC, p = T；t op ; while ( !=NUL| to!-1) whie （p !=NULL） VSIT(p);SACK+op = p;p p-child;p TKtop-; phld； 2.二叉树的中序遍历(非递归算法）算法思想:若 所指结点不为空,则将该结点的地址 入栈，然后再将 p指向其左孩子结点;若 p
5、所指向的结点为空,则从堆栈中退出栈顶元素（某个结点的地址)送 ,并访问该结点，然后再将 p指向该结点的右孩子结点。反复上述过程，直到p = NUL且堆栈为空,遍历结束。 #dfne MAXTACK vo InOdrTverse(BTe T） TreeSTACKA_STAK, =T;in p = -1; whle(p ！= NUL | op! -1)；wile ( ! NUL) STCK+to= p;p pchild; STAKop-；VIIT(p);p =p-chld；.二叉树的后序遍历（非递归算法）算法思想:当 指向某一结点时，不能立即对它进行访问，而要先访问它的左子树,因而要将此结点的地址
6、入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到),还不能对它进行访问，还需要先访问它的右子树,因此，再一次将该结点的地址入栈。只有当该结点的右子树访问完毕后回到该结点时,才干访问该结点。为了标明某结点与否可以访问，引入一种标志变量 fa，当 fla 时表达该结点暂不访问, flag 1时表达该结点可以访问。flg的值随同该结点的地址一起入栈和出栈。因此,算法中设立了两个堆栈,其中STCK1寄存结点的地址，STACK2寄存标志变量 fag,两个堆栈使用同一栈顶指针 op，且 的初始值为 1。#defe MX_AC 5oi osOrdrTraerse(Te ) ree ST
7、ACK1MAX_TC， = T;n SACK2AXSTAC, flg,t=-; while （p != ULL | t != -1) wle ( != NULL） SCK1+to =p;STACKtp 0； = p-lcd；p = SACK1top；fla = STACK2top-;if （lag = ) STCK+op p;STACK2top = 1;p = p-ild； els VIST(p);p = NULL; 4.二叉树的按层次遍历算法思想:设立一种队列,一方面将根结点(的地址)入队列,然后依次从队列中退出一种元素,每退出一种元素，先访问该元素所指的结点，然后依次将该结点的左孩子结点(
8、若存在的话)和右孩子结点（若存在的话)入队列。如此反复下去,直到队列为空。#define A_QUU 5 vid LayerereTraerse(Tree T）Bre QUEEMAX_QUEUE， p;intfront， rear;if （ != UL)UEE = ;fron -1;rea= 0;whe （frot lchil != NULL)QUEU+ea = ll；i (-rchd ！= NLL)QEE+rear rchild;5.建立二叉树（从键盘输入数据,先序遍历递归算法) Te CrateB（)harch；BTT; cnf（%,c);if （ch= )trn LL;ese T (BT
9、ree)malloc（size(TNoe)；T-data =ch;lchld CreteB();-rchid =reatT()；rturn T; 6建立二叉树（从数组获取数据) Bree CreateB(nt A, int i,intn）BTree p； if ( n)reurn NLL; p = (BTree)malloc(sio(BTNod)）;-daa = Ai;p-hld = reaeBT(,2*i, n);-rchil CreateT（A, 2i1, n)；return ; T = CeatBT(A, 1, n）; BTreeCreateB(it A，in n) int i;Tre *pT； /相应 n个结点申请可容纳 个指针变量的内存空间pT = (Bre )maloc(sizeof(Bree）*n);/若数组中的某个元素不等于零,则申请相应的结点空间并进行赋值or (i=; i= n; i+) if （Ai!= ) i = （Tree)mllo（sizeof(BNode）);pTi-at=Ai; e pi = ULL;/ 修改结点的指针域的内容，使父结点指向左、右孩子结点 for (i=1； lld = 2i;pi-rcid= 2*i+1; .求二叉树的深度(递归算法) it
