算法与数据结构 期末考试复习ppt课件.ppt

《算法与数据结构 期末考试复习ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构复习2013秋季属于程序设计的一个重要内容，训练如何对数据信息进行抽象。算法与数据结构的主要内容对数据信息进行抽象，从逻辑关系上，可以得到四大类数据结构：集合线性结构（线性表、栈、队列、串、数组）树形结构图状结构或网状结构对应四种逻辑关系，均可以采用两种存储结构进行物理存储：顺序存储结构链式存储结构（指针型链表、数组型静态链表）对应四种逻辑关系，均可以设计出具体的操作方法结构的初始化、销毁，数据的查找、插入、删除、比较等对四种逻辑关系的操作方法进行了具体的编程实现，也例举了它们的一些具体应用。多项式的表示和操作离散事件系统模拟递归程序的实现文本编辑系统的设

2、计霍夫曼编码方法判定树的构造最短路径、关键路径、拓扑排序对于集合结构，研究了两种重要操作，即排序和查找第一章绪论1、基本概念和术语◆“数据结构”课程的研究内容及在计算机科学中的地位；◆数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型；◆逻辑结构和物理结构、顺序存储结构和链式存储结构；2、抽象数据类型的表示和实现◆三元组表示法；◆熟悉类c语言的语法；3、算法和算法分析◆算法的定义和5个重要特性；◆算法设计的4个要求及含义；◆算法效率的度量●渐进时间复杂度的概念；●简单算法的时间复杂度的估算；第二章线性表1、线性表的类型定义◆线性结构◆线性表的定义及特性2、线性表

3、的顺序表示和实现◆线性表的动态分配顺序存储结构◆线性表插入、删除算法，算法2.4、2.5◆插入、删除算法的平均时间复杂度的估算3、线性表的链式表示和实现◆线性链表的概念◆线性单链表的存储结构和创建、插入、删除、合并算法◆循环链表的概念、特点◆双向链表的存储结构和插入删除算法，算法2.18、2.194、一元多项式的表示与相加算法typedefstructPNode{floatcoef；//系数intexpn；//指数structPNode*next；}PNode，PLinkList；相加算法要求读懂、理解，算法2.23pabxs例如：在线性链表两个数据元素a和b间插入x,

4、已知p指针指向a。s->next=p->next;p->next=s;StatusListInsert_L(LinkList&L,inti,ElemTypee){//在位置i插入元素e；p=L;j=0;while(p&&jnext;++j}if(!p

5、

6、j>i-1)returnERROR;//指定的插入位置超界；s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}第三章栈和队列1、栈的表示和实现◆栈的概念、特点、表示和实现（顺序存储结构）；◆

7、栈的初始化、取栈顶元素、元素的入栈、出栈算法，47页；2、栈的应用◆数制转换算法，算法3.1；◆求解n阶Hanoi塔问题的递归过程和算法，算法3.5；3、队列的定义、特点◆链队列的表示和实现、元素的插入和删除算法；◆循环队列的表示和实现、元素的插入和删除算法；◆离散事件模拟过程、算法、运行结果，算法3.7；顺序栈typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;栈的存储结构StatusPush(SqStack&S,SElemTypee){if(S.top–S.base>=S.stacksiz

8、e){//栈满，追加空间；S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType))；if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//先将元素压入堆栈，后移动指针；returnOK;}StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;//堆栈为空

9、；e=*--S.top;//先移动指针,再将元素弹出堆栈；returnOK;}栈顶指针top等于栈底指针base时，栈是空栈。top123450进栈A栈满BCDEF非空栈的栈顶指针始终指向栈顶元素的下一个位置。toptoptoptoptoptop出栈123450ABCDEFtoptoptoptop=base栈空toptoptop=base123450栈空basetop=base先把元素压入堆栈，再移动指针。先移动指针，再把栈顶元素弹出。只能在栈顶进行数据元素的入栈和出栈操作。StatusEnQueue(LinkQueue&Q,QElem