数据结构经典算法

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

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

2、条件，若满足则将其删除。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);}}23.逆转线性链表voidReverse(LinkList&list){LinkListp,q,

3、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.将

4、两个按值有序排列的非空线性链表合并为一个按值有序的线性链表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

5、){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;}3二、树1.二叉树的先序遍历（非递归算法）算法思想：若p所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将p指向其左孩子结点；若p所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址），将p指向其右孩子结点。重

6、复上述过程，直到p=NULL且堆栈为空，遍历结束。#defineMAX_STACK50voidPreOrderTraverse(BTreeT){BTreeSTACK[MAX_STACK],p=T;inttop=-1;while(p!=NULL

7、

8、top!=-1){while(p!=NULL){VISIT(p);STACK[++top]=p;p=p->lchild;}p=STACK[top--];p=p->rchild;}}2.二叉树的中序遍历（非递归算法）算法思想：若p所指结点不为空，则将该结点的地址p入栈，然后再将p

9、指向其左孩子结点；若p所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址）送p，并访问该结点，然后再将p指向该结点的右孩子结点。重复上述过程，直到p=NULL且堆栈为空，遍历结束。#defineMAX_STACK50voidInOrderTraverse(BTreeT){BTreeSTACK[MAX_STACK],p=T;inttop=-1;while(p!=NULL

10、

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

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