2011数据结构之线性表.pptVIP

线性表 濮阳市第一高级中学 王晓斌 如图2.3是线性表 (a1,a2,a3,a4,a5,a6,a7,a8) 对应的链式存储结构示意图。 当然必须将第一个结点的地址160 放到一个指针变量如 H 中，最后一个结点没有后继, 其指针域必需置空，表明到此结束，这样就可以从第一个结点的地址开始“顺藤摸瓜”，找到每个结点。 作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用图2.4的形式而不用图2.3的形式表示。 通常我们用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中， 头指针为“NIL”则表示一个空表。 110 a5 200 … … 150 a2 190 160 a1 150 … … 190 a3 210 200 a6 260 210 a4 110 … …. 240 a8 Nil … ... 260 a7 240 单链表的建立与遍历 单链表的特点： (1) 在单链表上插入、删除一个结点，必须知道其前驱结点。 (2) 单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。 下面通过具体的例子来看单链表的建立与遍历。 例4 在线性表头位置插入新元素 键入简化的学生记录（如只有学生的学号），把它们组成线性链表，并输出各记录信息。要求每一新元素都插入到已生成链表的表头位置。 [算法分析]： 可以分两部分来实现。第一部分是依次键入学号，创建新的表元素，并插入到表头位置。当遇到输入结束标志后，即已生成了所要的线性链表。第二部分是由表头开始，“顺藤摸瓜”遍历所有表元素并输出学号，直到表尾。要设置两个指针变量，其一总是指向表头位置，其二指向新的表元素，兼作遍历表时的工作量。不妨设在程序运行中先后键入4名学生的学号2，5，4，1，以键入32767（最大的整数）作为结束标志。 program exampel2_4; {linked list generation—to the head of the list} type natural=1..Maxint; pointer =^Item; Item=record number : natural; next : pointer; end; var head, temp: pointer; n: natural; begin writeln(‘Enter students’’ numbers. 32767 to stop:’); head:= nil; read(n); while nMaxint do begin new(temp); with temp^ do begin number:=n; next:=head; end; {上一行的with……end部分等同于Temp ^. number:=n; Temp ^.next:=head;} head:=temp; read(n); end; writeln(‘The output:’); temp:=head; while tempnil do begin write(temp^. number:8); temp:=temp ^.next; end; end. [回顾与思考]： 学习线性链表操作的一个有效方法是画出链表以及指针变量的变化情况。因为指针变量所维护的是地址，表元素之间的链接也靠的是地址，所以地址一乱就整个乱了套。本程序运行后所生成的线性链表及指针变量位置如图2-6： 从输出结果来看，是以反序输出学号，即体现了“先进后出”的规律。 如果每次新的表元素插入到表尾，则输出时体现“先进先出”的规律。 例5 编写插入表尾的链表生成及遍历程序。 [算法分析]：同样以最简化的学生信息（只有学号）为例来说明在原线性链表的表尾插入新的元素。为了提高执行速度，除了用表头指针变量外还增加一个总指向表尾的指针变量。这样一个指向表头一个提向表尾，操作起来就比较方便了。另外还要对表为空及非空情形进行判断并作相应处理。 program exampl2_5;{linked list generation-to the tail of the list} type natural=1..MaxInt; pointer=^item; item=record number: natural; next : pointer; end; var head, temp, Tail: pointer; n: natural; begin writeln(Enter students numb