基于算法本科最新毕业论文

整个研制过程，都体现了面向实用，面向软件开发者的思想。

鉴于该语言有这么优秀的特点，该论文选择C++为编程语言。 9.2 具体实现步骤 9.2.1 哈夫曼算法的实现

通过第三章对哈夫曼问题的分析，可以得出哈夫曼算法思路为：

（1）以n个字母为结点构成n棵仅含一个点的二叉树集合，字母的频率即为结点的权。

（2）每次从二叉树集合中找出两个权最小者合并为一棵二叉树：

增加一个根结点将这两棵树作为左右子树。新树的权为两棵子树的权之和。 （3）反复进行步骤（2）直到只剩一棵树为止。如图9.1所示。

Fig. 9.1 Huffman tree 图9.1 哈夫曼树

哈夫曼树的算法： template

BinaryTreeHuffmanTree(T f[]， int n) {根据权f[1:n]构造霍夫曼树 创建一个单节点树的数组

Huffman *W=newHuffman [n+1]； BinaryTree z，zero； for(int i=1；i<=n；i++){ z.MakeTree(i， zero， zero)； W[i].weight=f[i]； W[i].tree=z； } 数组变成—个最小堆 MinHeap>Q(1)； Q.Initialize(w，n，n)； 将堆中的树不断合并 Huffman x,y for(i=1;i

Q.DeleteMin(x)； Q.DeleteMin(y)；

z.MakeTree(0, x.tree, y.tree)； x.weight+=y.weight；x.tree=z Q.Insert(x)； }

Q. DeleteMin(x)；最后的树 Q. Deactivate()； delete[]w； return x.tree； 算法分析

HuffmanTree初始化优先队列Q需要O(n)。DeleteMin和Insert需O(logn)。n-1次的合并总共需要O(nlogn)。所以n个字符的哈夫曼算法的计算时间为O(nlogn)。 9.2.2 单源最短路径问题

问题：给定带权有向图G=(V,E)，其中每条边的权是一个非负实数。要计算从V的一点v0(源)到所有其他各顶点的最短路长度。路长指路上各边权之和。

算法思路(Dijkstra)：设最短路长已知的终点集合为S，初始时v0∈S，其最短路长为0，然后用贪心选择逐步扩充S：每次在V-S中，选择路径长度值最小的一条最短路径的终点x加入S。

构造路长最短的最短路径：设已构造i条最短路径，则下一个加入S的终点u必是V-S中具有最小路径长度的终点，其长度或者是弧(v0，u)，或者是中间只经过S中的顶点而最后到达顶点u的路径。

算法描述：

(1)用带权的邻接矩阵c来表示带权有向图，c[i][j]表示弧上的权值。若∈V，则置c[i][j]为∞。设S为已知最短路径的终点的集合，它的初始状态为空集。从源点v到图上其余各点vi的当前最短路径长度的初值为：dist[i]=c[v][i] vi∈V

(2)选择vj，使得dist[j]=Min{dist[i]|vi∈V-S}，vj就是长度最短的最短路径的终点。令S=SU{j}。

(3)修改从v到集合V-S上任一顶点vk的当前最短路径长度：如果dist[j]+c[j][k]

(4)重复操作(2)，(3)共n-1次。

voidDijkstra(int n, intv,Type dist[], int prev[], Type **c) { bool s[maxint]；

for (int i=1;i<=n; i++){

dist[i]=c[v][i]； s[i]=false；

if(dist[i]= =maxint) prev[i]=0 else prev[i]=v ; } dist[v]=0；s[v]=true； for (int i=1;i

int temp=maxint； int u= v；

for (int j= 1；j<=n；j++) if ((!s[j])&&(dist[j]

u=j；

temp=dist[j]；} s[u]=true；

for (int j=1；j<=n;j++) ；

if((!s[j])＆＆(c[u][j]

Type newdist=dist[u)+c[u][j] if (newdist

dist[]]=newdist；

prev[j]=u; }}}} 算法分析

用带权邻接矩阵表示有n个顶点和e条边的带权有向图，主循环体需要O(n)时间，循环需要执行n-1次，所以完成循环需要O(n2)。 9.2.3 删数问题

通过第五章对删数问题的分析，可以得出删数算法的思路为： （1）x1

（2）如果xk

数Nl，可表示为x1x2?xixkxm?xn。

（3）对N1而言，即删去了1位数后，原问题T变成了需对n-1位数删去k-1个数新问题T’。

（4）新问题和原问题相同，只是问题规模由n减小为n-1，删去的数字个数由k减少为k-1。

（5）基于此种删除策略，对新问题T’，选择最近下降点的数进行删除，如此进行下去，直至删去k个数为止。

算法分析：时间复杂性为O(n)，空间复杂性为O(n)。 9.2.4 会场安排问题

通过第八章对会场安排问题的分析，可以得出解会场安排问题的思路为： （1）n个活动开始和结束时间分别是s[i]和f[i]，而且f[1]

注：这里的stack只是作为统计最大的重叠数目用，如果要真的模拟使用情况，用queue模拟响应的活动安排好。

算法复杂度为O（nlogn）。 9.3程序编码与程序调试

具体应用核心代码见附录，调试结果见图9.2、图9.3、图9.4、图9.5所示。