数据结构算法汇总、.doc

数据试验算法汇总第2章 线性表第3章 顺序表的操作Status InitList(SqList &L) /*构造一个空的顺序表 要求程序运行时通过屏幕提示用户输入5个数据:3,7,11,10,2，建立相应的顺序表，并输出给用户确认。*/int i;L.elem = (ElemType*)malloc( LIST_INIT_SIZE * sizeof(ElemType) );L.listsize = LIST_INIT_SIZE;L.length = 5;printf(请输入5个数据：n);for ( i = 0; i L.length; +i )scanf( %d, &L.elemi );printf(你输入的数据为：);for ( i = 0; i L.length; +i )printf( %d , L.elemi );printf(n);return OK;Status Create(SqList &L,int n)/建立顺序表，并输出到屏幕验证int i;for(i=1;i=n;i+)printf(请输入第%d个值:,i);scanf(%d,L.elem+i-1);for(i=1;i=L.length;i+)printf(%d,*(L.elem+i-1);return OK;1、 顺序表的建立（从键盘或者数组中导入数据）Status InitList(SqList &L) /创建一个顺序表 int i,n; printf(请输入表元素的个数：); scanf(%d,&n); L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); for(i=0;in;i+) scanf(%d,L.elem+i); L.length=n; L.listsize=LIST_INIT_SIZE; return OK; 2、 顺序表按照值查找位置int LocateElem(SqList L, ElemType e) /根据数据元素的值，返回它在线性表L中的位置 int i; for(i=0;iL.length;i+) if(*(L.elem+i)=e) return i+1; return -1; 3、 顺序表按照序号查找元素的值Status GetElem(SqList L,int i,ElemType &e) /根据数据元素在线性表L中的位置，返回它的值e=*(L.elem+i-1);return OK; 4、 顺序表数据元素的插入Status ListInsert(SqList &L,int i,ElemType e) / 在L中第i个位置之前插入新的数据元素e，L的长度加1 ElemType *newbase; int j; if(iL.length+1) return ERROR; if(L.length=L.listsize) newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTNCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTNCREMENT; for(j=L.length;j=i;j-) *(L.elem+j)=*(L.elem+j-1); *(L.elem+j)=e; L.length+; return OK; 5、 顺序表数据元素的删除Status ListDelete(SqList &L,int i,ElemType &e) /删除L的第i个数据元素，并用e返回其值，L的长度减1int j; if(iL.length) return ERROR;e=*(L.elem+i-1);for(j=i;jL.length;j+) *(L.elem+j-1)=*(L.elem+j);L.length-; return OK; 6、 顺序表数据元素的输出 Status visit(SqList L) /按序输出顺序表的各个元素值 int i; for(i=0;inext=NULL;for(i=1;idata);p-next=L-next;L-next=p; void CreateList2(LinkList &L,int n) / 正位序输入n个元素的值，建立带表头结构的单链线性表LLinkList p,r;int i;L=(LinkList)malloc(sizeof(LNode);if(!L) exit(OVERFLOW);L-next=NULL;r=L;for(i=1;idata);r-next=p;p-next=NULL;r=p; 2、 单链表的输出Status visit(LinkList L) /按序输出单链表的各个元素值LinkList p=L-next;while(p)printf(%dt,p-data);p=p-next;return OK; 3、 单链表结点的插入Status ListInsert(LinkList L,int i,ElemType e)/在带头节点的单链表L中第i个位置之前插入元素eint j=0;LinkList p=L,q;while(p&jnext;j+;if(!p|ji-1)return ERROR;q=(LinkList)malloc(sizeof(LNode);if(!q) exit(OVERFLOW);q-data=e;q-next=p-next;p-next=q;return OK; 4、 单链表结点的删除Status ListDelete(LinkList L,int i,ElemType& e)/在带头节点的单链表L中，删除第i个元素，并由e返回其值int j=0;LinkList p=L,q;while(p&jnext;j+;if(!p|ji-1)return ERROR;q=p-next;e=q-data;p-next=q-next; free(q);return OK;5、单链表中按照结点的值查找结点的位序 int LocateElem(LinkList L,ElemType e) / 返回L中第1个值为e 的数据元素的位序，若这样的数据元素不存在,则返回值为0 int i=0; LinkList p; p=L-next; while(p) i+;if(p-data=e) return i;p=p-next; return 0; 6、 单链表中按照结点的位序返回结点的值Status GetElem(LinkList L,int i,ElemType &e) / L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则回 ERRORint j=1;LinkList p;p=L-next;while(p&jnext;j+;if(!p|ji) return ERROR;e=p-data;return OK; 7、 单链表的初始化（新建一个只含头结点的单链表）Status InitList(LinkList &L) / 构造一个空的单链表LL=(LinkList)malloc(sizeof(LNode);if(!L) exit(OVERFLOW);L-next=NULL;return OK; 8、 单链表的销毁（所有结点都要销毁）Status DestroyList(LinkList L) / 销毁单链表L LinkList p;while(L-next)p=L-next;L-next=p-next;free(p);return OK; 9、 求单链表的长度int ListLength(LinkList L) / 返回L中数据元素个数int i=0;LinkList p;p=L-next;while(p)i+;p=p-next;return i; 10、两个单链表的归并void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) /已知线性表La和Lb中的数据元素按值非递减排列 /归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列LinkList pa=La-next,pb=Lb-next,pc;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa; pc=pa; pa=pa-next; elsepc-next=pb; pc=pb; pb=pb-next;if(pa) pc-next=pa;if(pb) pc-next=pb; free(Lb);第三章 栈和队列栈的操作（顺序栈）1、 初始化一个顺序栈Status InitStack(SqStack &S) /栈的初始化S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;2、 建立一个栈（从键盘或者数组中导入数据）Status CreatStack(SqStack &S) /栈的创建int n;printf(请输入元素个数：);scanf(%d,&n);S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;printf(请输入元素值：);while(S.top-S.base)=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType); if(!S.base) exit(ERROR);S.top=S.base+S.stacksize;S.stacksize+=STACK_INCREMENT;*(S.top+)=e;return OK;6、 元素出栈Status Pop(SqStack &S,SElemType &e) / 在教科书第47页 / 若栈S不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base)return ERROR;e=*(-S.top);return OK; 7、 计算栈中数据元素的个数int StackLength(SqStack S) / 返回栈S的元素个数，即栈的长度return S.top-S.base;递归1、 递归实现阶乘int f(int n) /递归求n!if(n=0)return 1;elsereturn n*f(n-1);2、 递归实现链表的输出void PrintList_L(LinkList L) /递归实现单链表的输出if(L)printf(%dt,L-data);PrintList_L(L-next);3、 递归实现链表的归并 LinkList mergeListRecur(LinkList list1,LinkList list2) /递归实现单链表的顺序归并LinkList head=NULL;if(!list1)return list2;if(!list2)return list1;if(list1-datadata)head=list1;head-next=mergeListRecur(list1-next,list2);return head;elsehead=list2;head-next=mergeListRecur(list1,list2-next);return head;4、 递归实现链表的逆序LinkList reverse(LinkList p) /递归实现单链表的逆置LinkList q,h;if(!p-next)return p;elseq=p-next;h=reverse(q-next);q-next=p-next;p-next=NULL;return h;5、 递归求链表的长度int ListLength(LinkList L) /递归求单链表的长度if(!L) return 0;elsereturn 1+ListLength(L-next);队列1、 循环队列的初始化Status InitQueue(SqQueue &Q) / 构造一个空队列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base) exit(OVERFLOW);Q.front=Q.rear=0;return OK;2、 循环队列的数据元素进队Status EnQueue(SqQueue &Q,QElemType e) / 插入元素e为队列Q的新的队尾元素。if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;3、 循环队列的数据元素出队Status DeQueue(SqQueue &Q,QElemType &e) / 若队列Q不空，删除Q的队头元素，用e返回其值,并返回OK，否则返回ERROR;if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;4、 循环队列的求长度int QueueLength(SqQueue Q) / 求队列Q的元素个数bbreturn (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;5、 循环队列的判空Status QueueEmpty(SqQueue Q) /若队列Q为空队列，则返回TRUE，否则返回FALSEif(Q.front=Q.rear)return TRUE;elsereturn FALSE;第六章 树和二叉树二叉树的操作（采用二叉链式存储）1、 二叉树的建立Status CreateBiTree(BiTree &T) / 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)TElemType ch;scanf(%c,&ch);if(ch= ) T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);if(!T) exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild); return OK;2、 二叉树的遍历（四种）Status PreOrderTraverse(BiTree T,void(*Visit)(TElemType) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1/ 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) Visit(T-data); PreOrderTraverse(T-lchild,Visit); PreOrderTraverse(T-rchild,Visit); return OK;Status InOrderTraverse(BiTree T,void(*Visit)(TElemType) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数/ 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) InOrderTraverse(T-lchild,Visit); Visit(T-data); InOrderTraverse(T-rchild,Visit); return OK;Status PostOrderTraverse(BiTree T,void(*Visit)(TElemType) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数/ 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) PostOrderTraverse(T-lchild,Visit); PostOrderTraverse(T-rchild,Visit); Visit(T-data); return OK;Status LevelOrderTraverse(BiTree T,void(*Visit)(TElemType) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数/ 操作结果：层序递归遍历T(利用队列)，对每个结点调用函数Visit一次且仅一次 LinkQueue q; QElemType a; if(T) InitQueue(q); EnQueue(q,T); while(!QueueEmpty(q) DeQueue(q,a); Visit(a-data); if(a-lchild) EnQueue(q,a-lchild); if(a-rchild) EnQueue(q,a-rchild); return OK;3、 二叉树的输出Status PrintTree(BiTree bt,int nLayer) /* 按竖向树状打印的二叉树 */ int i;if(bt)PrintTree(bt-lchild,nLayer+1);for(i=0;idata);PrintTree(bt-rchild,nLayer+1);return OK;4、 求二叉树高度int BiTreeDepth(BiTree T) /求二叉树高度int i,j,depth;if(!T)depth=0;elsei=BiTreeDepth(T-lchild);j=BiTreeDepth(T-rchild);depth=1+(ij?i:j);return depth;5、 交换二叉树的左右子树void exchg_tree(BiTree T) /交换二叉树的左右子树BiTree q;if(T)q=T-rchild;T-rchild=T-lchild;T-lchild=q; exchg_tree(T-lchild);exchg_tree(T-rchild);6、 求二叉树中某数元素所在的层数int TreeLevel(BiTree T,TElemType e) /求二叉树中某数元素所在的层数int i,j,level;if(T) if(T-data=e) return 1;i=TreeLevel(T-lchild,e);j=TreeLevel(T-rchild,e);level=ij?i:j;if(level!=0)level+;return level;return 0;7、 求二叉树的结点个数void CountNode(BiTree T,int &count) /求二叉树的结点个数if(T)count+;CountNode(T-lchild,count);CountNode(T-rchild,count);8、 求二叉树的叶子数void CountLeaf(BiTree T,int &count) /求二叉树的叶子数if(T)if(T-lchild=NULL&T-rchild=NULL)count+; CountLeaf(T-lchild,count); CountLeaf(T-rchild,count);int LeafCount(BiTree T)/统计树中树叶的个数if ( !T )return 0;else if ( T-lchild = NULL & T-rchild = NULL )return 1;elsereturn LeafCount( T-lchild ) + LeafCount( T-rchild );9、 根据二叉树中数据元素的值返回指向该结点的指针10、根据二叉树中数据元素的值返回指向该结点兄弟的指针11、销毁二叉树 Status DestroyBiTree(BiTree &T) / 初始条件：二叉树T存在。操作结果：销毁二叉树T if(T) DestroyBiTree(T-lchild); DestroyBiTree(T-rchild); free(T); T=NULL; return OK; 树的操作（采用左孩子右兄弟存储结构）1、 创建树void CreateTree(CSTree &T) / 构造树Tchar c20; / 临时存放孩子结点(设不超过20个)的值CSTree p,p1;LinkQueue q;int i,m;InitQueue(q); / 初始化队列qprintf(请输入根结点(字符型，空格为空)：);scanf(%c%*c,&c0); / 输入根结点的值if(c0!= ) / 非空树T=(CSTree)malloc(sizeof(CSNode); / 建立根结点T-data=c0; / 给根结点赋值T-nextsibling=NULL; / 根结点没有下一个兄弟EnQueue(q,T); / 入队根结点的指针while(!QueueEmpty(q) / 队不空DeQueue(q,p); / 出队一个结点的指针printf(请按长幼顺序输入结点%c的所有孩子：,p-data);gets(c); / 将结点的所有孩子作为字符串输入m=strlen(c);if(m0) / 有孩子p1=p-firstchild=(CSTree)malloc(sizeof(CSNode); / 建立长子结点p1-data=c0; / 给长子结点赋值EnQueue(q,p1); / 入队p1结点的指针for(i=1;inextsibling=(CSTree)malloc(sizeof(CSNode);/建立下一个兄弟结点p1=p1-nextsibling; / p1指向下一个兄弟结点p1-data=ci; / 给p1所指结点赋值EnQueue(q,p1); / 入队p1结点的指针p1-nextsibling=NULL; / 最后一个结点没有下一个兄弟else / 无孩子p-firstchild=NULL; / 长子指针为空elseT=NULL; / 空树2、 求树的深度int TreeDepth(CSTree T) / 初始条件：树T存在。操作结果：返回T的深度 CSTree p=T-firstchild;int depth,max=0;if(!T) return 0;if(!p) return 1;for(;p;p=p-nextsibling)depth=TreeDepth(p);if(depthmax) max=depth;return max+1;3、 求树中给定结点的右兄弟TElemType RightSibling(CSTree T,TElemType cur_e) / 初始条件：树T存在，cur_e是T中某个结点/ 操作结果：若cur_e有右兄弟，则返回它的右兄弟；否则返回“空” CSTree f,p; f=Point(T,cur_e); p=f-nextsibling; if(f&p) for(;p;p=p-nextsibling) return p-data; else return NULL;4、 树的先根、后根遍历void PreOrderTraverse(CSTree T,void(*visit)(TElemType)/先根遍历CSTree p;if(T) visit(T-