線性表演示文稿

線性表演示文稿目前一頁\總數(shù)三十一頁\編于八點優(yōu)選線性表目前二頁\總數(shù)三十一頁\編于八點數(shù)據(jù)結(jié)構(gòu)概論知識點2.1.線性表的概念線性表的抽象數(shù)據(jù)類型線性表的存儲結(jié)構(gòu)線性表運(yùn)算分類2.2.順序表(向量)順序表的類定義順序表的運(yùn)算實現(xiàn)2.3.鏈表單鏈表雙鏈表循環(huán)鏈表2.4.線性表實現(xiàn)方法的比較目前三頁\總數(shù)三十一頁\編于八點本章討論幾種常用的線性數(shù)據(jù)結(jié)構(gòu)(統(tǒng)稱為線性表)：順序表（也稱為向量，是用順序結(jié)構(gòu)實現(xiàn)的線性表），類似于C/C++語言中的數(shù)組，實現(xiàn)了封裝、提供了豐富的功能。鏈表（用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)的線性表）：鏈?zhǔn)浇Y(jié)構(gòu)的線性表，在結(jié)點中附件指針域來表達(dá)結(jié)點之間的前驅(qū)/后繼關(guān)系。單鏈表；雙鏈表；循環(huán)鏈表：循環(huán)單鏈表，循環(huán)雙鏈表。目前四頁\總數(shù)三十一頁\編于八點2.1線性表線性表是一類線性（區(qū)別于樹形結(jié)構(gòu)和圖結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)，它有多種存儲結(jié)構(gòu)和應(yīng)用方法，從而可以細(xì)分為順序表、鏈表、隊列、棧等?！熬€性表”是從邏輯結(jié)構(gòu)的角度來描述數(shù)據(jù)結(jié)構(gòu)的，它主要有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。目前五頁\總數(shù)三十一頁\編于八點2.1.1線性表的抽象數(shù)據(jù)類型線性表：直觀地講，線性表的特點是它的所有結(jié)點可以排列成一個線性序列，n0→n1→n2→…→nk。在線性表中：有唯一的開始結(jié)點，它沒有前驅(qū)；其他結(jié)點都有唯一的前驅(qū)結(jié)點。有唯一的末尾結(jié)點，它沒有后繼；其他結(jié)點都有唯一的后繼結(jié)點。除開始結(jié)點和末尾結(jié)點外，其他結(jié)點稱為中間結(jié)點，中間結(jié)點有唯一的前驅(qū)和后繼?？梢詮碾x散數(shù)學(xué)的角度對線性表進(jìn)行嚴(yán)格定義(略)。目前六頁\總數(shù)三十一頁\編于八點2.1.3線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)：如何開辟存儲空間，各結(jié)點存儲空間的聯(lián)系，如何實現(xiàn)等。線性表的存儲結(jié)構(gòu)主要有兩種：定長的順序存儲結(jié)構(gòu)。特點是線性表結(jié)點可以按地址相鄰的順序存儲在一片連續(xù)的存儲空間中，線性表的固定長度限制了線性表結(jié)點個數(shù)變化不能超過該固定長度。變長的線性存儲結(jié)構(gòu)。具體形式有鏈?zhǔn)酱鎯Y(jié)構(gòu)，動態(tài)數(shù)組等。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，各結(jié)點的存儲空間動態(tài)申請和釋放，通過指針域來表達(dá)結(jié)點的前驅(qū)/后繼關(guān)系。動態(tài)數(shù)組：定長數(shù)組的變形，當(dāng)結(jié)點個數(shù)超出最大限度時，重新申請更長的數(shù)組（new和delete運(yùn)算符）。目前七頁\總數(shù)三十一頁\編于八點2.1.2線性表運(yùn)算分類典型的運(yùn)算：增(加)、刪(除)、查(找)、(修)改。目前八頁\總數(shù)三十一頁\編于八點2.2順序表－向量順序表(sequentiallist)又稱為向量(vector)，它采用定長的一維數(shù)組存儲結(jié)構(gòu)。向量的主要特性：元素的類型相同。元素順序地存儲在一塊有連續(xù)地址的存儲空間中，每一個元素按其順序有唯一的索引值，又稱下標(biāo)值，用它可以方便地訪問元素內(nèi)容。順序表類似于C/C++語言中的數(shù)組，將各種操作封裝一個類。目前九頁\總數(shù)三十一頁\編于八點向量的抽象數(shù)據(jù)類型向量的抽象數(shù)據(jù)類型數(shù)據(jù)成員：向量長度，當(dāng)前元素個數(shù)，指向元素所占存儲空間的指針。函數(shù)成員(操作)：追加元素、插入元素、刪除元素、查找、判空、判滿、輸出所有結(jié)點的值。目前十頁\總數(shù)三十一頁\編于八點順序表的類定義//順序表的類定義template<classT>classarrList{private: T*aList;//int*aList; intmaxSize; intcurLen; intposition;public: arrList(constintsize){ maxSize=size; aList=newT[maxSize];//aList=newint[maxSize]; curLen=position=0; } ~arrList(){ delete[]aList; }

voidclear(){ delete[]aList; curLen=position=0; aList=newT[maxSize];} intlength(); boolappend(constTvalue); boolinsert(constintp,constTvalue); booldeletion(constintp); boolsetValue(constintp,constTvalue); boolgetValue(constintp,T&value); boolgetPos(int&p,constTvalue);};目前十一頁\總數(shù)三十一頁\編于八點template<classT>boolarrList<T>::setValue(constintp,constTvalue){ if(…) … T[p]=value; returntrue;}template<classT>boolarrList<T>::getValue(constintp,T&value){ if(…) … value=T[p]; returntrue;}目前十二頁\總數(shù)三十一頁\編于八點順序表的運(yùn)算實現(xiàn)順序表的檢索//arrList_getPos線性表的檢索template<classT>boolarrList<T>::getPos(int&p,constTvalue){ inti; for(i=0;i<n;i++) if(value==aList[i]){ p=i; returntrue; } returnfalse;}

目前十三頁\總數(shù)三十一頁\編于八點順序表的運(yùn)算實現(xiàn)順序表的插入//arrList_insert線性表的插入template<classT>boolarrList<T>::insert(constintp,constTvalue){ inti; if(curLen>=maxSize){ cout<<"Thelistisoverflow"<<endl; returnfalse; } if(p<0||p>curLen){ cout<<"Insertionpointisillegal"<<endl; returnfalse; } for(i=curLen;i>p;i--) aList[i]=aList[i-1]; aList[p]=value; curLen++; returntrue;}

目前十四頁\總數(shù)三十一頁\編于八點15插入算法的執(zhí)行時間插入操作的主要代價體現(xiàn)在表中元素的移動

在位置i插入元素，需移動k-i個元素元素總個數(shù)為k，假設(shè)各個位置插入的概率相等，均為p＝1/k平均移動元素次數(shù)為總時間開銷估計為O(k)目前十五頁\總數(shù)三十一頁\編于八點順序表的運(yùn)算實現(xiàn)順序表的刪除//arrList_deletion線性表的刪除template<classT>boolarrList<T>::deletion(constintp){ inti; if(curLen<=0){ cout<<"Noelementtodelete\n"<<endl; returnfalse; } if(p<0||p>curLen-1){ cout<<"deletionisillegal\n"<<endl; returnfalse; } for(i=p;i<curLen-1;i++) aList[i]=aList[i+1]; curLen--; returntrue;}

目前十六頁\總數(shù)三十一頁\編于八點2.3鏈表鏈表(linked

list)的特點是動態(tài)申請內(nèi)存空間，并通過指針來鏈接結(jié)點，按照線性表的前驅(qū)/后繼關(guān)系把一個個結(jié)點鏈接起來。幾種用于線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)：單鏈表；雙鏈表；循環(huán)單鏈表；循環(huán)雙鏈表。鏈表存儲是最常用的存儲方式之一，它不僅可以用來表示線性表，而且也可以用于其他非線性的數(shù)據(jù)結(jié)構(gòu)中，如樹結(jié)構(gòu)和圖結(jié)構(gòu)。目前十七頁\總數(shù)三十一頁\編于八點2.3.1單鏈表在單鏈表中，每個結(jié)點由兩部分組成：存放結(jié)點數(shù)據(jù)的data域；存放指向后繼結(jié)點的next指針域。因為每個結(jié)點中只有指向后繼結(jié)點的指針，因此由這種結(jié)點鏈接而成的鏈表，稱為單鏈表。表首指針head：指向單鏈表中第0個結(jié)點(結(jié)點序號從0開始計起)。template<classT>classLink //單鏈表中的結(jié)點類{public: Tdata; Link<T>*next; Link();};目前十八頁\總數(shù)三十一頁\編于八點單鏈表的抽象數(shù)據(jù)類型數(shù)據(jù)成員：表首指針head，單鏈表長度len。函數(shù)成員(操作)：查找結(jié)點、插入結(jié)點、刪除結(jié)點、求單鏈表長度、輸出所有結(jié)點的值。目前十九頁\總數(shù)三十一頁\編于八點20單鏈表的結(jié)點類型template<classT>classLink{public: T data; //用于保存結(jié)點元素的內(nèi)容 Link<T> *next; //指向后繼結(jié)點的指針

Link(constTinfo,constLink<T>*nextValue=NULL){ data=info; next=nextValue; } Link(constLink<T>*nextValue){ next=nextValue; }};目前二十頁\總數(shù)三十一頁\編于八點21單鏈表的定義template<classT>classlnkList:publicList<T>{ private: Link<T>*head; //單鏈表的頭 intlength; Link<T>*setPos(constintp); //返回線性表指向第p個元素的指針值public: lnkList(ints); //構(gòu)造函數(shù) ~lnkList(); //析構(gòu)函數(shù) boolisEmpty(); //判斷鏈表是否為空 voidclear(); //將鏈表存儲的內(nèi)容清除，成為空表 intlength(); //返回此順序表的當(dāng)前實際長度 boolappend(cosntTvalue); //在表尾添加一個元素value，表的長度增1 boolinsert(cosntintp,cosntTvalue); //在位置p上插入一個元素value，表的長度增1 booldelete(cosntintp); //刪除位置p上的元素，表的長度減1 boolgetValue(cosntintp,T&value); //返回位置p的元素值 boolgetPos(int&p,constTvalue); //查找值為value的元素，返回第1次出現(xiàn)的位置}目前二十一頁\總數(shù)三十一頁\編于八點查找單鏈表中第i個結(jié)點講解：查找結(jié)點數(shù)據(jù)為指定值的結(jié)點。setPos函數(shù)：查找第i個結(jié)點，并返回該結(jié)點的指針。查找的實現(xiàn)：通過結(jié)點的指針實現(xiàn)遍歷(即掃描)所有的結(jié)點，直至找到滿足要求的結(jié)點為止。目前二十二頁\總數(shù)三十一頁\編于八點23查找單鏈表中第i個結(jié)點//函數(shù)返回值是找到的結(jié)點指針template<classT> //線性表的元素類型為TLink<T>*lnkList<T>::setPos(inti){

intcount=0;if(i==-1) //i為-1則定位到頭結(jié)點 returnhead; //循鏈定位，若i為0則定位到第一個結(jié)點

Link<T>*p=newLink<T>(head->next); while(p!=NULL&&count<i){ p=p->next; count++;};returnp;//指向第i結(jié)點，i＝0,1,…，當(dāng)鏈表中結(jié)點數(shù)小于i時返回NULL}目前二十三頁\總數(shù)三十一頁\編于八點在單鏈表中插入結(jié)點講解：在指針p所指向結(jié)點的后面插入新結(jié)點。insert函數(shù)：插入新結(jié)點，使之成為第i個結(jié)點，返回該結(jié)點的指針插入結(jié)點的實現(xiàn)：特別需要注意修改相關(guān)指針的值。目前二十四頁\總數(shù)三十一頁\編于八點25單鏈表的插入20231215headtail在23和12之間插入1020231215headtail10創(chuàng)建新結(jié)點新結(jié)點指向右邊的結(jié)點左邊結(jié)點指向新結(jié)點目前二十五頁\總數(shù)三十一頁\編于八點26單鏈表插入算法//插入數(shù)據(jù)內(nèi)容為value的新結(jié)點作為第i個結(jié)點

template<classT> //線性表的元素類型為TboollnkList<T>::insert(constinti,constTvalue){ Link<T>*p,*q;

if((p=setPos(i-1))==NULL){ //p是第i個結(jié)點的前驅(qū) cout<<"非法插入點"<<endl; returnfalse; } q=newLink<T>(value,p->next); p->next=q; if(p==tail) //插入點在鏈尾，插入結(jié)點成為新的鏈尾 tail=q; returntrue;}目前二十六頁\總數(shù)三十一頁\編于八點在單鏈表中刪除結(jié)點講解：刪除指針p所指向的結(jié)點。deletion函數(shù)：刪除第i個結(jié)點。刪除結(jié)點的實現(xiàn)：特別需要注意修改相關(guān)指針的值。目前二十七頁\總數(shù)三十一頁\編于八點28

用p指向元素x的結(jié)點,可以嗎?

….

….xhead

p

….x

p

單鏈表刪除示意目前二十八頁\總數(shù)三十一頁\編于八點29

x

pppnext=qne