第二講線性表

第二講線性表第1頁，課件共40頁，創(chuàng)作于2023年2月2課程內(nèi)容邏輯結構線性表存儲結構順序表—向量鏈表典型運算第2頁，課件共40頁，創(chuàng)作于2023年2月32.1線性表線性表的抽象數(shù)據(jù)類型ADT線性表的存儲結構線性表的典型操作第3頁，課件共40頁，創(chuàng)作于2023年2月4線性表的概念線性表定義：由有限結點集N，以及定義在結點集N上的線性關系r

所組成的線性結構。這些結點稱為線性表的元素“地址相鄰的順序”和“指針指向相鄰的順序”線性表（N,r）的數(shù)學定義唯一的開始結點：沒有前驅，但有一個唯一的直接后繼唯一的終止結點：沒有后繼，但有一個唯一的直接前驅內(nèi)部結點：有一個唯一的直接前驅，也有一個唯一的直接后繼線性表的長度(包含的結點個數(shù))為0的線性表稱為空表線性表的關系r是前驅關系，應具有反對稱性和傳遞性第4頁，課件共40頁，創(chuàng)作于2023年2月5舉例開始節(jié)點（首結點）終止節(jié)點（尾結點）內(nèi)部節(jié)點n2的前驅n1的后繼長度為k要求：內(nèi)部結點具有相同的數(shù)據(jù)類型

每個元素都有自己的位置第5頁，課件共40頁，創(chuàng)作于2023年2月6線性表運算分類list(-)：創(chuàng)建線性表的一個實例~list()：線性表消亡（即析構函數(shù)）獲取有關當前線性表的信息

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

為存儲在磁盤上的線性表所用第8頁，課件共40頁，創(chuàng)作于2023年2月92.2順序表—向量順序表(Sequentiallist)，又稱向量(Vector)采用定長的一維數(shù)組存儲結構主要特性:元素的類型相同

元素順序存儲在連續(xù)存儲空間中，每一個元素唯一的索引值（下標），讀寫元素方便使用常數(shù)作為向量長度，程序運行時保持不變第9頁，課件共40頁，創(chuàng)作于2023年2月10邏輯和存儲結構第10頁，課件共40頁，創(chuàng)作于2023年2月11向量的類定義enumBoolean{False,True};constintMax_length=100;Template<classELEM>//假定順序表的元素類型T為ELEMclasslist{//順序表，向量private: intmsize;//私有變量，順序表實例的最大長度 intcurr_len;//私有變量，順序表實例的當前長度 ELEM*nodelist;//私有變量，存儲順序表實例的向量public: //以下列出成員函數(shù)（順序表的算子集) intcurr;//當前下標，順序表的公共變量 list(constintsize);//構造算子，實參是表實例的最大長度

~list();//析構算子，用于將該表實例刪去第11頁，課件共40頁，創(chuàng)作于2023年2月12voidclear();//將順序表存儲的內(nèi)容清除，成為空表 intlength();//返回此順序表的當前實際長度 boolappend(constELEM&);//表尾增一新元素，表長加1 boolinsert(constELEM&);//在當前下標curr位置插入元素新值 booldelete(constintp);//刪去位置p的元素，表長減1； boolsetValue(intp,constTvalue); //用value修改位置p的元素值 //把p位置的值返回到變量value中； boolgetvalue(constintp,T&value); //查找值為value的元素，并返回第1次出現(xiàn)的位置 boolgetPos(int&p,constTvalue); }第12頁，課件共40頁，創(chuàng)作于2023年2月13查找元素目的:查找某個位置的值或者某個值的位置 template<classT> //假定順序表的元素類型為T boolarrList<T>::getPos(int&p,constTvalue){ inti;//元素下標 for(i=0;i<n;i++) //依次比較 if(value==aList[i]){ //下標為i的元素與value相等 p=i; //將下標由參數(shù)p返回 returntrue; } returnfalse;//順序表沒有元素值為value的元素 }第13頁，課件共40頁，創(chuàng)作于2023年2月14插入元素運算boolinsert(constintp,constTvlaue)在當前下標p=t位置插入元素新值valuecurr_len=k條件判斷：1、當前下標[0，curr_len]；2、當前長度（<msize）第14頁，課件共40頁，創(chuàng)作于2023年2月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起往右移動直到p aList[p]=value; //位置p處插入新元素

curLen++;

//表的實際長度增1 returntrue;}第15頁，課件共40頁，創(chuàng)作于2023年2月16算法執(zhí)行時間主要代價元素的移動元素總個數(shù)為n，各個位置插入的概率相等為p＝1/n

平均移動元素次數(shù)為總時間開銷估計為O（n）第16頁，課件共40頁，創(chuàng)作于2023年2月17刪除元素運算Delete(constintp)下標t位置值作為返回值，并刪去該元素條件判斷：1、當前下標[0，curr_len）；2、當前長度（>0）第17頁，課件共40頁，創(chuàng)作于2023年2月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開始每個元素左移直到curLen,curLen--; //表的實際長度減1returntrue;}第18頁，課件共40頁，創(chuàng)作于2023年2月19算法時間代價與插入操作相似，O(n)

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

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

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

指針調整過程第26頁，課件共40頁，創(chuàng)作于2023年2月27刪除結點過程描述

x

ppnext=dnext;dd=pnext;free(d)P節(jié)點不能不存在或者為尾節(jié)點！！第27頁，課件共40頁，創(chuàng)作于2023年2月28刪除算法template<classT> //線性表的元素類型為TboollnkList<T>::delete((constinti){ Link<T>*p,*d; if((p=setPos(i-1))==NULL||p==tail){//待刪結點不存在; cout<<"非法刪除點"<<endl;returnfalse; } d=p->next; //d是真正待刪結點 if(d==tail){ //待刪結點為尾結點，則修改尾指針 tail=p; p->next=NULL: deleted; } else{p->next=d->next;deleted;}//刪除結點d并修改鏈指針 returntrue;}第28頁，課件共40頁，創(chuàng)作于2023年2月29求長度算法intlength(){ Link<T>*p=head->next; intcount=0; while(p!=NULL){ p=p->next; count++; } returncount;}

第29頁，課件共40頁，創(chuàng)作于2023年2月30思考題：為什么引入頭節(jié)點？有利于對空鏈表進行操作或者在鏈表表頭進行操作等特殊情況的處理。例如單鏈表為空時的插入；單鏈表被刪除為空表時的處理；插入作為表的第一個節(jié)點；刪除表的第一個節(jié)點第30頁，課件共40頁，創(chuàng)作于2023年2月31單鏈表分析單鏈表的主要不足之處link字段僅僅指向后繼結點，不能有效地找到前驅雙鏈表彌補了上述不足之處增加一個指向前驅的指針第31頁，課件共40頁，創(chuàng)作于2023年2月32雙鏈表類型說明structDblListNode{ ELEMdata;

DblListNode*prev; DblListNode*next;};

structDoubleList{ DblListNode*head，*tail;};指向前驅結點指向后繼結點datanextprev第32頁，課件共40頁，創(chuàng)作于2023年2月33刪除結點示意圖刪除p所指的結點setPos(i)pp->prev->next=p->next;p->next->prev=p->prev;pp->prev=NULL;p->next=NULL;p^^free(p)第33頁，課件共40頁，創(chuàng)作于2023年2月34插入結點示意圖在p所指結點后插入一個新的結點setPos(i-1)pq->next=p->next;q->prev=p;qpp->