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

《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第2章 線性表》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第2章 線性表（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第2章 線性表 線性結(jié)構(gòu)：在數(shù)據(jù)元素的非空集中，存在唯一的一個首元素，存在唯一的一個尾元素，除首元素外每個元素均只有一個直接前驅(qū)，除末元素外每個元素均只有一個直接后繼。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,aiD, i=1,2,n-1為序偶，表示前后關(guān)系意義：明確了首元素、尾元素、直接前驅(qū)、直接后繼的定義。 數(shù)據(jù)類型的框架定義（vector,list）class List public: List(); virtual List(); / 基本操作 int Length(); /

2、 求長度 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); / 合并 / 基本算法：集合運算 List & Union(List &L); / 集合并 List & Inter(List &L); / 集合交 / 應(yīng)用算法：多項式運算 ;2 順序線性表2.1

3、類的定義 邏輯結(jié)構(gòu)中的“前后關(guān)系”：物理結(jié)構(gòu)中的“相鄰關(guān)系”loc(ai)=loc(a0)+i*sizeof(單個數(shù)據(jù)元素)注意：第i個元素的下標(biāo)是i-1靜態(tài)順序存儲結(jié)構(gòu)： const int MaxSize=100; class SeqListprivate: T m_DataMaxSize; / 存放數(shù)據(jù)元素的數(shù)組 int m_Length; / 線性表的長度動態(tài)順序存儲結(jié)構(gòu)：(vector)class SeqListprivate: T *m_Data; / 存放數(shù)據(jù)元素的連續(xù)空間 int m_Size; / 線性表的空間大小 int m_Length; / 線性表的長度延伸思考：表長變

4、化與空間變化的關(guān)系Insert(1)1Insert(2)12Insert(3)123Insert(4)1234Insert(5)12345Insert(6)123456Insert(7)1234567Insert(8)12345678Insert(9)1234567892.2 基本操作/ 項目路徑：1SeqList整數(shù)順序表/2.2.1 構(gòu)造/析構(gòu)/ “靜態(tài)順序存儲結(jié)構(gòu)”版本SeqList:SeqList() m_Length=0; SeqList: SeqList( ) SeqList:SeqList(int a, int n) if(nMaxSize) throw 參數(shù)非法; for(in

5、t i=0; in; i+) m_Datai=ai; m_Length=n;/“動態(tài)順序存儲結(jié)構(gòu)”版本 空間的分配/回收2.2.2 簡單“讀/寫”操作/ 取第i個元素的值int SeqList:Get(int i) if(im_Length) throw 查找位置非法; return m_Datai-1;/ 對第i個元素賦值void SeqList:Set(int i,int e) if(im_Length) throw 查找位置非法; m_Datai-1 = e;/ 輸出所有元素void SeqList:Output() for(int i=0;im_Length;i+) coutm_Dat

6、ai ; cout= MaxSize) throw 上溢; if(im_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個元素刪除前：刪除后：int SeqList:Delete(int i) if(m_Length=0) throw 下溢; if(im_Length) throw 位置不合理; int e = m_Datai-1; for(int j=i; jm_Length; j+) m_Dataj-1=

7、m_Dataj; / 向前移位 m_Length-; return e;2.3 效率分析 存、取：O(1) 直接 插、刪：O(n) 移動元素費時2.4 基本算法2.4.1 有序順序表的合并思路1：以插入單個元素為基礎(chǔ)的合并。 時間復(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(im_Length & jL.m_Length)

8、if(m_DataiAppend(m_Datai); i+; else newL-Append(L.m_Dataj); j+; while(iAppend(m_Datai); i+; while(jAppend(L.m_Dataj); j+; return *newL;2.4.1無序順序表的并集SeqList & SeqList:Union(SeqList &L)2.4.1無序順序表的交集SeqList & SeqList:Inter(SeqList &L)2.4.1無序順序表的逆序void SeqList:Reverse()2.4.1剔除無序順序表中的某種元素剔除順序表中的所有0元素，要求較

9、高效率。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的個數(shù) For(int i=0; im_Length; i+) If(m_Datai=0) k+; Else m_Datai-k = m_Datai; m_Length = m_Length-k;2.5 從類向類模板進(jìn)階/ 項目路徑：2SeqList順序表模板/2.6 面向函數(shù)的編程風(fēng)格/ 檢查向量中各有序（增序）子向量的位置template void SearchSortedList(const vector &data,vector &si, vector &ei) si.clear(); ei.clear(); for(int i=0; idata.size(); ) si.push_back(i); while(idatai) i+; ei.push_back(i); i+; 2-7