数据结构(C语言版)_知识点串联

第一章绪论逻辑结构：线性结构（2线性表；3栈和队列；4数组和广义表；5串）和非线性（6树；7图）8查找；9排序存储结构：顺序存储、链式存储、索引存储、散列存储顺序存储和链式存储的优缺点：顺序存储优点：存取方式是随机的，读取数据比较方便缺点：插入和删除操作需要移动大量的数据链式存储方式的优缺点与顺序相反。判断算法好坏的标准：时间复杂度和空间复杂度第二章线性表线性表：由n（n=0）个相同数据类型的元素组成的有限序列。逻辑特征：（1：1）第一个结点是开始结点，无前驱有唯一的后继最后一个结点是终端节点，无后继有唯一的前驱中间结点，有唯一前驱和唯一的后继逻辑结构的定义方式：（元素1，元素2，。。。）存储结构：（物理结构）顺序存储(用数组体现)：预先分配一段连续的区域，静态分配inta[10];a表示a[0]的地址顺序表：两层含义：逻辑结构上线性结构物理上顺序存储链式存储（用指针）：占用的区域不一定连续，动态分配；mallocfree链表：两层含义：逻辑结构上线性结构物理上链式存储顺序表的插入：maxsize表示最多存放的元素的个数，size表示有效元素的个数1、判断满不满：满的条件：size==maxsize2、插入的位置是不是合法（i=1&&i=size+1）3、后移（先移动后面的）4、插入size++；顺序表的删除：1、判断空间是否是空（size==0）2、判断位置是不是合法（1=i=size）3、前移（先移动前面的）4、Size--链表：分类：单链表、循环链表、双链表三个术语：头结点、头指针、开始结点插入操作：p结点的后面1、生成空间：s=(S*)malloc(sizeof(S));2、赋值：s-data=X;3、s-next=p-next;(修改新结点的指针)4、P-next=s;链表的删除：p结点的后面的结点1、q=p-next;2、p-next=q-next;//p-next=p-next-next;3、free(q);删除p结点本身：A、寻找p结点的前驱结点,转化为删除p结点的前驱结点的后继q=head;while(q-next!=p)q=q-next;q-next=p-next;free(p);B、删除p的后继（p结点不是终端结点，p一定要有后继）q=p-next;p-data=q-data;p-next=q-next;free(q);第三章栈和队列栈和队列是特殊的线性表。特殊在插入和删除操作都是在表的端点处进行。栈Stack：操作受限（插入和删除）的线性表。在线性表的末尾做插入和删除，叫做栈顶top线性表的开始部分叫做栈底bottom特点：FILO典型应用：函数的调用存储方式：顺序存储（用数组体现，静态分配存储空间）链式存储（涉及到指针，动态分配存储空间）顺序栈的插入：top表示栈顶元素的下标，定义是int类型的，格式是inttop；maxsize表示空间的大小，最多存放多少个元素(在顺序表的基础上修改的，红颜色粗体部分去掉)1、判断满不满：满的条件是top==maxsize-12、插入的位置是不是合法（i=1&&i=size+1）：去掉原因是位置固定size+13、后移（先移动后面的）：去掉4、top++；插入（data[top]=X）顺序栈的删除：(在顺序表的基础上修改的，红颜色粗体部分去掉)1、判断空间是否是空（top==-1top0）2、判断位置是不是合法（1=i=size）3、前移（先移动前面的）4、top--链栈的插入操作：top表示栈顶的指针，类似于head，top是指针变量格式：数据类型*top；1、生成空间：s=malloc（。。。。）；2、赋值：s-data=X;3、修改指针：s-next=top;(先修改的是新结点的指针)4、修改top指针：top=s；链栈的删除：1、p=top;2、top=top-next;3、free(p);进栈的顺序是123，则可能的出栈的顺序是123、132、213、231、312、321进栈的顺序是1234，则可能的出栈的顺序是1234、1243、1324、1342、1432、2134、2143、2314、2341、2431、3214、3241、3421、4321队列：1、定义：操作受限的线性表（在表的一端进行插入、在另一端进行删除）2、在线性表的末尾进行插入操作，叫做队尾rear在线性表的开始做删除操作，叫做队头front3、特点：FIFO4、存储结构：顺序存储（用数组体现，静态分配存储空间）链式存储（用指针体现，动态分配存储空间）入队列的顺序是1234，则出队的顺序是1234。循环队列：队列的顺序存储结构循环队列长度是maxsize，则最多存放maxsize-1个元素Front表示：队头元素的前一个位置Rear：队尾元素的下标循环队列空的条件是：front==rear循环队列满的条件是：front==(rear+1)%maxsize循环队列的元素的个数是：(rear-front+maxsize)%maxsize循环队列的队头元素的下标：（front+1）%maxsize备注：凡涉及到+1，都要%maxsize顺序队列的插入：(在顺序表的基础上修改的，红颜色粗体部分去掉)1、判断满不满：满的条件：front==（rear+1）%maxsize2、插入：rear=(rear+1)%maxsizedata[rear]=X;顺序队列的删除：(在顺序表的基础上修改的，红颜色粗体部分去掉)1、判断空间是否是空：空的条件是front==rear2、删除：front=(front+1)%maxsize链队列：队列的链式存储结构Front表示的队头元素的指针Rear表示队尾的指针链队列的插入操作：1、p=malloc(…);2、p-data=X;3、p-next=NULL;（先修改新产生结点的指针）4、rear-next=p;5、rear=p;链队列的删除:（带头结点的队列）一、删除真正的队头元素1、判断队列是否为空:空的条件是front==rear2、s=front-next;3、front-next=s-next;4、free(s);二、通过删除头结点转化为删除队头元素1、判断队列是否为空:空的条件是front==rear2、s=front;3、front=front-next;4、free(s);练习：(10,20,30)1、线性表，画出带头结点的单链表2、栈，分别画出顺序存储结构链式存储结构3、队列，分别画出顺序存储结构链式存储结构第四章数组和广义表数组：两种操作（查找和修改）两种存储结构：按行优先、按列优先运算：计算地址、计算按行优先时的地址按列优先时是哪个元素广义表：（不考）表头一定是原子。（×）表头一定是广义表。（×）表尾一定是原子。（×）表尾一定是广义表。（√）第五章串两个串相等的充要条件是：串长相等并且对应位置上的字符要相同。空串和空白串区别：串的运算：串的链接、求子串、求子串在主串中的位置（模式匹配）、串的比较、串的复制、串的替换等等。Inta[]=”123”;(√)Inta[10];a=”123”;(×)Charname[10]=”gmm”;For(i=0;isize;i++)If(strcmp(name,stu[i].name)==0)练习：输出所有的“水仙花数”。所谓“水仙花数”是指一个3位数，其各位数字立方和等于该数本身。例如：153是一个水仙花数，应为153=13+53+33。第六章树树：非线性结构1、定义：有n（n=0）个结点组成的有限集合。对于非空树来说：有且仅有一个根结点；子树由t1，t2.。。互斥的集合。2、术语：结点的度、树的度、树的高度、路径、路径的长度、树的路径长度、树的带权路径长度3、树的存储：双亲表示法、孩子表示法、双亲孩子表示法、孩子兄弟表示法二叉树：判断：二叉树是树；是度为2的树；是特殊的树；是度为2的有序树。（×）5个性质：性质1：二叉树第i层上最多2i-1（数学归纳法）性质2：深度为k的二叉树上最多2k-1（等比数列）性质3：二叉树上度为0的节点有n0个，度为2的节点有n2个，则n0=n2+1（N=n0+n1+n2=0*n0+1*n1+2*n2+1）满二叉树完全二叉树满二叉树一定是完全二叉树。（√）完全二叉树一定是满二叉树。（×）完全二叉树的结点如果有左孩子，则它一定有右孩子。（×）完全二叉树的结点如果有右孩子，则它一定有左孩子。（√）性质4：有n个节点的完全二叉树，深度为：。。。。。（假设深度k，2k-1-1+1≤n≤2k-1）「」性质5：把完全二叉树编码，从上到下，同一层上从左向右，I=1：是根结点，没有双亲；i1：有双亲，双亲编码是」i/2」；I:2i是左孩子，如果存在右孩子，则右孩子的编码是2i+1；I:2i+1是它的右孩子，左孩子的编码是2i。练习：1、有1001个结点的完全二叉树，树的高度为（），其中叶子结点的个数为（），度为1的结点的个数为（），度为2的结点的个数为（）。2、已知二叉树有52个叶子结点，度为1的结点个数为30则总结点个数为（）。二叉树的存储：顺序存储---完全二叉树的存储（下表为0的空间没用性质5来判断双亲和孩子的关系）链式存储（二叉链表、带双亲的二叉链表（三叉链表））-一般二叉树二叉树的遍历：先序遍历（第一个节点是根结点）、中序遍历（来判断左右子树的结点）、后序遍历（最后一个节点是根结点）根据先序和中序、中序和后序得到二叉树。练习：1、已知二叉树的中序遍历序列是ACBDGHFE，后序遍历序列是ABDCFHEG，请构造一棵二叉树。2、已知二叉树的层次遍历序列为ABCDEFGHIJK，中序序列为DBGEHJACIKF，请构造一棵二叉树。3、已知二叉树的前序、中序和后序遍历序列如下，其中有一些看不清的字母用*表示，请先填写*处的字母，再构造一棵符合条件的二叉树。(1)前序遍历序列是：*BC***G*(2)中序遍历序列是：CB*EAGH*(3)后序遍历序列是：*EDB**FA树、森林和二叉树之间的转换：树----二叉树：加线、抹线、调整（结论：转换后的二叉树没有右子树）二叉树-----树：加线、抹线、调整森林-----二叉树：二叉树-----森林：树、森林和二叉树的遍历1、树的先跟遍历次序与它所对应的二叉树的先序遍历次序相同；2、树的后跟遍历次序与它所对应的二叉树的中序遍历次序相同；3、森林的先序遍历次序与它所对应的二叉树的先序遍历次序相同；4、森林的中序遍历次序与它所对应的二叉树的中序遍历次序相同；哈弗曼树及其编码：术语：路径、路径的长度、树的路径长度（从根结点到每一个叶子结点的路径长度之和）、带权路径长度（根结点到叶子结点的路径长度*权值和）构造：每次找两个权值最小的结点进行合并，得到的新节点的权值放到最后，循环合并，直到只剩下一个结点的时候结束过程，这时候的二叉树就是所求的最优二叉树（哈夫曼树）。哈弗曼编码：左分支为0右分支为1，从根结点到叶子结点所经过的边的编码就是它所对应的哈弗曼编码。第七章图1、定义：图：Graph两个集合V(vertex)E有向图：VEV,W弧头（箭头指向谁终点）弧尾（起点）无向图：（V,W）==（W,V）2、术语：完全图（任意两个定点之间都有边无向图n*（n-1）/2有向图n*(n-1)）结点的度：与这个顶点相关联的边的条数入度：针对的有向图以这个顶点为弧头出度：针对有向图以这个顶点为弧尾边的个数：所有顶点的度的总和/2连通图：如果两个顶点之间有路径，那么这两个顶点就是连通的连通图：无向图任意两个顶点之间都有路径判断：完全图一定是连通图（√）连通图一定是完全图（×）连通分量：非连通图的极大连通子图强连通图强连通分量：有向图生成树：连通图，有n个顶点，至少需要n-1边使得它连通连通图的极小连通子图3、图的存储：（1）邻接矩阵：如果有n个顶点的无向图，存储空间压缩n*(n+