邊第2講 線性表

數(shù)據(jù)結(jié)構(gòu)定義:相關(guān)聯(lián)的數(shù)據(jù)元素的集合。由某一數(shù)據(jù)元素的集合及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成記為： Data_Structure={D,S}其中，D是某一數(shù)據(jù)元素的集合，S是該集合中所有數(shù)據(jù)元素之間的關(guān)系組成的有限集合

數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語言順序存儲(chǔ)表示鏈接存儲(chǔ)表示數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語言順序存儲(chǔ)表示鏈接存儲(chǔ)表示順序存儲(chǔ)

所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰。

鏈?zhǔn)酱鎯?chǔ)

所有元素存放在可以不連續(xù)的存貯單元中，但元素之間的關(guān)系可以通過地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。（2）在對數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。第2章線性表線性表(LinearList)線性表的定義

n（0）個(gè)數(shù)據(jù)元素的有限序列.記作

（a1,a2,…,an）

ai

是表中數(shù)據(jù)元素，n是表長度。

遍歷逐項(xiàng)訪問：

從前向后從后向前

線性表的特點(diǎn)除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)(前件)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼(后件)。a1a2a3a4a5a6線性表基本操作

1．intLength()const

初始條件：線性表已存在。

操作結(jié)果：返回線性表元素個(gè)數(shù)。

2．boolEmpty()const

初始條件：線性表已存在。

操作結(jié)果：如線性表為空，則返回true，否則返回false。3．voidClear()

初始條件：線性表已存在。

操作結(jié)果：清空線性表。

4．ElemTypeGetElem(inti)const

初始條件：線性表已存在，1≤i≤Length()。

操作結(jié)果：用e返回第i個(gè)元素的值。

5．voidSetElem(inti,constElemTypee)

初始條件：線性表已存在，1≤i≤Length()。

操作結(jié)果：將線性表的第i個(gè)位置的元素賦值為e。

6．voidDelete(inti)

初始條件：線性表已存在，1≤i≤Length()。

操作結(jié)果：刪除線性表的第i個(gè)位置的元素,長度減1。

8．voidInsert(inti,ElemTypee)

初始條件：線性表已存在，

1≤i≤Length()+1。

操作結(jié)果：在線性表的第i個(gè)位置前插入元素e，長度加1。線性表的順序存儲(chǔ)結(jié)構(gòu)順序表(SequentialList)順序表的定義和特點(diǎn)定義將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間中。可利用一維數(shù)組描述存儲(chǔ)結(jié)構(gòu)特點(diǎn)線性表的順序存儲(chǔ)方式遍歷順序訪問

253457164809

012345dataa1a2a3a4a5a6

012345Va1a2a3a4a5a6

//順序表類模板template<classT>classSqList{private://順序表實(shí)現(xiàn)的數(shù)據(jù)成員: intcount; //元素個(gè)數(shù) intmaxSize; //順序表最大元素個(gè)數(shù) T*V; //元素存儲(chǔ)空間順序表(SqList)類模板的定義順序表(SeqList)類模板的定義//順序表類模板template<classT>classSqList{private://順序表實(shí)現(xiàn)的數(shù)據(jù)成員: intcount; //元素個(gè)數(shù) intmaxSize; //順序表最大元素個(gè)數(shù) T*V; //元素存儲(chǔ)空間public:

//成員函數(shù)

SqList(){maxSize=0;count=0;return;}

SqList(int);

//建立空順序表，申請存儲(chǔ)空間

intLength();//求順序表的長度

voidPrt();

//順序輸出順序表中的元素與順序表長度

intFlag();

//檢測順序表的狀態(tài)

voidInsert(int,T);

//在表的指定位置前插入新元素

voidDelete(int);

//在表中刪除指定元素};//建立空順序表template<classT>SqList<T>::SqList(intsize){maxSize=size;//存儲(chǔ)空間容量V=newT[maxSize];//動(dòng)態(tài)申請存儲(chǔ)空間count=0;//順序表長度為0，即建立空順序表return;}//求表長template<classT> intSqList<T>::Length(){returncount; }//順序輸出順序表中的元素與順序表長度template<classT>voidSqList<T>::Prt(){inti;cout<<"count="<<count<<endl;for(i=0;i<count;i++)cout<<V[i]<<endl;return;}//檢測順序表的狀態(tài),返回值是0，代表表空；是-1代表//已滿；返回值是1，代表正常不滿不空；template<classT>intSqList<T>::Flag(){if(count==maxSize)return(-1);//存儲(chǔ)空間已滿，返回-1if(count==0)return(0);//順序表為空，返回0return(1);//正常返回1 }表項(xiàng)的插入25345716480963

a1a2a3a4a5a6a7a8V50插入bi表項(xiàng)的插入25345716480963

a1a2a3a4a5a6a7a8V50插入x2534575016480963

a1a2a3xa4a5a6a7V50i//在表的指定位置前插入新元素template<classT>voidSqList<T>::Insert(inti,Tx){intk;if(count==maxSize)//存儲(chǔ)空間已滿，上溢錯(cuò)誤{cout<<"overflow"<<endl;return;}if(i>count)i=count+1;//默認(rèn)為在最后一個(gè)元素之后插入if(i<1)i=1;//默認(rèn)為在第一個(gè)元素之前插入

for(k=count;k>=i;k--) v[k]=v[k-1];//從最后一個(gè)元素直到第i個(gè)元素均后移一個(gè)位置v[i-1]=x;//插入新元素count++;//順序表長度加1return;}表項(xiàng)的刪除2534575016480963

a1a2a3a4a5a6a7a8V16刪除x表項(xiàng)的刪除2534575016480963

a1a2a3a4a5a6a7a8V16刪除x25345750480963

a1a2a3a4a6a7a8a9V//在順序表中刪除指定元素template<classT>voidSqList<T>::Delete(inti){intk;if(count==0)//順序表為空，下溢錯(cuò)誤 {cout<<"underflow!"<<endl;return;}if((i<1)||(i>count))//順序表中沒有這個(gè)元素 {cout<<"Notthiselementinthelist!"<<endl;return; }for(k=i;k<count;k++) v[k-1]=v[k];//從第i個(gè)元素直到最后一個(gè)元素均前移一個(gè)位置count--;//順序表長度減1return;}插入算法花費(fèi)的時(shí)間，主要在于循環(huán)中元素的后移（其它語句花費(fèi)的時(shí)間可以省去），即從插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，當(dāng)插入位置i=１時(shí)，全部元素都得移動(dòng)，需n次移動(dòng)，當(dāng)i=n+１時(shí)，不需移動(dòng)元素，故在i位置插入時(shí)移動(dòng)次數(shù)為n-i+1，假設(shè)在每個(gè)位置插入的概率相等為，則平均移動(dòng)元素的次數(shù)為=

故時(shí)間復(fù)雜度為O(n)。同理，可推出刪除運(yùn)算的平均移動(dòng)次數(shù)為，故時(shí)間復(fù)雜度為O(n)。時(shí)間復(fù)雜度分析/文件名L2_3.cpp #include"SqList.h" intmain() {SqList<double>s1(100);//建立容量為100的空順序表對象s1 cout<<"第1次輸出順序表對象s1:"<<endl; s1.Prt(); s1.Insert(0,1.5);//在第0個(gè)元素前插入1.5s1.Insert(1,2.5);//在第1個(gè)元素前插入2.5s1.Insert(4,3.5);//在第4個(gè)元素前插入3.5 cout<<"第2次輸出順序表對象s1:"<<endl;s1.Prt();s1.Delete(0);//刪除順序表s1中的第0個(gè)元素s1.Delete(2);//刪除順序表s1中的第2個(gè)元素 cout<<"第3次輸出順序表對象s1:"<<endl;s1.Prt(); cout<<s1.Length()<<endl;cout<<s1.Flag()<<endl; return0; }線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)結(jié)點(diǎn)可以不連續(xù)存儲(chǔ)表可擴(kuò)充單鏈表

(SinglyLinkedList)單鏈表的類模板類模板更易于復(fù)用。在單鏈表的類模板定義中，增加了頭結(jié)點(diǎn)。//結(jié)點(diǎn)類模板template<classElemType>structNode{//數(shù)據(jù)成員: ElemTypedata; //數(shù)據(jù)域 Node<ElemType>*next; //指針域//構(gòu)造函數(shù)模板: Node(); //無參數(shù)的構(gòu)造函數(shù)模板 Node(ElemTypeitem,Node<ElemType>*link= NULL);//已知數(shù)據(jù)域和指針域建立結(jié)構(gòu)};//簡單線性鏈表類模板template<classElemType>classSimpleLinkList{protected://鏈表實(shí)現(xiàn)的數(shù)據(jù)成員: Node<ElemType>*head; //頭結(jié)點(diǎn)指針//輔助函數(shù)模板: Node<ElemType>*GetElemPtr(intposition)const; //返回指向第position個(gè)結(jié)點(diǎn)的指針 voidInit(); //初始化線性表public://抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明: SimpleLinkList(); //無參數(shù)構(gòu)造函數(shù)模板 virtual~SimpleLinkList(); //析構(gòu)函數(shù)模板 intLength()const; //求線性表長度

boolEmpty()const; //判斷線性表是否為空 voidClear(); //將線性表清空 voidTraverse(void(*visit)(constElemType&)) const; //遍歷線性表 StatusCodeGetElem(intposition,ElemType&e) const; //求指定位置的元素 StatusCodeSetElem(intposition,constElemType &e); //設(shè)置指定位置的元素值 StatusCodeDelete(intposition,ElemType&e);

//刪除元素

StatusCodeInsert(intposition,constElemType&e);

//插入元素 SimpleLinkList(constSimpleLinkList<ElemType> ©); //復(fù)制構(gòu)造函數(shù)模板 SimpleLinkList<ElemType>&operator=(const SimpleLinkList<ElemType>©);

//重載賦值運(yùn)算符};單鏈表中的插入與刪除插入newPtr=newNode<ElemType>(e,tmpPtr->next);tmpPtr->next=newPtr;

template<classElemType>StatusCodeSimpleLinkList<ElemType>::Insert( intposition,constElemType&e)//操作結(jié)果：在線性表的第position個(gè)位置前插入元素e// position的取值范圍為1≤position≤Length()+1// position合法時(shí)返回SUCCESS,否則返回// RANGE_ERROR{ if(position<1||position>Length()+1) { //position范圍錯(cuò) returnRANGE_ERROR; //位置不合法 } else { //position合法 Node<ElemType>*tmpPtr; tmpPtr=GetElemPtr(position-1);

//取出指向第position-1個(gè)結(jié)點(diǎn)的指針 Node<ElemType>*newPtr; newPtr=newNode<ElemType>(e, tmpPtr->next); //生成新結(jié)點(diǎn) tmpPtr->next=newPtr;

//將tmpPtr插入到鏈表中 returnSUCCESS; }}刪除 tmpPtr->next