数据结构复习要点(整理版)精品
【关键字】设计、情况、方法、条件、空间、运行、问题、有效、继续、执行、保持、建立、掌握、特点、位置、关键、稳定、思想、需要、重点、需求、方式、办法、规模、结构、速度、关系、分析、满足、理顺、优先、实现
第一章数据结构概述
基本概念与术语
1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。
2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。
（补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。）
4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：
1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。
2.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。
3.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。
4.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。
（2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。
想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构：
1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。
2.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。
5.时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1)
2.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n)
3.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++
时间复杂度的大小比较：
O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 6.算法与程序： （1）算法的5个特性 1、输入：有零个或多个输入 2、输出：有一个或多个输出 3、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。（程序与算法的区别在于，程序不需要有有穷性） 4、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。没有歧义。 5、可行性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。 （2）.算法设计的要求： 1、正确性（达到预期效果，满足问题需求） 2、健壮性（能处理合法数据，也能对不合法的数据作出反应，不会产生不可预期的后果） 3、可读性（要求算法易于理解，便于分析） 4、可修改可扩展性 5、高效率（较好的时空性能） 补充内容： 1、名词解释：数据结构、二元组 数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。 二元组就是一种用来表示某个数据对象以及各个元素之间关系的有限集合。 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有两种类型，它们分别是顺序存储结构、链式存储结构 6.在一般情况下，一个算法的时间复杂度是问题规模的函数 7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log 2 n）、平方阶O(n^2)、指数阶O(2^n)。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。 第二章线性表 定义：线性表是n个数据元素的有限序列。一个数据元素可由若干个数据项组成。 1. 顺序表结构 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。 2. 单链表 （1）链表结点结构 线性表中的数据元素可以用任意的一组存储单元来存储，用指针表示逻辑关系逻辑相邻的两元素的存储空间可以是不连续的。 （2）链表操作算法：初始化、插入、输出、删除、遍历 初始化：p=(struct student *)malloc(sizeof(struct student)); 插入：p->next=head->next; head->next=p; 输出：printf(“%d”,p->data); 删除：q=p->next; p->next = q->next ; free(q); 结点遍历：for(p=head;p;p=p->next); 补充内容： 1、线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。 2、在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的操作语句为P->next = q->next ; free(q); 3、在长度为N的顺序表中，插入一个新元素平均需要移动表中N/2个元素，删除一个元素平均需要移动（N-1）/2个元素。 4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用顺序表存储结构最节省运算时间。 5、已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336，则顺序表的 首地址为300。（第n个元素的地址即首地址+(n-1)*每个元素的存储空间，如a[12]（第13个元素）的地址=a[0]+12*3） 6、设有一带头结点单链表L，请编写该单链表的初始化，插入、输出和删除函数。（函数名自定义） 结点定义： typedef int datatype; //结点数据类型，假设为int typedef struct node { //结点结构 datatype data; struct node *next; //双向链表还应加上*previous } Lnode, * pointer ; //结点类型,结点指针类型 typedef pointer lklist; //单链表类型，即头指针类型 1.初始化： lklist initlist() { pointer head; head=new node;//这是C++做法 //head=( pointer)malloc(sizeof(Lnode)); 这是C语言做法 head->next=NULL; //循环链表则是head->next=head; //双向链表应加上head->previos=NULL; return head; } 2.插入：（C语言中需要把head转化为全局变量才能实现此程序） int insert(lklist head,datatype x,int i){ pointer q,s; q=get(head,i-1); //找第i-1个点 if(q==NULL) //无第i-1点，即i<1或i>n+1时 { cout<<”非法插入位置!\n”; //这是C++做法，即C语言中的printf(“非法插入位置!\n”); return 0; } s=new node;//生成新结点即C语言中的s=( pointer)malloc(sizeof(Lnode)); s->data=x; s->next=q->next; //新点的后继是原第i个点 q->next=s; //原第i-1个点的后继是新点 return 1; //插入成功 } 3.删除：（C语言中需要把head转化为全局变量才能实现此程序） int delete(lklist head,int i) { pointer p,q; q=get(head,i-1); //找待删点的直接前趋 if(q==NULL || q->next==NULL) //即i<1或i>n时 {cout<<”非法删除位置!\n”;return 0;} p=q->next; //保存待删点地址 q->next=p->next; //修改前趋的后继指针 delete p; //释放结点即C语言中的free(p); return 1; //删除成 1. 不带头结点的单链表head为空的判定条件是(A ) A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL 2. 带头结点的单链表head为空的判定条件是(B ) A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL 3. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B ) A. s->next=p; p->next=s; B. s->next=p->next; p->next=s; C. s->next=p->next; p=s; D. p->next=s; s->next=p; 4. 在一个单链表中，若删除p所指结点的后续结点，则执行(A ) A. p->next=p->next->next; B. p=p->next; p->next=p->next->next; C. p->next=p->next D. p=p->next->next 5. 从一个具有n个结点的有序单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（B ）个结点。 A. n B. n/2 C. (n-1)/2 D. O(n㏒2n) 6. 给定有n个元素的向量，建立一个有序单链表的时间复杂度（B） A.O(1) B.O(n) C.O(n2) D.O(n㏒2n) 7.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B) A.O(1) B.O(n) C.O(n2) D.O(n㏒2n) 8. 在一个单链表中删除q所指结点时，应执行如下操作： q=p->next; p->next=( p->next->next ); free(q);//这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。 9. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行： s->next=( p->next ) p->next=(s)操作。 10. 对于一个具有n个节点的单链表,在已知所指结点后插入一个新结点的时间复杂度是(O （1）)；在给定值为x的结点后插入一个新结点的时间复杂度是（O(n)）。 11.问答题 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? 顺序表的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。 (2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？ 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。 第三章栈和队列 1. 栈 （1）栈的结构与定义 定义：限定仅在表尾进行插入或删除操作的线性表。 结构： typedef struct list{ int listsize; //栈的容量 struct list *head; //栈顶指针 struct list *base; //栈底指针 } （2）顺序栈操作算法：入栈、出栈、判断栈空等（这个是使用数组进行操作的，具体内容参照书本P46-47） （3）链栈的结构与定义 2. 队列 （1）队列的定义 定义：只允许在表的一端进行插入，而在另一端删除元素。 ---------------------------------------------------------------------------------------------------------------- 补充内容： 1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（B） A. BCDAE B. EDACB C. BCADE D. AEDCB 2、栈的顺序表示中，用TOP表示栈顶元素，那么栈空的条件是（D） A. TOP==STACKSIZE B. TOP==1 C. TOP==0 D. TOP==-1 3、允许在一端插入，在另一端删除的线性表称为队列。插入的一端为表头，删除的一端为表尾。 4、栈的特点是先进后出，队列的特点是先进先出。 5、对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是O(1)（即与已有元素N无关）。 6、已知链栈Q，编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输出。（要求判断栈空、出栈、入栈用函数实现）（详看考点2） 7.出队与取队头元素的区别：出队就是删除对头的数据元素，取队头元素是获取对头的数据元素值，不需要删除。 8.链栈与顺序栈相比，比较明显的优点是：（D） A.插入操作比较容易 B.删除操作比较容易 C.不会出现栈空的情况 D.不会出现栈满的情况 考点1：队列的编程： 结构： typedef struct QNode{ int date; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; 创建： LinkQueue InitQueue(LinkQueue Q) { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.front->next=NULL; return (Q); } 入队： LinkQueue EnQueue(LinkQueue Q,int e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); p->date=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return (Q); } 出队： LinkQueue DeQueue(LinkQueue Q) { int e; QueuePtr p; p=Q.front->next; e=p->date; Q.front=p->next; printf("%d",e); if(Q.rear==p)Q.rear=Q.front=NULL; free(p); return (Q); } 考点2：栈的编程： 创建： struct list *creat() { struct list *p; p=(struct list *)malloc(LEN); p->next=NULL; return(p); } 入栈： struct list *push(struct list *head,int a) { struct list *p; p=(struct list *)malloc(LEN); p->num=a; p->next=head; return(p); } 出栈： struct list *pop(struct list *head) { struct list *p; p=head->next; free(head); return(p); } 判断栈空： int listempty(struct list *head) { if(head->next)return 0; else return 1; } 第四章串（不是重点内容） 1.串是由零个或多个字符组成的有限序列 2.串的赋值：x=’abc’;或x[ ]=’abc’; 第五章数组和广义表（不是重点内容） 1. 多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。 2. 明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。 3. 将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。补充内容： 三元组： 结构： typedef struct{ int i,j; //元素行下标及列下标 int e; //元素值 }Triple; typedef struct{ int mu,nu,tu; //矩阵的行数、列数、非零元素个数 Triple data[MAXSIZE+1]; //矩阵包含的三元组表，data[0]未用 }TSMatrix; 十字链表： typedef struct OLNode{ int i,j; //元素行下标及列下标 int e; //元素值 struct OLNode *right,*down; //行的后继以及列的后继 } OLNode，*OLink; typedef struct{ int mu,nu,tu; //矩阵的行数、列数、非零元素个数 OLink *rhead,*chead; //行和列的表头指针组的首地址 }CrossList; CrossList Creat（CrossList M）{ int m,n,t; scanf(“%d%d%d”,&m,&n,&t); M.mu=m;M.nu=n;M.tu=t; M.rhead=( OLink *)malloc((m+1)*sizeof(OLink)); //开辟行表头指针组 M.chead=( OLink *)malloc((n+1)*sizeof(OLink)); //开辟行列头指针组 M.rhead[]=M.chead[]=NULL; //初始化 ……//接下来就是赋值和入链 ｝ 第六章树和二叉树 1．树 （1）树的概念及术语 树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件： ⑴有且仅有一个特定的称为根的结点； ⑵当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。 （2）结点的度：结点所拥有的子树的个数。 树的度：树中所有结点的度的最大值。 （3）叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 （4）孩子、双亲：树中某结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 （5）路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1<=i （7）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数，也称高度。 （8）层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。 （9）有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树 （10）树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式（树， 不是二叉树，没中序遍历。) 2．二叉树 （1）二叉树的定义：二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 （满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。） 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。 完全二叉树的特点： 1.在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。 2.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 3. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 4. 深度为k的完全二叉树在k-1层上一定是满二叉树。 （3）二叉树的性质： 性质1：二叉树的第i层上最多有2i-1个结点（i≥1）。 性质2：一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。深度为k 且具有2k-1个结点的二叉树一定是满二叉树 性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。（一个结点的度就是指它放出的射线） 性质4：具有n个结点的完全二叉树的深度为log2n +1。 性质5：对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有： （1）如果i＞1，则结点i的双亲结点的序号为i/2；如果i＝1，则结点i是根结点，无双亲结点。 （2）如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。 （3）如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点i无右孩子。3．二叉树的遍历（递归调用与访问的顺序不同而产生不同的遍历方法） （1）先序遍历 void XianXu(BiTree T){ if(T){ printf("%c",T->data); //先访问 XianXu(T->lchild); //再继续遍历 XianXu(T->rchild); } } （2）中序遍历 （3）后序遍历 4. 森林与二叉树的转换 （1）同级以左为亲，即左一结点的右孩子是与它同级的右一结点 （2）只认最左路线为亲子路线，即结点的左孩子是它下一级结点的最左的元素 5. 哈夫曼树 （1）哈夫曼树的基本概念： 哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。 （2）哈夫曼树的特点： 1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点. （3）哈夫曼树的构造算法思想及构造过程（森林与哈夫曼编码） 就是求各权值和路径相乘之后叠加的最小值。 ---------------------------------------------------------------------------------------------------------------------- 1、已知一棵完全二叉树有47个结点，则该二叉树有（C）个叶子结点。 A. 6 B. 12 C. 24 D.48 解法如下： 1+2+4+8+16=31 计算从第一层到n-1层的结点个数 47-31=16 计算第n层的叶子结点个数 16-16/2=8 计算第n-1层的叶子结点个数 所以，叶子结点数=16+8=24 计算第n层和第n-1层的总叶子结点数 2、已知遍历一棵二叉树的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵树（C ）。 C图如下： A ↙↘ B F ↙↘↘ C D G ↙ E 4、完全二叉树必须满足的条件为: ：一棵具有n个结点的二叉树，它的结构与满二叉树的前n个结点的的结构相同。 5、哈夫曼树不存在度为1的结点。 6、有5个带权结点，其权值分别为2，5，3，7，11，根据哈夫曼算法构建该树，并计算该树的带权路径长度。（构建哈夫曼树，很简单，从小开始，计算相加，然后把所有叶子结点乘以等级数字然后相加。也即是：带权路径长度=叶结点的权值*路径长度） 7.试找出分别满足下列条件的所有二叉树： ⑴前序序列和中序序列相同：只有右子树 ⑵中序序列和后序序列相同：只有左子树 ⑶前序序列和后序序列相同：只有根，空二叉树 第七章图 1.图的基本概念：图的基本术语及推论 图的结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 设图有n个顶点，则： 有1/2 n(n-1)条边的无向图称为完全图 有n（n-1）条弧的有向图称为有向完全图 元素被多少条弧的箭头所指，它的入度就为多少；反之，出度。 第一个顶点和最后一个顶点相同的路径叫做回路或环 顶点不重复出现的路径叫简单路径 若图中任意两个顶点之间存在路径（不一定是直接相连），则称作连通图 2.邻接矩阵： W i,j 邻接矩阵的定义：A[i][j]={ 0 即VR中不存在 3. 图的遍历 （1）深度优先遍历 步骤：1.从任意顶点开始访问。 2.访问后把该元素对应的访问标志赋值为1表示已访问该数据元素 3.寻找与其有关未被访问的所有邻接顶点，并从该顶点开始进行访问 4. 重复2、3步骤直到该连通图的所有顶点均已访问完毕 （2）广度优先遍历 步骤：1.从任意顶点开始访问。 2.访问后把该元素对应的访问标志赋值为1表示已访问该数据元素 3.寻找与其有关未被访问的邻接顶点，并按顺序入列直到所有邻接顶点均 已访问完毕 4.把最先入列的顶点出列，以它为顶点开始访问 5. 重复2、3、4步骤直到该连通图的所有顶点均已访问完毕 第八九十章 查找表 是由同一类型的数据元素（或记录）构成的集合 对查找表的操作有： （1）查询某个“特定的”数据元素是否在查找表中； （2）检索某个“特定的”数据元素的各种属性 （3）在查找表中插入一个数据元素； （4）从查找表中删去某个特定元素 静态查找表 只进行前两种“查找”操作的查找表为静态查找表 动态查找表 若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则成为动态查找表 排序 其功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 第二章线性表 一、顺序表和链表的优缺点 1.顺序表 定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素（平均约需移动一半结点，当n很大时，算法的效率较低） 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 2.链式存储结构 定义：由分别表示a1,a2,…,a i-1,a i,…,a n的N 个结点依次相链构成的链表，称为线性表的链式存储表示 优势： (1)能有效利用存储空间； 动态存储分配的结构，不需预先为线性表分配足够大的空间，而是向系统“随用随取”，在删除元素时可同时释放空间。 (2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作； 插入或删除时只需要修改指针，而不需要元素移动。 劣势： (1)不能随机存取数据元素； (2)丢失了一些顺序表的长处，如线性表的“表长”和数据元素在线性表中的 “位序”，在单链表中都看不见了。如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。 二、单链表中删除一个节点和插入一个节点的语句操作，p29 1.插入元素操作 算法基本思想：首先找到相应结点，然后修改相应指针。 假定在a，b之间插入结点X，s指向X, p指向a，指针修改语句为： s->next=p->next; p->next =s; 2.删除元素操作 算法基本思想:首先找到第i-1 个结点，然后修改相应指针。 删除b结点，其中，P指向a，指针修改语句为：p->next=p->next->next； 三、单链表的就地逆置习题集2.22 算法的基本思想：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点）。 算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。 void reverse (Linklist H){ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p){ q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 第三章栈和队列 一、栈和队列的特性 1.特点 栈必须按“后进先出”（LIFO）的规则进行操作，仅限在表尾进行插入和删除的操作。 队列（FIFO）必须按“先进先出”的规则进行操作，队尾插入，队头删除。 二、循环队列为空和满的判定方法，p63 队空条件：front == rear; 队满条件：(rear + 1) % maxSize == front 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 数据结构基础知识整理 *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数 据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或 多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而 实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 （补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。） 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。 （2）数据的存储结构：数据元素及其关系在计算机的表示称为数据的存储结构。 想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5.时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1) 2.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n) 3.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) /** *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。 *17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。 *18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。 *19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈：采用顺序存储结构的栈，称为顺序栈。 *21、链栈：采用链式存储结构的栈，称为链栈。 *22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列：采用顺序存储结构的队列，称为顺序队列。 *25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环， 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1 数据结构基本知识 数据（Data） 数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括： 整数、实数、字符串、图像和声音等。 数据元素（Data Element） 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。 数据项是具有独立含义的最小标识单位。 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 1．数据结构一般包括以下三方面内容： ①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）； 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）； 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 ③数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的 检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1．1】学生成绩表，见下表。 注意：在表中指出数据元素、数据项、开始结点和终端结点等概念 （1）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。 表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。数据结构与算法基础知识总结
数据结构整理完整版
(完整版)非常实用的数据结构知识点总结
数据结构复习提纲(整理)
数据结构基础知识整理
数据结构复习要点整理版
数据结构基础知识大全
2021年自考02331数据结构重点总结最终修订
大学数据结构期末知识点重点总结
数据结构基本知识.