北郵計算機科學與技術專業(yè)課設要求大二數(shù)據(jù)結構作業(yè)dsc2

第二章.線性表（Chapter2.LinearLists)§2.1線性表的邏輯結構Linear_list=（D,R）其中：D={ai|ai∈D0,i=1,2,…,n,n≥0}

R={N}N={<ai-1,ai>|ai-1,ai∈D0,i=2,3,…,n}線性表特點：1、存在著唯一被稱為“第一個”的元素2、存在著唯一被稱為“最后一個”的元素3、除第一個外，每個元素均只有唯一前驅（predecessor）4、除最后一個外，每個元素均只有唯一后繼（successor）線性表的基本操作：InitiateLengthGetPriorNextLocateInsertDeleteEmptyClear§2.2線性表的存儲結構一、順序存儲結構bb+lb+2l…b+(i-1)l…b+(n-1)l#defineMAXLENuser_supplytypedefstruct{elemtypeelem[MAXLEN];intlistsize;}sqlist;#defineLIST_INIT_SIZEuser_supply#defineLISTINCREMENTuser_supplytypedefstruct{elemtype*elem;intlength;intlistsize;}sqlist;也可以用動態(tài)數(shù)組實現(xiàn)：statusInitiate(splist&L){L.elem=(elemtype*)malloc(LIST_INIT_SIZE*sizeof(elemtype));if(!L.elem)exit(overflow);L.length=0;L.listsize=LIST_INIT_SIZE;}//還可用realloc函數(shù)來重新分配空間，大小調整為增量順序表的插入：這是我的地方，我要住這兒！行，我們這就給你倒地兒！順序表的插入：二、鏈式存儲結構a1a2aian……Htypedefstructlnode{elemtypedata;structlnode*next;}lnode,*linkedlist;

由上可見，在鏈表的某一結點后插入一結點是很容易的，但若要插在鏈表頭部，則需另行處理。為使插入操作統(tǒng)一，可在鏈表頭部加上一個頭結點（headnode）。帶頭結點的鏈表，插入和刪除操作就統(tǒng)一了。a1aian……H鏈表的插入：ai+1a1aiai+1an……H我要插在這兒！行，你就插這兒吧！

上面講的是單鏈表（singlylinkedlists），此外，還有靜態(tài)鏈表（implementinglinkedlistsusingarray）、循環(huán)鏈表（circularlinkedlists）、雙向鏈表（doublylinkedlists）和雙向循環(huán)鏈表（doublycircularlinkedlists）。12ina1a2anH…H…ana2a1TH…ana2a1T

你們有誰能告訴我數(shù)組和鏈表在使用時的優(yōu)缺點？2、在數(shù)據(jù)量已確定時，數(shù)組比鏈表節(jié)約空間；3、在數(shù)據(jù)量不確定時，鏈表比數(shù)組節(jié)約空間；4、鏈表的插入刪除時不需要大量的數(shù)據(jù)移動。1、數(shù)組能隨機存?。╮andomaccess）各數(shù)據(jù)元素，亦即給出元素下標（index），就能訪問該元素；§2.3一元多項式（polynomial）的表示及運算typedefstruct{intcoef;intexp;}eletp;eletppoly[m];順序存儲結構表示：鏈式存儲結構表示：intcoef;intexp;}*poly;typedefstruct