波动或事先无法确定长度的线性表。 授课时须强调线性表应用的广泛性。建议多举后续课程上将要学到的内容为例。例如, 存储管理本质上就是利用线性表管理可利用空间:程序设计语言编译器中的符号表也是典型 的线性表:散列方法则是把顺序表和链表结合起来的一种数据结构。 6.课后练习和实习 作为教学的重要一环,课后练习和上机实习帮助学生巩固课堂所学理论知识,训练学生 创新思维能力训练、工程实践能力。 线性表部分可以安排3-4道书面作业,也可采用 ACM/ICPC程序竞赛题库POJ系统安 排1-2道的实习题来巩固线性表部分的知识。例如,下面的ACM题目 http://acm.pku.edu.cn/judgeoNline/problem?Id=1012(Joseph) htt/ acm.pku.edu. cn/Judge Online/problem?id=1153(内存分配) 7.教学案例 以单链表删除元素及其复杂性分析为例 下面的算法给出了删除单链表第i个结点的代码,相应的操作过程参见下面的图示 bool InkList<T>: delete(int,∥假定线性表的元素类型为T template <class T> ∥p是第i个结点的前驱 if(p= NULL)i ∥待删结点不存在,即给定的i大于当前链中元素个数 cout<< the deletion point is illegal"<<endl ∥q是真正待删结点 if (q= tail) ∥待删结点为尾结点,则修改尾指针 if (q I=null)i ∥删除结点q并修改链指针 p->next =q->next, return true “时 a)删除前指针情况 b)删除后指针情况 授课时根据情况可能需要补充动态存储管理的问题。删除单链表中的结点,可以使用 delete命令释放被删结点所占用的空间,否则这些占用空间会变成存储空间中无法利用的垃 圾,影响随后的再使用。 delete是C++程序语言为动态存储管理提供的两个重要命令,与C 语言标准函数库中提供的free函数具有同样的功能。 授课时上面的图示最好改用动画为好。此外,需要强调的是在链表的位置i进行删除操 作时,需要先定位到位置i-1的结点,这也是某些应用中需要在抽象数据类型中增加一个表 示当前位置的成员的原因,具体到用单链表方式实现时,通常保持当前位置的前一个指针以 方便操作。否则在插入和删除前均需一个时间代价为O)的定位操作。 8.总结波动或事先无法确定长度的线性表。 授课时须强调线性表应用的广泛性。建议多举后续课程上将要学到的内容为例。例如， 存储管理本质上就是利用线性表管理可利用空间；程序设计语言编译器中的符号表也是典型 的线性表；散列方法则是把顺序表和链表结合起来的一种数据结构。 6．课后练习和实习 作为教学的重要一环，课后练习和上机实习帮助学生巩固课堂所学理论知识，训练学生 创新思维能力训练、工程实践能力。 线性表部分可以安排 3-4 道书面作业，也可采用 ACM/ICPC 程序竞赛题库 POJ 系统安 排 1-2 道的实习题来巩固线性表部分的知识。例如，下面的 ACM 题目： http://acm.pku.edu.cn/JudgeOnline/problem?id=1012 （Joseph） http://acm.pku.edu.cn/JudgeOnline/problem?id=1153（内存分配） 7．教学案例 以单链表删除元素及其复杂性分析为例。 下面的算法给出了删除单链表第 i 个结点的代码，相应的操作过程参见下面的图示。 template <class T> // 假定线性表的元素类型为 T bool lnkList<T>:: delete (int i) { Link<T> *p, *q; p = setPos(i-1); // p 是第 i 个结点的前驱 if (p == NULL ) { // 待删结点不存在，即给定的 i 大于当前链中元素个数 cout << " the deletion point is illegal"<<endl; return false; } q = p->next; // q 是真正待删结点 if (q == tail) // 待删结点为尾结点，则修改尾指针 tail = p; if (q != NULL) { // 删除结点 q 并修改链指针 p->next = q->next; delete q; } return true; } a) 删除前指针情况 b) 删除后指针情况 授课时根据情况可能需要补充动态存储管理的问题。删除单链表中的结点，可以使用 delete 命令释放被删结点所占用的空间，否则这些占用空间会变成存储空间中无法利用的垃 圾，影响随后的再使用。delete 是 C++程序语言为动态存储管理提供的两个重要命令，与 C 语言标准函数库中提供的 free 函数具有同样的功能。 授课时上面的图示最好改用动画为好。此外，需要强调的是在链表的位置 i 进行删除操 作时，需要先定位到位置 i-1 的结点，这也是某些应用中需要在抽象数据类型中增加一个表 示当前位置的成员的原因，具体到用单链表方式实现时，通常保持当前位置的前一个指针以 方便操作。否则在插入和删除前均需一个时间代价为 O(n)的定位操作。 8．总结