数据结构-资源试题库及解析《数据结构》期末考试试卷D卷-简答题4-配套说课稿.docx

大数据技术与应用专业教学资源库 《数据结构》课程说课稿 《数据结构》期末考试试卷D卷-简答题4 主讲：章万静  序号 PPT 说课稿 幻灯片 1 大家好。我是《数据结构》课程的主讲教师——章老师。 下面我们开始重点分析试卷D中的题目。 幻灯片 2 我们来看一下简答题。 幻灯片 3 简答题的第4题。 将下图中的树形结构采用孩子链表表示法进行存储。这道题5分。 我们来看看这棵树，树中共有10个结点，我们可以采用双亲表示法、或者孩子链表表示法来存储树形结构。本题要求采用孩子链表表示法来进行存储。 幻灯片 4 在使用孩子链表表示法的时候，要注意以下两点： 1、树中所有的结点存放在一个顺序结构中，即存放在数组的data域中。 2、树中每个结点设置一个孩子链表，孩子链表的头指针链接在其父亲结点的后面，即存放在数组相应的指针域中。 下面，我们来具体分析这棵树采用孩子链表表示法时如何进行存储？ 第一步，在数组的data域中存储各个结点的信息。我们将树中从根结点开始，从上到下，从左到右，所有的10个结点按顺序存放，下标从0开始，先存放第一层的结点，根结点A，然后第二层的结点，B，C，D，最后存放第三层的结点，E，F，G，H，I，J，data域存放结束后，A存放在下标为0的空间里，J存放在下标为9的空间里。 第二步，在每个有孩子的结点后面链接一个单链表，依次存放各个孩子的相关信息，需要注意的是单链表的结点中依次存放的是孩子结点在数组中的下标。 A结点有3个孩子，B，C，D。所以在结点A的后面链接一个单链表，有3个链结点，分别存放B在数组中的下标1， C在数组中的下标2， D在数组中的下标3，最后一个结点3的指针域中存放一个空指针。 B结点有2个孩子，E，F。所以在结点B的后面链接一个单链表，有2个链结点，分别存放E在数组中的下标4， F在数组中的下标5，最后一个结点5的指针域中存放一个空指针。 C结点有3个孩子，G，H，I。所以在结点C的后面链接一个单链表，有3个链结点，分别存放G在数组中的下标6， H在数组中的下标7， I在数组中的下标8，最后一个结点8的指针域中存放一个空指针。 D结点有1个孩子，J。所以在结点D的后面链接一个单链表，有1个链结点，存放J在数组中的下标9，最后一个结点9的指针域中存放一个空指针。 其他结点E，F，G，H，I，J都没有孩子，所以这些结点后面的指针域中都存放一个空指针。 这样，树中10个结点，采用孩子链表表示法就存储完毕，各个结点在数组中顺序存储，每个结点后面链接着其所有孩子的链结点。 幻灯片 5 本次微课就介绍到这里，希望大家好好理解与掌握。谢谢观看。