本文提出一个新的数据结构概念——动态数据结构。基于这个概念，本文实现了一种新的数据结构——池及其在一维和二维时的情况。本文同时对这种新的数据结构在VLSI电路布局设计中的应用和在打印机任务调度中的应用进行了研究。 本文的主要贡献概括如下： 1.本文讨论了各种计算机应用中的动态数据处理要求，之后提出了动 态数据结构的概念。根据这一新概念，本文建议了一种新的数据结 构——池，它能对数据进行动态处理（例如，数据的表示，查找， 合并，排序和存储等等）。 2.本文研究了一维池和二维池的实现，对一维池和二维池的顺序存 取、基于周期机制和基于触发机制的动态秩序维持程序进行了研 究，并定义了一维池和二维池的基本运算。 3.本文成功地将池和遗传算法相结合，形成改进的基于池的遗传算法 （PGA），以作为池的一种灵活应用。然后，将基于池的遗传算法 （PGA）用于解决门阵列布局设计。对门阵列布局算例的计算机仿 搞要 真结果表明使用基于池的遗传算法汀GA）能够获得比传统遗传算 法（GA）更好的结果。 4．本文将快速进化规划算法（FEP）用于同样的门阵列布局算例，也 取得了满意的结果。 5．为减小通道布线中线网间的串扰，本文提出一个基于扰动的算法。 我们将此算法运用到若干benchlnn例子上去，并和已知的一些结 果进行了比较，结果表明我们建议的基于扰动的算法能够获得比文 甲 献p7习21更优的性能。 动态数据结构一池是一种普适的工具，可以用来解决其他计算机科学领域中的问题，比如进程管理、并行计算中的任务分配等。作为一个具体的应用，本文将二维池应用到打印机任务调度中，仿真结果表明算法能解决繁重的计算机排队打印问题。