数据结构复习指导

《数据结构复习指导》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构复习指导unabletoconnectGoogletranslate233李建霖-2014年11月2日数据结构复习指导1前言本文谈题目，谈算法多一些，数据结构这个课程我自己不像是大学物理，工科数学分析或者是数字电路通过上课认真听讲记笔记，通过考前进行大量应试训练获得应试技巧学习并且顺利通过期末或是免修考试，让我写一个可操作的应试性速成指南也确实有些为难，不过还好，我们学院的数据结构期末卷子应试性弱，更加强调对算法的理解和对相关素养的考察。大家要将功夫放在平时，我们学院的数据结构期末考卷相比上学期程序设计考卷没有那么强的应试性，只有两种题型，一

2、是对给定问题演示经典算法的中间结果，二是算法设计。只要平时上机认真写，期末是不用像数学物理一样过分备考，可以通过平时的积累完成期末考试的挑战。本文根据课本，为大家整理了数据结构的知识要点，并结合我自己的学习体会总结了一些应试技巧和对要点的理解。大家使用时可以三个不同的层次，“及格就行”、“完成教学大纲的要求”和“比较系统的掌握和理解一些重要的数据结构”，第一个层次主要谈应试性的技巧，使用波浪线。第二个层次不使用特殊格式，第三个层次主要谈我我自己对数据结构理解和要求，使用下划线。本文还有附录是从网上找到的课本中所有例题的c语言实现和一些数据结构基本操作的

3、实现，”清华严蔚敏《数据结构》的全部代码实现C语言.doc”上有课本上所有例题的代码，也有数据结构基本操作。”数据结构源代码(C实现).pdf”则是把各个数据结构的基本操作整理得比较好。希望大家把重要部分掌握，能在期末考试编程题中轻松答出。关于课本，课本有些地方写的太罗嗦又不够严谨，有时候读起来可能有些费劲，有些地方又不把问题实质讲清楚，只是就事论事。大范围推荐竞赛书籍没有意义，对课本有更高需求的同学可以来找我借书。如果大家在学习数据结构遇到困难，也欢迎大家与我交流。后面会附上联系方式。如有疏漏，欢迎批评指正。联系方式：李建霖lijianlin1995

4、@gmail.com130-5758-5275(拒接为vc++用户解答问题)左光胜QQ:1643190721152-5181-6863括弧脾气好大帅哥括弧完数据结构复习指导2第零部分绪论第一张绪论一些需要记忆的概念见课本P131.算法的概念:算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。2.算法的五个重要特征:有穷性、确定性、可行性、输入、输出。3.算法的四个设计要求:正确性、可读性、健壮性和低存储量需求。第一部分线性数据结构第二章线性表带头结点的单链表的操作是基本功要掌握。我个人猜测这一章节的大部分基本操

5、作和课本上给出的算法都是考试中的常见考点。单链表排序可以写插入排序，但是我其实更推荐写归并排序。归并排序中merge函数除了本身有两个有序表求并集的功能，稍作改动还可以变成两个有序表求交集，要理解归并排序。合并操作实现见课本P21算法2.2[例1]（10分）假设一带头结点的无序单链表L，表中结点数据元素为整型，编写函数，将其调整为递增有序的链表。先写出算法思想，再给出程序代码。算法思想：可采用插入排序方法，程序略。[例2]（10分）已知有一个带头结点的单链表，元素值由正数、负数组成，编写函数，将所有的负数结点移到正数结点前面，要求T(n)=O(n)。先

6、写出算法思想，再给出程序代码。算法思想：可采用将所有的负数结点从链表中删除，再插入头结点之后，程序略。第三章栈和队列栈和队列是作为数据结构的概念，含义非别是后进先出表和先进先出表。所以都有链式和顺序两种实现方式，课本称为链式栈（不作要求）、顺序栈、链队列、顺序队列，几个基本操作的实现需要掌握。常考问题•数值转换：比较简单。课本P48算法3.1•表达式求值课本P53算法3.4数据结构复习指导3表达式求值有两种做法，一是可以由中缀表达式转化为后缀表达式，二是可以用两个栈直接对中缀表达式求值。具体程序见课本P53，需要掌握。实际上OPTR栈是一个单调栈，始

7、终维护了栈内运算符优先级不严格单调递增，由于出栈式使运算符参与运算，所以先出栈的运算符是优先级高的运算符，即保持了优先级高的运算符先运算。[例3]（7分）应用栈操作求解算术表达式：#(26+24/6)*(9-1)#,画出栈的变化过程。执行步骤步骤OPTR栈OPND栈输入字符1##(26+24/6)*(9-1)#2#((26+24/6)*(9-1)#3#(2626+24/6)*(9-1)#4#(+26+24/6)*(9-1)#5#(+262424/6)*(9-1)#6#(+/2624/6)*(9-1)#7#(+/262466)*(9-1)#8#(+264

8、)*(9-1)#9#(30)*(9-1)#10#30)*(9-1)#11#*30*(9-1)#