数据结构考研必背算法5星

数据结构考研必背算法5星文档说明：本文档是针对考研专业课《数据结构》所编写的，是对考研数据结构的核心算法进行总结，我们知道，不管是统考还是非统考，都会涉及至少10分的算法题（非统考至少25分），而这些题的答案都是在一些经典算法的思想上进行改进的，本文总结出必须要熟练掌握的算法，这些算法不管是考研初期还是冲刺，都应该高度重视，只要对这些代码进行熟练掌握，才能随机应变，希望对大家有所帮助；线性表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.删除线性表中数据域为X的所有结点；voidDel_X(Linklist&L,ElemtypeX){Linklistp,q=L;p=L-next;while(P!=NULL){if(p-data==X){q-next=p-next;free(p);p=q-next;}else{q=p;p=p-next;}}if(L-data==X){q=L;L=L-next;free(q);}}自我总结：3.删除不带头结点单链表L中所有值为X的结点（递归）voidDel_X(Linklist&L,ElemtypeX){LNode*p;if(L==NULL)return;if(L-data==X){P=L;L=L-next;free(p);Del_X(L,X);}else{Del_X(L-next,X);}}自我总结：4.删除带头结点单链表L中所有值为X的结点voidDel_X(Linklist&L,ElemtypeX){LNode*p=L-next,*pre=L,*q;while(P!=NULL){if(P-data==X){q=p;p=p-next;pre-next=p;free(q);}else{pre=p;p=p-next;}}}注：本算法是在无序单链表中删除满足某种条件的所有结点；如：若是要删除介于max和min之间的所有结点，只需将if语句改为if(p-datamin&&p-datamax)自我总结：5.逆转线性表（不带头）voidreverse(Linklist&L){Linklistp,q,r;p=L;q=NULL;while(p!=NULL){r=q;q=p;p=p-next;q-next=r;}L=q;}带头结点：Linklistreverse(LinklistL){LNode*pre,*p=L-next,*r=p-next;p-next=NULL;while(r!=NULL){pre=p;p=r;r=r-next;p-next=pre;}L-next=p;returnL;}自我总结：6.复制线性链表(递归)Linklistcopy(Linklistlist1){Linklistlist2;if(list1==NULL)returnNULL;else{list2=(Linklist)malloc(sizeof(LNode));list2-data=list1-data;list2-next=copy(list1-next);returnlist2;}}自我总结：7.将两个按值有序排列的非空线性表合并为一个按值有序的线性表LinklistMergelist(LinklistL1,LinklistL2){LinklistL3,p=L1,q=L2,r;if(L1-data=L2-data){L3=L1;r=L1;p=L1-next;}else{L3=L2;r=L2;q=L2-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;returnL3;}自我总结：8.将两个按值递增线性表合并为一个按值递减的线性表voidMergeList(LinkList&L1,LinkList&L2){LNode*r,*p1=L1-next;*p2=L2-next;L1-next=NULL;while(p1&&p2){if(p1-data=p2-data){r=p1-next;p1-next=L1-next;L1-next=p1;p1=r;}else{r=p2-next;p2-next=L1-next;L1-next=p2;p2=r;}if(p1){p2=p1;}while(p2){r=p2-next;p2-next=L1-next;L1-next=p2;p2=r;}free(L2);}}自我总结：树1.先序遍历（递归）voidPreOrder(BiTreeT){if(T!=NULL){visit(T);PreOrder(T-lchild);PreOrder(T-rchild);}}先序遍历（非递归）voidPreOrder(BiTreeT){InitStack(S);BiTreep=T;while(p!=NULL||!IsEmpty(S)){while(p!=NULL){visit(p);Push(S,p);p=p-rchild;}Pop(S,p);p=p-rchild;}}自我总结：2.中序遍历（递归）voidInOrder(BiTreeT){if(T!=NULL){InOrder(T-lchild);Visit(T);InOrder(T-rchild);}}中序遍历（非递归）voidInOrder(BiTreeT){InitStack(S);BiTreep=T;while(p||！IsEmpty(S)){if(p){Push(S,p);p=p-lchild;}else{Pop(S,p);Visit(p);p=p-rchild;}}}自我总结：3.后序遍历（递归）voidPostOrder(BiTreeT){if(T!=NULL){PostOrder(T-lchild);PostOrder(T-rchild);Visit(T);}}后序遍历（非递归）voidPostOrder(BiTreeT){InitStack(S);BiTreep=T;r=NULL;while(p||!IsEmpty(S)){if(p){Push(S,p);p=p-lchild;}else{GetTop(S,p);if(p-rchild&&p-rchild!=r){p=p-rchild;Push(S,p);p=p-lchild;}else{Pop(S,p);Visit(p);r=p;p=NULL;}}}}自我总结：4.层序遍历（自上而下，自左至右）voidLevelOrder(BiTreeT){InitQueue(Q);BiTreep;EnQueue(Q,T);while(!IsEmpty(Q)){DeQueue(Q,p);Visit(p);if(p-lchild!=NULL)EnQueue(Q,p-lchild);if(p-rchild!=NULL)EnQueue(Q,p-rchild);}}自我总结：5.层序遍历（自下而上，自右至左）voidInvertLevel(BiTreebt){StackS;QueueQ;if(bt!=NULL){InitStack(S);InitQueue(Q);EnQueue(Q,bt);while(IsEmpty(Q)==false){DeQueue(Q,p);Push(S,p);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);}while(IsEmpty(S)==false){Pop(S,p);visit(p-data);}}}自我总结：6.求二叉树深度（高度）（递归）intBtdepth(BiTreeT){if(T==NULL)return0;Ldep=Btdepth(T-lchild);rdep=Btdepth(T-rchild);if(ldeprdep)returnldep+1；elsereturnrdep+1;}注：求某一层结点个数，每一层结点个数，树的最大宽度等，都采用此思想自我总结：求二叉树深度（非递归）intBtdepth(BiTreeT){if(!T)return0;intfront=-1,rear=-1;intlast=0,level=0;BiTreeQ[MaxSize];Q[++rear]=T；BiTreep;while(frontrear){p=Q[++front];if(p-lchild)Q[++rear]=p-lchild;if(p-rchild)Q[++rear]=p-rchild;if(front==last){level++;last=rear;}}returnlevel;}自我总结：7.交换二叉树中所有结点的左右子树位置（递归）voidswap(BiTreeb){if(b){swap(b-lchild);swap(b-rchild);temp=b-lchild;b-lchild=b-rchild;b-rchild=temp;}}非递归#defineMAX_QUEUE50voidswap(BiTreeT){BiTreeQUEUE[MAX_QUEUE]，temp,p=T;intfront,rear;if(T!=NULL){QUEUE[0]=T;front=-1;rear=0;while(frontrear){p=QUEUE[++front];temp=p-lchild;p-lchild=p-rchild;p-rchild=temp;if(p-lchild!=NULL)QUEUE[++rear]=p-lchild;if(p-rchild!=NULL)QUEUE[++rear]=p-rchild;}}}自我总结：8.删除二叉树中以某个结点为根结点的子树voidDeleteXTree(BiTreebt){if(bt){DeleteXTree(bt-lchild);DeleteXTree(bt-rchild);free(bt);}}voidSearch(BiTreebt,ElemTypeX){if(bt){if(bt-data==X){DeleteXTree(bt);exit(0);}initQueue(Q);EnQueue(Q,bt);while(!IsEmpty(Q)){DeQueue(Q,p);if(p-lchild)if(p-lchild-data==X){DeleteXTree(p-lchild);p-lchild=NULL;}elseEnQueue(Q,p-lchild);if(p-rchild)if(p-rchild-data==X){DeleteXTree(p-rchild);p-rchild=NULL;}elseEnQueue(Q,p-rchild);}}}自我总结：9.建立二叉树（从键盘输入数据，先序遍历递归算法）BiTreeCreate(){charch;BiTreeT;scanf(%c,&ch);if(ch=='')returnNULL;else{T=(BiTree)malloc(sizeof(BTNode));T-data=ch;T-lchild=Create();T-rchild=Create();returnT;}}自我总结：10.建立二叉树（从数组获取数据）BitreeCreateBT(intA[],inti,intn){BiTreep;if(in)returnNULL;else{p=(BiTree)malloc(sizeof(BTNode));p-data=A[i