文档库 最新最全的文档下载
当前位置:文档库 › ACE源代码目录结构

ACE源代码目录结构

ACE源代码目录结构
ACE源代码目录结构

ACE源代码目录结构

ACE(ADAPTIVE Communication Environment),中文的意思就是自适配通讯环境,ACE是一个用于开发网络程序的优秀的C++的框架,在国外有很广泛的使用,在国内一些大的开发通讯产品的公司也有使用。我接触ACE也有一段时间了,虽然时间不长,但我还是感觉到ACE确实是一个好东西,对于丰富自己的知识面有很大的帮助。虽然我们项目目前是采用C语言来开发,但是当接触ACE后,你会发现“喔,原来程序还可以这样”。例如:我觉得ACE里面Reactor框架就是一个非常的东西,我们在开发网络程序的时候,常常采用poll 来监视各种网络事件,但当采用该框架后,你现在只是需要关系你的业务逻辑,当发生特定的网络事件后,框架会回调你的业务逻辑。其实按照这个思路,我们完全可以用C来实现类似的功能,当你完成这个后,你会发现你原来用C语言写的过程风格的代码竟然有了OO的味道。

ACE确实是好东西,但也不是能轻松的就能掌握的,我们还需要一步一步的来蚕食这个大象。万丈高楼平地起,首先我们还是了解一下ACE的目录结构,从整体上对ACE有一个认识,为今后的进一步学习打下一个基础。

解开ACE的压缩包后,你会发现一个ACE_wrappers目录,这个目录也就是ACE的HOME目录,它下面还包含着一些子目录:

ace:这个目录是ACE中最重要的目录,它包含了ACE的所有源码,但遗憾的是,ACE 的所有源文件和头文件全部杂乱的堆在这个目录里,这可能也是很多开源软件的缺点。其实ACE的代码完全可以按照不同的功能进行不同目录的划分,例如:Reactor框架和thread 框架代码完全可以划分开,我想一个代码组织良好的ACE,将会给大家的学习带来极大的好处,我将在后面的文章里给出ACE代码划分的方法;

ACEXML:这个目录包含了用ACE实现的一个XML解析器;

apps:这个目录包含了用ACE来实现的一些较大的应用程序,例如:JAWS,一个WEB 服务器;

ASNMP:基于ACE的SNMP协议实现;

bin:包含里用例方便开发的perl脚本程序,例如:在WIN32上开发DLL时候,需要导出DLL的接口;

docs:ACE的一些帮助文档,其中ACE-subsets.html文档,对我们划分ACE的代码有很大的帮助;

examples:是用ACE来编写的一些例子程序,方便更好的学习和理解ACE;

include:也是ACE中一个比较重要的目录,它包含了在不同的平台上编译时候的编译规则,库的编译规则等;

netsvcs:一些基于ACE的在分布式系统中常用的程序,例如:分布式系统日志系统,网络锁,时间同步等;

TAO:基于ACE的实时CORBA实现,TAO在分布式系统中使用相当广泛,也是一个不可多得的好资源;

tests:用来对ACE进行回归测试,也提供了一个学习ACE的很好的例子代码;

前几篇文章也提到过,ACE的所有源文件和头文件都杂乱堆在了ACE_wrappers/ace 目录下。这样的代码组织方式给学习ACE带来了很大的困难,很多朋友在看到ace目录下庞大的代码的时候,几乎就失去了学习ACE的信心^_^。因此,我们有必要对ACE的代码进行重新组织,以降低学习曲线。下面,我将给出我对ACE源码的划分方法。其实,我也是刚学习ACE没有多久,对ACE的了解还甚少,所以,我的源码划方式法不一定十分正确,这里共享出来,仅供大家参考。

其实,在ACE的帮助文档里,ACE-subsets.html和ACE-categories.html,这两个文档对指导ACE的源码划分起到了很大的作用,否则,我刚刚接触ACE,就想对其进行源码划分,是不可能完成的。ACE-subsets.html,这个文档主要介绍了ACE的library subsetting。正常情况下,在编译完ACE后,只会产生一个ACE的库。我们可以根据该文档的介绍,简单的修改一下Makefile,就可以对ACE的库进行子集化,我们可以编译出OS、Thread等这样的子库。ACE-categories.html,这个文档对ACE中的代码进行了一些功能上的分类。具体大家可以详细的参考一下这两个文档,这两个文档对学习ACE还是有一定的帮助的。

在ACE的源代码目录ace下,我将建立很多子目录,来对ACE的代码进行按功能分类:ACE_OS:该目录里包含的代码是OS的API的wrapper,也就是ACE的OS适配层;包含代码:

ARGV.cpp OS_Memory.cpp

Argv_Type_Converter.cpp OS_QoS.cpp

Base_Thread_Adapter.cpp OS_String.cpp

Basic_Types.cpp OS_TLI.cpp

Copy_Disabled.cpp OS_Thread_Adapter.cpp

Env_Value_T.cpp Sched_Params.cpp

Handle_Set.cpp Template_Instantiations.cpp

Makefile Thread_Hook.cpp

OS.cpp Time_Value.cpp

OS_Dirent.cpp

OS_Errno.cpp

OS_Log_Msg_Attributes.cpp

ACE_Codec:该目录包含的是ACE的各种编码类型的处理代码,目前只包含了BASE64编码的处理;

包含代码:Codecs.cpp Makefile

ACE_Connection:该目录包含的是ACE中的Acceptor-Connector框架代码和异步通讯类代码;

包含代码:

Acceptor.cpp Connector.cpp

Asynch_Acceptor.cpp Makefile

Asynch_Connector.cpp POSIX_Asynch_IO.cpp

Asynch_IO.cpp Strategies_T.cpp

Asynch_IO_Impl.cpp Svc_Handler.cpp

Asynch_Pseudo_Task.cpp WIN32_Asynch_IO.cpp

Cached_Connect_Strategy_T.cpp

Caching_Strategies_T.cpp

ACE_Demux:该目录包含的是ACE中的Reactor和Proactor框架代码;

包含代码:

Dev_Poll_Reactor.cpp Priority_Reactor.cpp TP_Reactor.cpp Event_Handler.cpp Proactor.cpp TkReactor.cpp

Event_Handler_T.cpp QtReactor.cpp WFMO_Reactor.cpp FlReactor.cpp Reactor.cpp WIN32_Proactor.cpp

Makefile SUN_Proactor.cpp XtReactor.cpp

Msg_WFMO_Reactor.cpp Select_Reactor.cpp

POSIX_CB_Proactor.cpp Select_Reactor_Base.cpp

POSIX_Proactor.cpp Select_Reactor_T.cpp

ACE_IPC:该目录包含的是ACE中进程间通讯的一些封装代码:

包含代码:

ATM_Acceptor.cpp Makefile

ATM_Addr.cpp Pipe.cpp

ATM_Connector.cpp SPIPE.cpp

ATM_Params.cpp SPIPE_Acceptor.cpp

ATM_QoS.cpp SPIPE_Addr.cpp

ATM_Stream.cpp SPIPE_Connector.cpp

DEV.cpp SPIPE_Stream.cpp

DEV_Addr.cpp SV_Message.cpp

DEV_Connector.cpp SV_Message_Queue.cpp DEV_IO.cpp SV_Semaphore_Complex.cpp FIFO.cpp SV_Semaphore_Simple.cpp FIFO_Recv.cpp SV_Shared_Memory.cpp

FIFO_Recv_Msg.cpp Signal.cpp

FIFO_Send.cpp TLI.cpp

FIFO_Send_Msg.cpp TLI_Acceptor.cpp

FILE.cpp TLI_Connector.cpp

FILE_Addr.cpp TLI_Stream.cpp

FILE_Connector.cpp TTY_IO.cpp

FILE_IO.cpp Typed_SV_Message.cpp IOStream.cpp Typed_SV_Message_Queue.cpp IOStream_T.cpp UNIX_Addr.cpp

IO_SAP.cpp UPIPE_Acceptor.cpp

MEM_Acceptor.cpp UPIPE_Connector.cpp

MEM_Addr.cpp UPIPE_Stream.cpp

MEM_Connector.cpp XTI_ATM_Mcast.cpp

MEM_IO.cpp

MEM_SAP.cpp

MEM_Stream.cpp

ACE_LIB:该目录将包含ACE编译好的各个子库;

ACE_Logging:该目录包含ACE中的日志处理相关代码;

包含代码:

Dump.cpp Log_Msg_UNIX_Syslog.cpp Dump_T.cpp Log_Record.cpp

Log_Msg.cpp Logging_Strategy.cpp

Log_Msg_Backend.cpp Makefile

Log_Msg_Callback.cpp Trace.cpp

Log_Msg_IPC.cpp

Log_Msg_NT_Event_Log.cpp

ACE_Memory:该目录包含了ACE内存处理相关代码;

包含代码:

Based_Pointer_Repository.cpp Obstack.cpp

Based_Pointer_T.cpp Obstack_T.cpp

Makefile PI_Malloc.cpp

Malloc.cpp Read_Buffer.cpp

Malloc_Allocator.cpp Shared_Memory.cpp Malloc_Instantiations.cpp Shared_Memory_MM.cpp Malloc_T.cpp Shared_Memory_SV.cpp Mem_Map.cpp

Memory_Pool.cpp

Obchunk.cpp

ACE_Misc:ACE中一些没有明确功能分类的代码,属于杂项;包含代码:

CE_Screen_Output.cpp NT_Service.cpp

Makefile gethrtime.cpp

ACE_Nameservices:该目录包含了ACE中名字服务相关代码;

包含代码:

Name_Space.cpp

Local_Name_Space.cpp Naming_Context.cpp

Local_Name_Space_T.cpp Registry_Name_Space.cpp

Makefile Remote_Name_Space.cpp

Name_Proxy.cpp

Name_Request_Reply.cpp

ACE_Sockets:该目录包含的是ACE的socket封装代码;

包含代码:

Addr.cpp SOCK_CODgram.cpp

INET_Addr.cpp SOCK_Connector.cpp

IPC_SAP.cpp SOCK_Dgram.cpp

LOCK_SOCK_Acceptor.cpp SOCK_Dgram_Bcast.cpp LSOCK.cpp SOCK_Dgram_Mcast.cpp

LSOCK_Acceptor.cpp SOCK_IO.cpp

LSOCK_CODgram.cpp SOCK_SEQPACK_Acceptor.cpp LSOCK_Connector.cpp SOCK_SEQPACK_Association.cpp LSOCK_Dgram.cpp SOCK_SEQPACK_Connector.cpp LSOCK_Stream.cpp SOCK_Stream.cpp

Makefile Sock_Connect.cpp

Multihomed_INET_Addr.cpp

SOCK.cpp

SOCK_Acceptor.cpp

ACE_Streams:该目录包含了ACE中的Streams和Task框架代码;

包含代码:

CDR_Base.cpp Module.cpp

CDR_Stream.cpp Multiplexor.cpp

Codeset_IBM1047.cpp Reactor_Notification_Strategy.cpp Codeset_Registry.cpp Stream.cpp

Codeset_Registry_db.cpp Stream_Modules.cpp

IO_Cntl_Msg.cpp Task.cpp

Makefile Task_T.cpp

Message_Queue.cpp

Message_Queue_T.cpp

ACE_Svcconf:该目录包含了ACE中的Service Configurator框架代码;

包含代码:

DLL.cpp Service_Types.cpp

DLL_Manager.cpp Shared_Object.cpp

Dynamic_Service.cpp Svc_Conf.l

Dynamic_Service_Base.cpp Svc_Conf.y

Makefile Svc_Conf_Lexer_Guard.cpp

Parse_Node.cpp Svc_Conf_l.cpp

Service_Config.cpp Svc_Conf_y.cpp

Service_Manager.cpp XML_Svc_Conf.cpp

Service_Object.cpp

Service_Repository.cpp

Service_Templates.cpp

ACE_Threads:该目录包含了ACE中的线程和同步机制相关代码,例如:thread manager;

包含代码:

Activation_Queue.cpp Process_Manager.cpp Thread.cpp

Atomic_Op.cpp Process_Mutex.cpp Thread_Adapter.cpp Atomic_Op_T.cpp Process_Semaphore.cpp Thread_Control.cpp File_Lock.cpp RW_Process_Mutex.cpp Thread_Exit.cpp Future.cpp Synch.cpp Thread_Manager.cpp

Future_Set.cpp Synch_Options.cpp Token.cpp

Makefile Synch_T.cpp

Process.cpp Test_and_Set.cpp

ACE_Timer:该目录包含ACE中和时间相关的代码;

包含代码:

Timer_Heap.cpp

Basic_Stats.cpp Timer_Heap_T.cpp

High_Res_Timer.cpp Timer_List.cpp

Makefile Timer_List_T.cpp

Profile_Timer.cpp Timer_Queue.cpp

System_Time.cpp Timer_Queue_Adapters.cpp

Time_Request_Reply.cpp Timer_Queue_T.cpp

Timeprobe.cpp Timer_Wheel.cpp

Timeprobe_T.cpp Timer_Wheel_T.cpp

Timer_Hash.cpp

Timer_Hash_T.cpp

ACE_Token:Token是ACE中实现的一种同步机制,保证严格的FIFO或LIFO策略来获得锁。ACE通过Token机制实现了分布式同步机制。

包含代码:

Local_Tokens.cpp Token_Collection.cpp Token_Request_Reply.cpp Makefile Token_Invariants.cpp

Remote_Tokens.cpp Token_Manager.cpp

ACE_Utils:ACE中的一些基础数据结构和算法的工具类代码;

包含代码:

ACE.cpp Init_ACE.cpp

Active_Map_Manager.cpp Intrusive_List.cpp

Active_Map_Manager_T.cpp Intrusive_List_Node.cpp Arg_Shifter.cpp Lib_Find.cpp

Array_Base.cpp Makefile

Auto_IncDec_T.cpp Managed_Object.cpp

Auto_Ptr.cpp Map.cpp

Cache_Map_Manager_T.cpp Map_Manager.cpp Caching_Utility_T.cpp Map_T.cpp

Capabilities.cpp Message_Block.cpp

Cleanup_Strategies_T.cpp Message_Block_T.cpp Configuration.cpp Method_Request.cpp Configuration_Import_Export.cpp Node.cpp

Connection_Recycling_Strategy.cpp Notification_Strategy.cpp Containers.cpp Object_Manager.cpp Containers_T.cpp Pair.cpp

Date_Time.cpp Pair_T.cpp

Dirent.cpp RB_Tree.cpp

Dirent_Selector.cpp Recyclable.cpp

Dynamic.cpp Refcountable.cpp

Filecache.cpp Registry.cpp

Flag_Manip.cpp SString.cpp

Framework_Component.cpp Sample_History.cpp Framework_Component_T.cpp Singleton.cpp

Free_List.cpp Stats.cpp

Functor.cpp String_Base.cpp

Functor_T.cpp String_Base_Const.cpp

Get_Opt.cpp Swap.cpp

Handle_Ops.cpp Unbounded_Queue.cpp

Hash_Cache_Map_Manager_T.cpp Unbounded_Set.cpp

Hash_Map_Manager.cpp Unbounded_Set_Ex.cpp

Hash_Map_Manager_T.cpp Vector_T.cpp

Hash_Map_With_Allocator_T.cpp

Hashable.cpp

include:该目录又包含子目录ace,也就是说include/ace/目录下,包含了ACE的所有头文件和.i文件,之所以这样组织,是因为ACE中的源文件和头文件的包含文件的方式为:#include "ace/OS.h",所以采用这种目录结构方式来存放头文件和.i文件。这里,对头文件和.i 文件,没有进一步按照功能划分,就是因为#include "ace/OS.h"这种包含方式,如果头文件和.i文件也按照功能划分,那么代码修改量相当大;

通过上面给出的目录结构和源文件功能划分及头文件组织方式,相信读者以可以自行对ACE代码进行整理了。在实际整理和编译代码的过程中,需要修改Makefile和ACE头文件中以_T方式为后缀的头文件,例如:Obstack_T.h,需要修改里面模板源文件包含路径。我将在下一篇文章中进行描述。

我再次强调,上面ACE源码划分方式,不一定十分正确^_^,随着我们ACE学习和理解的深入,我们可能会进行更改。其实,在我们整理ACE源文件的时候,我们可以进一步了解ACE的各个源文件大致功能,对我们以后更深入的学习大有裨益。

在ACE的源代码目录里,有源文件.cpp、头文件.h,我们还发现有以.i和.inl为扩展名的文件。其实,以.i和.inl为扩展名的文件是ACE源码中inline函数的存放形式。

在说明ACE中为什么采用这种方式来存放inline函数之前,我们来说一下inline关键字是什么意识。我们知道当调用一个函数的时候,涉及到返回地址和参数压栈等一些操作,这些操作是函数调用本身的开销。在原来的C代码中,通常采用宏定义的方式模拟函数,来消除函数调用的开销,因此我们知道宏是在预编译时候进行处理的。但是,宏定义本身也有很多缺陷,很容易造成错误的使用。这就是inline关键字诞生的原因。用inline关键字定义的函数,在编译的时候,并不会产生真正的函数,而是在该函数调用处直接展开代码,这样就消除了函数调用的开销。注意,inline关键字,只是给编译器的一个暗示,是不是真的进行了inline处理,是由编译器决定的。

那为什么ACE会采用这样一个特殊的方式来存放inline函呢?我们结合实例给出答案。我们看一下,Reactor.h文件的结尾处,有如下的处理:

#if defined (__ACE_INLINE__)

#include "ace/Reactor.i"

#endif /* __ACE_INLINE__ */

在看一下Reactor.cpp文件开头处的宏处理:

#if !defined (__ACE_INLINE__)

#include "ace/Reactor.i"

#endif /* __ACE_INLINE__ */

上面的Reactor.h,Reactor.cpp和Reactor.i文件是ACE的Reactor框架的相关代码。上面的宏定义我们很好理解,在头文件中的处理为:如果定义了宏__ACE_INLINE__,那么我们就把Reactor.i文件include到头文件中。在源文件中处理为:如果没有定义宏

__ACE_INLINE__,那么就把Reactor.i文件include到源文件中。其实有了上面inline 含义的介绍,我们不难理解为什么采用这种方式来进行处理。这里我们假设定义了宏

__ACE_INLINE__,并且Reactor.i文件是被include到源文件里,而不是被include头文件里,那么会产生什么后果那?我们知道inline函数,在编译器编译后,是不会产生真正的函数的,因此,如果有其它源文件,例如zhx.cpp,调用了Reactor.i文件中的inline函数,那么在连接的时候,就会抛出符号无法解析的错误,而如果Reactor.i文件是被include 到了头文件中,并且我们在zhx.cpp中有调用Reactor.i文件中的函数,那么在zhx.cpp 中,只需要包含Reactor.h头文件即可,则Reactor.i的相关inline函数在zhx.cpp也进行了代码展开处理。如果没有定义宏__ACE_INLINE__,则Reactor.i被include到源文件中,没有任何问题,因为Reactor.i中的函数在编译后,会产生真正的函数,而不是被inline 处理。这就是ACE为什么采用这样的方式进行处理的原因。

在上面的介绍中,我们同时也发现了inline的缺点,就是它会造成代码的膨胀。因此,不是什么样的函数都适合用inline来定义,只有那些短小的函数才适合采用inline处理。注:ACE为什么会采用.i和.inl两种扩展名形式的文件来存放inline函数,我还不是很清楚,但感觉以.inl形式存放的文件是早期ACE代码中的方式,后期的ACE代码采用.i方式来存放inline函数,也就是说这应该是一个历史遗留问题^_^,开源项目的缺点。

数据结构课程实验指导书

数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法,并做了相应的性能分析和比较,课程内容丰富,理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: 1)理论艰深,方法灵活,给学习带来困难; 2)内容丰富,涉及的知识较多,学习有一定的难度; 3)侧重于知识的实际应用,要求学生有较好的思维以及较强的分析和解决问题的能力,因而加大了学习的难度; 根据《数据结构》课程本身的特性,通过实验实践内容的训练,突出构造性思维训练的特征,目的是提高学生分析问题,组织数据及设计大型软件的能力。 课程上机实验的目的,不仅仅是验证教材和讲课的内容,检查自己所编的程序是否正确,课程安排的上机实验的目的可以概括为如下几个方面: (1)加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的习题复杂得多,也更接近实际。实验着眼于原理与应用的结合点,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力;另一方面,能使书上的知识变" 活" ,起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时,觉得无从下手。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出

现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法,而实验题是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧,多人合作,以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点,使学生学会如何把书本上和课堂上学到的知识用于解决实际问题,从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境,学习上机调试程序一个程序从编辑,编译,连接到运行,都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件,软件条件,只有学会使用这些环境,才能进行 程序开发工作。通过上机实验,熟练地掌握程序的开发环境,为以后真正编写计算机程序解决实际问题打下基础。同时,在今后遇到其它开发环境时就会触类旁通,很快掌握新系统的使用。 完成程序的编写,决不意味着万事大吉。你认为万无一失的程序,实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作,尽快掌握程序调试方法是非常重要的。分析问题,选择算法,编好程序,只能说完成一半工作,另一半工作就是调试程序,运行程序并得到正确结果。 二、实验要求 常用的软件开发方法,是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高,但为了培养一个软件工作者所应具备的科学工作的方法和作风,也应遵循以下五个步骤来完成实验题目: 1) 问题分析和任务定义 在进行设计之前,首先应该充分地分析和理解问题,明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的

数据结构题目及c语言代码

目题程设计《数据结构》课)C语言程序实现采用():3选王(学时目 题1:猴子一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m 的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求:m及n要求从键盘输入,存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include #include // 链表节点 typedef struct _RingNode { int pos; struct _RingNode *next; }RingNode, *RingNodePtr; // 创建约瑟夫环,pHead:链表头指针,count:链表元素个数 void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) {

pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf(\ %d, pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next;

数据结构源代码(清华大学+严蔚敏)

void Union(List &La, List Lb) { // 算法2.1 // 将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len,Lb_len,i; ElemType e; La_len = ListLength(La); // 求线性表的长度 Lb_len = ListLength(Lb); for (i=1; i<=Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal)) // La中不存在和e相同的数据元素 ListInsert(La, ++La_len, e); // 插入 } } // union void MergeList(List La, List Lb, List &Lc) { // 算法2.2 // 已知线性表La和Lb中的元素按值非递减排列。 // 归并La和Lb得到新的线性表Lc,Lc的元素也按值非递减排列。int La_len, Lb_len; ElemType ai, bj; int i=1, j=1, k=0; InitList(Lc); La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i <= La_len) && (j <= Lb_len)) { // La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; } else { ListInsert(Lc, ++k, bj); ++j; } } while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } while (j <= Lb_len) { GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); } } // MergeList Status InitList_Sq(SqList &L) { // 算法2.3 // 构造一个空的线性表L。 L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) return OK; // 存储分配失败 L.length = 0; // 空表长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 算法2.4 // 在顺序线性表L的第i个元素之前插入新的元素e, // i的合法值为1≤i≤ListLength_Sq(L)+1 ElemType *p; if (i < 1 || i > L.length+1) return ERROR; // i值不合法 if (L.length >= L.listsize) { // 当前存储空间已满,增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) return ERROR; // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 } ElemType *q = &(L.elem[i-1]); // q为插入位置 for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; // 插入e ++L.length; // 表长增1 return OK; } // ListInsert_Sq Status ListDelete_Sq(SqList &L, int i, ElemType &e) { // 算法2.5 // 在顺序线性表L中删除第i个元素,并用e返回其值。 // i的合法值为1≤i≤ListLength_Sq(L)。 ElemType *p, *q; if (i<1 || i>L.length) return ERROR; // i值不合法 p = &(L.elem[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.elem+L.length-1; // 表尾元素的位置 for (++p; p<=q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移--L.length; // 表长减1 return OK; } // ListDelete_Sq int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { // 算法2.6 // 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。// 若找到,则返回其在L中的位序,否则返回0。 int i; ElemType *p; i = 1; // i的初值为第1个元素的位序 p = L.elem; // p的初值为第1个元素的存储位置 while (i <= L.length && !(*compare)(*p++, e)) ++i; if (i <= L.length) return i; else return 0; } // LocateElem_Sq void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { // 算法2.7 // 已知顺序线性表La和Lb的元素按值非递减排列。 // 归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列。ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType)); if (!Lc.elem) exit(OVERFLOW); // 存储分配失败 pa_last = La.elem+La.length-1; pb_last = Lb.elem+Lb.length-1;

数据结构实验报告代码

线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) {

数据结构:树形结构完整代码,各种遍历方法,直接能跑

#include #include #define TElemType int typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef BiTree DataType; typedef struct queuenode{ DataType data; struct queuenode *next; } QueueNode; //LINKQUEUE //HEAD POINTER, AND REAR POINTER ARE A V ALIBALE typedef struct { QueueNode *front; QueueNode *rear; } LinkQueue; int InitQueue(LinkQueue *Q); int DestroyQueue(LinkQueue *Q); int QueueEmpty(LinkQueue Q); int EnQueue(LinkQueue *Q, DataType e); DataType DeQueue(LinkQueue *Q); int CreateBiTree(BiTree *T); int PreOrderTraverse(BiTree T, int (*visit)(TElemType e)); int PreOrderTraverse2(BiTree T, int (*visit)(TElemType e)); int InOrderTraverse(BiTree T, int (*visit)(TElemType e)); int InOrderTraverse2(BiTree T, int (*visit)(TElemType e)); int PostOrderTraverse(BiTree T, int (*visit)(TElemType e)); int PostOrderTraverse2(BiTree T, int (*visit)(TElemType e)); int LevelOrderTraverse(BiTree T, int (*visit)(TElemType e)); int printElem(TElemType e); int InitBiTree(BiTree *T); int DestroyBiTree(BiTree *T); int ClearBiTree(BiTree *T); int BiTreeEmpty(BiTree T); int BiTreeDepth(BiTree T);

数据结构课程设计报告(校园导游系统)附有源代码

课程论文(设计)2011-2012学年第2学期 课程名称:数据结构课程设计 课程性质:实践课 专业班级: 考核方式:考查 学生姓名: 学号: 学时:1周 教师姓名:

目录 1. 作业内容 (1) 2. 基本思路 (1) 2.1 本校10个景点 (1) 2.2 图的初始化 (2) 2.3 图的遍历 (2) 2.4 求最短路径 (3) 3.系统流程 (4) 3.1 系统的简单说明 (4) 3.2 系统流程图 (5) 4. 系统运行效果图 (5) 4.1 校园导游界面 (5) 4.2 华农校园地图 (6) 4.3 景点的相关信息查询 (6) 4.4 任意两个景点间的最短路径 (7) 4.5 退出校园导游系统 (8) 5.总结 (9) 6.参考文献 (10)

1. 作业内容 设计一个校园导游程序,为来访客人提供各种信息查询任务。基本要求: (1)设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介信息,以边表示路权,存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询 (3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。 2. 基本思路 要完成对整个导游图系统的功能实现,需要对的每一项功能都有清楚的设想和认识,了解并明确每一项功能的实现需要解决的问题,选择正确并且高效的算法把问题逐个解决,最终实现程序的正确调试运行。有以下设计思路: (1).结合本校的实际情况,选出10个景点; (2).人为手工为选出的10个景点赋上相关信息(名称、代号、简介信息、以及路权等等); (3).根据选出来的10个景点用邻接矩阵存储校园图。 (4).依照景点的相关信息创建校园图。 (5).把纸质上的内容,利用C++编程语言编写查找景点相关信息的程序。 (6).根据人为赋值的路权,迪杰斯特拉算法计算任意两点之间的最短路径。 (7).综上所诉,用一个主函数把这些板块合成,生产一个菜单界面呈现在用户面前。 为此,可把系统分为以下几个核心:图的初始化、图的遍历、求最佳路线。 2.1 选出本校10个景点 结合华南农业大学实际情况,我选出以下10个景点,从1到10编号:

数据结构实验一的源代码

#include #include typedef struct Node { int key;//密码 int num;//编号 struct Node *next;//指向下一个节点 } Node, *Link; void InitList(Link &L) //创建一个空的链表{ L = (Node *)malloc(sizeof(Node)); if (!L) exit(1); L->key = 0; L->num = 0; L->next = L; } void Creatlinklist(int n, Link &L) //初始化链表{ Link p, q; q = L; for (int i = 1; i <= n; i++) { p = (Node *)malloc(sizeof(Node)); if (!p) exit(1); scanf("%d", &p->key); p->num = i; L->next = p; L = p; } L->next = q->next; free(q); } Link Locate_m(Link &p, int m)//找到第m个 { Link q; for (int j = 1; jnext; q = p->next; m = q->key;

return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码:\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); }

运动会分数统计数据结构课程设计(含源代码)

. 计算机学院信管专业 数据结构课程设计 题目:运动会分数统计班级: 姓名:学号: 同组人: 起迄日期: 课程设计地点: 指导教师: 评阅意见: 成绩评定: 评阅人:日期: 完成日期:2013年12月

目录 1、需求分析 (02) 2、概要设计 (03) 3、详细设计 (04) 4、调试分析和测试结果 (05) 5、总结 (13) 6、参考文献 (14) 7、致 (14) 8、附录 (14)

1、需求分析 (1)任务: 参加运动会有n个学校,学校编号为1……n。比赛分成m个男子项目,和w 个女子项目。项目编号为男子1……m,女子m+1……m+w。不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m<=20,n<=20) (2)功能要求: a).可以输入各个项目的前三名或前五名的成绩; b).能统计各学校总分, c).可以按学校编号、学校总分、男女团体总分排序输出; d).可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的学校。 (3)规定: 输入数据形式和围:20以的整数(如果做得更好可以输入学校的名称,运动项目的名称) (4)输出形式: 有中文提示,各学校分数为整形 (5)界面要求: 有合理的提示,每个功能可以设立菜单,根据提示,可以完成相关的功能要求。 (6)存储结构: 学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在

数据文件中。 (7)测试数据: 要求使用1、全部合法数据;2、整体非法数据;3、局部非法数据。进行程序测试,以保证程序的稳定。测试数据及测试结果请在上交的资料中写明; 2、概要设计 (1)文字分析 本课设要求输入信息,统计分数,执行排序与查找功能,在要求中没有在建立数据之后进行插入和删除操作,而在排序和查找过程中有许多的随机读取数据操作,因此使用顺序结构而不用链表。由于各个要求属性具有一定的联系,在定义数据时使用结构体和结构体数组来存储信息数据。考虑到程序的要求在设计函数时将学校个数和项目个数设计为可变的数据,为方便使用设计菜单函数(menu),而由于要求将信息存储在文件中故设计文件的存储(savetofile)与读取函数(readfromfile),信息输入函数(input)在输入基本信息后由系统统计总分的容并全部存入文件file中,在接下来的函数中开始都需要读取文件中的信息,信息的输出(output)输出输入函数中统计后的各项信息,在排序输出(sortput)中使用冒泡排序法进行不同关键字的排序,查询函数(search)采用顺序表的查找来完成。

数据结构实验程序

顺序表的基本操作 #include using namespace std; typedef int datatype; #define maxsize 1024 #define NULL -1 typedef struct { datatype *data; int last; }sequenlist; void SETNULL(sequenlist &L) { L.data=new datatype[maxsize]; for(int i=0;i>https://www.wendangku.net/doc/5d14965262.html,st; cout<<"请输入"<>L.data[i]; } int LENGTH(sequenlist &L) { int i=0; while(L.data[i]!=NULL) i++; return i; } datatype GET(sequenlist &L,int i) { if(i<1||i>https://www.wendangku.net/doc/5d14965262.html,st) { cout<<"error1"<

int j=0; while(L.data[j]!=x) j++; if(j==https://www.wendangku.net/doc/5d14965262.html,st) { cout<<"所查找值不存在!"<=maxsize-1) { cout<<"overflow"; return NULL; } else if(i<1||(i>https://www.wendangku.net/doc/5d14965262.html,st)) { cout<<"error2"<=i-1;j--) L.data[j+1]=L.data[j]; L.data[i-1]=x; https://www.wendangku.net/doc/5d14965262.html,st++; } return 1; } int DELETE(sequenlist &L,int i) { int j; if((i<1)||(i>https://www.wendangku.net/doc/5d14965262.html,st+1)) { cout<<"error3"<

数据结构课程设计文章编辑(附录中有全部代码)

课程设计任务书 专业名称:计算机科学与技术(软件工程) 课程名称:数据结构课程设计 设计题目:文章编辑问题 起止时间:2013年6 月24 日至2013年7 月12 日 问题描述 静态存储一页文章,每行最多不超过80个字符,共N行,程序可以统计出文字、数字、空格的个数,并且可以对文章中特定内容进行查找及替换,同时也可以删除指定内容。 基本要求 (1)分别统计出其中英文字母数和空格数及整篇文章总字数; (2)统计某一字符串在文章中出现的次数,并输出该次数; (3)查找出文章中某一段文字,并用其他文字进行替换; (4)删除某一子串,并将后面的字符前移。 输出形式: (1)分行输出用户输入的各行字符; (2)分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"; (3)查找出指定字符串在文章中出现的所有地方并替换,输出替换后结果; (4)输出删除某一字符串后的文章; 实现提示 存储结构使用线性表,分别用几个子函数实现相应的功能,并且使用菜单的形式,可以选择所要进行的操作(查找、替换、删除、统计等)。

文章编辑系统 1概要设计 本次课程设计的题目是文章编辑系统,本系统的功能描述如下:用户新建文本、浏览新建文本、文本字符统计、指定字符串统计、指定字符串删除、指定字符串替换等操作。 1.新建文本 2.浏览输入文本 3.文本字符统计 4.指定字符串统计 5.指定字符串删除 6.指定字符串替换 7.退出系统 本系统包含七个功能模块,分别为:新建文本模块,浏览输入文本模块,指定字符串统计模块,指定字符串删除模块,指定字符串删除模块,指定字符串替换模块以退出系统模块。新建文本模块实现用户录入文本信息,并且系统自动保存录入信息。浏览输入文本模块实现了显示用户录入信息的功能。指定字符串统模块实现了对英文字母数和空格数及整篇文章总字数的统计。指定字符串统计实现了统计用户自定义字符串个数的功能。指定字符串删除模块实现了对用户自定义字符串的删除。指定字符串替换模块实现了替换用户自定义字符串为用户定义的新字符功能。退出系统模块实现了退出系统功能。

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include >验目的 掌握顺序栈的基本操作:初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)分析问题的要求,编写和调试完成程序。 (3)保存和打印出程序的运行结果,并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下:

(1)定义栈的顺序存取结构。 (2)分别定义顺序栈的基本操作(初始化栈、判栈空否、入栈、出栈等)。 (3)定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中,括号配对共有四种情况:左右括号配对次序不正确;右括号多于左括号;左括号多于右括号;左右括号匹配正确。 (4)设计一个测试主函数进行测试。 (5)对程序的运行结果进行分析。 实验代码: #include < > #define MaxSize 100 typedef struct { ??? int data[MaxSize]; ??? int top; }SqStack; void InitStack(SqStack *st) 验目的 (1)进一步掌握指针变量的用途和程序设计方法。 (2)掌握二叉树的结构特征,以及链式存储结构的特点及程序设计方法。 (3)掌握构造二叉树的基本方法。 (4)掌握二叉树遍历算法的设计方法。 3.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)掌握一个实际二叉树的创建方法。 (3)掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。 4.实验内容 (1)定义二叉链存储结构。

图书管理系统(含源代码)c语言_数据结构课程设计报告

数据结构大作业 图书管理系统 工程管理121279044 伍 目录 一、题目要求 (1) 二、总体设计 (2) 三、编码实现 (2) 1) 定义图书结构体 (2) 2) 登记操作 (2) 3) 查看操作 (2) 4) 删除操作 (2) 5) Main函数 (2) 四、调试与测试 (2) 五、五心得体会 (2) 六、用户手册 (2)

一、题目要求 1)目的要求 本课程设计任务的目的是要求学生按照分析、设计、编码、调试和测试的软件开发过程独立完成管理系统设计,以及C语言算法的掌握,并能最终实现本系统的功能要求,通过这个程序可以学习到以前调试短程序没有的的经验。 2)题目要求 实现图书管理信息系统的设计。要现图书添加、显示全部图书、查询、借阅和归还。主要考查利用文件的操作! 二、总体设计

三、编码实现 1)定义图书结构体 struct book{ char bookname[20]; //书名 int NO; //书编号 char type[20]; //类型 int date; //到书日期 }; struct person{ char name[10]; // char classes[20]; //班级 int number; //学号 char telephone[12]; //联系 int NO; //书编号 char bookname[20]; //书名 int borrowdate; //借书日期 int returndate; //还书日期 2)登记操作 void new_book() //登记新书{ FILE *fp; struct book b; int i,j; if((fp=fopen("shuku.txt","a"))==NULL){ printf("File open error!\n");

数据结构上机实验线性表单链表源代码

#include template class LinearList { public: virtual bool IsEmpty()const=0; virtual int Length()const=0; virtual bool Find(int i,T& x)const=0; virtual int Search(T x)const=0; virtual bool Insert(int i,T x)=0; virtual bool Update(int i,T x)=0; virtual bool Delete(int i)=0; virtual void Output(ostream& out)const=0; protected: int n; }; #include "linearlist" template class SeqList:public LinearLisr { public: SeqList(int mSize); ~SeqList(){delete [] elements;} bool IsEmpty()const; bool Find(int i,T& x)const; int Length()const; int Search(T x)const; bool Insert(int i,T x); bool Update(int i,T x); bool Delete(int i); void Output(ostream& out)const; private: int maxLength; T *elements; }; template SeqList::SeqList(int mSize) { maxLength=mSize;

数据结构算法大全有代码

排序算法有:插入排序,合并排序,冒泡排序,选择排序,希尔排序,堆排序,快速排序,计数排序,基数排序,桶排序(没有实现) 。比较一下学习后的心得。我不是很清楚他们的时间复杂度,也真的不知道他们到底谁快谁慢,因为书上的推导我确实只是小小了解,并没有消化。也没有完全理解他们的精髓,所以又什么错误的还需要高手指点。呵呵。 1. 普及一下排序稳定,所谓排序稳定就是指:如果两个数相同,对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是 A = {1,1,1,2,2}稳定就是排序后第一个 1 就是排序前的第一个1,第二个1 就是排序前第二个1,第三个1 就是排序前的第三个1。同理 2 也是一样。这里用颜色标明了。不稳定呢就是他们的顺序不应和开始顺序一致。也就是可能会是A={1,1,1,2,2}这样的结果。 2. 普及一下原地排序:原地排序就是指不申请多余的空间来进行的排序,就是在原来的排序数据中比较和交换的排序。例如快速排序,堆排序等都是原地排序,合并排序,计数排序等不是原地排序。 3. 感觉谁最好,在我的印象中快速排序是最好的,时间复杂度:n*log(n) ,不稳定排序。原 地排序。他的名字很棒,快速嘛。当然快了。我觉得他的思想很不错,分治,而且还是原地排序,省去和很多的空间浪费。速度也是很快的,n*log(n) 。但是有一个软肋就是如果已经是排好的情况下时间复杂度就是n*n, 不过在加入随机的情况下这种情况也得以好转,而且他可以做任意的比较,只要你能给出两个元素的大小关系就可以了。适用范围广,速度快。 4. 插入排序:n*n 的时间复杂度,稳定排序,原地排序。插入排序是我学的第一个排序,速 度还是很快的,特别是在数组已排好了之后,用它的思想来插入一个数据,效率是很高的。因为不用全部排。他的数据交换也很少,只是数据后移,然后放入要插入的数据。(这里不 是指调用插入排序,而是用它的思想) 。我觉得,在数据大部分都排好了,用插入排序会给你带来很大的方便。数据的移动和交换都很少。 插入排序主要思想是:把要排序的数字插入到已经排好的数据中。(我自己理 解的哈)。例如12356 是已经排好的序,我们将4插入到他们中,时插入之后也是排好序的。这里显而易见是插入到 3 的后面。变为123456. 实现思路:插入排序就是先是一个有序的数据,然后把要插入的数据插到指定的位置,而排序首先给的就是无序的,我们怎么确定先得到一个有序的数据呢?答案就是:如果只有一个,当然是有序的咯。我们先拿一个出来,他是有序的,然后把数据一个一个插入到其中,那么插入之后是有序的,所以直到最后都是有序的。。哈哈。结果就出来了! 当然在写的时候还是有一个技巧的,不需要开额外的数组,下标从第二个元素开始遍历直到最后一个,然后插入到前面已经有序的数据中。这样就不会浪费空间了。插入排序用处还是 很多的,特别是链表中,因为链表是指针存放的,没有数组那么好准确的用下标表示,插入是简单有效的方法。嘻嘻。。废话少说, 源代码奉上: 1 #include 2 #include 3 4 // 插入排序从小到大,nData 为要排序的数据,nNum 为数据的个数,该排序是稳定的排序 5 bool InsertionSort(int nData[], int nNum) 6 { 7 for (int i = 1; i < nNum; ++i) // 遍历数组,进行插入排序 8 { 9 int nTemp = nData[i];

数据结构实验(七种排序算法的实现)题目和源程序

1、直接插入排序 2、希尔排序 3、2-路归并排序 4、折半插入排序 5、冒泡排序 6、快速排序 7、堆排序 /*---------------------------------------- * 07_排序.cpp -- 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘2011年写 ----------------------------------------*/ // ds07.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "stdio.h" #include #include using namespace std; #define MAXSIZE 20 typedefintKeyType; typedefstruct{ KeyType key; //关键字项 KeyType data; //数据项 }RedType; //记录类型 typedefstruct{ RedTypearr[MAXSIZE+1]; //arr[0]闲置或用作哨兵单元int length; //顺序表长度 }SqList; //顺序表类型typedefSqListHeapType; //对顺序表L做一趟希尔插入排序 //前后记录位置的增量是dk //r[0]只是暂存单元 //当j<=0时,插入位置已找到 voidshellInsert(SqList&L, intdk) {

int i, j; for (i = dk + 1; i <= L.length; i++) { if (L.arr[i].key 0 &&L.arr[0].key = high + 1; j--) L.arr[j + 1] = L.arr[j];//记录后移 L.arr[high + 1] = L.arr[0];//插入 }//for }//BInsertSort //直接插入排序

相关文档
相关文档 最新文档