教学实习报告2

实验名称： 单链表反向输出

实验目的：

1. 深入理解链表的组成特点，掌握链表的单向访问特性。 2. 掌握基本的循环结构，理解链表遍历的循环结束条件。

3. 掌握链表的遍历的核心语句，以及使学生更进一步地提高程序调试能力。

实验内容：

编写一个子函数用于输出一个单向链表，其中形参为该链表的头结点地址，在主函数中调用该子函数，对其进行调试和验证。并自行编写代码实现单链表的逆向输出。 下面是我所编写的子程序代码：

void output(EMP *p)/*用于实现单向链表的单向输出*/ { p=p->next;

while(p!=NULL) { printf(

p=p->next;

}

EMP* found(EMP* p,int n)/*遍历链表并返回第n个数据结点的地址*/ { return (p->next==NULL||n==1)?p:found(p->next,n-1); /*运用栈的思想*/ }

void output(EMP *p) { p=p->next; while(p!=NULL) {

printf(

} }

该程序是在实验一的基础上进行编辑的，为了方便理解，先将上次实验的主要代码呈现如下： ······ ······

······

long creat(EMP *head)；/*创建函数已经在上次试验中定义过了，具体代码不再赘述*/ void main()/*实现链表的逆向排列*/ { int i; long n; double t;

EMPlist.head=(EMP*)malloc(sizeof(EMP));/*参数的初始化*/

EMPlist.head->next=NULL; EMPlist.rear=NULL; EMPlist.len=0; printf(

/*调用创建函数*/

printf(

output(EMPlist.head);/*调用输出函数，实参为已建立链表的表头指针*/ if(n>=0)

{

putchar('\n');

for(i=0;i

{ t=found(EMPlist.head->next,i+1)->x;

found(EMPlist.head->next,i+1)->x=found(EMPlist.head->next,n-i)->x;/*由于需要大

量的调用函数，程序的时间代价太大*/ found(EMPlist.head->next,n-i)->x=t; }

基本思想：

考虑到单向链表的单向访问特性，欲实现链表的单向输出，应该在给定头结点的基础上从前往后一次访问。

对于要反向输出一个单向链表，我认为基本思想就两个，使其虚拟有双向的特性，这个可以通过数组实现，当然也可以编写found函数进行虚拟数组的输出乃至排序。第二个思想就是改变其访问方向，这个一方面可以通过链表内容的转置实现，另一方面也可以通过直接改变指针的指向实现。在此我选择比较简单的虚拟数组手法，借助found函数进行内容的逆向输出。

Output（）函数的具体的流程图如下：

}

printf(

转置的基本思想：

采用虚拟数组，即运用对数组进行转置的思想，在不改变原链表的各节点的指向的连接方式的前提下，更换节点内的数据域的各成员的数值。然后调用输出函数即实现本程序的要求。

经典针对数组的转置代码：

for(i=0;i

在本程序中我完全是移植了这段代码，链表的（内容）转置。

但是这种思想的有效实现是要在借助found函数的成功编写的基础上的。在这里，found 函数的作用就相当于数组的

验证数据如下（采用实验一的结果作为本程序的验证条件）：

输出结果：

转置前：

10 58 97 105 135 20 【换行】

转置后：

20 135 105 97 58 10【换行】

实验总结：

本次实习过程中没有遇到太大的困难，从思路构架，代码编写到调试和验证，没有遇到什么问题。我想一个程序编的效率高不高与编程人员对程序本身的理解和思考是有直接联系的。所以在以后的实习过程中，要多思考，多总结经验，这样才能真正的有所进步。另外，从这个程序我们可以发现在实际的程序算法的构思中，时间的代价和空间代价，以及代码的长度都有一定的相互制约关系，在今后的程序编写中应该注意这个问题。