数据结构问题

《数据结构问题》由会员分享，可在线阅读，更多相关《数据结构问题（11页珍藏版）》请在装配图网上搜索。

1、常见的数据结构问题动态数组存储问题：在日常生活中的应用我们不可能将数组的长度确定，但是实际情况又要求对数据进行一些处理，因此用链表来存储数据是一种很理想的状态。1. 插入元素static void insertLinklist(LinkList list,char e) /插入节点 LinkList p; p = new LinkList(); p.data = e; if (list = null) list = p; p.nextNode = null; else p.nextNode = list.nextNode; list.nextNode = p; 2. 排序static void

2、 DynamicSort(LinkList q) /动态数组排序 LinkList p = q; /p用来表示当前链表并存储head int i,j,k=0; char t; /用于交换 while(p != null) k+; /计量链表的元素个数 p = p.nextNode; p = q; for(i=0;i k-1;i+) /用一个双层循环对链表进行排序 for(j=0;j p.nextNode.data) t = p.data; p.data = p.nextNode.data; p.nextNode.data = t; p = p.nextNode; p = q; 测试结果简单约瑟

3、夫环：问题描述罗马人攻占了乔塔帕特，41个人藏在山洞中，其中包括约瑟夫和他的一个朋友。而此时另外39个人为了表示忠贞准备集体自杀，他们约定41个人围成一个圈，由第一个人开始顺时针报数，每报数为3的人就立刻自杀，然后由下一个人重新报数，依次类推，直到所有人都死亡.但最后约瑟夫和他的朋友却躲过了一劫，请问他们在圈中的原始位置。解题思路我们分析一下就可以得到，到最后的两个人时只要只剩下约瑟夫和他的朋友就可以了。那么如何达到目的呢：一个明显的求解的方法就是将41个人排成一个环，内圈为按照顺时针的最初编号，外圈为每个人数到数字3的顺序，我们可以使用数组来保存约瑟夫环中该自杀的数据，而数组的下标作为参与人

4、员的编号，并将数组看做环形来处理。源码这里只给出关键的处理函数，测试的主方法用户可以自行编写： /*在while里面嵌套一个do-while；在do-while里面执行杀人的准备， *每计数到三就跳出一次循环，打印语句，并将对应的man数组值设为约瑟夫编号 * */ static void Josephus(int alive) /约瑟夫方法，alive为要存活的人数 /约瑟夫编号，如果没被杀死，值为0；杀死了之后值为约瑟夫编号，即第几个被杀死的 int man = new intNum; /声明为数组,Java的特性，全部被初始化为0； int i = 0; /用于计数口号，为3则杀掉 in

5、t count = 0,pos = 0; /计数器和计量位置的下标 while(count Num-alive) do pos = (pos+1)%Num; / if(manpos=0) i+; /未被砍，i加1； if(i=KillMan) i=0; break; /要死人了，跳出do-while; while (true); count+; manpos = count; /赋值给数组，表示是第几个被杀死的； System.out.println(No.+pos+ Died! + His Josephus number is +manpos); /表示这个人已经死了； System.out

6、.println(); System.out.println(); /找到幸存者编号 pos = 0; while(pos Num) if(manpos=0) System.out.println(One position is + pos); pos+; 测试结果需要两个人存活，所以这里输入2：复杂约瑟夫环问题描述n个人环坐一圈，按照顺时针方向依次编号为1、2、3、.、n。有一个黑盒子里放置着许多的字条，其上写有随机的数字。每个人随机取一个字条，上面的对应数字即为出列数字。游戏开始时，任选一个处理数字M,从第一个人开始，按编号顺序自1开始顺序报数，报到m的人出列，同时将手中的数字作为新的出列

7、数字。然后从下一个人开始重新从1开始报数，如此循环下去，直至最后一人。分析思路这里和前面的思路类似，只是我们要注意两个问题：-由于这里的n是可变的，不能用数组表示，应该用链表。另外n个人首尾相接，应该使用循环链表。-出列数字不是固定的，每个人都有不同的值，这里应该单独处理。处理源码package com.Test;import java.util.Scanner;/*解决简单的约瑟夫环问题* */public class test static Scanner IN = new Scanner(System.in); static LinkList head = null,tail = nul

8、l; /链表的头指针和尾指针 int size = 0; public static void main(String args) test t = new test(); int e,baoshu; /初次报数号 System.out.println(Input the number in the rings:); int num = IN.nextInt(); /输入约瑟夫环人数 System.out.println(According the order input the OutputLine Number:); e = IN.nextInt(); t.addHead(1,e); fo

9、r(int i=2;i =num;i+) e = IN.nextInt(); t.addTail(i,e); System.out.println(Input the first one to Output!); baoshu = IN.nextInt(); Josephus(head,baoshu); /求解复杂约瑟夫环 System.out.println(); /* *思路：逐个计数啊，到谁谁就出列； *然后重置出列数，从下一个开始计数，直到剩下最后一个人（p.next = p） */ static void Josephus(LinkList head,int m) /约瑟夫方法，al

10、ive为要存活的人数 LinkList q,p; int i; q = p = head; while (q.next != p) q = q.next; System.out.println(); while(p.next != p) /循环的终止的条件就是只剩一个人； for(i = 0;i m-1;i+) q = p; p = p.next; q.next = p.next; /删除p指向的节点 /一组循环完后，一人出列； System.out.println(The number + p.no + is out!+ His number is +p.psw); m = p.psw; /

11、将出列号设为出列人的出列号 p = null; p = q.next; /从下一个人开始继续计数 System.out.println(The last one is : + p.no+! His number is +p.psw); public void addHead(int i,int psw) head = new LinkList(i,psw,head); if(tail = null) tail = head; size+; public void addTail(int i,int psw) tail.next = new LinkList(i,psw); tail = tai

12、l.next; tail.next = head; size+; 测试结果城市的最短总距离问题描述求解一个城市群间的最短总距离，即要求遍历所有城市的最短距离。算法解析问题也即在图论中求解最小生成树：（1）、将图中所有顶点的集合记为V,最小生成树中的顶点集合为U。初始时，V中包含所有顶点，而U为空。（2）、首先从V集合中取出一个顶点（设为V0）,将其加入到集合U中。（3）、从V0的邻接点钟选择点Vn，使（V0,Vn）边的权值最小，得到最小生成树的一条边。将Vn点加入集合U.（4）、接着从V-U集合中再选出一个与V0，Vn邻接的顶点，找出权值最小的一条边。得到最小生成树的另一条边。将该顶点加入结合

13、U。（5）、按上述步骤不断重复，最后便可以得到该图的最小生成树。源代码public static void main(String args)throws Exception static void PrimGraph(GraphMatrix GM) /最小生成树算法 int i,j,k,min,sum; int weight = new intGraphMatrix.MaxNum; char vtempx = new charGraphMatrix.MaxNum; /保留顶点信息 sum = 0; for(i=1;i GM.VertextNum;i+) weighti = GM.EdgeWe

14、ight0i; if(weighti=MaxValue) vtempxi = (char)NoL; else vtempxi = GM.Vertex0; /邻接顶点 vtempx0 = USED; /选用 weight0 = MaxValue; for(i=1;i GM.VertextNum;i+) min = weight0; k = i; for(j = 1;j = GM.VertextNum;j+) if(weightj 0) /找到权值更小的未使用边 min = weighti; /保存权值 k = j; /保存邻接点序号 sum += min; System.out.println(

15、vtempxk+ +GM.Vertexk); /输出生成树的一条边 vtempxk = USED; weightk = MaxValue; for(j=0;j GM.VertextNum;j+) if(GM.EdgeWeightkj weightj & vtempxj!=0) weightj = GM.EdgeWeightkj; vtempxj = GM.Vertexk; System.out.println(The smallest sum of weight is +sum);测试结果括号配对算法描述这里很明显的我们应该用栈结构来描述：（1）、输入一个字符，当该字符是括号字符时，程序进入循

16、环处理；（2）、如果是左括号，将其入栈，并继续继续执行步骤1；（3）、如果是右括号，则取出栈顶数据进行对比，如果匹配不进行操作；否则必须将刚才取出的栈顶数据重新入栈，再将刚才输入的括号也入栈；（4）、然后输入下一个字，重复执行，直到所有的字符都得到操作。源码：/用于匹配的方法；void pipei() throws Exception Stack stack; char ch; char temp = 3; int match = 0; stack = new Stack(0); /初始化一个栈,为空 BufferedReader reader = new BufferedReader(new

17、 InputStreamReader(System.in); ch = (char) reader.read(); /输入一个字符 while (ch != 0) if (getElementCount() = -1) push(ch); else temp = pop(); /取出栈顶元素 match = 0; if (temp = & ch = ) match = 1; if (temp = ( & ch = ) match = 1; if (temp = ) match = 1; if (temp = & ch = ) match = 1; if (match = 0) /不匹配 push(temp); push(ch); ch = (char) reader.read(); /输入下一个字符 if (getElementCount() = -1) System.out.println(Total pipei!); /完全匹配 else System.out.println(Not pipei!);