線性表演示文稿

線性表演示文稿目前一頁\總數(shù)三十一頁\編于八點優(yōu)選線性表目前二頁\總數(shù)三十一頁\編于八點數(shù)據(jù)結構概論知識點2.1.線性表的概念線性表的抽象數(shù)據(jù)類型線性表的存儲結構線性表運算分類2.2.順序表(向量)順序表的類定義順序表的運算實現(xiàn)2.3.鏈表單鏈表雙鏈表循環(huán)鏈表2.4.線性表實現(xiàn)方法的比較目前三頁\總數(shù)三十一頁\編于八點本章討論幾種常用的線性數(shù)據(jù)結構(統(tǒng)稱為線性表)：順序表（也稱為向量，是用順序結構實現(xiàn)的線性表），類似于C/C++語言中的數(shù)組，實現(xiàn)了封裝、提供了豐富的功能。鏈表（用鏈式結構實現(xiàn)的線性表）：鏈式結構的線性表，在結點中附件指針域來表達結點之間的前驅/后繼關系。單鏈表；雙鏈表；循環(huán)鏈表：循環(huán)單鏈表，循環(huán)雙鏈表。目前四頁\總數(shù)三十一頁\編于八點2.1線性表線性表是一類線性（區(qū)別于樹形結構和圖結構）數(shù)據(jù)結構，它有多種存儲結構和應用方法，從而可以細分為順序表、鏈表、隊列、棧等?！熬€性表”是從邏輯結構的角度來描述數(shù)據(jù)結構的，它主要有兩種存儲結構：順序存儲結構和鏈式存儲結構。目前五頁\總數(shù)三十一頁\編于八點2.1.1線性表的抽象數(shù)據(jù)類型線性表：直觀地講，線性表的特點是它的所有結點可以排列成一個線性序列，n0→n1→n2→…→nk。在線性表中：有唯一的開始結點，它沒有前驅；其他結點都有唯一的前驅結點。有唯一的末尾結點，它沒有后繼；其他結點都有唯一的后繼結點。除開始結點和末尾結點外，其他結點稱為中間結點，中間結點有唯一的前驅和后繼?？梢詮碾x散數(shù)學的角度對線性表進行嚴格定義(略)。目前六頁\總數(shù)三十一頁\編于八點2.1.3線性表的存儲結構線性表的存儲結構：如何開辟存儲空間，各結點存儲空間的聯(lián)系，如何實現(xiàn)等。線性表的存儲結構主要有兩種：定長的順序存儲結構。特點是線性表結點可以按地址相鄰的順序存儲在一片連續(xù)的存儲空間中，線性表的固定長度限制了線性表結點個數(shù)變化不能超過該固定長度。變長的線性存儲結構。具體形式有鏈式存儲結構，動態(tài)數(shù)組等。在鏈式存儲結構中，各結點的存儲空間動態(tài)申請和釋放，通過指針域來表達結點的前驅/后繼關系。動態(tài)數(shù)組：定長數(shù)組的變形，當結點個數(shù)超出最大限度時，重新申請更長的數(shù)組（new和delete運算符）。目前七頁\總數(shù)三十一頁\編于八點2.1.2線性表運算分類典型的運算：增(加)、刪(除)、查(找)、(修)改。目前八頁\總數(shù)三十一頁\編于八點2.2順序表－向量順序表(sequentiallist)又稱為向量(vector)，它采用定長的一維數(shù)組存儲結構。向量的主要特性：元素的類型相同。元素順序地存儲在一塊有連續(xù)地址的存儲空間中，每一個元素按其順序有唯一的索引值，又稱下標值，用它可以方便地訪問元素內容。順序表類似于C/C++語言中的數(shù)組，將各種操作封裝一個類。目前九頁\總數(shù)三十一頁\編于八點向量的抽象數(shù)據(jù)類型向量的抽象數(shù)據(jù)類型數(shù)據(jù)成員：向量長度，當前元素個數(shù)，指向元素所占存儲空間的指針。函數(shù)成員(操作)：追加元素、插入元素、刪除元素、查找、判空、判滿、輸出所有結點的值。目前十頁\總數(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ù)三十一頁\編于八點順序表的運算實現(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ù)三十一頁\編于八點順序表的運算實現(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，假設各個位置插入的概率相等，均為p＝1/k平均移動元素次數(shù)為總時間開銷估計為O(k)目前十五頁\總數(shù)三十一頁\編于八點順序表的運算實現(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)申請內存空間，并通過指針來鏈接結點，按照線性表的前驅/后繼關系把一個個結點鏈接起來。幾種用于線性表的鏈式存儲結構：單鏈表；雙鏈表；循環(huán)單鏈表；循環(huán)雙鏈表。鏈表存儲是最常用的存儲方式之一，它不僅可以用來表示線性表，而且也可以用于其他非線性的數(shù)據(jù)結構中，如樹結構和圖結構。目前十七頁\總數(shù)三十一頁\編于八點2.3.1單鏈表在單鏈表中，每個結點由兩部分組成：存放結點數(shù)據(jù)的data域；存放指向后繼結點的next指針域。因為每個結點中只有指向后繼結點的指針，因此由這種結點鏈接而成的鏈表，稱為單鏈表。表首指針head：指向單鏈表中第0個結點(結點序號從0開始計起)。template<classT>classLink //單鏈表中的結點類{public: Tdata; Link<T>*next; Link();};目前十八頁\總數(shù)三十一頁\編于八點單鏈表的抽象數(shù)據(jù)類型數(shù)據(jù)成員：表首指針head，單鏈表長度len。函數(shù)成員(操作)：查找結點、插入結點、刪除結點、求單鏈表長度、輸出所有結點的值。目前十九頁\總數(shù)三十一頁\編于八點20單鏈表的結點類型template<classT>classLink{public: T data; //用于保存結點元素的內容 Link<T> *next; //指向后繼結點的指針

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); //構造函數(shù) ~lnkList(); //析構函數(shù) boolisEmpty(); //判斷鏈表是否為空 voidclear(); //將鏈表存儲的內容清除，成為空表 intlength(); //返回此順序表的當前實際長度 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個結點講解：查找結點數(shù)據(jù)為指定值的結點。setPos函數(shù)：查找第i個結點，并返回該結點的指針。查找的實現(xiàn)：通過結點的指針實現(xiàn)遍歷(即掃描)所有的結點，直至找到滿足要求的結點為止。目前二十二頁\總數(shù)三十一頁\編于八點23查找單鏈表中第i個結點//函數(shù)返回值是找到的結點指針template<classT> //線性表的元素類型為TLink<T>*lnkList<T>::setPos(inti){

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

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

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

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

用p指向元素x的結點,可以嗎?

….

….xhead

p

….x

p

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

x

pppnext=qne