北郵計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)課設(shè)要求大二數(shù)據(jù)結(jié)構(gòu)作業(yè)dsc2

第二章.線性表（Chapter2.LinearLists)§2.1線性表的邏輯結(jié)構(gòu)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}線性表特點(diǎn)：1、存在著唯一被稱(chēng)為“第一個(gè)”的元素2、存在著唯一被稱(chēng)為“最后一個(gè)”的元素3、除第一個(gè)外，每個(gè)元素均只有唯一前驅(qū)（predecessor）4、除最后一個(gè)外，每個(gè)元素均只有唯一后繼（successor）線性表的基本操作：InitiateLengthGetPriorNextLocateInsertDeleteEmptyClear§2.2線性表的存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)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;也可以用動(dòng)態(tài)數(shù)組實(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ù)來(lái)重新分配空間，大小調(diào)整為增量順序表的插入：這是我的地方，我要住這兒！行，我們這就給你倒地兒！順序表的插入：二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)a1a2aian……Htypedefstructlnode{elemtypedata;structlnode*next;}lnode,*linkedlist;

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

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

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