考研数据结构算法经典.doc

《考研数据结构算法经典.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构算法背诵一、线性表1.逆转顺序表中的所有元素算法思想：第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，……，依此类推。voidReverse(intA[],intn){inti,t;for(i=0;i

2、t){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.复制线性链表（

3、递归）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

4、指向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

5、.二叉树的先序遍历（非递归算法）算法思想：若p所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将p指向其左孩子结点；若p所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址），将p指向其右孩子结点。重复上述过程，直到p=NULL且堆栈为空，遍历结束。#defineMAX_STACK50voidPreOrderTraverse(BTreeT){BTreeSTACK[MAX_STACK],p=T;inttop=-1;while(p!=NULL

6、

7、top!=-1){while(p!=NULL){VISIT(p);STACK[++top]=p;p=p->lchild;}p=STACK[

8、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

9、

10、top!=-1);{while(p!=NULL){STACK[++top]=p;

11、p=p->lchild;}p=STACK[top--];VISIT(p);p=p->rchild;}}3.二叉树的后序遍历（非递归算法）算法思想：当p指向某一结点时，不能马上对它进行访问，而要先访问它的左子树，因而要将此结点的地址入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到），还不能对它进行访问，还需要先访问它的右子树，所以，再一次将该结点的地址入栈。只有当该结点的右子树