下载文档原格式
期末复习复习第一章绪论数据：计算机处理的信息总称数据项：最小单位数据元素：最基本单数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。
概念：数据元素之间的关系线性结构：一对逻辑结构非线性结构数据结构树：一对多图：多对多顺序存储结构链表存储结构存储结构。
索引。
基。
散列。
础知数据运算识算法描述：指令的有限有序序列有穷性确定性算法特性可行性算法输入输出时间复杂度算法分析空间复杂度、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。
1 2、算法分析的两个主要方面是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
4、数据项是数据的最小单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
线性表复习第二章定义逻辑关系：前趋后继节省空间基本特点随机存取插、删效率低顺序存储结构插入基本运算删除一个数据一个指针多占空特查找费插、删效率无法查找前趋结单链运算特点：单链表+前趋指针域链表存储双向结构链表插入运算删除特点：单链表的尾结点指针循环指向附加头结点。
链表运算：联接1 、一个指向后继结点的指针、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 2、线性表采用顺序存储，必须占用一片连续的存储单元、线性表采用链式存储，便于进行插入和删除操作3 、线性表采用顺序存储和链式存储优缺点比较。
4 5、简单算法复习栈和队列第三章．栈的概念：在一端操作的线性表LIFO栈的特点：先进后出存储结初始化push 进栈运算算法pop出栈队列概念：在两端操作的线性表FIFO队列特点：先进先出假溢出顺序队列front=rear队空：循环队列front=(rear+1)%MAXSIZE队满：队列front∧队空：链队列rear初始化判空顺序：进队基本运算链队：出队取队首元素1栈和队列的异同点。
、、2栈和队列的基本运算出栈和出队、3 、4基本运算复习串第四章．n(≥)个字符组成的有限序列1定义：由”c……cS=”cc n231串长度、空白串、空串。
数据结构期末复习要点第一章绪论1、掌握基本概念和术语，看教材P4—P6部分内容；2、看P10—P11关于类C的语法描述，算法设计写代码时可用到；3、掌握算法的特征（5个）和要求（5个）（P13—P14），能够结合具体算法分析算法的时间复杂度和空间复杂度（比如线性表的插入、删除操作，查找、排序等操作），理解O(n)、O(1)等时间复杂度的具体含义（P14—P17）。
第二章线性表1、看教材P21—P26，掌握有关线性表顺序存储的内容：（1）顺序表的随机存取（P21计算地址的公式）；（2）顺序表的表示（P22的Typedef）；（3）顺序表为空、为满的判定，插入和删除操作的特征以及时间复杂度的分析（P23—P25）；（4）有关顺序表的编程题。
2、看教材P27—P30，掌握有关线性表链式存储的内容：（1）单链表的表示（P28的Typedef）；（2）单链表为空的判定（带头结点、不带头结点）；（3）单链表插入、删除操作的特征（操作点的确定以和指针的修改）以及时间复杂度分析（P29—P30）；（4）有关单链表的编程。
3、为节约时间，循环链表、双向链表以及多项式加法可以不看；4、算法设计题要求写代码，在本章体现的可能性比较大。
第三章栈和队列1、顺序栈的表示，栈操作的特点以及为空、为满的判定（P46—P47）；2、栈的应用举例看个标题就足够了；3、链队列的表示以及入队、出队操作（P61—P62）；4、循环队列为空、为满的判定（P65的代码中）；5、离散事件模拟这节不用看；6、第四章只需要看P70就够了，掌握串的特点（元素受限），串长度、空串、串的位置、串相等几个概念即可。
第六章树和二叉树1、看教材P120，了解有关树的概念和术语；2、了解二叉树的链式存储结构（P127），掌握二叉树的性质（P123—P125），并会做题（参考课件或指导书相关内容）；3、掌握二叉树的各种遍历算法（P128—P129或课件）：（1）能够根据二叉树写出各种遍历序列；（2）能够由两种遍历序列（必须包含中序序列）恢复二叉树；（3）理解二叉树遍历算法的递归代码，能够读懂代码含义。
第一章1. 怎样理解“算法+数据结构=程序”这个公式？举例说明。
算法是语句序列解决特定问题的固有程序片段。
数据结构是确定数据间的关系。
从具体问题抽象出一个合适的数学模型、然后设计一个解决此数学模型的算法，最后编写出程序。
寻求数学模型的是指就是数据结构要完成的工作。
参看书p1前两段的描述。
2. 数据结构的概念，它包含哪三方面的内容？数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科。
参看书p3包含三方面的内容:1、数据之间的逻辑关系2、数据在计算机中的存储方式3、在数据上定义的运算的集合。
3. 数据、数据元素、数据项的基本概念。
举例说明数据元素和数据项的联系与区别。
数据：描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。
数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑或处理。
数据项：数据项是具有独立含义的最小标识单位，是数据元的一个具体值，是数据记录中最基本的、不可分的有名数据单位。
例1：class A{int c[123];int i;};class B{A a;}B b;b.a是数据项，B是数据元素例2：一本书的数目信息为一个数据元素，而数目信息中每一项（如书名、作者名等）为一个数据项4. 从逻辑结构来看，数据结构有哪四种基本结构，各自的特点是什么？1、集合（数据元素之间同属于一个集合，再无其他关系）2、线性结构（数据元素之间存在一对一的关系）3、树形结构（数据元素之间一对多的关系）4、图状结构或网状结构（数据元素之间多对多的关系）5. 从物理结构来看，数据结构有哪两种基本结构，各自的特点是什么？1、顺序存储结构特点：借助元素在存储器中的相应位置来表示数据元素之间的逻辑关系。
2、链式存储结构特定：借助元素在存储地址的指针表示数据元素之间的逻辑关系。
6. 算法的5个特征，4个评价标准是什么？特征:有穷性、确定性、可行性、输入、输出。
//顺序表#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define MAX 5#define INCREMENT 5typedef struct{int * pBase;int len;int count;}SQLIST,* PSQLIST;//初始化顺序表void initSqList(PSQLIST);//插入元素bool insertList(PSQLIST,int,int);//判断是否已满bool isFull(PSQLIST);//遍历顺序表void show_arr(PSQLIST);//判断是否为空bool isEmpty(PSQLIST);//删除元素，并返回删除元素的值void deleteList(PSQLIST,int,int *);int main(void){SQLIST sqList;initSqList(&sqList);insertList(&sqList,1,1);insertList(&sqList,2,2);insertList(&sqList,3,3);insertList(&sqList,4,4);insertList(&sqList,1,0);insertList(&sqList,3,5);show_arr(&sqList);int val;deleteList(&sqList,1,&val);show_arr(&sqList);printf("被删除的元素为%d",val);return 0;}void initSqList(PSQLIST pSqList){//为顺序表第一个元素分配地址pSqList->pBase = (int *)malloc(sizeof(int)*MAX);//内存分配失败，退出if(pSqList->pBase == NULL){printf("分配失败！\n");exit(-1);}pSqList->len = MAX;pSqList->count = 0;}//插入元素,在第pos个元素之前插入元素bool insertList(PSQLIST pSqList,int pos,int val){ if(pos<1||pos>pSqList->len+1) //判断pos的范围是否有效return false;if(isFull(pSqList)){int * newBase = (int *)realloc(pSqList->pBase,(pSqList->len + INCREMENT) * sizeof(int));if (newBase != NULL){pSqList->pBase = newBase;pSqList->len += INCREMENT;printf("扩容成功！\n");}elseexit(-1);}int * q = &(pSqList->pBase[pos-1]);int * p;for(p = &(pSqList->pBase[pSqList->count-1]);p >= q;--p){*(p+1) = *p;}*q = val;pSqList->count ++;return true;}//删除索引为index的元素，并返回删除元素的值void deleteList(PSQLIST pSqList,int index,int * val){if(isEmpty(pSqList)){printf("顺序表为空！\n");exit(-1);}* val = pSqList->pBase[index];for(int i = index;i<pSqList->count-1;i++){ pSqList->pBase[i] = pSqList->pBase[i+1];}pSqList->count--;}//判断是否已满bool isFull(PSQLIST pSqList){if(pSqList->len == pSqList->count)return true;return false;}//判断是否为空bool isEmpty(PSQLIST pSqList){if(pSqList->count == 0)return true;return false;}//遍历顺序表void show_arr(PSQLIST pSqList){if(isEmpty(pSqList)){printf("数组为空！\n");}else{for(int i = 0;i<pSqList->count;i++){printf("%d ",pSqList->pBase[i]);}printf("\n");}}//顺序表时间复杂度1.插入操作最好情况：在表尾插入，时间复杂度为O(1) 最坏情况：在表头插入，时间复杂度为O(n) 平均时间复杂度：O(n);2.删除操作最好情况：删除表尾，时间复杂度为O(1) 最坏情况：删除表头，时间复杂度为O(n) 平均时间复杂度：O(n);//单链表#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef struct Node{int data; //数据域struct Node * pNext;//指针域}NODE,*PNODE;//创建链表PNODE creatList(void);//插入元素,头插void insertHead(PNODE,int);//插入元素，尾插void insertTail(PNODE,int);//在位置pos插入元素void insertLink(PNODE,int,int);//删除在位置pos的元素void delLink(PNODE,int,int *);//判断是否为空bool isEmpty(PNODE);//遍历链表void showLink(PNODE);//链表长度int LenLink(PNODE);//获取第pos位置元素的值void getLink(PNODE,int,int *);int main(void){PNODE pHead = creatList();insertHead(pHead,3);insertHead(pHead,4);insertHead(pHead,5);insertHead(pHead,6);insertHead(pHead,7);insertTail(pHead,2);showLink(pHead);printf("链表长度为%d\n",LenLink(pHead));insertLink(pHead,3,100);showLink(pHead);int val;int i = 3;getLink(pHead,i,&val);printf("第%d个元素的值为:%d\n",i,val);int delVal;delLink(pHead,7,&delVal);printf("删除的元素为：%d\n",delVal);showLink(pHead);return 0;}//创建链表PNODE creatList(void){PNODE pHead = (PNODE)malloc(sizeof(NODE));if(pHead == NULL){printf("分配失败！\n");exit(-1);}pHead->pNext = NULL;return pHead;}//判断是否为空bool isEmpty(PNODE pHead){if(pHead -> pNext == NULL)return true;return false;}//插入元素,头插void insertHead(PNODE pHead,int val){PNODE p = (PNODE)malloc(sizeof(NODE));if(p == NULL){printf("分配失败！\n");exit(-1);}p->data = val;p->pNext = pHead->pNext;pHead -> pNext = p;}//插入元素，尾插void insertTail(PNODE pHead,int val){PNODE pNew = (PNODE)malloc(sizeof(NODE));pNew->data = val;if(pNew == NULL){printf("分配失败！\n");exit(-1);}PNODE p = pHead->pNext;while(p->pNext !=NULL){p = p->pNext;}p->pNext = pNew;}//插入元素void insertLink(PNODE pHead,int pos,int val){ if( pos<1 ||pos > LenLink(pHead)+1){printf("插入失败！\n");exit(-1);}PNODE pNew = (PNODE)malloc(sizeof(NODE));pNew->data = val;if(pNew == NULL){printf("分配失败！\n");exit(-1);}PNODE p = pHead;for (int i = 1;i<pos ;i++ )p = p->pNext;pNew->pNext = p->pNext;p->pNext = pNew;}//删除在位置pos的元素void delLink(PNODE pHead,int pos,int * val){ if( pos<1 ||pos > LenLink(pHead)){printf("删除失败！\n");exit(-1);}if(isEmpty(pHead)){printf("链表为空！\n");exit(-1);}PNODE p = pHead;int i;for(i = 0;i<pos-1;i++){p = p->pNext;}PNODE q = p->pNext;//在位置pos的元素p->pNext = q->pNext;*val = q->data;q->pNext = NULL;free(q);}//获取第pos位置元素的值void getLink(PNODE pHead,int pos,int * val){ if( pos<1 ||pos > LenLink(pHead)){printf("查找失败！\n");exit(-1);}PNODE p = pHead->pNext;for (int i = 1;i<pos ;i++ )p = p->pNext;*val = p->data;}//链表长度int LenLink(PNODE pHead){PNODE p = pHead->pNext;int len = 0;while(p!=NULL){p = p->pNext;len++;}return len;}//遍历链表void showLink(PNODE pHead){PNODE p = pHead->pNext;while(p != NULL){printf("%d ",p->data);p = p->pNext;}printf("\n");}//单链表时间复杂度插入和删除操作的时间复杂度为O(1)查找的平均时间复杂度为O(n) //顺序栈#include <stdio.h>#include <malloc.h>#include <stdlib.h>#define SIZE 5#define INCREMENT 5typedef struct{int * base;int size;//当前已分配的存储空间int * top;}SQSTACK,*PSQSTACK;//初始化栈void initStack(PSQSTACK);//入栈void push(PSQSTACK,int);//出栈void pop(PSQSTACK,int *);//遍历栈void showStack(PSQSTACK);//判断是否栈满bool isFull(PSQSTACK);//判断是否为空栈bool isEmpty(PSQSTACK);int main(void){SQSTACK sqStack;initStack(&sqStack);push(&sqStack,0);int popVal;pop(&sqStack,&popVal);printf("出栈元素：%d\n",popVal);return 0;}//初始化栈void initStack(PSQSTACK pSqStack){pSqStack->base = (int *)malloc(sizeof(int)*SIZE);if(pSqStack->base==NULL){printf("内存分配失败！\n");exit(-1);}pSqStack->top = pSqStack->base;pSqStack->size = SIZE;}//入栈void push(PSQSTACK pSqStack,int val){if(isFull(pSqStack)){int * newBase = (int *)realloc(pSqStack->base,sizeof(int)*(SIZE+INCREMENT));if(newBase != NULL){printf("扩容成功！\n");pSqStack->base = newBase;pSqStack->size += INCREMENT;pSqStack->top = pSqStack->base + SIZE;}elseexit(-1);}*pSqStack->top++ = val;}//出栈void pop(PSQSTACK pSqStack,int * val){if(isEmpty(pSqStack)){printf("栈已空!\n");exit(-1);}*val = * --pSqStack->top;}//判断是否栈满bool isFull(PSQSTACK pSqStack){if(pSqStack->top - pSqStack->base > pSqStack->size)return true;return false;} //判断是否为空栈bool isEmpty(PSQSTACK pSqStack){if(pSqStack->top == pSqStack->base){return true;}return false;}//栈与递归----汉诺塔#include <stdio.h>void Hanoi(int,char,char,char);int main(void){int n;printf("请输入要移动盘子的个数:");scanf("%d",&n);char ch1 = 'A';char ch2 = 'B';char ch3 = 'c';Hanoi(n,'A','B','C');return 0;}void Hanoi(int n,char a,char b,char c){if(1 == n){printf("将编号为%d的盘子直接从%c柱子移动到%c柱子\n",n,a,c);}else{Hanoi(n-1,a,b,c);printf("将编号为%d的盘子直接从%c柱子移动到%c柱子\n",n,a,c);Hanoi(n-1,b,a,c);}}//栈的应用1.表达式求值2.递归---Hanoi3.进制转换4.迷宫求解5.层次遍历二叉树//链式队列#include <stdio.h>#include <malloc.h>#include <stdlib.h>typedef struct Node{int data;struct Node * pNext;}NODE,* PNODE;typedef struct{PNODE front;//对队头指针PNODE rear;//队尾指针}LinkQueue,*PLinkQueue;//初始化队列void initQueue(PLinkQueue);//入队void inQueue(PLinkQueue,int);//出队void outQueue(PLinkQueue,int *);//判断队列是否为空bool isEmpty(PLinkQueue);int main(void){LinkQueue q;initQueue(&q);inQueue(&q,1);inQueue(&q,2);inQueue(&q,3);int val;outQueue(&q,&val);printf("%d\n",val);outQueue(&q,&val);printf("%d\n",val);outQueue(&q,&val);printf("%d\n",val);return 0;}//初始化队列void initQueue(PLinkQueue q){q->front = (PNODE)malloc(sizeof(NODE));if(q->front == NULL){printf("内存分配失败！\n");exit(-1);}q->rear = q->front;q->front->pNext = NULL;}//入队void inQueue(PLinkQueue pLink,int val){ PNODE p = (PNODE)malloc(sizeof(NODE)); //分配新结点地址if(p == NULL){printf("内存分配失败！\n");exit(-1);}p->data = val;p->pNext = NULL;pLink->rear->pNext = p;pLink->rear = p;}//出队void outQueue(PLinkQueue pLink,int * val){if(isEmpty(pLink)){printf("队列为空,出队失败！\n");exit(-1);}PNODE p = pLink->front->pNext;*val = p->data;pLink->front->pNext = p->pNext;p->pNext = NULL;free(p);if(p == pLink->rear){ //栈空时，将对首指针指向队尾pLink->rear = pLink->front;}}//判断队列是否为空bool isEmpty(PLinkQueue pLink){if(pLink->front == pLink->rear)return true;return false;}//循环队列#include <stdio.h>#include <malloc.h>typedef struct Queue{int * pBase;int front;int rear;}QUEUE,* PQUEUE;//初始化void initQueue(PQUEUE);//入队bool enQueue(PQUEUE,int);//遍历数组void traverseQueue(PQUEUE);//判断队列是否已满bool isFull(PQUEUE);//判断队列是否为空bool isEmpty(PQUEUE);//出队bool outQueue(PQUEUE,int *);int main(void){QUEUE q;initQueue(&q);enQueue(&q,2);enQueue(&q,3);enQueue(&q,1);enQueue(&q,7);enQueue(&q,8);enQueue(&q,9);traverseQueue(&q);int val;if(outQueue(&q,&val)){printf("出队成功，出队的元素为：%d\n",val);traverseQueue(&q);}if(outQueue(&q,&val)){printf("出队成功，出队的元素为：%d\n",val);traverseQueue(&q);}return 0;}//初始化数组void initQueue(PQUEUE pQueue){pQueue->pBase = (int *)malloc(sizeof(int)*6);pQueue->front = 0;pQueue->rear = 0;}//入队bool enQueue(PQUEUE pQueue,int val){ if(isFull(pQueue))return false;pQueue->pBase[pQueue->rear] = val;pQueue->rear = (pQueue->rear+1)%6;}//判断队列是否已满bool isFull(PQUEUE pQueue){if((pQueue->rear+1)%6 == pQueue->front)return true;return false;}//遍历数组void traverseQueue(PQUEUE pQueue){int i = pQueue->front;while(i != pQueue->rear){printf("%d ",pQueue->pBase[i]);i = (i+1)%6;}printf("\n");}//判断队列是否为空bool isEmpty(PQUEUE pQueue){if(pQueue->front == pQueue->rear)return true;return false;}//出队bool outQueue(PQUEUE pQueue,int * pVal){ if(isEmpty(pQueue))return false;*pVal = pQueue->pBase[pQueue->front];pQueue->front = (pQueue->front+1) % 6;return true;}//队列的应用1.解决主机与外部设部之间速度不匹配的问题（建立缓冲区）2.解决由多用户引起的资源竞争问题数组1.一维数组可以看做是一个线性表；二维数组可以看做元素是线性表的线性表。
1.复杂性分析对各种操作的时间复杂性的分析。
主要是链表，树，排序等简单一些的分析。
分析的时候,从简单的入手,学会方法。
后续的各种豆可能让你分析时间复杂度。
线性链表（顺序表和单链表）链表循环链表双向链表2.线性结构队列（循环队列)栈链表主要操作:找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除)。
栈：查找，插入（位置固定），删除(位置固定）队列：查找，插入（位置固定)，删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）(插入）倒置：(查找）循环链表双向链表栈：(插入删除查找)队列(插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。
3.二叉树基本概念二叉树是每个节点最多有两个子树的有序树。
二叉树常被用于实现二叉查找树和二叉堆。
值得注意的是,二叉树不是树的特殊情形。
二叉树是每个结点最多有两个子树的有序树。
通常根的子树被称作“左子树”(left subtree）和“右子树”（right subtree）。
二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的每个结点至多只有二棵子树（不存在出度大于2的结点），二叉树的子树有左右之分,次序不能颠倒。
二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2；2。
树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：（1）空二叉树——如图（a)；（2)只有一个根结点的二叉树——如图（b);(3）只有左子树——如图（c）；（4)只有右子树-—如图（d）;(5）完全二叉树-—如图（e)注意:尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质（1）在非空二叉树中，第i层的结点总数不超过, i〉=1;(2）深度为h的二叉树最多有2^h—1个结点（h>=1），最少有h个结点；（3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2,则N0=N2+1；(4）具有n个结点的完全二叉树的深度为(5）有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系: 若I为结点编号则如果I>1,则其父结点的编号为I/2;如果2*I<=N，则其左儿子(即左子树的根结点）的编号为2*I；若2＊I>N,则无左儿子；如果2＊I+1〈=N,则其右儿子的结点编号为2*I+1；若2*I+1〉N，则无右儿子。
数据结构-（严蔚敏C语⾔版）-学习、复习提纲期末复习第⼀章绪论复习1、计算机算法必须具备输⼊、输出、可⾏性、确定性、有穷性５个特性。
2、算法分析的两个主要⽅⾯是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
数据结算法数据：计算机处理的信息总称数据项：最⼩单位数据元素：最基本单概念：数据元素之间的关系线性结构：⼀对⼀⾮线性结构树：⼀对多图：多对多顺序存储结构链表存储结构算法描述：指令的有限有有穷性确定性可⾏性时间复杂4、数据项是数据的最⼩单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
第⼆章线性表复习1、在双链表中，每个结点有两个指针域，包括⼀个指向前驱结点的指针、⼀个指向后继结点的指针2、线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元定义节省空间随机存取插⼊3、线性表采⽤链式存储，便于进⾏插⼊和删除操作4、线性表采⽤顺序存储和链式存储优缺点⽐较。
5、简单算法第三章栈和队列复习1、栈和队列的异同点。
2、栈和队列的基本运算 3、出栈和出队 4、基本运算存储结栈的概念：在⼀端操作的线性运算算栈的特点：先进后出初始化进栈顺序队队列概念：在两端操作的线性假溢出链队列队列特点：先进先出基本运顺序：队空：队满：(1)队初始化判空进队第四章串复习第五章数组和⼴义表复习定义：由n(≥1)个字符组成的有限序列紧缩格式⾮紧缩格式以字节为单位的存储基本运(s) 串长度 (s12) 联接 (s12) ⽐较模式匹失败链接值匹配算法单字符链表串串变量的存储映像：串名、串值对应关系表顺序存储压缩存储⾏优先顺序存放列优先顺序存放稀疏矩应⽤表达式⼴义表定义：n(≥0)个元素的有限序表头：(A)= a 1 概念：长度、深度、原⼦、⼦表尾：(A)=(a23,…)表结特殊矩对称矩阵三⾓矩阵三元组存储：三元组原⼦结第六章树复习1、三个结点可以组成2种不同形态的树。
2、⼀个稀疏矩阵*n 采⽤三元组形式表⽰，若完成了其的转置运算要经过哪⼏步:⼆叉树概定义：递归定义，不为空双亲、孩⼦、叶⼦、兄弟、存储⽅顺序：满、完全⼆⼆叉树已知先根、中根序列画树；先根线索线索线索树的画法树、森林与⼆叉树的相互树、森⼆叉排树的应哈夫曼左中哈夫曼树的矩阵的⾏、列数值互换、矩阵元素所在⾏列值互换、元素在矩阵中排列的位置）重新排列3、若⼆叉树中每⼀层结点的个数都达到了最⼤，则称为⼀棵满⼆叉树。
第1章绪论1.1复习笔记一、数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
二、基本概念和术语数据数据（data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，它是计算机程序加工的“原料”。
2.数据元素数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3.数据对象数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。
4．数据结构数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。
（1）数据结构的基本结构根据数据元素之间关系的不同特性，通常有下列四类基本结构：① 集合。
数据元素之间除了“同属于一个集合”的关系外，别无其它关系。
② 线性结构。
数据元素之间存在一个对一个的关系。
③ 树形结构。
数据元素之间存在一个对多个的关系。
④ 图状结构或网状结构。
数据元素之间存在多个对多个的关系。
如图1-1所示为上述四类基本结构的关系图。
图1-1 四类基本结构的关系图（2）数据结构的形式定义数据结构的形式定义为：数据结构是一个二元组Data_Structure==（D，S）其中：D表示数据元素的有限集，S表示D上关系的有限集。
（3）数据结构在计算机中的表示数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。
它包括数据元素的表示和关系的表示。
① 元素的表示。
计算机数据元素用一个由若干位组合起来形成的一个位串表示。
② 关系的表示。
计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。
并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。
a.顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
b.非顺序映象的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑关系。
一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。
所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。
但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。
线性表：基础章节，必考内容之一。
考题多数为基本概念题，名校考题中，鲜有大型算法设计题。
如果有，也是与其它章节内容相结合。
栈和队列：基础章节，容易出基本概念题，必考内容之一。
而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。
串：基础章节，概念较为简单。
专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。
多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。
一般如果要出题，多数不会作为大题出。
数组常与“查找，排序”等章节结合来作为大题考查。
树和二叉树：重点难点章节，各校必考章节。
各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。
通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。
图：重点难点章节，名校尤爱考。
如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。
查找：重点难点章节，概念较多，联系较为紧密，容易混淆。
出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。
算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。
排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。
在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。
算法设计大题中，如果作为出题，那么常与数组结合来考查。
二、数据结构各章节重点勾划：第0章概述本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。
大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。
本章考点不多，只要稍加注意理解即可。
1 / 9第一章线性表作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。
在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。
总体来说，线性表一章可供考查的重要考点有以下几个方面：1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。
2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。
3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。
静态链表与顺序表的相似及不同之处。
4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。
其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。
此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。
在链表的小题型中，经常考到一些诸如：判表空的题。
在不同的链表中，其判表空的方式是不一样的，请大家注意。
5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。
单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。
第二章栈与队列栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。
所以，理解栈与队列，是走向DS高手的一条必由之路，。
学习此章前，你可以问一下自己是不是已经知道了以下几点：1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。
栈与队列存取数据（请注意包括：存和取两部分）的特点。
2.递归算法。
栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。
其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。
3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。
4.循环队列中判队空、队满条件，循环队列中入队与出队算法。
2 / 9如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。
注意，我说的是可以不看书，并不是可以不作题哦。
第三章串经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。
串，在概念上是比较少的一个章节，也是最容易自学的章节之一，但正如每个过来人所了解的，KMP算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡垒有：1.串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。
运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。
3.顺序串与链串及块链串的区别和联系，实现方式。
4.KMP算法思想。
KMP中next数组以及nextval数组的求法。
明确传统模式匹配算法的不足，明确next数组需要改进之外。
其中，理解算法是核心，会求数组是得分点。
不用我多说，这一节内容是本章的重中之重。
可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。
第四章数组与广义表学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经“一回生，二回熟”了，所以，在概念上，不会存在太大障碍。
但作为考研课程来说，本章的考查重点可能与大学里的程序语言所关注的不太一样，下面会作介绍。
广义表的概念，是数据结构里第一次出现的。
它是线性表或表元素的有限序列，构成该结构的每个子表或元素也是线性结构的，所以，这一章也归入线性结构中。
本章的考查重点有：1.多维数组中某数组元素的position求解。
一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。
2.明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。
3.将特殊矩阵中的元素按相应的换算方式存入数组中。
这些矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵3 / 9等。
熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。
掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。
4.广义表的概念，特别应该明确表头与表尾的定义。
这一点，是理解整个广义表一节算法的基础。
近来，在一些学校中，出现了这样一种题目类型：给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值，要求求出原广义表L。
大家要留意。
5.与广义表有关的递归算法。
由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。
比如：求表深度，复制广义表等。
这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。
第五章树与二叉树从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。
所以，树这一章的重要性，已经不说自明了。
总体来说，树一章的知识点包括：二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。
下面我们来看考试中对以上知识的主要考查方法：1.二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+1的性质，n个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：2*i，右为：2*i+1）。
二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。
2.二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。
二叉树的遍历算法有三种：先序，中序和后序。
其划分的依据是视其每个算法中对根结点数据的访问顺序而定。
不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。
由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利4 / 9用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。
我会在另一篇系列文章（）里给出三种遍历的递归和非递归算法的背记版，到时请大家一定熟记。
3.可在三种遍历算法的基础上改造完成的其它二叉树算法：求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。
如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。
4.线索二叉树：线索二叉树的引出，是为避免如二叉树遍历时的递归求解。
众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。
对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。
5.最优二叉树（哈夫曼树）：最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。
