《數(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| 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(); // 求長度
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); // 合并
// 基本算法：集合運算
List & Union(List &L); // 集合并
List & Inter(List &L); // 集合交
// 應(yīng)用算法：多項式運算
…………
};
2 順序線性表
2.1 類的定義
邏輯結(jié)構(gòu)中的“前后關(guān)系”：物理結(jié)構(gòu)中的“相鄰關(guān)系”
loc(ai)=loc(a0)+i*sizeof(單個數(shù)據(jù)元
4、素)
注意：第i個元素的下標(biāo)是i-1
靜態(tài)順序存儲結(jié)構(gòu)：
const int MaxSize=100;
class SeqList
{
private:
T m_Data[MaxSize]; // 存放數(shù)據(jù)元素的數(shù)組
int m_Length; // 線性表的長度
……………
}
動態(tài)順序存儲結(jié)構(gòu)：(vector)
class SeqList
{
private:
T *m_Data; // 存放數(shù)據(jù)元素的連續(xù)空間
int m_Size; // 線性表的空間大小
int m_Length
5、; // 線性表的長度
……………
}
延伸思考：表長變化與空間變化的關(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 基本操作
/////////////////////////////////
// 項目路徑：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(n>MaxSize) throw "參數(shù)非法";
for(int i
7、=0; im_Length) throw "查找位置非法";
return m_Data[i-1];
}
// 對第i個元素賦值
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個元素
刪除前：
刪除后：
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) 移動元素費時
2.4 基本算法
2.4.1 有序順序表的合并
思路1：以插入單個元素為基礎(chǔ)的合并。
時間復(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無序順序表的并集
SeqList & SeqList::Union(SeqList &L)
2.4.1無序順序表的交集
SeqList & SeqList::Inter(SeqList &L)
2.4.1無序順序表的逆序
void SeqList::Reverse()
2.4.1剔除無序順序表中的某種元素
剔除順序表中的所有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的個數(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
數(shù)據(jù)結(jié)構(gòu)(C語言版) 第2章 線性表
