《数据结构C语言版复习攻略精品资料.doc》由会员分享，可在线阅读，更多相关《数据结构C语言版复习攻略精品资料.doc（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章：绪论一、基础知识概念和术语(黑体字部分)。另外，注意：1、数据元素是数据的基本单位。P42、数据项是数据不可分割的最小单位。P53、数据结构及其形式定义。P5四种基本结构：集合线性结构树形结构图（网）状结构4、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系P65、数据类型 P7 抽象数据类型（ADT）P7 ADT=（数据对象，数据关系，基本操作） ADT细分为原子类型，固定聚合，可变聚合类型。P86、算法的概念 P137、算法的五个特征 有穷性 确定性 可行性 输入（0个或多个） 输出（1个或多
2、个）8、算法设计的要求：正确性可读性健壮性效率与低存储量其中正确性的四个层次（通常要求达到C层）。9、算法的时间复杂度 P15 常见有： O(1)，O(n)，O(n2)，O(log2n) 分析算法的时间复杂度时，log2n常简单记作log n。，O(n log2n)，O(2n) 语句频度，用归纳法计算。10、算法的空间复杂度 P17二、算法起泡排序。P16另一种形式void BubbleSort ( DataType a, int n ) for ( i=0; in-1; i+ ) for ( j=0; jaj+1 ) ajaj+1;或void BubbleSort ( DataType a,
3、 int n ) for ( i=1; in; i+ ) for ( j=0; jaj+1 ) ajaj+1;或void BubbleSort ( DataType a, int n ) for ( i=0; in-1; i+ ) change = fasle; for ( j=0; jaj+1 ) ajaj+1; change = true; if ( !change ) break; 说明：a) 考试中要求写算法时，可用类C，也可用C程序。b) 尽量书写算法说明，言简意赅。c) 技巧：用“边界值验证法”检查下标越界错误。 如上第一个： 第二个循环条件若写作jn-i，则当i=0时 aj+1会
4、越界。d) 时间复杂度为O(n2)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。第二章、线性表一、基础知识和算法1、线性表及其特点线性表是n个数据元素的有限序列。线性结构的特点： “第一个” “最后一个” 前驱 后继。 这里太简炼了，只是为了便于记忆。2、顺序表线性表的顺序存储结构（1）特点：a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。（2）类型定义简而言之，“数组+长度” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。const int MAXSIZE = 线性表最大长度;typedef structDataType elemMA
5、XSIZE;int length; SqList;注：a) SqList为类型名，可换用其他写法。 b) DataType是数据元素的类型，根据需要确定。 c) MAXSIZE根据需要确定。如const int MAXSIZE=64; d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以 e) 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length=L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的
6、元素到新分配的空间中。（3）基本形态1. 顺序表空01MAXSIZE-1.L.elemL.elemL.elemL.length=0L.length=MAXSIZE0L.lengthMAXSIZE条件 L.length=0不允许删除操作2. 顺序表满条件 L.length=MAXSIZE不允许插入操作3. 不空也不满可以插入，删除（4）基本算法遍历4. 顺序访问所有元素for ( i=0; iL.length; i+ ) visit ( L.elemi ); 5 查找元素xfor ( i=0; iL.length; i+ ) if ( L.elemi=x ) break;if ( iL.leng
7、th ) 找到;else 未找到;(2) 插入算法 ListInsert(&L,i,x)1. 前提：表不满2. 合理的插入范围：1iL.length+1注：位序i在C/C+中对应于下标i-1。3. 步骤 第i至最后所有元素后移一个元素 在第i个位置插入元素x 表长增14. 算法bool 这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。 ListInsert ( SqList& L, int i, DataType x ) if ( L.length=MAXSIZE | iL.length+1 ) return false; / 失败 / 元素后移 fo
8、r ( j=L.length-1; j=i-1; j- ) / 这里j为下标，从L.length-1到i-1 L.elemj+1 = L.elemj; / 若作为位序，有如何修改？ / 插入x L.elemi-1 = x; / 表长增1 L.length+; return true; / 插入成功(3) 删除算法 ListDelete(&L,i,&x)1. 前提：表非空2. 合理的删除范围：1iL.length3. 步骤取出第i个元素第i个元素之后的元素向前移动一个位置表长减14. 算法bool ListDelete ( SqList& L, int i, DataType& x ) if (
9、 L.length=0 | iL.length ) return false; / 失败 x = L.elemi-1; for ( j=i; jnext = 02. 单链表不空条件：L-next != 0(10) 基本算法 （遍历）1. 顺序访问所有元素借助指针，“顺藤摸瓜”(沿着链表访问结点)。p = L-next; / 注意起始位置的考虑while ( p!=NULL ) / 判表尾，另外 (p!=0)或(p)均可 visit( p-data ); / 访问:可以换成各种操作 p = p-next; / 指针沿着链表向后移动例：打印单链表中的数据。void PrintLinkList (
10、LinkList L ) p = L-next; while ( p!=NULL ) print ( p-data ); / 访问：打印数据域 p = p-next; 2. 查找元素x/ 在单链表L中查找元素x/ 若找到，返回指向该结点的指针；否则返回空指针LinkList Find ( LinkList L, DataType x ) p = L-next; while ( p!=NULL ) if ( p-data = x ) return p; / 找到x p = p-next; return NULL; / 未找到/ 在单链表L中查找元素x/ 若找到，返回该元素的位序；否则返回0int
11、 Find ( LinkList L, DataType x ) p = L-next; j = 1; while ( p!=NULL ) if ( p-data = x ) return j; / 找到x p = p-next; j+; / 计数器随指针改变 return 0; / 未找到前一个算法的另一种写法：p = L-next;while ( p & p-data!=x ) p = p-next;if ( p & p-data=x ) return p;else return 0;或者p = L-next;while ( p & p-data!=x ) p = p-next;retur
12、n p; / 为什么3. 查找第i个元素LinkList Get ( LinkList L, int i ) p = L-next; j = 1; while ( p & jnext; j+; if ( p & j=i ) return p; else return 0;4. 查找第i-1个元素p = L; j = 0;while ( p & jnext; j+;if ( p & j=i-1 ) return p;else return 0;(11) 插入算法 ListInsert(&L,i,x)技巧：画图辅助分析。思路： 先查找第i-1个元素 若找到，在其后插入新结点bool 这里返回tru
13、e表示正确插入，返回false表示插入失败。 ListInsert ( LinkList &L, int i, DataType x ) / 查找第i-1个元素p p = L; j = 0; while ( p & jnext; j+; / 若找到，在p后插入xai-1-插入前执行之后执行之后-pxsai-1-px-sai-1-px-s if ( p & j=i-1 ) s = (LinkList) malloc(sizeof(LNode); s-data = x; s-next = p-next; / p-next = s; / return true; / 插入成功 else return
14、 false; / 插入失败注意： a) 要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。 b) 能够插入的条件： p & j=i-1 。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。 c) 新建结点时需要动态分配内存。 s = (LinkList) malloc(sizeof(LNode); 若检查是否分配成功，可用 if ( s=NULL ) exit(1); / 分配失败则终止程序 d) 完成插入的步骤：。技巧：先修改新结点的指针域。(12) 删除算法 ListDelete(&L,i,&x)思路： 先查找第i-1个元素 若找到且其后存在第i个
15、元素，则用x返回数据，并删除之ai-1-删除前ai-p-sai-1-执行之后ai-p-sai-1-执行之后ai-p-bool ListDelete ( LinkList &L, int i, int &x ) / 查找第i-1个元素p p = L; j = 0; while ( p & jnext; j+; /若存在第i个元素，则用x返回数据，并删除之 if ( p & j=i-1 & p-next ) / 可以删除 s = p-next; / p-next = s-next; / x = s-data; free (s); return true; else return false;注意：
16、 a) 要求p找到第i-1个而非第i个元素。为什么？ b) 能够进行删除的条件： p & j=i-1 & p-next 。条件中的p-next就是要保证第i个元素存在，否则无法删除。若写成p-next & j=i-1也不妥，因为此时(循环结束时)可能有p=NULL，所以必须先确定p不空。技巧：将条件中的“大前提”放在前面。该条件也不可以写成p-next & p & j=i-1，因为先有p!=0才有p-next，上式颠倒了这一关系。 c) 释放结点的方法。 free(s); d) 完成删除的步骤：。(13) 建立链表的两种方法思路： 建立空表（头结点）； 依次插入数据结点（每次插入表尾得(a1,
17、a2,an)，每次插入表头得(an,a2,a1)）。1. 顺序建表void CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkList) malloc(sizeof(LNode); L-next = NULL; / 空表 p = L; / 用p指向表尾 / 插入元素 for ( i=0; idata = x; / 插入表尾 s-next = p-next; p-next = s; p = s; / 新的表尾 2. 逆序建表void CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkL
18、ist) malloc(sizeof(LNode); L-next = NULL; / 空表 / 插入元素 for ( i=0; idata = x; / 插入表头 s-next = L-next; L-next = s; 循环链表(14) 特点最后一个结点的指针指向头结点。anCBA(b)(a)Ea1L.L(15) 类型定义同单链表。(16) 基本形态空表：L-next = L。非空表。(17) 与单链表的联系判断表尾的方法不同：单链表用p=NULL；循环链表用p=L。其余操作相同。双向循环链表(18) 特点一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成
19、循环链表。datapriornext(19) 类型定义typedef struct DuLNode DataType data; struct DuLNode *prior, *next; / 两个指针 DuLNode, *DuLinkList;(20) 基本形态空表：用后向指针判断L-next = L，或者用前向指针判断L-prior = L。非空表。a1a2anLL. .(21) 与单链表和循环链表的联系最大不同：前驱容易求得，可以向前遍历。判断表尾的方法与循环链表相同：p=L。插入和删除时需要修改两个方向的指针。(22) 插入和删除需要修改两个方向的指针。例如：(见下表)表 Error!
20、 No text of specified style in document.2 双向循环链表的插入和删除p之后插入sp之前插入s删除p之后继s删除ps-next = p-next;p-next = s;s-prior = p;s-next-prior = s;s-prior = p-prior;p-prior = s;s-next = p;s-prior-next = s;s = p-next;p-next = s-next;p-next-prior = p;p-prior-next = p-next;p-next-prior = p-prior;顺序表与单链表的比较表 Error! No
21、 text of specified style in document.3 顺序表和单链表的比较顺序表单链表以地址相邻表示关系用指针表示关系随机访问，取元素O(1)顺序访问，取元素O(n)插入、删除需要移动元素O(n)插入、删除不用移动元素O(n)(用于查找位置)总结：需要反复插入、删除，宜采用链表；反复提取，很少插入、删除，宜采用顺序表。第三章、栈和队列栈栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。链栈存储结构a1/anS.an-1用不带头结点的单链表实现。类型定义同单链表。基本形态a1/anS.an-1S
22、/1. 栈空条件: S = NULL2. 栈非空3. 栈满（一般不出现）基本算法4. 入栈 Push (&s, x)bool Push ( LinkList &s, DataType x ) / 新建结点 p = (LinkList) malloc (sizeof(LNode); if ( !p ) return false; / 失败 p-data = x; / 插入栈顶 p-next = s; s = p; return true;5. 出栈 Pop (&s, &x)前提：栈非空。bool Pop ( LinkList &s, DataType &x ) if ( s=NULL ) ret
23、urn false; / 栈空 / 删除栈顶元素 p = s; s = s-next; x = p-data; free ( p ); return true;6. 栈顶元素前提：栈非空。bool Top ( LinkList &s, DataType &x ) if ( s=NULL ) return false; / 栈空 x = s-data; return true;顺序栈存储结构类似于顺序表，插入和删除操作固定于表尾。类型定义简单说，“数组 + 长度” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。const int MAXSIZE = 栈的最大容量；typedef stru
24、ct DataType elemMAXSIZE; int top; SqStack;基本形态7. 栈空条件 s.top = 0;8. 栈满条件 s.top = MAXSIZE9. 栈不空、不满基本算法10. 入栈 Push (&s, x)前提：栈不满bool Push ( SqStack& s, DataType x ) if ( s.top = MAXSIZE ) return false; / 栈满 s.elemtop = x; / 或者s.elemtop+ = x; top+; / 代替这两行 return true;11. 出栈 Pop (&s, &x)前提：栈非空bool Pop (
25、 SqStack &s, DataType &x ) if ( s.top=0 ) return false; top-; / 可用x=s.elem-top; x = s.elemtop; / 代替这两行 return true;12. 栈顶元素前提：栈非空s.elemtop-1 即是。队列队列，队头，队尾，空队列，先进先出(FIFO)。链队列：队列的链式存储结构。循环队列：队列的顺序存储结构之一。链队列存储结构/-a1-a2-an/.Q.frontQ.rearQ.frontQ.rear简而言之，“单链表 + 尾指针” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。类型定义课本P61。
26、typedef struct LinkList front; LinkList rear; LinkQueue;基本形态队列空：Q.front=Q.rear。非空队列。基本算法13. 入队列课本P62。插入队尾，注意保持Q.rear指向队尾。14. 出队列课本P62。删除队头元素，特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。循环队列存储结构简单说，“数组 + 头、尾位置” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。类型定义const int MAXSIZE = 队列最大容量;typedef struct DataType elemMAXS
27、IZE; int front, rear; / 队头、队尾位置 SqQueue;基本形态通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为 front, rear)。15. 队列空条件：Q.front = Q.rear。不能出队列。16. 队列满条件：(Q.rear+1)%MAXSIZE = Q.front （少用一个元素时）。不能入队列。17. 队列不空也不满frontreara1rearfronta3a2a4a1rearfronta3a2frontreartag:0frontreara3a4a1a2frontrea
28、rtag:1a3a4a5a1a218. 加一标志区分队列空和队列满的情况可以用满所有空间。队列空和队列满时都有Q.front=Q.rear，再用标志区分。队列空：Q.front=Q.rear and Q.tag=0；队列满：Q.front=Q.rear and Q.tag=1。基本算法19. 入队列前提：队列不满。bool EnQueue ( SqQueue &Q, DataType x ) if ( (Q.rear+1)%MAXSIZE=Q.front ) return false; / 队列满 / 入队列 Q.elem Q.rear = x; Q.rear = (Q.rear+1)%MAX
29、SIZE; return true;20. 出队列前提：队列非空。bool DeQueue ( SqQueue &Q, DataType &x ) if ( Q.front=Q.rear ) return false; / 队列空 / 出队列 x = Q.elem Q.front; Q.front = (Q.front+1)%MAXSIZE; return true;21. 队列中元素个数结论：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。int QueueLength ( SqQueue Q ) retu
30、rn (Q.rear-Q.front+MAXSIZE)%MAXSIZE;22. 用标志区分队列空和满用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下：void InitQueue ( SqQueue &Q ) Q.front = Q.rear = 0; Q.tag = 0;bool EnQueue ( SqQueue &Q, DataType x ) if ( Q.front=Q.rear and Q.tag=1 ) return false; Q.elem Q.rear = x; Q.rear = (Q.rear+1)%MAXSIZE; if ( Q.tag=0 ) Q
31、.tag = 1; / 队列非空 return true;bool DeQueue ( SqQueue &Q, DataType &x ) if ( Q.front=Q.rear and Q.tag=0 ) return false; x = Q.elem Q.front ; Q.front = (Q.front+1)%MAXSIZE; if ( Q.front=Q.rear ) Q.tag = 0; / 队列空 return true;int QueueLength ( SqQueue Q ) if ( Q.front=Q.rear and Q.tag=1 ) return MAXSIZE;
32、 / 队列满 else return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; / 队列不满(包含队列空的情况)栈和队列比较都是线形结构，栈的操作LIFO（后进先出），队列操作FIFO（先进先出）。简化的栈和队列结构在算法中使用栈和队列时可以采用简化的形式。表 Error! No text of specified style in document.4 简化的栈和队列结构简化栈简化队列结构“s + top”结构“q + front + rear”初始化top = 0;初始化front=rear=0;入栈stop+ = x;入队列qrear = x;rear = (r
33、ear+1)%MAXSIZE;出栈x = s-top;出队列x = qfront;front = (front+1)%MAXSIZE;栈顶stop-1队列头qfront栈空top = 0队列空front = rear说明：只要栈(队列)的容量足够大，算法中可以省去检查栈(队列)满的情况。栈和队列的应用23. 表达式求值参见课本P53。24. 括号匹配例：检查表达式中的括号是否正确匹配。如 ( ) 正确，( ) 则错误。分析：每个左括号都“期待”对应的右括号，匹配成功则可以消去。思路：遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或
34、者最后栈中还有未匹配的左括号，也都是匹配错误。/ 检查输入的表达式中括号是否匹配bool MatchBrackets () const int MAXSIZE = 1024; / 栈的最大容量 char s MAXSIZE; / 简化的栈结构 int top; / 栈顶 / 栈初始化 top = 0; / 检查括号是否匹配 ch = getchar(); while ( ch!=EOF ) switch ( ch ) case (, , : s top+ = ch; / 所有左括号入栈 break; case ): if ( top=0 or s -top!=( ) return false;
35、 / 栈空或右括号与栈顶左括号失配 case : if ( top=0 or s -top!= ) return false; case : if ( top=0 or s -top!= ) return false; ch = getchar(); / 取下一个字符 if ( top=0 ) return true; / 正好匹配 else return false; / 栈中尚有未匹配的左括号25. 递归程序的非递归化将递归程序转化为非递归程序时常使用栈来实现。26. 作业排队如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列。27. 按层次遍历二叉树void LevelOrder ( BinTree bt, VisitFunc visit ) const int MAXSIZE = 1024; / 队列容量(足够大即可) BinTree q MAXSIZE; / 简化的队列结构 int front, rear; / 队头、队尾 if ( ! bt ) return ; / 初始化队列，根结点入队列 front = rear = 0; q rear = bt; rear = (rear+1)%MAXSIZE; / 队列不空，则取出队头访问并将其左右孩子入队列 while ( front!=rear ) p =