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

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

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

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

4、或成為數(shù)組鏈表,該鏈表儲存的數(shù)據(jù)類型為string,請實現(xiàn)以下的功能。public:List(; /構(gòu)造函數(shù)int size( const; /返回鏈表的長度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、的元素換為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位置的元素是鏈表的哪個位置,如果當前位置沒有存放數(shù)據(jù),則返回-1int set_position( int position const; /返回鏈表第position位置的數(shù)據(jù)所存放的數(shù)組index,如果不存在position位置,則返回-1要求:在實現(xiàn)要求的結(jié)構(gòu)的基礎上,需在main函數(shù)中編寫下面所述的簡單測試程序,請使用屏幕輸入輸出。(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)請按照position:content空格index輸出,三個變量請按照head:?、available:?、以及l(fā)ast_used:?輸出。每一步完成輸出以后,請打印一個空行。每一步的輸出應該是這樣的(不代表正確答案,只說明輸出格式:0:XXX 21:YYY 42:TTT 5head:2avaibale:3last_used:1對于其他具體信息請參考課本6.5 Linked Lists In Arrays二、設計一個隊列,要求用二個順序存儲結(jié)構(gòu)的棧,通過這二個棧的相關運算實現(xiàn)隊列的以下功能。Queue(;/構(gòu)造函數(shù)bool empty(;/返回隊列是否已空bool full(;/返回隊列是否已滿int serve(;/出隊列,成功返回0,否則返回-1int append(const string &item; /item進隊列,成功返回0,否則返回-1int retrieve(string &item const; /將隊列頭的值賦給item,成功返回0,否則返回-1要求:在實現(xiàn)要求的結(jié)構(gòu)的基礎上,需在main函數(shù)中編寫下面所述