数据结构开卷一纸小抄

绪论(【数据】【数据对象】【数据元素】【数据项】)数据：对客观事物的符号表示；所有能输入到计算机中，并被计算机程序处理的符号总称。数据元素：数据的基本单位。（可由若干个数据项组成）数据对象：性质相同的数据元素的集合，数据的一个子集。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。（无操作）抽象数据类型：指一个数学模型以及定义在该模型上的一组操作。（有操作）顺序存储结构——相对位置;链式存储结构——借助指针算法五特性：有穷、确定、可行、输入、输出。时间复杂度：问题随着规模N的增大，算法执行时间的增长率；常见O(n)、O(nlogn)、O(n^2)空间复杂度：算法所需存储空间的量度。（原地工作——常数）线性表线性表：n个数据元素的有限序列。顺序存储：逻辑结构与物理结构一致；缺点：插入、删除元素需要移动，平均约一半的元素。属于随机存取方式。链式存储：逻辑结构与物理结构不一致；属于顺序存储方式。顺序表：线性表采用顺序存储结构表示。有序表：内容按从小到大排列的线性表。线性链表：单向、双向、循环（不特殊说明，均带头结点）StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在L的第i个元素之前插入一个新结点eif(i1||iL.Length+1)returnERROR;if(L.length=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}//ListInsert_SqADTList{InitList(&L)//构造空线性表LDestroyList(&L)//销毁线性表LClearList(&L)//将L重置为空表ListEmpty(L)//判断L是否为空表，返回TRUE/FALSEListLength(L)//返回L中数据元素个数GetElem(L,i,&e)//用e返回L中第i个数据元素的值LocateElem(L,e,compare())//返回L中第1个与e满足compare函数关系的元素位序PriorElem/NextElem(L,cur_e,&pre_e/&next_e)//返回L中e的前驱/后继ListInsert(&L,i,e)//在L中第i个位置前插入元素e，表长+1ListDelete(&L,i,&e)//删除L中第i个数据元素，并用e返回其值，表长-1ListTraverse(L,visit())//遍历L的每个元素，并对其调用visit函数}//——线性表的动态分配顺序存储结构——typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的储存容量}SqList;//——线性表的线性链表存储结构——typedefstruct{ElemTypedata;structLNode*next;}LNode,*LinkList;StatusCreateList_L(LinkList&L,intn){//逆序创建链表L=(LNode*)malloc(sizeof(LNode));if(!L)returnERROR;L-next=NULL;//创建头结点for(i=n;i0;i--){cindata;//输入元素信息p=(LNode*)malloc(sizeof(LNode));if(!p)returnERROR;p-data=data;//创建结点p-next=L-next;L-next=p;//将新结点插入到首端}returnOK;}StatusCreate_L(LinkList&L,intn){//正序创建链表L=(LNode*)malloc(sizeof(LNode));if(!L)returnERROR;//创建头结点last=L;//设置last指针for(inti=1;i=n;i++){cindata;//输入元素信息p=(LNode*)malloc(sizeof(LNode));if(!p)returnERROR;p-data=data;//创建结点last-next=p;last=p;//将新结点插到链表尾端}last-next=NULL;returnOK;}删除结点一定要释放空间！第3章栈和队列栈：限定仅在表尾进行插入或删除操作的线性表。后进先出（LIFO)队列：在一端进行插入，另一端删除元素。先进先出（FIFO）//——带头节点的线性链表类型——typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//链表类型Linkhead,tail;//指向头/尾结点intlen;//数据元素的个数}LinkList;StatusListDelete_L(LinkLIst&L,inti,ElemType&e){//删除带头结点的单链表L中第i个结点，并由e返回其值p=L;j=0;while(p-next&&ji-1){p=p-next;j++;}//查找第i-1个结点，并由p指向if(!(p-next)||ji-1)returnERROR;//删除位置不合理q=p-next;e=q-data;//删除结点，并将其值赋给ep-next=q-next;//修改前驱指针freeq;//释放结点returnOK;}//——栈的顺序存储表示——typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈的大小}SqStack;//构造前和销毁后，base=NULLADTSqStack{InitStack(&S)//构造空栈SDestroyStack(&S)//销毁栈SClearStack(&S)//将S置为空栈StcakEmpty(S)//判断S是否为空栈，返回TRUE/FALSEStackLength(S)//返回S中数据元素个数GetTop(S,SELemType&e)//用e返回S的栈顶元素（并返回OK）Push(&S,SElemTypee)//插入元素e为新的栈顶元素Pop(&S,SElemType&e)//删除S的栈顶元素，用e返回其值（并返回OK）StackTraverse(S,Status(*Visit)())//从栈底调用Visit函数遍历至栈顶//——队列的顺序存储结构——【循环队列】typedefstruct{QElemType*base;intfront;//头指针intrear;//尾指针}SqStack;//——队列的链式存储结构——【单链队列】typedefstructQNode{//结点类型QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{//队列类型QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;//若队列不空：//头指针指向队列头元素；//尾指针指向队尾元素的下一个位置。ADTLinkQueue{InitQueue(&Q)//构造空队列QDestroyQueue(&Q)//销毁队列QClearQueue(&Q)//将Q置为空队列QueueEmpty(Q)//判断Q是否为空队列，返回TRUE/FALSEQueueLength(Q)//返回Q中数据元素个数GetHead(Q,QELemType&e)//用e返回Q的队头元素（并返回OK）EnQueue(&Q,QElemTypee)//插入元素e为新的队尾元素DeQueue(&Q,QElemType&e)//删除Q的队头元素，用e返回其值（并返回OK）QueueTraverse(Q,Status(*Visit)())//从队头调用Visit函数遍历至队尾第6章树与二叉树树：以分支关系定义的层次结构。森林：m(m=0)棵互不相交的树的集合。二叉树：每个结点之多只有两棵子树，并且有左右之分。完全二叉树：若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。二叉树五性质：1.第i层上之多有2^(i-1)个结点(i=1)2.深度为k的二叉树至多有2^k-1个结点(k=1)3.对于任意一棵二叉树，如果终端节点数为n0，度为2的节点数为n2，则n0=n2+14.具有n个结点的完全二叉树的深度为下取整(log2n)+15.对n个结点的完全二叉树，按层从上到下，每层从左到右(1)第i个结点的双亲是下取整(i/2)(2)如果2in，则是叶子结点，否则左孩子是2i(3)如果2i+1n，则结点i无右孩子，否则右孩子是2i+1WLP最小的二叉树称为最优二叉树（赫夫曼树）赫夫曼树特点：1.每个结点的度不是0，就是2；2.如果有n个权值，赫夫曼树就有2n-1个结点；其中n个叶子结点；n-1个度为2的结点。3.构造赫夫曼树就是构造n-1个度为2的结点过程。Root(T)//返回T的根BiTreeEmpty（T）//判断T是否为空树，返回TRUE/FALSECreateBiTree(&T,definition)//按definition构造二叉树TValue(T,e)//返回e的值Assign(T,&e,value)//结点e赋值为ValueParent(T,e)//返回e的双亲节点，无则返回NULLLeftChild/RightChild(T,e)//返回e的左/右孩子，无则返回NULLLeftSibling/RightSibling(T,e)//返回e的左/右兄弟，无则返回NULLInsertChild(T,p,LR,c)//根据LR的0/1值，插入c为T中p结点的左/右子树，原有结点成为c的右子树DeleteChild(T,p,LR)//根据LR的0/1值，删除T中p结点的左/右子树PreOrderTraverse(T,Visit())//先序遍历T，依次对每个结点调用Visit函数InOrderTraverse(T,Visit())//中序遍历T，依次对每个结点调用Visit函数PostOrderTraverse(T,Visit())//后序遍历T，依次对每个结点调用Visit函数LevelOrderTraverse(T,Visit())//层序遍历T，依次对每个结点调用Visit函数ADTBiTree{InitBiTree(&T)//构造空二叉树TDestroyBiTree(&T)//销毁二叉树TClearBiTree(&T)//将T置为空二叉树BiTreeDepth(T)//返回T的深度StatusCreateBiTree(BiTree&T){//先序构造二叉树scanf(&ch);if(ch==‘‘)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BitNode))))exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}returnOK;}Statushiberarchy(BiTreeT){//层序遍历二叉树if(!T)returnOK;InitQueue(Q);visit(T-data);EnQueue(Q,T);//一定要结点入队while(!QueueEmpty(Q)){/