數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第2章 線性表

第2章 線性表 線性結(jié)構(gòu)：在數(shù)據(jù)元素的非空集中，存在唯一的一個(gè)首元素，存在唯一的一個(gè)尾元素，除首元素外每個(gè)元素均只有一個(gè)直接前驅(qū)，除末元素外每個(gè)元素均只有一個(gè)直接后繼。1 邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的形式定義：Linear_list=(D，S，P)D = ai| aiElemSet, i=0,1,2,n-1S = <ai-1,ai>| ai-1,aiD, i=1,2,n-1<ai-1,ai>為序偶，表示前后關(guān)系意義：明確了首元素、尾元素、直接前驅(qū)、直接后繼的定義。 數(shù)據(jù)類型的框架定義（vector,list）class List public: List(); virtual List(); / 基本操作 int Length(); / 求長(zhǎng)度 void Output(); / 遍歷/輸出 void Insert(int i, T e); / 插入 void Delete(int i); / 刪除 T Get(int i); / 按位查找 int Search(T e); / 按值查找 / 基本算法：組合功能 void Reverse(); / 逆序 void Sort(); / 排序 void Merge(List &L); / 合并 / 基本算法：集合運(yùn)算 List & Union(List &L); / 集合并 List & Inter(List &L); / 集合交 / 應(yīng)用算法：多項(xiàng)式運(yùn)算 ;2 順序線性表2.1 類的定義 邏輯結(jié)構(gòu)中的“前后關(guān)系”：物理結(jié)構(gòu)中的“相鄰關(guān)系”loc(ai)=loc(a0)+i*sizeof(單個(gè)數(shù)據(jù)元素)注意：第i個(gè)元素的下標(biāo)是i-1靜態(tài)順序存儲(chǔ)結(jié)構(gòu)： const int MaxSize=100; class SeqListprivate: T m_DataMaxSize; / 存放數(shù)據(jù)元素的數(shù)組 int m_Length; / 線性表的長(zhǎng)度動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)：(vector)class SeqListprivate: T *m_Data; / 存放數(shù)據(jù)元素的連續(xù)空間 int m_Size; / 線性表的空間大小 int m_Length; / 線性表的長(zhǎng)度延伸思考：表長(zhǎng)變化與空間變化的關(guān)系Insert(1)1Insert(2)12Insert(3)123Insert(4)1234Insert(5)12345Insert(6)123456Insert(7)1234567Insert(8)12345678Insert(9)1234567892.2 基本操作/ 項(xiàng)目路徑：1SeqList整數(shù)順序表/2.2.1 構(gòu)造/析構(gòu)/ “靜態(tài)順序存儲(chǔ)結(jié)構(gòu)”版本SeqList:SeqList() m_Length=0; SeqList: SeqList( ) SeqList:SeqList(int a, int n) if(n>MaxSize) throw "參數(shù)非法" for(int i=0; i<n; i+) m_Datai=ai; m_Length=n;/“動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)”版本 空間的分配/回收2.2.2 簡(jiǎn)單“讀/寫(xiě)”操作/ 取第i個(gè)元素的值int SeqList:Get(int i) if(i<1 && i>m_Length) throw "查找位置非法" return m_Datai-1;/ 對(duì)第i個(gè)元素賦值void SeqList:Set(int i,int e) if(i<1 && i>m_Length) throw "查找位置非法" m_Datai-1 = e;/ 輸出所有元素void SeqList:Output() for(int i=0;i<m_Length;i+) cout<<m_Datai<<" " cout<<endl;2.2.3 插入/ 將e插入到第i個(gè)元素之后插入前：插入后：void SeqList:Insert(int i, int e) if(m_Length >= MaxSize) throw "上溢" if(i<1 | i>m_Length+1) throw "位置不合理" for(int j=m_Length; j>=i; j-) m_Dataj=m_Dataj-1; / 向后移位 m_Datai-1 = e; m_Length+; 2.2.4 刪除/ 刪除第i個(gè)元素刪除前：刪除后：int SeqList:Delete(int i) if(m_Length=0) throw "下溢" if(i<1 | i>m_Length) throw "位置不合理" int e = m_Datai-1; for(int j=i; j<m_Length; j+) m_Dataj-1=m_Dataj; / 向前移位 m_Length-; return e;2.3 效率分析 存、?。篛(1) 直接 插、刪：O(n) 移動(dòng)元素費(fèi)時(shí)2.4 基本算法2.4.1 有序順序表的合并思路1：以插入單個(gè)元素為基礎(chǔ)的合并。 時(shí)間復(fù)雜度？思路2：充分利用順序表中的有序關(guān)系，提高效率。void SeqList:Append(int e) Insert(m_Length+1,e); SeqList & SeqList:Merge(SeqList &L) SeqList *newL = new SeqList; int i=0,j=0; while(i<m_Length && j<L.m_Length) if(m_Datai<=L.m_Dataj) newL->Append(m_Datai); i+; else newL->Append(L.m_Dataj); j+; while(i<m_Length) newL->Append(m_Datai); i+; while(j<L.m_Length) newL->Append(L.m_Dataj); j+; return *newL;2.4.1無(wú)序順序表的并集SeqList & SeqList:Union(SeqList &L)2.4.1無(wú)序順序表的交集SeqList & SeqList:Inter(SeqList &L)2.4.1無(wú)序順序表的逆序void SeqList:Reverse()2.4.1剔除無(wú)序順序表中的某種元素剔除順序表中的所有0元素，要求較高效率。1 2 0 3 4 0 0 0 5 6 7 0 0 8 9=> 1 2 3 4 5 6 7 8 9void SeqList:Remove(int e) int k=0; / k是e的個(gè)數(shù) For(int i=0; i<m_Length; i+) If(m_Datai=0) k+; Else m_Datai-k = m_Datai; m_Length = m_Length-k;2.5 從類向類模板進(jìn)階/ 項(xiàng)目路徑：2SeqList順序表模板/2.6 面向函數(shù)的編程風(fēng)格/ 檢查向量中各有序（增序）子向量的位置template<class T> void SearchSortedList(const vector<T> &data,vector<int> &si, vector<int> &ei) si.clear(); ei.clear(); for(int i=0; i<data.size(); ) si.push_back(i); while(i<data.size() && datai+1>datai) i+; ei.push_back(i); i+; 2-7