課程設(shè)計(jì)--鏈表存儲(chǔ)方式下的數(shù)據(jù)的插入刪除和搜索

1、山東大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告學(xué) 號(hào)姓 名 年 級(jí) 2010 專 業(yè) 軟件工程 班 級(jí) 三班 學(xué) 期11-12學(xué)年第二學(xué)期日期: 2011年2月22日一 課程設(shè)計(jì)題目：鏈表存儲(chǔ)方式下的數(shù)據(jù)的插入，刪除和搜索。二 課程設(shè)計(jì)內(nèi)容描述： 需求 以動(dòng)態(tài)演示的形式向用戶展示在鏈表存儲(chǔ)方式下的數(shù)據(jù)記性插入，刪除和搜索的實(shí)現(xiàn)方法和內(nèi)部過程。 輸入 以系統(tǒng)自動(dòng)生成的方式新建鏈表，可以選擇有序或無序生成，在面板顯示出鏈表，鏈結(jié)點(diǎn)以箭頭連接，以帶色的方框內(nèi)的數(shù)字為數(shù)據(jù)，需要生成特定鏈表可選擇數(shù)據(jù)插入在鏈表首。 輸出 在面板顯示及顯示三種操作(插入，查找和刪除)的具體方法和流程，顯示方式以指示箭頭來表示對(duì)鏈表

2、內(nèi)容或位置的查詢。插入或刪除操作則在圖中畫出節(jié)點(diǎn)增加或者減少的過程。 功能 該程序可實(shí)現(xiàn)單向鏈表的插入刪除和查找過程的演示，以動(dòng)態(tài)的顯示展示其操作過程。 測(cè)試 通過輸入框中用戶輸入的數(shù)據(jù)和七個(gè)按鈕的操作選擇相應(yīng)的功能，可實(shí)現(xiàn)動(dòng)態(tài)演示。三 思想和算法： 對(duì)于演示可分為用戶界面和動(dòng)畫演示兩個(gè)部分在用戶界面添加按鈕，輸入框，單項(xiàng)選擇和演示區(qū)域，演示區(qū)域?qū)⑹褂脛?dòng)畫演示進(jìn)行展示。在用戶界面分別給按鈕及輸入框等添加監(jiān)聽器，通過調(diào)用動(dòng)畫演示方法以實(shí)現(xiàn)按鈕功能。動(dòng)畫演示通過創(chuàng)建show類實(shí)現(xiàn)鏈結(jié)點(diǎn)和創(chuàng)建showgroup類實(shí)現(xiàn)鏈結(jié)點(diǎn)的的動(dòng)態(tài)顯示。其內(nèi)部引用awt.graphics類實(shí)現(xiàn)畫線等功能。 對(duì)于三種操

3、作來說，插入和刪除的實(shí)現(xiàn)都必須依靠查找的功能，因此，在代碼中有很大一部分是可以通用的，實(shí)現(xiàn)查找功能可分為兩種：按用戶輸入的數(shù)據(jù)查找和按用戶輸入的位置查找，判定條件分別是show類中的值和showgroup中的curin值。插入操作需要在已建好的鏈表中增加一個(gè)節(jié)點(diǎn)，這就需要插入點(diǎn)以后的節(jié)點(diǎn)向后移動(dòng)一個(gè)位置，將插入的節(jié)點(diǎn)放在該位置上，而刪除是將插入點(diǎn)以后的節(jié)點(diǎn)向前移動(dòng)一個(gè)位置。在showgroup類中，定義鏈表數(shù)據(jù)的數(shù)組以存儲(chǔ)數(shù)據(jù)，將數(shù)組內(nèi)的數(shù)據(jù)分別賦給各個(gè)節(jié)點(diǎn)，通過創(chuàng)建鏈表的方法創(chuàng)建鏈表。四使用說明 1運(yùn)行 打開eclipse，導(dǎo)入工程，運(yùn)行后，將顯示如下界面界面中有七個(gè)按鈕，一個(gè)單選項(xiàng)和兩個(gè)輸

4、入框連續(xù)單擊“新建”，按提示操作選擇無序，出現(xiàn)以下界面或者選擇有序則出現(xiàn)以下界面當(dāng)輸入有誤時(shí)，則會(huì)有提示新建功能完成位置查找功能連續(xù)單擊“數(shù)據(jù)查找”，按提示操作數(shù)據(jù)查找功能輸入位置或數(shù)據(jù)不存在時(shí)刪除操作按位置刪除 其他操作不再贅述。五調(diào)試說明 導(dǎo)入工程后，打開所有代碼，主程序在link.linklist，運(yùn)行即可。六代碼linklist類package link;import java.applet.applet;import java.awt.*;import java.awt.event.*;import java.text.numberformat;import java.util.ev

5、entobject;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)

6、;newbutton = new button(新建);panel1.add(newbutton);newbutton.addactionlistener(this);/ 插入按鈕設(shè)置insposbutton = new button(位置插入);panel1.add(insposbutton);insposbutton.addactionlistener(this);insdatabutton = new button(數(shù)據(jù)插入);panel1.add(insdatabutton);insdatabutton.addactionlistener(this);/ 查找按鈕設(shè)置finddatab

7、utton = new button(數(shù)據(jù)查找);panel1.add(finddatabutton);finddatabutton.addactionlistener(this);findposbutton = new button(位置查找);panel1.add(findposbutton);findposbutton.addactionlistener(this);/ 刪除按鈕設(shè)置deldatabutton = new button(數(shù)據(jù)刪除);panel1.add(deldatabutton);deldatabutton.addactionlistener(this);delposb

8、utton = 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.additem

9、listener(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(輸入數(shù)字: );panel3.add(tf);panel panel4=new panel();panel.add(panel4);panel4.setlayout(new flowlay

10、out(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

11、) runner.stop();runner = null;public void paint(graphics g) theshowgroup.draw(g);public void update(graphics g) paint(g);/ 監(jiān)聽按鈕及輸入框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)

12、;gpnumber=integer.parseint(s2); catch (numberformatexception _ex) gpnumber = 0;gpnumber=0;isnumber = false;/ 監(jiān)聽按鈕/各個(gè)按鈕的監(jiān)聽，輸入數(shù)據(jù)和調(diào)用相應(yīng)的方法if (actionevent.getsource() = newbutton)theshowgroup.newlist(isnumber, gpnumber);else if (actionevent.getsource() = insdatabutton)theshowgroup.datainsert(isnumber, gp

13、number);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 (a

14、ctionevent.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 itemeve

15、nt) 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 | fl

16、ag & !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 isnumb

17、er;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;c

18、lass 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;/ 創(chuàng)建節(jié)點(diǎn)private show makeshow(int i) int j = 100 + (int) (math.random() * 154d)

19、;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(boole

20、an flag) if (isokchangesort & flag != notsorted)notsorted = flag;if (!isokchangesort)note = 改變順序;drawmode = 1;/ 新建鏈表，int為鏈表長(zhǎng)度public void newlist(boolean flag, int i) / 判斷按鈕areinserting = false;aredeleting = false;if (opmode != 1) opmode = 1;codepart = 1;switch (codepart) case 1: / 001note = 輸入鏈表長(zhǎng)度，第

21、一個(gè)輸入框?yàn)殚L(zhǎng)度，第二個(gè)輸入0;drawmode = 1;codepart = 2;oldcurin = curin;curin = 0;return;case 2: / 002if (!flag | i 28) note = 長(zhǎng)度值有誤: （0 _ + 28 + );codepart = 1; else note = 即將創(chuàng)建長(zhǎng)度為 + i + 的鏈表;codepart = 3;drawmode = 1;return;case 3: / 003note = 選擇有序或者無序鏈表;isokchangesort = true;drawmode = 1;codepart = 4;return;ca

22、se 4: / 004if (notsorted)note = 你選擇了數(shù)據(jù)無序;elsenote = 您選擇了數(shù)據(jù)有序;isokchangesort = false;totallinks = 0;drawmode = 2;codepart = 5;return;case 5: / 005totallinks = i;dofill(totallinks);note = 鏈表創(chuàng)建完成;鏈表長(zhǎng)度 = + totallinks;oldcurin = curin;curin = 0;drawmode = 2;codepart = 6;return;case 6: / 006note = 單擊任意按鈕;

23、drawmode = 1;codepart = 1;return;/ 建立數(shù)組存儲(chǔ)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+) / 隨機(jī)數(shù)生成，存入數(shù)組int i1 = (int) (math.random() * 999d);temppers = makeshow(i1);linkarrayk =

24、 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); /按輸入的數(shù)據(jù)插入public void datainse

25、rt(boolean flag, int i) /位置插入算法aredeleting = false;if (opmode != 3) opmode = 3;codepart = 1;switch (codepart) case 1: / 001oldcurin = curin;curin = 0;insertatend = false;note = 輸入要插入的數(shù)據(jù);drawmode = 1;codepart = 2;return;case 2: / 002if (!flag | i 999) note = 無法插入: 數(shù)值在0 - + 999;codepart = 1; else if (

26、totallinks = 28) note = 無法插入: 數(shù)據(jù)已滿;codepart = 6; else inskey = i;temppers = makeshow(inskey);if (notsorted) note = 即將插入這個(gè)數(shù)據(jù) + inskey;codepart = 4; else note = 即將尋找插入點(diǎn);codepart = 3;drawmode = 1;return;case 3: / 003if (curin = totallinks - 1& inskey linkarraycurin.persdata.getheight() note = found ins

27、ertion 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 = 數(shù)據(jù)插入，鏈表

28、復(fù)位;drawmode = 1;codepart = 5;return;case 5: / 005if (insertatend) oldcurin = curin+;note = 插入以下數(shù)據(jù) + inskey+ 在鏈表末; else areinserting = false;for (int j = totallinks; j curin; j-)linkarrayj = linkarrayj - 1;note = 插入以下數(shù)據(jù) + inskey;linkarraycurin = new link(temppers);totallinks+;drawmode = 2;codepart =

29、6;return;case 6: / 006note = 插入完成;鏈表長(zhǎng)度 = + 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 =

30、3;codepart = 1;switch (codepart) case 1: / 001oldcurin = curin;curin = 0;insertatend = false;note = 輸入要插入的位置和數(shù)據(jù)，分別填入兩個(gè)輸入框;drawmode = 1;codepart = 2;return;case 2: / 002if (!flag | i totallinks) note = 無法插入，位置超限;codepart = 1; else if (totallinks = 28) note = 無法插入: 數(shù)據(jù)已滿;codepart = 6; else inspkey = i;

31、temppers = makeshow(data);if (notsorted) note = 即將插入這個(gè)數(shù)據(jù) ，位置 + inspkey+數(shù)據(jù)+data;codepart = 4; else note = 即將尋找插入點(diǎn);codepart = 3;drawmode = 1;return;case 3: / 003if (curin = totallinks - 1& inskey =curin) note = 已找到位置;insertatend = true;codepart = 5; else if (inspkey curin) note = 正尋找位置;oldcurin = curi

32、n+;codepart = 3; else note = 已找到位置;codepart = 4;drawmode = 1;return;case 4: / 004areinserting = true;if (notsorted)insdex = 0;elseinsdex = curin;note = 數(shù)據(jù)插入，鏈表復(fù)位;drawmode = 1;codepart = 5;return;case 5: / 005if (insertatend) oldcurin = curin+;note = 插入以下數(shù)據(jù) + inspkey+ 在鏈表末; else areinserting = false;

33、for (int j = totallinks; j curin; j-)linkarrayj = linkarrayj - 1;note = 插入以下數(shù)據(jù) + inspkey;linkarraycurin = new link(temppers);totallinks+;drawmode = 2;codepart = 6;return;case 6: / 006note = 插入完成; 鏈表長(zhǎng)度 = + totallinks;drawmode = 1;codepart = 7;return;case 7: / 007oldcurin = curin;curin = 0;note = 按任意按

34、鈕;drawmode = 1;codepart = 1;return; /按輸入的數(shù)據(jù)查找public void datafind(boolean flag, int i) / 數(shù)據(jù)查找算法areinserting = false;aredeleting = false;if (opmode != 4) opmode = 4;codepart = 1;switch (codepart) case 4: / 004case 5: / 005default:break;case 1: / 001note = 輸入要查找的數(shù)據(jù);codepart = 2;break;case 2: / 002if (

35、!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 = 已經(jīng)找到 + findkey;codepart = 6;break;if (curin = totallinks - 1 | !notsorted& curin findkey) note

36、= 未找到 + 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) opmod

37、e = 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: / 003i

38、f (curin = findpkey) note = 已經(jīng)找到位置 + 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;d

39、rawmode = 1; /按輸入的數(shù)據(jù)刪除public void datadelete(boolean flag, int i) / 數(shù)據(jù)刪除算法areinserting = false;if (opmode != 5) opmode = 5;codepart = 1;switch (codepart) case 1: / 001note = 輸入要?jiǎng)h除的數(shù)據(jù);drawmode = 1;codepart = 2;return;case 2: / 002if (!flag | i 999) note = 數(shù)據(jù)超限0 - + 999;codepart = 1; else delkey = i;o

40、ldcurin = curin;curin = 0;note = 正在查找數(shù)據(jù) + delkey;codepart = 3;drawmode = 1;return;case 3: / 003if (linkarraycurin.persdata.getheight() = delkey) note = 已經(jīng)找到數(shù)據(jù) + delkey;if (curin = totallinks - 1)codepart = 5;elsecodepart = 4; else if (curin = totallinks - 1 | !notsorted& linkarraycurin.persdata.geth

41、eight() delkey) note = 無法找到 + delkey;codepart = 6; else note = 正在查找數(shù)據(jù) + delkey;oldcurin = curin+;codepart = 3;drawmode = 1;return;case 4: / 004aredeleting = true;deldex = curin;note = 刪除完成，鏈表復(fù)位;drawmode = 1;codepart = 5;return;case 5: / 005aredeleting = false;for (int j = curin; j totallinks - 1; j+

42、)linkarrayj = linkarrayj + 1;totallinks-;oldcurin = curin;curin = 0;note = 刪除數(shù)據(jù)完成 + 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) opmod

43、e = 5;codepart = 1;switch (codepart) case 1: / 001note = 輸入要?jiǎng)h除的位置;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 (cu

44、rin = delpkey) note = 已經(jīng)找到位置 + 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: / 004aredeletin

45、g = true;deldex = curin;note = 刪除完成，鏈表即將復(fù)位;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