论文部分内容阅读
摘要：通过多年教学实践和项目实践，以及计算机专业专升本辅导、考研辅导等各种方式和途径，总结了学生在学习中的一些比较常见的问题。如何学好数据结构这门核心的专业基础课，简单的总结方法，希望对准备相应考试、和深入学习的学生有所帮助。
关键词：数据结构；学习总结
中图分类号：TP305 文献标识码：A 文章编号：1009-3044（2018）16-0127-01
1 前提引入
“数据结构”按照课本上知识点的排列（以严蔚敏编著的教材为例），前四章主要研究线性结构，第五章主要讲解数组和广义表，可以看作是线性结构和非线性结构的一个转折章节也可以作为线性结构的拓展章节，第六章主要讲解树形结构，第七章主要讲解图形结构。第九章和第十章主要讲解数据的处理——查找和排序；本篇文章主要针对学习前七章的知识而提出一些见解。如何学好数据结构，主要从下面几个方面着手。
2 主要内容
首要原则是掌握每一章节的基本概念并要理解运用。基本概念中往往隐含着解决相关问题的基本方法。比如线性表的定义：“一个线性表是n个数据元素的有限序列”，其中n>=0；首先n=0时，线性表称为空表；n>0时，为非空表；基本操作时空表不能进行取元素和删除元素操作，其次数据元素可以简单到是一个字符如线性表L=（a，b，c，d，e，f），也可以是一条记录，这时数据元素的定义一般是抽象的结构体类型定义；最后线性表中元素是“有序”的，这里的有序并不是指递增或者递减有序，而是元素之间存在相邻顺序关系，元素的位置有序，这时就有了元素位序的概念，类似的又可以引申出前驱结点和后继结点的相关知识；基本概念中不仅描述了什么是线性表，还隐含了对线性表的基本操作问题。还有一些基本概念联系在一起记忆效果会更好，比如栈、队列和线性表，栈、队列均是受限制的线性表，并且又具有自己独特的概念，同理顺序栈、顺序队列均是操作受限制的顺序表，链栈、链队列均是操作受限制的单链表；广义表是线性表的一种推广，若广义表中元素均为不可再分的原子此时的广义表就成了线性表；联想式的记忆节省了时间提高了效率。
概念和性质最密集的是在第六章树与森林，树的概念显然是递归的，树是一种递归的数据结构，这为树的操作埋下伏笔，例如求树的高度时就可以采用递归算法；同样如结点的度、树的度、分支结点、叶子结点、树的高度等基本概念中同样蕴含着一些基本操作的题目，例如 “已知一棵树的度为3，度为1的结点个数为n1，度为2的结点个数为n2，度为3的结点个数为n3，求叶子结点的个数”，解决这类问题的关键就是把握好树的度、结点的度等基本概念的联系。二叉树的基本概念难度比较大，对于这些基本概念还要学会总结性记忆。例如：“一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。”由概念总结到二叉树的两个特点：每个结点的度小于等于2，是有序树；然而需要警惕的是总结反过来未必成立，例如：“满足这两个特点的树一定是二叉树吗？”未必，因为度小于等于2的有序树不一定是二叉树，概念中还要体现二叉树的子树需要分左子树、右子树；根据这些总结和推理有些题目就迎刃而解了，例如：“有3个结点能构造成多少种不同形态的二叉树？”很明显答案是5种，类似的题目如：“有3个结点能构造成多少中不同形态的树？”；此外想要掌握好基本概念还应该注意一些概念的别名，例如线性表又称为向量表，广义表又称为列表，哈夫曼树又称为最优二叉树、赫夫曼树，散列表又称为哈希表、杂凑表等等。
其次掌握每一种数据结构的基本性质。基本性质是解决问题的基本标准。最先接触的物理结构是顺序表，其特性是元素逻辑位置相邻其物理存放位置必相邻，即顺序表中元素占一块连续的存储单元，并且是一种随机存取的存储结构；所以常见的出题如“若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用什么存储方式最节省运算时间？ “设长度为n的线性表顺序存贮，若在它的第i-1和第i个元素之间插入一個元素， 共需移动 几个元素（1 Status push（Linkstack S， elemtype e ）
{p=（LinkStack）malloc（sizeof（SNode））；
p->data = e；
p->next = s； s=p；
return OK ；
最后学会总结基础知识并灵活运用，即使用最基础的知识解决较难的问题，常见到对线索二叉树进行遍历的算法。首先思考二叉树加线索的目的最直观的目的是便于找结点的前驱和后继，操作时就要依据线索进行遍历，可以使用前驱线索也可以使用后继线索，比如采用后继线索对中序线索化二叉树进行中序遍历。基本遍历方法即递归方法LDR，若二叉树非空则首先要找到二叉树的第一个结点，分析中序遍历的第一个结点是沿着根结点出发访问到第一个没有左孩子的结点；而后根据的后继线索逐个访问第二个结点、第三个结点直至最后一个结点。于是程序就可以这样实现：
Void inorderThrtree（BiThrTree T）
{ BiThrTree p=T；
while （p->LTag==Link） p=p->lchild；
printf（"%c"，p->data）；
while（ p->rchild）
{ if （p->RTag==Link）
{p=p->rchild；
while（p->LTag==Link） p=p->lchild；}
else p=p->rchild；
printf（"%c"，p->data）；
}
注意该算法中关键点在于if （p->RTag==Link） {p=p->rchild…}，找到第一个结点以后需要对其进行判断，因为线索二叉树中不是所有结点都有后继线索，所以需要判断语句，如果没有后继线索即p有右子树，则还是根据基本的遍历方法LDR分析，此刻p结点的后继结点是以p为根结点的右子树中序遍历下的第一个结点，结果分析问题又回到了找第一个结点上了，所以就有了p=p->rchild；while（p->Ltag==Link） p=p->lchild；此后再找第三个、第四个直至最后一个都采用同样重复判断方法。
3 总结
学好数据结构不仅仅从这几个方面着手，关键还在于勤奋和认真，多思考多动手做，这样的学生才能在各种考试中脱颖而出得到一个好成绩。
参考文献：
[1] 严蔚敏.数据结构（C语言版）[M].清华大学，1997.
[2] 李春葆.数据结构和算法教程[M].清华大学，2009.
关键词：数据结构；学习总结
中图分类号：TP305 文献标识码：A 文章编号：1009-3044（2018）16-0127-01
1 前提引入
“数据结构”按照课本上知识点的排列（以严蔚敏编著的教材为例），前四章主要研究线性结构，第五章主要讲解数组和广义表，可以看作是线性结构和非线性结构的一个转折章节也可以作为线性结构的拓展章节，第六章主要讲解树形结构，第七章主要讲解图形结构。第九章和第十章主要讲解数据的处理——查找和排序；本篇文章主要针对学习前七章的知识而提出一些见解。如何学好数据结构，主要从下面几个方面着手。
2 主要内容
首要原则是掌握每一章节的基本概念并要理解运用。基本概念中往往隐含着解决相关问题的基本方法。比如线性表的定义：“一个线性表是n个数据元素的有限序列”，其中n>=0；首先n=0时，线性表称为空表；n>0时，为非空表；基本操作时空表不能进行取元素和删除元素操作，其次数据元素可以简单到是一个字符如线性表L=（a，b，c，d，e，f），也可以是一条记录，这时数据元素的定义一般是抽象的结构体类型定义；最后线性表中元素是“有序”的，这里的有序并不是指递增或者递减有序，而是元素之间存在相邻顺序关系，元素的位置有序，这时就有了元素位序的概念，类似的又可以引申出前驱结点和后继结点的相关知识；基本概念中不仅描述了什么是线性表，还隐含了对线性表的基本操作问题。还有一些基本概念联系在一起记忆效果会更好，比如栈、队列和线性表，栈、队列均是受限制的线性表，并且又具有自己独特的概念，同理顺序栈、顺序队列均是操作受限制的顺序表，链栈、链队列均是操作受限制的单链表；广义表是线性表的一种推广，若广义表中元素均为不可再分的原子此时的广义表就成了线性表；联想式的记忆节省了时间提高了效率。
概念和性质最密集的是在第六章树与森林，树的概念显然是递归的，树是一种递归的数据结构，这为树的操作埋下伏笔，例如求树的高度时就可以采用递归算法；同样如结点的度、树的度、分支结点、叶子结点、树的高度等基本概念中同样蕴含着一些基本操作的题目，例如 “已知一棵树的度为3，度为1的结点个数为n1，度为2的结点个数为n2，度为3的结点个数为n3，求叶子结点的个数”，解决这类问题的关键就是把握好树的度、结点的度等基本概念的联系。二叉树的基本概念难度比较大，对于这些基本概念还要学会总结性记忆。例如：“一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。”由概念总结到二叉树的两个特点：每个结点的度小于等于2，是有序树；然而需要警惕的是总结反过来未必成立，例如：“满足这两个特点的树一定是二叉树吗？”未必，因为度小于等于2的有序树不一定是二叉树，概念中还要体现二叉树的子树需要分左子树、右子树；根据这些总结和推理有些题目就迎刃而解了，例如：“有3个结点能构造成多少种不同形态的二叉树？”很明显答案是5种，类似的题目如：“有3个结点能构造成多少中不同形态的树？”；此外想要掌握好基本概念还应该注意一些概念的别名，例如线性表又称为向量表，广义表又称为列表，哈夫曼树又称为最优二叉树、赫夫曼树，散列表又称为哈希表、杂凑表等等。
其次掌握每一种数据结构的基本性质。基本性质是解决问题的基本标准。最先接触的物理结构是顺序表，其特性是元素逻辑位置相邻其物理存放位置必相邻，即顺序表中元素占一块连续的存储单元，并且是一种随机存取的存储结构；所以常见的出题如“若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用什么存储方式最节省运算时间？ “设长度为n的线性表顺序存贮，若在它的第i-1和第i个元素之间插入一個元素， 共需移动 几个元素（1
{p=（LinkStack）malloc（sizeof（SNode））；
p->data = e；
p->next = s； s=p；
return OK ；
最后学会总结基础知识并灵活运用，即使用最基础的知识解决较难的问题，常见到对线索二叉树进行遍历的算法。首先思考二叉树加线索的目的最直观的目的是便于找结点的前驱和后继，操作时就要依据线索进行遍历，可以使用前驱线索也可以使用后继线索，比如采用后继线索对中序线索化二叉树进行中序遍历。基本遍历方法即递归方法LDR，若二叉树非空则首先要找到二叉树的第一个结点，分析中序遍历的第一个结点是沿着根结点出发访问到第一个没有左孩子的结点；而后根据的后继线索逐个访问第二个结点、第三个结点直至最后一个结点。于是程序就可以这样实现：
Void inorderThrtree（BiThrTree T）
{ BiThrTree p=T；
while （p->LTag==Link） p=p->lchild；
printf（"%c"，p->data）；
while（ p->rchild）
{ if （p->RTag==Link）
{p=p->rchild；
while（p->LTag==Link） p=p->lchild；}
else p=p->rchild；
printf（"%c"，p->data）；
}
注意该算法中关键点在于if （p->RTag==Link） {p=p->rchild…}，找到第一个结点以后需要对其进行判断，因为线索二叉树中不是所有结点都有后继线索，所以需要判断语句，如果没有后继线索即p有右子树，则还是根据基本的遍历方法LDR分析，此刻p结点的后继结点是以p为根结点的右子树中序遍历下的第一个结点，结果分析问题又回到了找第一个结点上了，所以就有了p=p->rchild；while（p->Ltag==Link） p=p->lchild；此后再找第三个、第四个直至最后一个都采用同样重复判断方法。
3 总结
学好数据结构不仅仅从这几个方面着手，关键还在于勤奋和认真，多思考多动手做，这样的学生才能在各种考试中脱颖而出得到一个好成绩。
参考文献：
[1] 严蔚敏.数据结构（C语言版）[M].清华大学，1997.
[2] 李春葆.数据结构和算法教程[M].清华大学，2009.