线性表线性表的顺序表示静态分配#defineMaxSize10//定义最大长度typedefstruct{intdata[MaxSize];//ElemType=int,*使用静态“数组”来存储和访问数据元素intlength;//序列表的当前长度}SqList;动态分配#defineInitSize10//序列表的初始长度typedefstruct{int*data;//ElemType=int,*声明指向动态分配数组的指针intMaxSize;//序列表的最大容量intlength;//序列表的当前长度}SqList;//初始化序列表voidInitList(SqList&L){//使用malloc函数申请一个连续的存储空间L.data=(int*)malloc(InitSize*大小（整数））；L.length=0;L.MaxSize=InitSize;}特点：随机存取，查找元素所需的时间复杂度为O(1)。存储密度高，每个节点只存储数据元素。扩容不方便（即使通过动态分配实现，扩长的时间复杂度也比较高，因为需要将数据复制到新的区域）。插入删除操作不方便，需要移动大量元素：O(n)。线性表的链表表示单链表structLNode{//定义单链表节点类型LNode:nodeElemTypedata;//每个节点存储一个数据元素data:datafieldstructLNode*next;//指针指向下一个Nodenext:指针字段};双链表typedefstructDNode{//定义双链表节点类型ElemTypedata;//数据字段structDNode*prior,*next;//前驱和后继指针}DNode,*DLinklist;Loop单链表最后一个节点的指针不为NULL，而是指向头节点。循环双链表头节点的prior指向尾节点，尾节点的next指向头节点。静态链表#defineMaxSize10//静态链表的最大长度typedefstruct{//定义静态链表结构类型ELemTypedata;//存储数据元素intnext;//下一个元素的数组下标}SLinkList[MaxSize];voidtestSLinkList(){SLinkLista;}栈（stack）栈是一种特殊的线性表：它只允许在一端插入或删除，其逻辑结构与普通线性表相同。Bottom：不允许插入和删除的一端（栈底元素为栈底元素）Emptystack：没有任何元素的空表特点：后进先出（入栈的元素先出来栈的）缺点：栈的大小是不可变的，解决方法——共享栈的顺序存储#defineMaxSize10//定义栈中元素的最大个数typedefstruct{ElemTypedata[MaxSize];//静态数组存储栈中的元素inttop;//栈顶元素}SqStack;voidtestStack(){SqStackS;//声明一个顺序堆栈（分配空间）//连续存储空间的大小是MaxSize*sizeof(ElemType)}栈的链式存储结构。因此，链式栈实际上是一个只能通过头部插值来插入或删除数据的链表typedefstructLinknode{ElemTypedata;//数据字段结构Linknode*next;//指针字段}*LiStack;//栈类型定义应用栈括号匹配中的应用中缀表达式（需要分隔符）后缀表达式（反波兰表达式）栈应用递归中的队列（Queue）队列是一个有限操作的线性表。它只允许在一端插入（入队）和在另一端删除（退出）。操作特点：先进先出FIFO队列头：允许删除的队列一端：允许插入空队列一端：没有任何元素的空表#defineMaxSize10;//定义队列中元素的最大数量typedefstruct{ElemTypedata[MaxSize];//使用静态数组存储队列元素//连续的存储空间，大小为——MaxSize*sizeof(ElemType)intfront,rear;//队列头指针和队列尾指针}SqQueue;队头指针：指向队头元素；队列尾指针：指向队列尾元素的下一个位置（下一个应该插入的位置）循环队列（判断满）方案一：牺牲一个单元来区分空满尾指针的下一个位置是队头，即(Q.rear+1)%MaxSize==Q.frontCircularQueue——入队：只能从队尾插入（满句时使用方案1）boolEnQueue(SqQueue&Q,ElemTypex){if((Q.rear+1)%MaxSize==Q.front)//队列已满returnfalse;Q.data[Q.rear]=x;//将x插入队列尾部Q.rear=(Q.rear+1)%MaxSize;//尾指针加1取modreturntrue;}循环队列-出队：只能出队在队头的元素Team//Dequeue，删除一个队头元素，用x返回boolDeQueue(SqQueue&Q,ElemType&x){if(Q.rear==Q.front)//空队返回false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;//队列头指针后移动returntrue;}循环队列-获取队列头元素boolGetHead(SqQueue&Q,ElemType&x){if(Q.rear==Q.front)//队空报错returnfalse;x=Q.data[Q.front];returntrue;}方案二：在不牺牲存储空间的情况下，设置size为记录队列定义一个变量size此时记录了几个数据元素，初始化size=0，入队成功size++，出队成功size--，根据size的值判断队伍是满还是空。=0方案三：在不牺牲存储空间的情况下，设置tag定义一个变量tag，tag=0--最近的操作是删除操作；tag=1--最近的操作是插入操作；每次删除操作成功，设置tag=0；只有删除操作可能导致团队为空；每次插入操作成功，设置tag=1；只有插入操作可能导致团队满员；队满条件：Q.front==Q.rear&&tag==1队空条件：Q.front==Q.rear&&tag==0队列链存储结构typedefstructLinkNode{//链队列节点ElemType数据;structLinkNode*next;}typedefstruct{//链式队列LinkNode*front,*rear;//队列头尾指针}LinkQueue;双端队列双端队列允许从线性表的两端进行插入和删除；如果只使用其中一个一端的插入和删除操作相当于一个栈；input-restricteddouble-endedqueue：允许一端插入，两端允许删除的线性表；output-restricteddouble-endedqueue：允许两端插入，一端删除的线性表；字符串序列表#defineMAXLEN255//预定义的最大字符串长度为255typedefstruct{charch[MAXLEN];//静态数组实现（定长顺序存储）//每个分量存储一个字符//每个char字符占用1Bint长度；//字符串的实际长度}SString;堆分配//动态数组实现typedefstruct{char*ch;//根据字符串长度分配存储区，ch指向字符串intlength的基地址；//字符串的长度}HString;HStringS;S.ch=(char*)malloc(MAXLINE*sizeof(char));//基址指针指向连续空间的起始位置//malloc()需要手动free()S.length;链式存储typedefstructStringNode{charch;//每个节点存储1个字符structStringNode*next;}StringNode,*String;树序存储#defineMaxSize100structTreeNode{ElemTypevalue;//节点元素中的数据boolisEmpty;//节点是否为空}链式存储//二叉树节点structElemType{intvalue;};typedefstructBiTnode{ElemTypedata;//数据字段structBiTNode*lchild,*rchild;//左右子指针}BiTNode,*BiTree;计算机科学中的树二叉树二叉树二叉搜索树笛卡尔树顶层树T树笛卡尔树范围最值查询和最低公共祖先（距离两个节点最近的公共祖先）自平衡二叉搜索树AA树AVL树红黑树拉伸树树栈节点大小平衡树AVL树它本质上是一个二叉搜索树，其特点是：1.首先是一棵二叉查找树2.具有平衡条件：每个节点的左右子树的高度之差（平衡因子）的绝对值至多为1.在也就是说，AVL树本质上是一种具有平衡功能的二叉搜索树（binarysortingtree，二叉搜索树）。红黑树是一种专门的AVL树，可以在O(logn)时间内进行查找、插入和删除。除了二叉搜索树强加的一般要求外，我们将以下内容添加到任何有效的红黑树中附加要求：属性1.节点为红色或黑色。性质2.根节点是黑色的。性质3.所有的叶子都是黑色的。（叶子是NIL节点）性质4.每个红色节点的两个子节点都是黑色的。（从每个叶子到根的所有路径上不能有两个连续的红色节点）性质5.从任何节点到每个叶子的所有路径都包含相同数量的黑色节点。这些约束强化了红黑树的一个关键属性：从根到叶子的最长可能路径不超过最短可能路径的两倍。结果是树大致平衡。因为对一个值的插入、删除、查找等操作的最坏情况时间要求与树的高度成正比。这个理论上的高度上限允许红黑树在最坏的情况下仍然有效，这与普通的二叉搜索树不同。B树?B树?B+树?B*树?Bx树?UB树?2-3树?2-3-4树?(a,b)-tree-tree&pic=1&sug=1&enc=utf8)Dancingtree?H树B树(B-)和B树的查询时间复杂度不是固定的，跟key在树中的位置有关，最好是O(1)。B-tree，其中B的意思是balance（平衡的意思），B-tree是一种多路自平衡搜索树B-tree具有以下特点：所有key值分布在整棵树中（索引值和特定数据在每个节点中）；任一关键字出现且仅出现在一个节点中；搜索可能以非叶节点结束（最佳情况O(1)可以找到数据）；在关键字集合中做一次搜索，性能接近二分查找；B树是专门为磁盘等外部存储而设计的，对大块数据的读写有很好的性能，所以一般用在文件系统和数据库中。B+树的时间复杂度固定为lognTrie?Prefixtree?Suffixtree?RadixtreeSpacedivisiontree?Quadtree?Octree?vp-tree?Rtree?R*tree?R+tree?Xtree?Mtree?Segment树?HilbertR树?优先级R树算法冒泡排序多次遍历一个列表。需要比较相邻的两个项目，交换顺序选择排序每次遍历链表只交换一次数据，将其更改到正确的位置。排列n条数据总共需要n-1次遍历。插入排序每一个新的数据项插入到前面的子表中希尔排序缩小区间排序是在插入排序的基础上，将待排序的列表划分为一些子列表，然后对每个子列表进行插入排序。合并排序将两个排序列表组合成一个排序的新列表。合并排序是一种递归算法，它连续地将列表分成两半。如果列表为空或只有一个元素，那么根据定义，它是排序的（最基本的情况），如果列表有多个元素，我们拆分列表并分别对两个部分调用递归排序。
