2024年4月30日发(作者：)

计算机科学２００８Ｖｏ１．３５ＮＱ．１　１　

基于链表的同构化首尾排序新算法　

——

“程序设计’’与“数据结构＂课程的融合创新案例研究　

周启海　

（西南财经大学信息技术应用研究所　成都６１００７４）　（西南财经大学经济信息２１－＿程学院　成都６１００７４）　

摘要依据同构化基本原理，研究和发现了基于传统内部首尾排序算法的同构化特点与本质；进而，利用其同构化　

特点与本质，提出了几种基于链表的首尾排序新算法；从而，进一步深化和推广了首尾排序算法的应用方式与实用范　

围；同时，也为“程序设计”、“数据结构”的课程融合、教学改革、教育创新提供了重要研究案例。　

关键词　同构化，链表，首尾排序，算法，课程融合　

Ｎｅｗ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　Ｓｏ￣ｉｎｇ　ｆｒｏｍ　Ｈｅａｄ　ａｎｄ　Ｒｅａｒ　Ｂａｓｅｄ　ｏｎ　Ｃｈａｉｎ　Ｌｉｓｔ　

Ｆｕｓｄｅ　ａｎｄ　Ｉｎｎｏｖａｔｄｅ　Ｃａｓｅ　Ｓｔｕｄｙ　ｏｆ“Ｐｒｏｇｒａｍ　Ｄｅｓｉｇｎ’’ａｎｄ“Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅ’’Ｓｕｂｊｅｃｔｓ　

Ｚｈｏｕ　Ｑｉ—ｈａｉ　

（Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ａｐｐｌｉｃａｔｉｏｎ，Ｓｏｕｔｈｗｅｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｉｎａｎｃｅ　ａｎｄ　Ｅｃｏｎｏｍｉｃｓ，Ｃｈｅｎｇｄｕ　６１００７４，Ｃｈｉｎａ）　

（Ｓｃｈｏｏｌ　ｏｆ　Ｅｃｏｎｏｍｉｃ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｏｕｔｈｗｅｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｉｎａｎｃｅ　ａｎｄ　Ｅｃｏｎｏｍｉｃｓ，Ｃｈｅｎｇｄｕ　６１００７４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ　Ａｃｃｏｒｄｉｎｇ　ｔＯ　ｉｓｏｍｏｒｐｈｉｃ　ｆｕｎｄａｍｅｎｔａｌ　ｐｒｉｎｃｉｐｌｅｓ，ｔｈｅ　ｉｓｏｍｏｒｐｈｉｃ　ｃｈａｒａｃｔｅｒｓ　ａｎｄ　ｎａｔｕｒｅｓ　ｏｆ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｓｏｒ—　

ｔｉｎｇ　ｆｒｏｍ　ｈｅａｄ　ａｎｄ　ｒｅａｒ　ｂａｓｅｄ　ｏｎ　ｔｒａｄｉｔｉｏｎａｌ　ｉｎｔｅｒｎａｌ　ｓｏｒｔｉｎｇ　ｗｅｒｅ　ｓｔｕｄｉｅｄ　ａｎｄ　ｆｏｕｎｄ．Ｆｕｒｔｈｅｒ，ｓｅｖｅｒａｌ　ｎｅｗ　ａｌｇｏｒｉｔｈｍｓ　

ｆｏｒ　ｓｏｒｔｉｎｇ　ｆｒｏｍ　ｈｅａｄ　ａｎｄ　ｒｅａｒ　ｂａｓｅｄ　ｏｎ　ｃｈａｉｎ　ｌｉｓｔｓ　ｗｅｒｅ　ａｄｖａｎｃｅｄ　ｂｙ　ｕｓｉｎｇ　ｔｈｅｉｒ　ｉｓｏｍｏｒｐｈｉｃ　ｃｈａｒａｃｔｅｒｓ　ａｎｄ　ｎａｔｕｒｅｓ．　

Ｔｈｅｒｅｆｏｒｅ，ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ　ｆｏｒｍｓ　ａｎｄ　ａｐｐｌｉｅｄ　ｒａｎｇｅｓ　ｏｆ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｓｏｒｔｉｎｇ　ｆｒｏｍ　ｈｅａｄ　ａｎｄ　ｒｅａｒ　ｗｅｒｅ　ｄｅｅｐｅｎｅｄ　ａｎｄ　ｅｘ—　

ｐｅｎｄｅｄ．Ｐｒｏｖｉｄｅｄ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｓｔｕｄｙｉｎｇ　ｃａｓｅ　ｆｏｒ　ｆｕｓｉｎｇ　ｓｕｂｊｅｃｔｓ，ｔｅａｃｈｉｎｇ　ｒｅｆｏｔｉｎ　ａｎｄ　ｉｎｎｏｖａｔｉｎｇ　ｅｄｕｃａｔｉｏｎ　ｏｆ“Ｐｒｏｇｒａｍ　

Ｄｅｓｉｇｎ”ａｎｄ“Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅ”．　

Ｋｅｙｗｏｒｄｓ　Ｉｓｏｍｏｒｐｈｉｃ，Ｃｈａｉｎ　ｌｉｓｔ，Ｓｏｒｔｉｎｇ　ｆｒｏｍ　ｈｅａｄ　ａｎｄ　ｒｅａｒ，Ａｌｇｏｒｉｔｈｍ，Ｆｕｓｉｎｇ　ｓｕｂｊｅｃｔｓ　

１　引言　

化首尾排序算法的实用范围与应用方式，并兼作“数据结构”　

与“程序设计”课程的课程融合、教学改革、教育创新案例研　

排序（即按给定判据使所论数据对象集各元素有序化），　

究。　

分为基于内存的内（部）排序，与面向外存的外（部）排序，且内　

排序常是外排序的基础。　

２基于数组的择换排序算法　

排序问题，历来是计算机科学中重要基础问题，是教学研　

把找最大数、最小数的算法思想分别应用于排序，可产生　

究（例如，它可作“数据结构”、“程序设计”的课程融合、教学　简洁明快、效率较高的择换排序算法；而把找最大数、最小数　

改革、教育创新的重要研究内容之一）、算法设计、系统开发与　的算法思想同时应用于排序，将催生巧妙简明、效率更高的首　

应用实践，既密切相关，又屡见不鲜的重要基本内容＿１　］。数　

尾排序算法ｌ＿３］。　

组是人们最常见、最常用、最习惯的内排序工具。令人惊叹的　

事实上，采用数组数据结构的首尾排序算法，基于、巧于、　

是，它使许多人长期来误认为数组似为唯一好用的内排序工　高于择换排序算法。它的处理特点是：　

具。但对那些采用链表作为主体数据结构的理论研究课题与　

（１）其处理数据集的当前处理范围，是分别从其首、尾两　

实际应用问题，而所论课题性质与问题场景又涉及其所论数　

端向其对称中心元，同步、相向、同时步进式收缩。　

据集的频繁增删、动态排序、顺序查找与随机检索等基本运算　

（２）首尾排序算法在其第　（一１，２，…，Ｅｎ／２］）遍齐头并进　

时，倘若再机械地沿袭通常基于数组的内排序方法，则势必将　

的首、尾双向择换处理中，把从当前处理数据集中同时所获得　

因其“作为目标数据处理场的链表与作为中间数据处理场的　的第ｉ小者、第ｉ大者，分别使之到所论数组的对称位置（即　

数组之间，必定存在且不可避免的数据对倒”所付出的大量时　

第　、第　一　＋１位），则可产生排序效率比文献［５］择换法提　

间开销，而严重降低解决所论课题与问题相关处理的算法效　

高近一倍的首尾法。　

率。此时，别开生面、新颖明智地采用的基于链表的排序算法　

（３）应特别注意“使第ｉ小者、第ｉ大者分别到其位操作”　

（例如：本文所给出的基于链表的首尾排序算法，或者文献［５］　

的新特点——如果第ｉ大者恰在到其位前的第ｉ小者位置，　

所给出的基于链表的择换排序算法），无疑是有效提高解决所　就必须“首先，使第ｉ小者到其位；然后，重新标记第ｉ大者新　

论课题与问题相关处理算法效率的可行之路。　

的所在位置；最后，才能使第ｉ大者到其位（即：新的所在位　

限于篇幅，本文在此仅以递增有序化输出任给ｎ（＜ｌＯ０）　

置）”；否则，就会出现“错到其位”的误操作。　

个自然数为例，阐明基于链表的首尾排序新算法，以扩展和深　据此，首尾排序算法可同构化描述表征如下：　

周启海教授，博（硕）士生导师，主要研究方向为计算几何、算法研究与应用、财经计算、同构化信息处理等。　

・

２２９・　

算法Ｅｇ０１　｛基于数组的首尾排序算法｝　

（｛ｉ，ｊ，ｋ，Ｍｉｎ，Ｍａｘ，ｎ，ｐｌ，ｐ２：整型；ａ：整型数组［１．．１ＯＯ］））；｛全局变　

量定义）　

＞＞＞｛算法开始｝　

＠：＼＼输出”输入数据个数：”；输入１３．／／　

直到０＜ｎ且ｎ＜１００；｛容错输入）　

对ｉ一１，ＴＲＵＮＣ（ｎ／２＋０．５）＠：＼＼｛排序遍数控制｝　

Ｍｉｎ＇￣ａ［－ｉ］；ｐ１一ｉ；｛标记初始第ｉ小者）　

Ｍａｘ＇￣Ｍｉｎ；ｐ２一ｐ１；ｋ—ｒｒｉ＋１；｛标记初始第ｉ大者｝　

对ｊ—ｉ＋１，ｐ２＠：（比较次数控制｝　

如果Ｍｉｎ＞ａ［ｊ］｛当前数据较小？）　

Ｔ：＼＼ｐ１＋－ｊ；Ｍｉｎ￣－ａＥｊ］／／｛标记当前最小者）　

Ｆ：如果Ｍａｘ＜ａ［ｊ］｛当前数据较大？｝　

Ｔ：＼＼ｐ２—ｊ；Ｍａｘ￣－－ａＥｊ］／／；｛标记当前最大者）　

如果ｐｌ＜＞ｉ（第ｉ小者不在其位？｝　

Ｔ：＼＼ａ［ｐ１］＂－－ａＦｉ］；ａ［ｉ］￣Ｍｉｍ｛使第ｉ小者到其位）　

如果ａ［ｐ１］一Ｍａｘ｛交换后为第ｉ大者？（注：此时第ｉ大　

者，已非ａ［ｐ２］）｝　

Ｔ：ｐ２一ｐｌ｛标记第ｉ大者新位（警告：须使第ｉ大者，又　

是ａ［ｐ２］）｝　

／／；　

如果ｐ２＜＞ｋ｛第ｉ大者不在其位？｝　

Ｔ：＼＼ａＥｐ２］￣ａＥｋ］；ａ［ｋ］￣Ｍａｘ／／；｛使第ｉ大者到其位）　

对ｉ—ｌ，ｎ一１＠：｛数据个数控制）　

输出ａ［．］＿｛递增输出各有序化数据）　

行输出ａ［ｎ］；　

！！！（算法结束｝　

３首尾排序算法的根本特点与同构本质　

本文作者依据自己提出的同构化基本原理　］，研究并发　

现了择换排序算法的根本特点与同构本质如下：　

①所论数据最小者、最大者的比较择选，只利用了存储这　

些数据的变量本身（此处为下标变量），而与其所在位置无关　

（即下标）；　

②当前最小者、最大者应在位置，则只利用了标记这些最　

小者、最大者原位置的变量本身（此处为标记其下标位置的标　

记变量），而与其所具数值无关；　

③把当前最小者、最大者分别交换到其应在位置，可不必　

打乱原变量序列的顺序；　

④必须有效解决“占位冲突”问题：在递增有序化中，当　

“使第ｉ小者到其位”的交换处理后，为确保“使第ｉ大者到其　

位”，必须切实解决交换处理中可能常的“大（者）占小（者）位　

（置）”的占位冲突问题；而在递减有序化中，当“使第ｉ大者到　

其位”的交换处理后，为确保“使第ｉ小者到其位”，必须切实　

解决交换处理中可能常的“小（者）占大（者）位（置）”的占位冲　

突问题。　

据此，可得出结论：只要能分别同构化地正确处理上述４　

个基本操作（即：当前最小者、最大者挑选；当前最小者、最大　

者位置标记；当前最小者、最大者分别交换到位；有效解决“占　

位冲突”），就并非一定要采用数组来实现首尾排序算法。事　

实上，链表与数组同为线性表的同构化本质属性，就从根本上　

决定了链表必定应该、而且可以同样用来解决排序问题。　

应当指出：　

（１）因基于链表的首尾排序处理同构化主要特性，是基于　

“首一中一尾”模式的双向、同时、同步有序化处理，故其首选　

数据结构理所当然应为双向链表，方可有利于对“首一中”方　

・

２３０・　

向与“中一尾”方向的双向有序化。　

（２）原采用数组作数据结构的首尾排序处理时，其数据范　

围对称中心可用数组下标位置——“首、尾下标值和之半”来　

直接确定。但这种数据范围对称中心的直接算术计算定位　

法，显然已不能简单移植到采用链表作数据结构时的首尾排　

序数据处理（因为此时已无法通过直接算术计算来确定数据　

范围对称中心的位置），而必须另行采用跟踪标记当前数据处　

理范围的“首元指针”与“尾元指针”的动态取值情况来描述。　

因此，若采用双向链表作为数据结构描述工具，并注意其　

数据范围对称中心确定处理的特定需要与特殊处理，则文献　

［５］所论“基于链表的结点插删、结点标记、（结点的数据字段）　

变量标记的３种同构化择换排序新算法”，显然应该而且可以　

对应地推广为基于双向链表的结点插删、结点标记、（结点的　

数据字段）变量标记的３种同构化首尾排序新算法。　

４基于变量标记的双向链表同构化首尾新算法　

为省篇幅，基于双向链表的结点插删同构化首尾排序新　

算法Ｅｇ０１、基于双向链表结点标记的同构化首尾排序新算法　

Ｅｇ０２均予略（事实上，只要借鉴文献［５］及本文算法Ｅｇ０３，就　

已不难给出之），而仅给出其构思最巧、方法最简、效率最高的　

基于双向链表的（结点的数据字段）变量标记的同构化首尾排　

序新算法Ｅｇ０３。　

算法Ｅｇ０３　｛基于字段变量标记的双向链表首尾排序算　

法）　

［［Ｌｉｎｋ＜一一＞指针　Ｎｏｄｅｓ］］；｛双向链表的指针类型定义）　

［［Ｎｏｄｅｓ＜＝一＞记录［Ｄａｔａ：整型；｛元素体定义：自身数据字段｝　

Ｐｒｅｃｅｄｅ，Ｓｕｃｃｅｅｄ：Ｌｉｎｋ］｛邻元体定义：（直　

接）前趋、后继指针字段）　

］］；｛双向链表的指针元素类型定义）　

｛｛ｉ，ｊ，Ｍｉｎ，Ｍａｘ，ｎ：整型））；｛整形变量定义｝　

（｛Ｈｅａｄ，Ｒｅａｒ，Ｒｅａｒ１，Ｖｉｓｉｔ１，Ｖｉｓｉｔ２，Ｐｌａｃｅｌ，Ｐｌａｃｅ２：Ｌｉｎｋ）｝；｛定义链　

表头、尾、访问、位置等｝　

＞＞＞｛算法开始｝　

＠：＼＼输出”请输人数据个数．ｎ一？”；输入ｎ｛提示下输入数据个数）　

｜ｆ　

直到ｎ＞一２；｛直到个数ｎ已合理且中意为止）　

（‘‘用单向链表存放初始数据序列”处理）　

生成结点Ｈｅａｄ；｛生成头结点，以存放第１个数据｝　

输入Ｈｅａｄ．Ｄａｔａ；｛存放第一个节点数据｝　

Ｈｅａｄ．Ｐｒｅｃｅｄｅ＊－Ｎｕｌｌ；｛使头结点前趋指针为空指针｝　

Ｈｅａｄ．Ｓｕｅｃｅｅｄ￣Ｎｕｌｌ；｛使头结点后继指针为空指针）　

Ｒｅａｒ＇＊－Ｈｅａｄ；｛头结点此时也是尾结点）　

Ｖｉｓｉｔｌ－＊－Ｈｅａｄ；｛标记初始链表头｝　

ｉ一２；｛结点序号计数器初值）　

当ｉ＜一ｎ＠：＼＼｛当链表尚有未生成结点时）　

生成结点Ｖｉｓｉｔ１；｛生成新尾结点｝　

输出“请输入第个ｉ数据个数”；输入Ｖｉｓｉｔ１．Ｄａｔａ；｛新尾结点加载数　

据）　

Ｖｉｓｉｔ１．Ｐｒｅｃｅｄｅ￣－Ｒｅａｒ；｛使新尾结点前趋指针连通原尾结点）　

Ｖｉｓｉｔ１．Ｓｕｃｃｅｅｄ－＊－－Ｎｕｌｌ；｛使新尾结点后继指针为空指针）　

Ｒｅａｒ．Ｓｕｃｃｅｅｄ－，－Ｖｉｓｉｔ１；｛使原尾结点后继指针连通新尾结点）　

Ｒｅａｒ￣Ｖｉｓｉｔｌ；｛标记新尾结点｝　

ｉ—ｉ＋１｛下一新结点序号生成）　

／／；　

｛‘‘用双向链表对初始数据序列进行排序”处理｝　

Ｖｉｓｉｔｌ￣－Ｈｅａｄ；｛排序遍数与始端（结点）控制指针｝　

Ｒｅａｒｌ－，－Ｒｅａｒ；｛排序尾端（结点）控制指针）　Ｖｉｓｉｔｌ￣Ｈｅａｄ；｛指针Ｖｉｓｉｔ１标记双向链表头结点）　

当Ｖｉｓｉｔｌ＜＞Ｒｅａｒｌ＠：＼＼｛当排序遍数未完时｝　

当Ｖｉｓｉｔ１＜＞Ｎｕｌｌ＠：＼＼｛当访问指针Ｖｉｓｉｔ１非空指针时）　

Ｐｌａｃｅｌ＇￣－－Ｖｉｓｉｔ１；｛标记当前范围最小者初始处）　输出Ｖｉｓｉｔ１．Ｄａｔａ；（输出当前结点数据字段｝　

Ｍｉｎ－￣－－Ｖｉｓｉｔ１．Ｄａｔａ；（标记当前范围最小者初始值）　

Ｖｉｓｉｔｌ－￣－－Ｖｉｓｉｔ１．Ｓｕｃｃｅｅｄ｛从头向尾步进：指向下一结点位置）　

Ｍａｘ－＊－Ｍｉｎ；｛最小者初始值兼作最大者初始值）　

／／；　

Ｐｌａｃｅ２－￣－－Ｖｉｓｉｔｌ；｛最小者初始处兼作最大者初始处）　行输出；　

Ｖｉｓｉｔ２＂．－Ｖｉｓｉｔ１．Ｓｕｃｃｅｅｄ；｛从下一结点起，择选当前最小、最大者｝　

ｆ　Ｉ　Ｉ　

当Ｖｉｓｉｔ２＜＞Ｒｅａｒ１．Ｓｕｃｃｅｅｄ＠：＼＼｛当尚有未选结点时｝　

结束语依据同构化基本定理。本文研究和发现了基于　

如果Ｖｉｓｉｔ２．Ｄａｔａ＜Ｍｉｎ｛当前结点数据更小吗？）　

传统内部首尾排序算法的同构化特点与本质；利用其同构化　

Ｔ：＼＼Ｍｉｗ＇－－Ｖｉｓｉｔ２．Ｄａｔａ；Ｐｌａｃｅｌ＊－Ｖｉｓｉｔ２／／（标记当前最小者及其位　

特点与本质，逐个更优地构造了基于链表的结点插删、结点标　

置）　

记、（结点数据字段）变量标记的３种首尾换排序新算法，有利　

Ｆ：如果Ｖｉｓｉｔ２．Ｄａｔａ＞Ｍａｘ｛当前结点数据更大吗？）　

于进一步深化和推广首尾排序算法的应用方式与实用范围。　

Ｔ：＼＼Ｍａｘ－．－Ｖｉｓｉｔ２．Ｄａｔａ￣Ｐｌａｃｅ２－．－－Ｖｉｓｉｔ２／／｛标记当前最大者及其位　

置）　

并且，这些基于链表的首尾排序算法及其编程实现，完全可作　

Ｖｉｓｉｔ２－￣Ｖｉｓｉｔ２．Ｓｕｃｃｅｅｄ（指向下一待访结点｝　

“程序设计”与“数据结构”的课程融合、教学改革、教育创新的　

一

｜｜　

个有效案例，而这已被由作者成功主持与主研的２００６年四　

如果Ｐｌａｃｅｌ＜＞Ｖｉｓｉｔｌ（当前最小者不在其位吗？｝　

川省级精品课程“数据结构”的教学研究与教改实践所证实。　

Ｔ：＼＼Ｐｌａｃｅ１．Ｄａｔａ￣－Ｖｉｓｉｔ１．Ｄａｔａ；Ｖｉｓｉｔ１．Ｄａｔａ￣－－Ｍｉｎ／／（使当前最小　

者直接到其位｝　

参考文献　

如果Ｐｌａｃｅ１．Ｄａｔａ＝Ｍａｘ｛当前最大者恰在交换后处吗？（当前最大　

Ｋｎｕｔｈ　Ｄ　Ｅ．Ｔｈｅ　Ａｒｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｐｒｏｇｒａｍｍｉｎｇ，Ｖｏｌｕｍｅ　１，　

者已不在Ｐｌａｃｅ２处）｝　

Ｆｕｎｄａｍｅｎｔａｌ　Ａｌｇｏｒｉｔｈｍｓ．Ａｄｄｉｓｏｎ－Ｗｅｓｌｅｙ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏｍｐａ—　

］

口　

　］　］　］］　］］　

Ｔ：Ｐｌａｃｅ２￣－－Ｐｌａｃｅｌ｛标记第ｉ大者新位（警告：必须使当前最大者又在　

ｎｙ，Ｉｎｅ．，１９７３　

Ｐｌａｃｅ２处））　

Ｋｎｕｔｈ　Ｄ　Ｅ．Ｔｈｅ　Ａｒｔ　ｏｆ　ｏＣｍｐｕｔｅｒ　Ｐｒｏｇｒａｍｍｉｎｇ，Ｖｏｌｕｍｅ　３，　

／／；　

Ｓｏｒｔｉｎｇ　ａｎｄ　Ｓｅａｒｃｈｉｎｇ．Ａｄｄｉｓｏｎ－Ｗｅｓｌｅｙ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏｍｐａｎｙ，　

如果Ｐｌａｃｅ２＜＞Ｒｅａｒｌ｛当前最大者不在其位吗？｝　

Ｉｎｃ．，１９７３　

Ｔ：＼＼Ｐｌａｃｅ２．Ｄａｔａ－，－Ｒｅａｒ１．Ｄａｔａ；Ｒｅａｒ１．Ｄａｔａ￣－Ｍａｘ／／｛使当前最大　

周启海．Ｃ＋＋同构化对象程序设计原理．北京：清华大学出版　

者直接到其位）　

社，北方交通大学出版社，２００４　

Ｖｉｓｉｔｌ－，－Ｖｉｓｉｔ１．Ｓｕｃｃｅｅｄ｛从头向中（心）步进：指向下一遍排序范围的　

严蔚敏．数据结构（Ｃ语言版）．北京：清华大学出版社，２００２　

始端结点）　

黄涛．基于链表的择换排序新算法——“数据结构”与“程序设　

如果Ｖｉｓｉｔｌ＜＞Ｒｅａｒｔ｛当前排序范围内并非只剩最后两个结点吗？）　

计”课程的融合创新案例研究Ｉ－Ｊ］．计算机科学，２００８，３５（１１）　

Ｒｅａｒｌ－，－－Ｒｅａｒ１．Ｐｒｅｅｅｄｅ（从尾向中（心）步进：指向下一遍排序范围的　周启海．Ｃ语言程序设计教程．北京：机械工业出版社，２００４　

尾端结点｝　

周启海，李朔枫，杨祥茂，等．论程序设计课程教学中的同构化创　

／／；　

新思想教育——“对一好一巧一妙一绝”的算法案例ＥＪ］．计算机　

｛‘‘输出双向链表中递增有序化各数据”的处理）　科学，２００７，３５（５）　

（上接第１６３页）　

ｌｅｖｅｌ　Ｃｏｎｓｔｒａｉｎｔｓ　ｔＯ　Ｓｐａｃｅ－ｌｅｖｅｌ　Ｃｏｎｓｔｒａｉｎｔｓ：Ｍａｋｉｎｇ　ｔｈｅ　Ｍｏｓｔ　

ＳＶ技术和数据划分技术生成两种形状的初始网格，用随机映　

ｏｆ　Ｐｒｉｏｒ　Ｋｎｏｗｌｅｄｇｅ　ｉｎ　ａＤｔａ　ＣＩｕｓｔｅｒｉｎｇ　ｆ｝Ｍｏｒｇａｎ　Ｋ，ｅｄ．Ｐｒｏ—　

射技术定义网格间的距离。实验表明所设计的网格距离定义　

ｅｅｅｄｉｇｎｓ　ｏｆ　ｔｈｅ　Ｎｉｎｅｔｅｅｎｔｈ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　

具有较好的数据特征捕捉能力，ＡＣＧＤ算法具有较好的聚类　

Ｌｅａｒｎｉｇｎ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＵＳＡ，２００２：３０７—３１４　

性能。　

Ｅ４］　

Ｂｅｎ－Ｈｕｒ　Ａ，Ｈｏｒｎ　Ｄ，Ｓｉｅｇｅｌｍａｎｎ　Ｈ　Ｔ．Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｃｌｕｓｔｅ—　

但是合并过程的控制仍是待解决的问题。在一个庞大的　

ｒｉｇｎ．Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｇｎ　Ｒｅｓｅａｒｃｈ，２００１，２：１２５—１３７　

合并路径图上通过分析得出合理的簇划分的结果仍是较困难　

［５］　丁世飞，史忠植，靳奉祥，等．基于广义信息距离的直接聚类算　

的任务，这也降低了聚类效率。如何评价合并状态的优劣来　

法．计算机研究与发展，２００７（４）：６７４—６７９　

Ｅ６３　

Ｎｏｖａｋ　Ｅ，Ｒｉｔｔｅｒ　Ｋ．Ｔｈｅ　Ｃｕｒｓｅ　ｏｆ　Ｄｉｍｅｎｓｉｏｎ　ａｎｄ　ａ　Ｕｎｉｖｅｒｓａｌ　

适时地终止合并操作是下一步的工作方向。　

Ｍｅｔｈｏｄ　ｆｏｒ　Ｎｕｍｅｒｉｃａｌ　Ｉｎｔｅｇｒａｔｉｏｎｆ｝Ｎａｍｂｅｒｇｅｒ　Ｇ，ｅｔ　ａ１．，ｅｄｓ．　

参考文献　

Ｍｕｌｔｉｖａｒｉａｔｅ　Ａｐｐｒｏｘｉｍａｔｉｏｎ　ａｎｄ　Ｓｐｌｉｎｅｓ．Ｇｅｒｍａｎｙ，１９９７：１７７　

１８８　

［１３　Ｂｒａｄｌｅｙ　Ｐ　Ｓ。Ｆａｙｙａｄ　Ｕ＾，Ｌ　Ｒｅｆｉｎｉｎｇ　Ｉｎｉｔｉａｌ　Ｐｏｉｎｔｓ　ｆｏｒ　ｋ－Ｍｅａｎｓ　

Ｅ７３　

ｈｔｔｐｔｉ｜　ｆ、　．ＣＳ．ｃｍｕ．ｅｄｕ／ａｆｓ／ｅｓ／ｐｒｏｊｅｅｔ／ｔｈｅｏ－１１／ｗｗｗ／ｎａｉｖｅ－　

Ｃｌｕｓｔｅｒｉｎｇ｝｛Ｐｒｏｃｅｅｄｉｇｎｓ　ｏｆ　１５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

ｂａｙｅｓ．ｈｔｍｌ　

Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＵＳＡ，１９９８：９１—９９　

［８３　

Ｎｇ　Ａ，Ｊｏｒｄａｎ　Ｍ，Ｗｅｉｓｓ　Ｙ．Ｏｎ　Ｓｐｅｃｔｒａｌ　Ｃｌｕｓｔｅｒｉｎｇ：Ａｎａｌｙｓｉｓ　

［２］Ｌａｎｃｅ　Ｇ　Ｎ，Ｗｉｌｌｉａｍｓ　Ｗ　Ａ　ｇｅｎｅｒａｌ　ｔｈｅｏｒｙ　ｏｆ　ｃｌａｓｓｉｆｉｃａｔｏｒｙ　

ａｎｄ　Ａｌｇｏｒｉｔｈｍ∥Ａｄｖａｎｃｅｓ　ｉｎ　Ｎｅｕｒａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　

ｓｏｒｔｉｎｇ　ｓｔｒａｔｅｇｉｅｓ．１．Ｈｉｅｒａｒｃｈｉｃａｌ　ｓｙｓｔｅｍｓ．Ｔｈｅ　Ｃｏｍｐｕｔｅｒ　

Ｓｙｓｔｅｍｓ．Ｃａｍｂｒｉｄｇｅ：ＭＩＴ　Ｐｒｅｓｓ，２００２　

ｒ３］

Ｊｏｕｒｎａ

ｌ＇１９６７，９（４）．．３

７３－３８０

［３］

　

Ｄａｎ　Ｋ　Ｓａｐａｎｄａｒ　Ｄ　Ｋ　Ｃｈｒｉｓｔｏｐｈｅｒ　ｎ　Ｍａｎｎｉ

ｎ　

ｎｇ　ｆｒｏｍ　Ｉｎｓｔａｎｃｅ－

［９］　

ｈｔｔｐ：／／ｗｗｗ．ｕｎｃｃ．ｅｄｕ／ｋｎｏｗｌｄｅｇｅｄｉｓｃｏｖｅｒｙ　

，，　，，　

・　

２３１　・