第二講線性表

第二講線性表第一頁(yè)，共四十頁(yè)，編輯于2023年，星期四2課程內(nèi)容邏輯結(jié)構(gòu)線性表存儲(chǔ)結(jié)構(gòu)順序表—向量鏈表典型運(yùn)算第二頁(yè)，共四十頁(yè)，編輯于2023年，星期四32.1線性表線性表的抽象數(shù)據(jù)類型ADT線性表的存儲(chǔ)結(jié)構(gòu)線性表的典型操作第三頁(yè)，共四十頁(yè)，編輯于2023年，星期四4線性表的概念線性表定義：由有限結(jié)點(diǎn)集N，以及定義在結(jié)點(diǎn)集N上的線性關(guān)系r

所組成的線性結(jié)構(gòu)。這些結(jié)點(diǎn)稱為線性表的元素“地址相鄰的順序”和“指針指向相鄰的順序”線性表（N,r）的數(shù)學(xué)定義唯一的開始結(jié)點(diǎn)：沒有前驅(qū)，但有一個(gè)唯一的直接后繼唯一的終止結(jié)點(diǎn)：沒有后繼，但有一個(gè)唯一的直接前驅(qū)內(nèi)部結(jié)點(diǎn)：有一個(gè)唯一的直接前驅(qū)，也有一個(gè)唯一的直接后繼線性表的長(zhǎng)度(包含的結(jié)點(diǎn)個(gè)數(shù))為0的線性表稱為空表線性表的關(guān)系r是前驅(qū)關(guān)系，應(yīng)具有反對(duì)稱性和傳遞性第四頁(yè)，共四十頁(yè)，編輯于2023年，星期四5舉例開始節(jié)點(diǎn)（首結(jié)點(diǎn)）終止節(jié)點(diǎn)（尾結(jié)點(diǎn)）內(nèi)部節(jié)點(diǎn)n2的前驅(qū)n1的后繼長(zhǎng)度為k要求：內(nèi)部結(jié)點(diǎn)具有相同的數(shù)據(jù)類型

每個(gè)元素都有自己的位置第五頁(yè)，共四十頁(yè)，編輯于2023年，星期四6線性表運(yùn)算分類list(-)：創(chuàng)建線性表的一個(gè)實(shí)例~list()：線性表消亡（即析構(gòu)函數(shù)）獲取有關(guān)當(dāng)前線性表的信息

位置尋內(nèi)容，內(nèi)容找位置訪問線性表并改變線性表的內(nèi)容或結(jié)構(gòu)插入、刪除、更改等線性表的輔助性管理操作游標(biāo)管理、當(dāng)前長(zhǎng)度管理第六頁(yè)，共四十頁(yè)，編輯于2023年，星期四7線性表ADTtemplate<classT>classList{//線性表類模板list，模板參數(shù)Tvoidclear();//置空線性表 boolisEmpty();//線性表為空返回true；voidappend(ELEMvalue)//表尾添加元素value，表長(zhǎng)加1；voidinsert(intp,Tvalue);//在p處插入value，表長(zhǎng)加1； voiddelete(intp); //刪去第p元素，表的長(zhǎng)度減1； boolgetPos(int&p,Tvalue)//查找value，并返回其位置； boolgetvalue(constintp,T&value);//把p位置的值返到value boolsetvalue(constintp,T&value);//用value修改p處值；}第七頁(yè)，共四十頁(yè)，編輯于2023年，星期四8線性表的存儲(chǔ)結(jié)構(gòu)定長(zhǎng)的靜態(tài)順序存儲(chǔ)結(jié)構(gòu)又稱為向量型的一維數(shù)組結(jié)構(gòu)存儲(chǔ)在連續(xù)的地址區(qū)域，隨機(jī)訪問，固定長(zhǎng)度缺陷變長(zhǎng)的動(dòng)態(tài)線性存儲(chǔ)結(jié)構(gòu)鏈接式存儲(chǔ)結(jié)構(gòu)按照前驅(qū)關(guān)系通過(guò)指針將元素鏈接動(dòng)態(tài)數(shù)組提供空間表管理，為長(zhǎng)度變化提供方法，長(zhǎng)度增大，可申請(qǐng)大空間順序文件

為存儲(chǔ)在磁盤上的線性表所用第八頁(yè)，共四十頁(yè)，編輯于2023年，星期四92.2順序表—向量順序表(Sequentiallist)，又稱向量(Vector)采用定長(zhǎng)的一維數(shù)組存儲(chǔ)結(jié)構(gòu)主要特性:元素的類型相同

元素順序存儲(chǔ)在連續(xù)存儲(chǔ)空間中，每一個(gè)元素唯一的索引值（下標(biāo)），讀寫元素方便使用常數(shù)作為向量長(zhǎng)度，程序運(yùn)行時(shí)保持不變第九頁(yè)，共四十頁(yè)，編輯于2023年，星期四10邏輯和存儲(chǔ)結(jié)構(gòu)第十頁(yè)，共四十頁(yè)，編輯于2023年，星期四11向量的類定義enumBoolean{False,True};constintMax_length=100;Template<classELEM>//假定順序表的元素類型T為ELEMclasslist{//順序表，向量private: intmsize;//私有變量，順序表實(shí)例的最大長(zhǎng)度 intcurr_len;//私有變量，順序表實(shí)例的當(dāng)前長(zhǎng)度 ELEM*nodelist;//私有變量，存儲(chǔ)順序表實(shí)例的向量public: //以下列出成員函數(shù)（順序表的算子集) intcurr;//當(dāng)前下標(biāo)，順序表的公共變量 list(constintsize);//構(gòu)造算子，實(shí)參是表實(shí)例的最大長(zhǎng)度

~list();//析構(gòu)算子，用于將該表實(shí)例刪去第十一頁(yè)，共四十頁(yè)，編輯于2023年，星期四12voidclear();//將順序表存儲(chǔ)的內(nèi)容清除，成為空表 intlength();//返回此順序表的當(dāng)前實(shí)際長(zhǎng)度 boolappend(constELEM&);//表尾增一新元素，表長(zhǎng)加1 boolinsert(constELEM&);//在當(dāng)前下標(biāo)curr位置插入元素新值 booldelete(constintp);//刪去位置p的元素，表長(zhǎng)減1； boolsetValue(intp,constTvalue); //用value修改位置p的元素值 //把p位置的值返回到變量value中； boolgetvalue(constintp,T&value); //查找值為value的元素，并返回第1次出現(xiàn)的位置 boolgetPos(int&p,constTvalue); }第十二頁(yè)，共四十頁(yè)，編輯于2023年，星期四13查找元素目的:查找某個(gè)位置的值或者某個(gè)值的位置 template<classT> //假定順序表的元素類型為T boolarrList<T>::getPos(int&p,constTvalue){ inti;//元素下標(biāo) for(i=0;i<n;i++) //依次比較 if(value==aList[i]){ //下標(biāo)為i的元素與value相等 p=i; //將下標(biāo)由參數(shù)p返回 returntrue; } returnfalse;//順序表沒有元素值為value的元素 }第十三頁(yè)，共四十頁(yè)，編輯于2023年，星期四14插入元素運(yùn)算boolinsert(constintp,constTvlaue)在當(dāng)前下標(biāo)p=t位置插入元素新值valuecurr_len=k條件判斷：1、當(dāng)前下標(biāo)[0，curr_len]；2、當(dāng)前長(zhǎng)度（<msize）第十四頁(yè)，共四十頁(yè)，編輯于2023年，星期四15插入算法template<classT> //假定順序表的元素類型為TboolarrList<T>::insert(intp,constTvalue){ inti; if(curLen>=maxSize) //檢查順序表是否溢出 returnfalse; if(p<0||p>curLen) //檢查插入位置是否合法 returnfalse; for(i=curLen;i>p;i--) aList[i]=aList[i-1]; //從表尾curLen-1起往右移動(dòng)直到p aList[p]=value; //位置p處插入新元素

curLen++;

//表的實(shí)際長(zhǎng)度增1 returntrue;}第十五頁(yè)，共四十頁(yè)，編輯于2023年，星期四16算法執(zhí)行時(shí)間主要代價(jià)元素的移動(dòng)元素總個(gè)數(shù)為n，各個(gè)位置插入的概率相等為p＝1/n

平均移動(dòng)元素次數(shù)為總時(shí)間開銷估計(jì)為O（n）第十六頁(yè)，共四十頁(yè)，編輯于2023年，星期四17刪除元素運(yùn)算Delete(constintp)下標(biāo)t位置值作為返回值，并刪去該元素條件判斷：1、當(dāng)前下標(biāo)[0，curr_len）；2、當(dāng)前長(zhǎng)度（>0）第十七頁(yè)，共四十頁(yè)，編輯于2023年，星期四18刪除算法template<classT> //順序表的元素類型為TboolarrList<T>::delete(intp){inti;if(curLen<=0) //檢查順序表是否為空 returnfalse;if(p<0||p>curLen-1)//檢查刪除位置是否合法 returnfalse;for(i=p;i<curLen-1;i++)aList[i]=aList[i+1]; //從位置p開始每個(gè)元素左移直到curLen,curLen--; //表的實(shí)際長(zhǎng)度減1returntrue;}第十八頁(yè)，共四十頁(yè)，編輯于2023年，星期四19算法時(shí)間代價(jià)與插入操作相似，O(n)

順序表讀取元素方便，時(shí)間代價(jià)為O(1)但插入、刪除操作則付出時(shí)間代價(jià)O(n)

第十九頁(yè)，共四十頁(yè)，編輯于2023年，星期四202.3鏈表(LinkedList)鏈表(linkedlist)指針指向保持前驅(qū)關(guān)系，節(jié)點(diǎn)不必物理相鄰動(dòng)態(tài)申請(qǐng)/釋放空間適合節(jié)點(diǎn)的動(dòng)態(tài)的插入/刪除，長(zhǎng)度變化無(wú)常鏈接存儲(chǔ)方法在非線性結(jié)構(gòu)（如樹、圖）中的應(yīng)用分類單鏈表雙鏈表循環(huán)鏈表第二十頁(yè)，共四十頁(yè)，編輯于2023年，星期四21單鏈表結(jié)點(diǎn)類型以及變量說(shuō)明structListNode{ ELEMdata；//存放線性表結(jié)點(diǎn)的數(shù)據(jù); ListNode*next;//存放指向后繼結(jié)點(diǎn)的指針；};typedefListNode*ListPtr;ListPtrhead,tail; //head指向單鏈表開始結(jié)點(diǎn)的指針；//tail指向單鏈表尾結(jié)點(diǎn)的指針，指針域null；第二十一頁(yè)，共四十頁(yè)，編輯于2023年，星期四22運(yùn)算集查找算法查找單鏈表中第i個(gè)結(jié)點(diǎn)算法插入算法插入數(shù)據(jù)內(nèi)容為value的新結(jié)點(diǎn)，為第i個(gè)結(jié)點(diǎn)。刪除算法刪除由參數(shù)link所指定的結(jié)點(diǎn)求長(zhǎng)度算法求單鏈表中元素的個(gè)數(shù)第二十二頁(yè)，共四十頁(yè)，編輯于2023年，星期四23單鏈表(Con.)HeaderNode不被作為表中的實(shí)際元素，值忽略head指向該節(jié)點(diǎn)訪問必須從head開始查找鏈表中的元素第二十三頁(yè)，共四十頁(yè)，編輯于2023年，星期四24鏈表檢索//函數(shù)返回值是找到的結(jié)點(diǎn)指針template<classT> //線性表的元素類型為TLink<T>*lnkList<T>::setPos(inti){ intcount=0;if(i==-1)returnhead; //i為-1則定位到頭結(jié)點(diǎn) Link<T>*p=head->next; while(p!=NULL&&count<i){//若i為0則定位到第1個(gè)結(jié)點(diǎn) p=p->next; count++;};returnp;//指向第i結(jié)點(diǎn)，i＝0,1,…n-1,當(dāng)鏈表中結(jié)點(diǎn)數(shù)小于i時(shí)返回NULL}第二十四頁(yè)，共四十頁(yè)，編輯于2023年，星期四25插入過(guò)程描述pqp＝setPos(i-1)q＝newListNode……pq……pq……q->next=p->nextp->next=q第二十五頁(yè)，共四十頁(yè)，編輯于2023年，星期四26插入算法ListNode*Insert(ELEMvalue,inti){ ListNode*p，*q; q=newListNode;//產(chǎn)生一個(gè)新結(jié)點(diǎn)空間q p=setPos(i-1);//找到待插位置的前一個(gè)位置p if(p==NULL)returnNULL;q->next=p->next; q->data=value;

p->next=q; if(q->next==NULL) last=q; //當(dāng)插入元素是最后位置時(shí)維護(hù)尾指針 returnq;}

指針調(diào)整過(guò)程第二十六頁(yè)，共四十頁(yè)，編輯于2023年，星期四27刪除結(jié)點(diǎn)過(guò)程描述

x

ppnext=dnext;dd=pnext;free(d)P節(jié)點(diǎn)不能不存在或者為尾節(jié)點(diǎn)?。〉诙唔?yè)，共四十頁(yè)，編輯于2023年，星期四28刪除算法template<classT> //線性表的元素類型為TboollnkList<T>::delete((constinti){ Link<T>*p,*d; if((p=setPos(i-1))==NULL||p==tail){//待刪結(jié)點(diǎn)不存在; cout<<"非法刪除點(diǎn)"<<endl;returnfalse; } d=p->next; //d是真正待刪結(jié)點(diǎn) if(d==tail){ //待刪結(jié)點(diǎn)為尾結(jié)點(diǎn)，則修改尾指針 tail=p; p->next=NULL: deleted; } else{p->next=d->next;deleted;}//刪除結(jié)點(diǎn)d并修改鏈指針 returntrue;}第二十八頁(yè)，共四十頁(yè)，編輯于2023年，星期四29求長(zhǎng)度算法intlength(){ Link<T>*p=head->next; intcount=0; while(p!=NULL){ p=p->next; count++; } returncount;}

第二十九頁(yè)，共四十頁(yè)，編輯于2023年，星期四30思考題：為什么引入頭節(jié)點(diǎn)？有利于對(duì)空鏈表進(jìn)行操作或者在鏈表表頭進(jìn)行操作等特殊情況的處理。例如單鏈表為空時(shí)的插入；單鏈表被刪除為空表時(shí)的處理；插入作為表的第一個(gè)節(jié)點(diǎn)；刪除表的第一個(gè)節(jié)點(diǎn)第三十頁(yè)，共四十頁(yè)，編輯于2023年，星期四31單鏈表分析單鏈表的主要不足之處link字段僅僅指向后繼結(jié)點(diǎn)，不能有效地找到前驅(qū)雙鏈表彌補(bǔ)了上述不足之處增加一個(gè)指向前驅(qū)的指針第三十一頁(yè)，共四十頁(yè)，編輯于2023年，星期四32雙鏈表類型說(shuō)明structDblListNode{ ELEMdata;

DblListNode*prev; DblListNode*next;};

structDoubleList{ DblListNode*head，*tail;};指向前驅(qū)結(jié)點(diǎn)指向后繼結(jié)點(diǎn)datanextprev第三十二頁(yè)，共四十頁(yè)，編輯于2023年，星期四33刪除結(jié)點(diǎn)示意圖刪除p所指的結(jié)點(diǎn)setPos(i)pp->prev->next=p->next;p->next->prev=p->prev;pp->prev=NULL;p->next=NULL;p^^free(p)第三十三頁(yè)，共四十頁(yè)，編輯于2023年，星期四34插入結(jié)點(diǎn)示意圖在p所指結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)setPos(i-1)pq->next=p->next;q->prev=p;qpp->next