【正文】 Length() const 初始條件：線性表已存在。 操作結果：返回線性表元素個數(shù)。 2． bool Empty() const 初始條件：線性表已存在。 操作結果：如線性表為空，則返回 true，否則返回 false。 四川大學計算機學院，主講教師：游洪躍 3． void Clear() 初始條件：線性表已存在。 操作結果：清空線性表。 4． void Traverse(void (*visit)(const ElemType amp。)) const 初始條件：線性表已存在。 操作結果：依次對線性表的每個元素調用函數(shù) (*visit)。 四川大學計算機學院，主講教師：游洪躍 5． StatusCode GetElem(int position, ElemType amp。e) const 初始條件：線性表已存在，1≤position≤Length() 。 操作結果：用 e返回第 position個元素的值。 6． StatusCode SetElem(int position, const ElemType amp。e) 初始條件：線性表已存在，1≤position≤Length() 。 操作結果：將線性表的第 position個位置的元素賦值為 e。 四川大學計算機學院，主講教師：游洪躍 7． StatusCode Delete(int position, ElemType amp。e) 初始條件：線性表已存在，1≤position≤Length() 。 操作結果：刪除線性表的第 position個位置的元素 , 并用 e返回其值，長度減 1。 8． StatusCode Insert(int position, const ElemType amp。e) 初始條件：線性表已存在，1≤position≤Length()+1 。 操作結果 ： 在線性表的第 position個位置前插入元素 e， 長度加 1。 四川大學計算機學院，主講教師：游洪躍 線性表的順序存儲結構 四川大學計算機學院，主講教師：游洪躍 順序表 (Sequential List) ? 順序表的定義和特點 – 定義 將線性表中的元素相繼存放在一個連續(xù)的存儲空間中。 – 可利用一維數(shù)組描述存儲結構 – 特點 線性表的順序存儲方式 – 遍歷 順序訪問 25 34 57 16 48 09 0 1 2 3 4 5 data 四川大學計算機學院，主講教師：游洪躍 順序表 (SeqList)類的定義 // 順序表類 template class elemType class SqList { protected: // 順序表實現(xiàn)的數(shù)據(jù)成員 : int count。 // 元素個數(shù) int maxSize。 // 順序表最大元素個數(shù) elemType *elems。 // 元素存儲空間 四川大學計算機學院，主講教師：游洪躍 // 輔助函數(shù) bool Full() const。 // 判斷線性表是否已滿 void Init(int size)。 // 初始化線性表 public: // 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認 // 方法聲明 : SqList(int size = DEFAULT_SIZE)。// 構造函數(shù) virtual ~SqList()。 // 析構函數(shù) int Length() const。 // 求線性表長度 bool Empty() const。 // 判斷線性表是否為空 void Clear()。 // 將線性表清空 四川大學計算機學院，主講教師：游洪躍 void Traverse(void (*Visit)(const elemType amp。)) const。 // 遍歷線性表 StatusCode GetElem(int position, elemType amp。e) const。 // 求指定位置的元素 StatusCode SetElem(int position, const elemType amp。e)。 // 設置指定位置的元素值 StatusCode Delete(int position, elemType amp。e)。 // 刪除元素 StatusCode Insert(int position, const elemType amp。e)。 // 插入元素 SqList(const SqListelemType amp。copy)。 // 復制構造函數(shù) SqListelemType amp。operator =(const SqListelemType amp。copy)。 // 賦值語句重載 }。 四川大學計算機學院，主講教師：游洪躍 順序表輔助函數(shù)的實現(xiàn) template class ElemType bool SqListElemType::Full() const // 操作結果：如線性表已滿，則返回 true，否則返回 false { return count == maxSize。 } 四川大學計算機學院，主講教師：游洪躍 template class ElemType void SqListElemType::Init(int size) // 操作結果：初始化線性表為最大元素個數(shù)為 size的空線 // 性表 { maxSize = size。 // 最大元素個數(shù) if (elems != NULL) delete []elems。// 釋放存儲空間 elems = new ElemType[maxSize]。// 分配存儲空間 count = 0。 // 空線性表元素個數(shù)為 0 } 四川大學計算機學院，主講教師：游洪躍 template class ElemType SqListElemType::SqList(int size) // 操作結果：構造一個最大元素個數(shù)為 size的空順序表 { elems = NULL。 // 未分配存儲空間前 ,elems為空 Init(size)。 // 初始化線性表 } template class ElemType SqListElemType::~SqList() // 操作結果：銷毀線性表 { delete []elems。 // 釋放存儲空間 } 順序表部分公共操作的實現(xiàn) 四川大學計算機學院，主講教師：游洪躍 表項的插入 25 34 57 16 48 09 63 ?? 0 1 2 3 4 5 6 7 data 50 插入 x 25 34 57 50 16 48 09 63 ?? 0 1 2 3 4 5 6 7 data 50 i 四川大學計算機學院，主講教師：游洪躍 template class ElemType StatusCode SqListElemType::Insert(int position, const ElemType amp。e) // 操作結果：在線性表的第 position個位置前插入元素 e, // position的的取值范圍為 1≤position≤Length()+1 // 如線性表已滿 ,則返回 OVER_FLOW, // 如 position合法 , 則返回 SUCCESS, 否則函數(shù)返回 // RANGE_ERROR { ElemType tmp。 int len = Length()。 四川大學計算機學院，主講教師：游洪躍 if (Full()) { // 線性表已滿返回 OVER_FLOW return OVER_FLOW。 } else if (position 1 || position len + 1) { // position范圍錯 return RANGE_ERROR。 } 四川大學計算機學院，主講教師：游洪躍 else { // 成功 count++。 // 插入后元素個數(shù)將自增 1 for (int curPosition = len。 curPosition = position。 curPosition) { // 插入位置之后的元素右移 GetElem(curPosition, tmp)。 SetElem(curPosition + 1, tmp)。 } SetElem(position, e)。//將 e賦值到 position位置處 return SUCCESS。 // 插入成功 } } 四川大學計算機學院，主講教師：游洪躍 表項的刪除 25 34 57 50 16 48 09 63 ?? 0 1 2 3 4 5 6 7 data 16刪除 x 25 34 57 50 48 09 63 ?? 0 1 2 3 4 5 6 7 data 四川大學計算機學院，主講教師：游洪躍 template class ElemType StatusCode SqListElemType::Delete(int position, ElemType amp。e) // 操作結果：刪除線性表的第 position個位置的元素 , 并前// 用 e返回其值 , position的的取值范圍為 // 1≤position≤Length(), position合法時函數(shù)返回 // SUCCESS,否則函數(shù)返回 RANGE_ERROR { int len = Length()。 ElemType tmp。 if (position 1 || position len) { // position范圍錯 return RANGE_ERROR。 } 四川大學計算機學院，主講教師：游洪躍 else { // position合法 GetElem(position, e)。 // 用 e返回被刪除元素的值 for (int curPosition = position + 1。 curPosition = len。 curPosition++) { // 被刪除元素之后的元素依次左移 GetElem(curPosition, tmp)。 SetElem(curPosition 1, tmp)。 } count。 // 刪除后元素個數(shù)將自減 1 return SUCCESS。 } } 四川大學計算機學院，主講教師：游洪躍 順序表的應用： 集合的“差”運算 // 文件路徑名 :s2_1\ template class ElemType void Difference(const SqListElemType amp。la, const SqListElemType amp。lb, SqListElemType amp。lc) // 操作結果 : 用 lc返回 la和 lb表示的集合的差集 // 方 法 : 在 la中取出元素 ,在 lb中進行查找 ,如果未在 lb中 // 出現(xiàn)了 ,將其插入到 lc { ElemType aItem, bItem。 ()。 // 清空 lc 四川大學計算機學院，主講教師：游洪躍 for (int aPosition = 1。 aPosition = ()。 aPosition++) { (aPosition, aItem)。 // 取出 la的一個元素 aItem bool isExist = false。 // 表示 aItem是否在 lb中出現(xiàn) for (int bPosition = 1。 bPosition = ()。 bPosition++) { (bPosition, bItem)。 // 取出 lb的一個元素 bItem 四川大學計算機學院，主講教師：游洪躍 if (aItem == bItem) { isExist = true。 // aItem同時在 la和 lb中 // 出現(xiàn) ,置 isExist為 true break。 // 退出內層循環(huán)