線性表設(shè)計與實現(xiàn)專題講座

線性表設(shè)計與實現(xiàn)專題講座線性表基本概念線性表定義線性表(List)是零個或多個數(shù)據(jù)元素的集合線性表中的數(shù)據(jù)元素之間是有順序的線性表中的數(shù)據(jù)元素個數(shù)是有限的線性表中的數(shù)據(jù)元素的類型必須相同數(shù)學定義線性表是具有相同類型的n（≥0）個數(shù)據(jù)元素的有限序列（a1,a2,…,an）ai是表項，n是表長度。性質(zhì)a0為線性表的第一個元素，只有一個后繼an為線性表的最后一個元素，只有一個前驅(qū)除a0和an外的其它元素ai，既有前驅(qū)，又有后繼

線性表能夠逐項訪問和順序存取練習下面的關(guān)系中可以用線性表描述的是A.班級中同學的友誼關(guān)系B.公司中的上下級關(guān)系C.冬天圖書館排隊占座關(guān)系D.花名冊上名字之間的關(guān)系線性表的操作創(chuàng)建線性表銷毀線性表清空線性表將元素插入線性表將元素從線性表中刪除獲取線性表中某個位置的元素獲取線性表的長度線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型線性表的操作在程序中的表現(xiàn)為一組函數(shù)C語言描述=====》線性表的設(shè)計與實現(xiàn)人生財富庫積累#ifndef_WBM_LIST_H_#define_WBM_LIST_H_typedefvoidList;typedefvoidListNode;//創(chuàng)建并且返回一個空的線性表List*LinkList_Create();//銷毀一個線性表listvoidList_Destroy(List*list);//將一個線性表list中的所有元素清空,線性表回到創(chuàng)建時的初始狀態(tài)voidList_Clear(List*list);//返回一個線性表list中的所有元素個數(shù)intList_Length(List*list);//向一個線性表list的pos位置處插入新元素nodeintList_Insert(List*list,ListNode*node,intpos);//獲取一個線性表list的pos位置處的元素ListNode*List_Get(List*list,intpos);//刪除一個線性表list的pos位置處的元素返回值為被刪除的元素，NULL表示刪除失敗ListNode*List_Delete(List*list,intpos);#endif線性表的順序存儲結(jié)構(gòu)1、基本概念2、設(shè)計與實現(xiàn)插入元素算法判斷線性表是否合法判斷插入位置是否合法把最后一個元素到插入位置的元素后移一個位置將新元素插入線性表長度加1獲取元素操作判斷線性表是否合法判斷位置是否合法直接通過數(shù)組下標的方式獲取元素刪除元素算法判斷線性表是否合法判斷刪除位置是否合法將元素取出將刪除位置后的元素分別向前移動一個位置線性表長度減13、優(yōu)點和缺點優(yōu)點：無需為線性表中的邏輯關(guān)系增加額外的空間可以快速的獲取表中合法位置的元素缺點：插入和刪除操作需要移動大量元素當線性表長度變化較大時難以確定存儲空間的容量線性表的鏈式存儲1、基本概念鏈式存儲定義為了表示每個數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系，每個元素除了存儲本身的信息外，還需要存儲指示其直接后繼的信息。表頭結(jié)點鏈表中的第一個結(jié)點，包含指向第一個數(shù)據(jù)元素的指針以及鏈表自身的一些信息數(shù)據(jù)結(jié)點鏈表中代表數(shù)據(jù)元素的結(jié)點，包含指向下一個數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息尾結(jié)點鏈表中的最后一個數(shù)據(jù)結(jié)點，其下一元素指針為空，表示無后繼。2、設(shè)計與實現(xiàn)在C語言中可以用結(jié)構(gòu)體來定義鏈表中的指針域鏈表中的表頭結(jié)點也可以用結(jié)構(gòu)體實現(xiàn)帶頭結(jié)點、位置從0的單鏈表返回鏈表中第3個位置處，元素的值LinkListNode*LinkList_Get(LinkList*list,intpos){ inti=0; TLinkList*tList=(TLinkList*)list; LinkListNode*current=NULL; LinkListNode*ret=NULL; if(list==NULL||pos<0||pos>=tList->length) { returnNULL; } current=(LinkListNode*)tList; for(i=0;i<pos;i++) { current=current->next; } ret=current->next; returnret;}返回第三個位置的移動pos次以后，當前指針指向哪里？答案：指向位置2，所以需要返回ret=current->next;備注： 循環(huán)遍歷時， 遍歷第1次，指向位置0 遍歷第2次，指向位置1 遍歷第3次，指向位置2 遍歷第n次，指向位置n-1;所以如果想返回位置n的元素的值，需要怎么做 ret=current->next;此問題是：指向頭結(jié)點的指針移動n次和第n個元素之間的關(guān)系？刪除元素3、優(yōu)點和缺點優(yōu)點：無需一次性定制鏈表的容量插入和刪除操作無需移動數(shù)據(jù)元素缺點：數(shù)據(jù)元素必須保存后繼元素的位置信息獲取指定數(shù)據(jù)的元素操作需要順序訪問之前的元素循環(huán)鏈表1、基本概念循環(huán)鏈表的定義：將單鏈表中最后一個數(shù)據(jù)元素的next指針指向第一個元素循環(huán)鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長度清空鏈表獲取第pos個元素操作插入元素到位置pos刪除位置pos處的元素新增功能：游標的定義在循環(huán)鏈表中可以定義一個“當前”指針，這個指針通常稱為游標，可以通過這個游標來遍歷鏈表中的所有元素。循環(huán)鏈表新操作獲取當前游標指向的數(shù)據(jù)元素將游標重置指向鏈表中的第一個數(shù)據(jù)元素將游標移動指向到鏈表中的下一個數(shù)據(jù)元素直接指定刪除鏈表中的某個數(shù)據(jù)元素CircleListNode*CircleList_DeleteNode(CircleList*list,CircleListNode*node);CircleListNode*CircleList_Reset(CircleList*list);CircleListNode*CircleList_Current(CircleList*list);CircleListNode*CircleList_Next(CircleList*list);2、設(shè)計與實現(xiàn)插入元素的分析普通位置插入元素添加第一個元素（第一次插入元素）最后一個位置插入元素第一個位置插入元素在第一個位置插入刪除節(jié)點3、優(yōu)點和缺點優(yōu)點：功能強了。循環(huán)鏈表只是在單鏈表的基礎(chǔ)上做了一個加強循環(huán)鏈表可以完全取代單鏈表的使用循環(huán)鏈表的Next和Current操作可以高效的遍歷鏈表中的所有元素缺點：代碼復雜度提高了約瑟夫問題-循環(huán)鏈表典型應(yīng)用n個人圍成一個圓圈，首先第1個人從1開始一個人一個人順時針報數(shù)，報到第m個人，令其出列。然后再從下一個人開始從1順時針報數(shù)，報到第m個人，再令其出列，…，如此下去，求出列順序。雙向鏈表1、基本概念單鏈表的結(jié)點都只有一個指向下一個結(jié)點的指針單鏈表的數(shù)據(jù)元素無法直接訪問其前驅(qū)元素逆序訪問單鏈表中的元素是極其耗時的操作！len=LinkList_Length(list);for(i=len-1;len>=0;i++)//O(n){LinkListNode*p=LinkList_Get(list,i);//O(n)//訪問數(shù)據(jù)元素p中的元素//}雙向鏈表的定義在單鏈表的結(jié)點中增加一個指向其前驅(qū)的pre指針雙向鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長度清空鏈表獲取第pos個元素操作插入元素到位置pos刪除位置pos處的元素2、設(shè)計與實現(xiàn)插入操作刪除操作雙向鏈表的新操作獲取當前游標指向的數(shù)據(jù)元素將游標重置指向鏈表中的第一個數(shù)據(jù)元素將游標移動指向到鏈表中的下一個數(shù)據(jù)元素將游標移動指向到鏈表中的上一個數(shù)據(jù)元素直接指定刪除鏈表中的某個數(shù)據(jù)元素DLinkListNode*DLinkList_DeleteNode(DLinkList*list,DLinkListNode*node);DLinkListNode*DLinkList_Reset(DLinkList*list);DLinkListNode*DLinkList_Current(DLinkList*list);DLinkListNode*DLinkList_Next(DLinkList*list);DLinkListNode*DLinkList_Pre(DLi