第一次數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)

1、第一次數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)有關(guān)實(shí)驗(yàn)說(shuō)明>>>1.本課程每學(xué)期大約會(huì)有五次左右的作業(yè),最后根據(jù)這些作業(yè)的完成情況評(píng)定“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)”的最終成績(jī)。2.全部的課程實(shí)驗(yàn)需使用C/C+編碼,并以Visual Studio 2008的C+編譯器為標(biāo)準(zhǔn)。3.一般每次作業(yè)布置后兩周內(nèi)需提交作業(yè),包括紙質(zhì)書(shū)面報(bào)告和電子版文件。其中紙質(zhì)書(shū)面報(bào)告在作業(yè)布置當(dāng)周的下下周一或周三上課時(shí)交給施老師,電子版文件在作業(yè)布置當(dāng)周的下下周三晚20:00前提交到學(xué)院服務(wù)器個(gè)人的DataStructure文件夾下。4.電子版文件一定準(zhǔn)時(shí)收取,無(wú)特殊原因,過(guò)期不候(即截止的周三晚24:00后不再接受。5.電子版文件需

2、包括程序源代碼和書(shū)面報(bào)告的電子版,兩者都是評(píng)分的重要依據(jù)。為了便于程序批改作業(yè),對(duì)電子版文件的提交格式作如下規(guī)范:a在每個(gè)人的DataStructure文件夾下應(yīng)建立N文件夾,N為1-?的阿拉伯?dāng)?shù)字,表示第幾次課程實(shí)驗(yàn)。在某次課程實(shí)驗(yàn)文件夾下,應(yīng)建立doc和src文件夾,其中doc文件夾下保存書(shū)面報(bào)告的電子版,src文件夾下保存每道題目的源代碼文件。b每道題目請(qǐng)只使用并提交一個(gè).cpp文件(而不是按照工程的方式每一個(gè)類使用一個(gè)頭文件和實(shí)現(xiàn)文件并以工程的形式組織,請(qǐng)以Ex?.cpp命名,這個(gè).cpp文件包含全部的實(shí)現(xiàn)類的頭申明、類的具體實(shí)現(xiàn)以及其他輸入輸出代碼。如本次作業(yè)需在c題目中提到的需要實(shí)

3、現(xiàn)的類結(jié)構(gòu),以及這些類所依賴的類結(jié)構(gòu)都不允許使用標(biāo)準(zhǔn)庫(kù)或第三方庫(kù)的內(nèi)容,均需自己編寫(xiě)。如本次作業(yè)第二題,除了要實(shí)現(xiàn)隊(duì)列外還要實(shí)現(xiàn)隊(duì)列所依賴的棧,并且在棧的實(shí)現(xiàn)中不允許使用C+標(biāo)準(zhǔn)庫(kù)的vector等改裝。d如果特殊情況下,需要用電子郵件提交作業(yè),請(qǐng)打包a中所述的文件夾N,發(fā)給助教,并在郵件中進(jìn)行必要的說(shuō)明。6.作業(yè)請(qǐng)不要抄襲,發(fā)現(xiàn)的特別雷同作業(yè)雙方將被記為本次作業(yè)不及格。7.無(wú)特殊情況,每周三晚上7:00-9:00 我會(huì)在培訓(xùn)樓430機(jī)房為大家解答問(wèn)題,其它時(shí)間可以到409找我,一般都在。8.第一次作業(yè)共有兩道題目,第一次作業(yè)的提交截止時(shí)間為:10月26日晚20:00pm。一、設(shè)計(jì)一個(gè)靜態(tài)鏈表(

4、或成為數(shù)組鏈表,該鏈表儲(chǔ)存的數(shù)據(jù)類型為string,請(qǐng)實(shí)現(xiàn)以下的功能。public:List(; /構(gòu)造函數(shù)int size( const; /返回鏈表的長(zhǎng)度bool full( const; /返回鏈表是否已滿bool empty( const; /返回鏈表是否已空void clear(; /清空鏈表int retrieve( int position, string &x const; /獲取鏈表第position位置的元素到x,成功返回0,否則返回-1 int replace( int position, const string &x ; /將鏈表第position位置

5、的元素?fù)Q為x,成功返回0,否則返回-1 int remove( int position, string &x ; /獲取并刪除鏈表第position位置的元素,成功返回0,否則返回-1int insert( int position, const string &x ; /將元素x插入到鏈表第position位置,成功返回0,否則返回-1 protected:int new_node(; /返回鏈表的數(shù)據(jù)載體(數(shù)組的可用index,如果鏈表已滿則返回-1void delete_node( int index; /刪除鏈表數(shù)據(jù)載體(數(shù)組index位置的元素int current

6、_position( int index const; /返回鏈表數(shù)據(jù)載體(數(shù)組index位置的元素是鏈表的哪個(gè)位置,如果當(dāng)前位置沒(méi)有存放數(shù)據(jù),則返回-1int set_position( int position const; /返回鏈表第position位置的數(shù)據(jù)所存放的數(shù)組index,如果不存在position位置,則返回-1要求:在實(shí)現(xiàn)要求的結(jié)構(gòu)的基礎(chǔ)上,需在main函數(shù)中編寫(xiě)下面所述的簡(jiǎn)單測(cè)試程序,請(qǐng)使用屏幕輸入輸出。(1按輸入序列:Jan、Feb、Mar、App、May 建立初始鏈表。(2在Feb 之前,May 之后,先后插入Jun、Ocb。(3先后刪除Mar 和Jan 。(4在A

7、pp之前插入Dec。每一步完成后輸出鏈表的狀態(tài),以及head、available、last_used的狀態(tài)。鏈表的狀態(tài)請(qǐng)按照position:content空格index輸出,三個(gè)變量請(qǐng)按照head:?、available:?、以及l(fā)ast_used:?輸出。每一步完成輸出以后,請(qǐng)打印一個(gè)空行。每一步的輸出應(yīng)該是這樣的(不代表正確答案,只說(shuō)明輸出格式:0:XXX 21:YYY 42:TTT 5head:2avaibale:3last_used:1對(duì)于其他具體信息請(qǐng)參考課本6.5 Linked Lists In Arrays二、設(shè)計(jì)一個(gè)隊(duì)列,要求用二個(gè)順序存儲(chǔ)結(jié)構(gòu)的棧,通過(guò)這二個(gè)棧的相關(guān)運(yùn)算實(shí)現(xiàn)隊(duì)列的以下功能。Queue(;/構(gòu)造函數(shù)bool empty(;/返回隊(duì)列是否已空bool full(;/返回隊(duì)列是否已滿int serve(;/出隊(duì)列,成功返回0,否則返回-1int append(const string &item; /item進(jìn)隊(duì)列,成功返回0,否則返回-1int retrieve(string &item const; /將隊(duì)列頭的值賦給item,成功返回0,否則返回-1要求:在實(shí)現(xiàn)要求的結(jié)構(gòu)的基礎(chǔ)上,需在main函數(shù)中編寫(xiě)下面所述