课程设计--链表存储方式下的数据的插入，删除和搜索.docx

山东大学软件学院数据结构课程设计报告学 号姓 名 年 级 2010 专 业 软件工程 班 级 三班 学 期11-12学年第二学期日期: 2011年2月22日一 课程设计题目：链表存储方式下的数据的插入，删除和搜索。二 课程设计内容描述： 需求 以动态演示的形式向用户展示在链表存储方式下的数据记性插入，删除和搜索的实现方法和内部过程。 输入 以系统自动生成的方式新建链表，可以选择有序或无序生成，在面板显示出链表，链结点以箭头连接，以带色的方框内的数字为数据，需要生成特定链表可选择数据插入在链表首。 输出 在面板显示及显示三种操作(插入，查找和删除)的具体方法和流程，显示方式以指示箭头来表示对链表内容或位置的查询。插入或删除操作则在图中画出节点增加或者减少的过程。 功能 该程序可实现单向链表的插入删除和查找过程的演示，以动态的显示展示其操作过程。 测试 通过输入框中用户输入的数据和七个按钮的操作选择相应的功能，可实现动态演示。三 思想和算法： 对于演示可分为用户界面和动画演示两个部分在用户界面添加按钮，输入框，单项选择和演示区域，演示区域将使用动画演示进行展示。在用户界面分别给按钮及输入框等添加监听器，通过调用动画演示方法以实现按钮功能。动画演示通过创建show类实现链结点和创建showgroup类实现链结点的的动态显示。其内部引用awt.graphics类实现画线等功能。 对于三种操作来说，插入和删除的实现都必须依靠查找的功能，因此，在代码中有很大一部分是可以通用的，实现查找功能可分为两种：按用户输入的数据查找和按用户输入的位置查找，判定条件分别是show类中的值和showgroup中的curin值。插入操作需要在已建好的链表中增加一个节点，这就需要插入点以后的节点向后移动一个位置，将插入的节点放在该位置上，而删除是将插入点以后的节点向前移动一个位置。在showgroup类中，定义链表数据的数组以存储数据，将数组内的数据分别赋给各个节点，通过创建链表的方法创建链表。四使用说明 1运行 打开eclipse，导入工程，运行后，将显示如下界面界面中有七个按钮，一个单选项和两个输入框连续单击“新建”，按提示操作选择无序，出现以下界面或者选择有序则出现以下界面当输入有误时，则会有提示新建功能完成位置查找功能连续单击“数据查找”，按提示操作数据查找功能输入位置或数据不存在时删除操作按位置删除 其他操作不再赘述。五调试说明 导入工程后，打开所有代码，主程序在link.linklist，运行即可。六代码linklist类package link;import java.applet.applet;import java.awt.*;import java.awt.event.*;import java.text.numberformat;import java.util.eventobject;public class linklist extends applet implements runnable, actionlistener,itemlistener public void init() / 添加panelsetlayout(new flowlayout();panel panel = new panel();add(panel);panel.setlayout(new flowlayout();panel panel1 = new panel();panel.add(panel1);panel1.setlayout(new flowlayout(0);newbutton = new button(新建);panel1.add(newbutton);newbutton.addactionlistener(this);/ 插入按钮设置insposbutton = new button(位置插入);panel1.add(insposbutton);insposbutton.addactionlistener(this);insdatabutton = new button(数据插入);panel1.add(insdatabutton);insdatabutton.addactionlistener(this);/ 查找按钮设置finddatabutton = new button(数据查找);panel1.add(finddatabutton);finddatabutton.addactionlistener(this);findposbutton = new button(位置查找);panel1.add(findposbutton);findposbutton.addactionlistener(this);/ 删除按钮设置deldatabutton = new button(数据删除);panel1.add(deldatabutton);deldatabutton.addactionlistener(this);delposbutton = new button(位置删除);panel1.add(delposbutton);delposbutton.addactionlistener(this);panel panel2 = new panel();panel.add(panel2);panel2.setlayout(new gridlayout(2, 1);checkboxgroup checkboxgroup = new checkboxgroup();nosort = new checkbox(无序, true, checkboxgroup);panel2.add(nosort);nosort.additemlistener(this);sort = new checkbox(有序, false, checkboxgroup);panel2.add(sort);sort.additemlistener(this);panel panel3 = new panel();panel.add(panel3);panel3.setlayout(new flowlayout(2);panel3.add(new label(输入数字: );panel3.add(tf);panel panel4=new panel();panel.add(panel4);panel4.setlayout(new flowlayout(4);panel4.add(new label();panel4.add(pf);/panel3.add(new label(shur);/panel3.add(pf);theshowgroup = new showgroup();theshowgroup.dofill(13);repaint();public void start() if (runner = null) runner = new thread(this);runner.start();suppresswarnings(deprecation)public void stop() if (runner != null) runner.stop();runner = null;public void paint(graphics g) theshowgroup.draw(g);public void update(graphics g) paint(g);/ 监听按钮及输入框public void actionperformed(actionevent actionevent) isnumber = true;string s1 = tf.gettext();string s2=pf.gettext();if (s2=null)s2=1;try gpnumber = integer.parseint(s1);gpnumber=integer.parseint(s2); catch (numberformatexception _ex) gpnumber = 0;gpnumber=0;isnumber = false;/ 监听按钮/各个按钮的监听，输入数据和调用相应的方法if (actionevent.getsource() = newbutton)theshowgroup.newlist(isnumber, gpnumber);else if (actionevent.getsource() = insdatabutton)theshowgroup.datainsert(isnumber, gpnumber);else if (actionevent.getsource() = insposbutton)theshowgroup.posinsert(isnumber, gpnumber,gpnumber);else if (actionevent.getsource() = finddatabutton)theshowgroup.datafind(isnumber, gpnumber);else if (actionevent.getsource() = findposbutton)theshowgroup.posfind(isnumber, gpnumber);else if (actionevent.getsource() = deldatabutton)theshowgroup.datadelete(isnumber, gpnumber);else if (actionevent.getsource() = delposbutton)theshowgroup.posdelete(isnumber, gpnumber);repaint();try thread.sleep(10l);return; catch (interruptedexception _ex) return;public void itemstatechanged(itemevent itemevent) boolean flag = itemevent.getsource() = nosort;boolean flag1 = theshowgroup.getsortstatus();boolean flag2 = theshowgroup.getchangestatus();theshowgroup.setsortstatus(flag);if (flag & flag2 & !flag1 | !flag & !flag2 & flag1) nosort.setstate(true);sort.setstate(false);if (!flag & flag2 & flag1 | flag & !flag2 & !flag1) nosort.setstate(false);sort.setstate(true);public void run() do; while (true);public linklist() gpnumber = -1;isnumber = false;tf = new textfield(, 4);pf =new textfield(,4);private thread runner;private showgroup theshowgroup;private int gpnumber,gpnumber;private boolean isnumber;private textfield tf,pf;private checkbox nosort;private checkbox sort;private button newbutton;private button insdatabutton, insposbutton;private button finddatabutton, findposbutton;private button deldatabutton, delposbutton;showgroup类package link;import java.awt.color;import java.awt.graphics;class showgroup public showgroup() linkarray = new link28;totallinks = 0;curin = oldcurin = 0;codepart = 1;/ codepart2 = 1;drawmode = 2;note = 按任意键;notsorted = true;isokchangesort = false;areinserting = false;/ inspkeynow=0;/ 创建节点private show makeshow(int i) int j = 100 + (int) (math.random() * 154d);int k = 100 + (int) (math.random() * 154d);int l = 100 + (int) (math.random() * 154d);color color = new color(j, k, l);return new show(i, color);/ 获取有序或无序链表public boolean getsortstatus() return notsorted;/ 获取选择改变值public boolean getchangestatus() return isokchangesort;public void setsortstatus(boolean flag) if (isokchangesort & flag != notsorted)notsorted = flag;if (!isokchangesort)note = 改变顺序;drawmode = 1;/ 新建链表，int为链表长度public void newlist(boolean flag, int i) / 判断按钮areinserting = false;aredeleting = false;if (opmode != 1) opmode = 1;codepart = 1;switch (codepart) case 1: / 001note = 输入链表长度，第一个输入框为长度，第二个输入0;drawmode = 1;codepart = 2;oldcurin = curin;curin = 0;return;case 2: / 002if (!flag | i 28) note = 长度值有误: （0 _ + 28 + );codepart = 1; else note = 即将创建长度为 + i + 的链表;codepart = 3;drawmode = 1;return;case 3: / 003note = 选择有序或者无序链表;isokchangesort = true;drawmode = 1;codepart = 4;return;case 4: / 004if (notsorted)note = 你选择了数据无序;elsenote = 您选择了数据有序;isokchangesort = false;totallinks = 0;drawmode = 2;codepart = 5;return;case 5: / 005totallinks = i;dofill(totallinks);note = 链表创建完成;链表长度 = + totallinks;oldcurin = curin;curin = 0;drawmode = 2;codepart = 6;return;case 6: / 006note = 单击任意按钮;drawmode = 1;codepart = 1;return;/ 建立数组存储public void dofill(int i) totallinks = i;for (int j = 0; j 28; j+)linkarrayj = null;oldcurin = curin;curin = 0;codepart = 1;if (notsorted) for (int k = 0; k totallinks; k+) / 随机数生成，存入数组int i1 = (int) (math.random() * 999d);temppers = makeshow(i1);linkarrayk = new link(temppers);return;int k1 = 0;int i2 = 0;for (int l = 0; l totallinks; l+) int l1 = (int) (999f - (float) i2) / (float) totallinks - (float) l);int j1 = (int) (math.random() * (double) l1);k1 += j1;i2 = k1;temppers = makeshow(k1);linkarrayl = new link(temppers); /按输入的数据插入public void datainsert(boolean flag, int i) /位置插入算法aredeleting = false;if (opmode != 3) opmode = 3;codepart = 1;switch (codepart) case 1: / 001oldcurin = curin;curin = 0;insertatend = false;note = 输入要插入的数据;drawmode = 1;codepart = 2;return;case 2: / 002if (!flag | i 999) note = 无法插入: 数值在0 - + 999;codepart = 1; else if (totallinks = 28) note = 无法插入: 数据已满;codepart = 6; else inskey = i;temppers = makeshow(inskey);if (notsorted) note = 即将插入这个数据 + inskey;codepart = 4; else note = 即将寻找插入点;codepart = 3;drawmode = 1;return;case 3: / 003if (curin = totallinks - 1& inskey linkarraycurin.persdata.getheight() note = found insertion point at end of list;insertatend = true;codepart = 5; else if (inskey linkarraycurin.persdata.getheight() note = 正寻找位置;oldcurin = curin+;codepart = 3; else note = 已找到位置;codepart = 4;drawmode = 1;return;case 4: / 004areinserting = true;if (notsorted)insdex = 0;elseinsdex = curin;note = 数据插入，链表复位;drawmode = 1;codepart = 5;return;case 5: / 005if (insertatend) oldcurin = curin+;note = 插入以下数据 + inskey+ 在链表末; else areinserting = false;for (int j = totallinks; j curin; j-)linkarrayj = linkarrayj - 1;note = 插入以下数据 + inskey;linkarraycurin = new link(temppers);totallinks+;drawmode = 2;codepart = 6;return;case 6: / 006note = 插入完成;链表长度 = + totallinks;drawmode = 1;codepart = 7;return;case 7: / 007oldcurin = curin;curin = 0;note = 按任意按钮;drawmode = 1;codepart = 1;return; /按输入的位置插入public void posinsert(boolean flag, int i,int data)/int data) / 按位置插入算法aredeleting = false;if (opmode != 3) opmode = 3;codepart = 1;switch (codepart) case 1: / 001oldcurin = curin;curin = 0;insertatend = false;note = 输入要插入的位置和数据，分别填入两个输入框;drawmode = 1;codepart = 2;return;case 2: / 002if (!flag | i totallinks) note = 无法插入，位置超限;codepart = 1; else if (totallinks = 28) note = 无法插入: 数据已满;codepart = 6; else inspkey = i;temppers = makeshow(data);if (notsorted) note = 即将插入这个数据 ，位置 + inspkey+数据+data;codepart = 4; else note = 即将寻找插入点;codepart = 3;drawmode = 1;return;case 3: / 003if (curin = totallinks - 1& inskey =curin) note = 已找到位置;insertatend = true;codepart = 5; else if (inspkey curin) note = 正寻找位置;oldcurin = curin+;codepart = 3; else note = 已找到位置;codepart = 4;drawmode = 1;return;case 4: / 004areinserting = true;if (notsorted)insdex = 0;elseinsdex = curin;note = 数据插入，链表复位;drawmode = 1;codepart = 5;return;case 5: / 005if (insertatend) oldcurin = curin+;note = 插入以下数据 + inspkey+ 在链表末; else areinserting = false;for (int j = totallinks; j curin; j-)linkarrayj = linkarrayj - 1;note = 插入以下数据 + inspkey;linkarraycurin = new link(temppers);totallinks+;drawmode = 2;codepart = 6;return;case 6: / 006note = 插入完成; 链表长度 = + totallinks;drawmode = 1;codepart = 7;return;case 7: / 007oldcurin = curin;curin = 0;note = 按任意按钮;drawmode = 1;codepart = 1;return; /按输入的数据查找public void datafind(boolean flag, int i) / 数据查找算法areinserting = false;aredeleting = false;if (opmode != 4) opmode = 4;codepart = 1;switch (codepart) case 4: / 004case 5: / 005default:break;case 1: / 001note = 输入要查找的数据;codepart = 2;break;case 2: / 002if (!flag | i 999) note = 输入有误0- + 999;codepart = 1; else findkey = i;oldcurin = curin;curin = 0;note = 正在查找 + findkey;codepart = 3;break;case 3: / 003if (linkarraycurin.persdata.getheight() = findkey) note = 已经找到 + findkey;codepart = 6;break;if (curin = totallinks - 1 | !notsorted& curin findkey) note = 未找到 + findkey;codepart = 6; else note = 正在查找 + findkey;oldcurin = curin+;codepart = 3;break;case 6: / 006oldcurin = curin;curin = 0;note = 按任意键;codepart = 1;break;drawmode = 1; /按输入的位置查找public void posfind(boolean flag, int i) / 位置查找算法areinserting = false;aredeleting = false;if (opmode != 4) opmode = 4;codepart = 1;switch (codepart) case 4: / 004case 5: / 005default:break;case 1: / 001note = 输入你查找的位置;codepart = 2;break;case 2: / 002if (!flag | i 28) note = 位置超出0- + totallinks;codepart = 1; else findpkey = i;oldcurin = curin;curin = 0;note = 正在查询位置 + findpkey;codepart = 3;break;case 3: / 003if (curin = findpkey) note = 已经找到位置 + findpkey;codepart = 6;break;if (curin = totallinks - 1 | !notsorted & curin findpkey) note = 无法找到位置 + findpkey;codepart = 6; else note = 正在查询位置 + findkey;oldcurin = curin+;codepart = 3;break;case 6: / 006oldcurin = curin;curin = 0;note = 按任意键;codepart = 1;break;drawmode = 1; /按输入的数据删除public void datadelete(boolean flag, int i) / 数据删除算法areinserting = false;if (opmode != 5) opmode = 5;codepart = 1;switch (codepart) case 1: / 001note = 输入要删除的数据;drawmode = 1;codepart = 2;return;case 2: / 002if (!flag | i 999) note = 数据超限0 - + 999;codepart = 1; else delkey = i;oldcurin = curin;curin = 0;note = 正在查找数据 + delkey;codepart = 3;drawmode = 1;return;case 3: / 003if (linkarraycurin.persdata.getheight() = delkey) note = 已经找到数据 + delkey;if (curin = totallinks - 1)codepart = 5;elsecodepart = 4; else if (curin = totallinks - 1 | !notsorted& linkarraycurin.persdata.getheight() delkey) note = 无法找到 + delkey;codepart = 6; else note = 正在查找数据 + delkey;oldcurin = curin+;codepart = 3;drawmode = 1;return;case 4: / 004aredeleting = true;deldex = curin;note = 删除完成，链表复位;drawmode = 1;codepart = 5;return;case 5: / 005aredeleting = false;for (int j = curin; j totallinks - 1; j+)linkarrayj = linkarrayj + 1;totallinks-;oldcurin = curin;curin = 0;note = 删除数据完成 + delkey;drawmode = 2;codepart = 6;return;case 6: / 006oldcurin = curin;curin = 0;note = 按任意键;codepart = 1;return; /按输入端位置删除public void posdelete(boolean flag, int i) / 位置删除算法areinserting = false;if (opmode != 5) opmode = 5;codepart = 1;switch (codepart) case 1: / 001note = 输入要删除的位置;drawmode = 1;codepart = 2;return;case 2: / 002if (!flag | i totallinks) note = 位置不存在0 - +totallinks;codepart = 1; else delpkey = i;oldcurin = curin;curin = 0;note = 正在查找位置 + delpkey;codepart = 3;drawmode = 1;return;case 3: / 003if (curin = delpkey) note = 已经找到位置 + delpkey;if (curin = totallinks - 1)codepart = 5;elsecodepart = 4; else if (curin = totallinks - 1 | !notsorted & curin delpkey) note = 无法找到位置 + delpkey;codepart = 6; else note = 正在查找位置 + delpkey;oldcurin = curin+;codepart = 3;drawmode = 1;return;case 4: / 004aredeleting = true;deldex = curin;note = 删除完成，链表即将复位;drawmode = 1;codepart = 5;return;case 5: / 005aredeleting = false;for (int j = curin; j totallinks - 1; j+)linkarrayj = linkarrayj + 1;totallinks-;oldcurin = curin;curin = 0;note = 删除完成 + delpkey;drawmode = 2;codepart = 6;return;case 6: / 006oldcurin = curin;curin = 0;note = 按任意键;codepart = 1;r