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

1、第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| ai∈ElemSet, i=0,1,2,…,n-1} S = {| ai-1,ai∈D, i=1,2,…,n-1} 　　為序偶，表示前后關(guān)系 意義：明確了首元素、尾元素、直接前驅(qū)、直接后繼的定義。 數(shù)據(jù)類型的框架定義（vect

2、or,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); // 按值查找 // 基本算法：

3、組合功能 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ù)元

4、素) 　　注意：第i個(gè)元素的下標(biāo)是i-1 靜態(tài)順序存儲(chǔ)結(jié)構(gòu)： const int MaxSize=100; class SeqList { private: T m_Data[MaxSize]; // 存放數(shù)據(jù)元素的數(shù)組 int m_Length; // 線性表的長(zhǎng)度 …………… } 　動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)：(vector) class SeqList { private: T *m_Data; // 存放數(shù)據(jù)元素的連續(xù)空間 int m_Size; // 線性表的空間大小 int m_Length

5、; // 線性表的長(zhǎng)度 …………… } 延伸思考：表長(zhǎng)變化與空間變化的關(guān)系 Insert(1) 1 Insert(2) 1 2 Insert(3) 1 2 3 Insert(4) 1 2 3 4 Insert(5) 1 2 3 4 5 Insert(6) 1 2 3 4 5 6 Insert(7) 1 2 3 4 5 6 7 Insert(8) 1 2 3 4 5 6 7 8 Insert(9) 1 2 3 4 5 6 7

6、 8 9 2.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

7、=0; im_Length) throw "查找位置非法"; return m_Data[i-1]; } // 對(duì)第i個(gè)元素賦值 void SeqList::Set(int i,int e) { if(i<1 && i>m_Length) throw "查找位置非法"; m_Data[i-

8、1] = e; } // 輸出所有元素 void SeqList::Output() { for(int i=0;i= MaxSize) throw "上溢"; if(i<1 || i>m_Length+1) throw "位置不合理"; for(int j

9、=m_Length; j>=i; j--) m_Data[j]=m_Data[j-1]; // 向后移位 m_Data[i-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_Data[i-1]; for(int j=i; j

10、 m_Data[j-1]=m_Data[j]; // 向前移位 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(SeqLis

11、t &L) { SeqList *newL = new SeqList; int i=0,j=0; while(iAppend(m_Data[i]); i++; } else { newL->Append(L.m_Data[j]); j++; } while(iAppend(m_Data[i]); i++; } while(j

12、th) { newL->Append(L.m_Data[j]); 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

13、 4 5 6 7 8 9 void SeqList::Remove(int e) { int k=0; // k是e的個(gè)數(shù) For(int i=0; i

14、////////// 2.6 面向函數(shù)的編程風(fēng)格 // 檢查向量中各有序（增序）子向量的位置 template void SearchSortedList(const vector &data,vector &si, vector &ei) { si.clear(); ei.clear(); for(int i=0; idata[i]) i++; ei.push_back(i); i++; } } 2-7