【文章內(nèi)容簡介】 } } if (!isExist) { // aItem在 la中出現(xiàn) ,而未在 lb中未出現(xiàn) , // 將其插入到 lc中 (() + 1, aItem)。 } } } 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 ? 特點 – 每個元素 (表項 )由結(jié)點 (Node)構(gòu)成。 – 線性結(jié)構(gòu) – 結(jié)點可以不連續(xù)存儲 – 表可擴(kuò)充 單鏈表 (Singly Linked List) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 單鏈表的類模板 ? 類模板將類的數(shù)據(jù)成員和成員函數(shù)設(shè)計得更完整、更靈活。 ? 類模板更易于復(fù)用。 ? 在單鏈表的類模板定義中，增加了表頭結(jié)點。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 // 結(jié)點類 template class ElemType struct Node { // 數(shù)據(jù)成員 : ElemType data。 // 數(shù)據(jù)域 NodeElemType *next。 // 指針域 // 構(gòu)造函數(shù) : Node()。 // 無參數(shù)的構(gòu)造函數(shù) Node(ElemType item, NodeElemType *link = NULL)。// 已知數(shù)數(shù)據(jù)域和指針域建立結(jié)構(gòu) }。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 // 簡單線性鏈表類 template class ElemType class SimpleLinkList { protected: // 鏈表實現(xiàn)的數(shù)據(jù)成員 : NodeElemType *head。 // 頭結(jié)點指針 // 輔助函數(shù) NodeElemType *GetElemPtr(int position) const。 // 返回指向第 position個結(jié)點的指針 void Init()。 // 初始化線性表 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 public: // 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明 : SimpleLinkList()。 // 無參數(shù)構(gòu)造函數(shù) virtual ~SimpleLinkList()。 // 析構(gòu)函數(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)。 // 設(shè)置指定位置的元素值 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 StatusCode Delete(int position, ElemType amp。e)。 // 刪除元素 StatusCode Insert(int position, const ElemType amp。e)。 // 插入元素 SimpleLinkList(const SimpleLinkListElemType amp。copy)。 // 復(fù)制構(gòu)造函數(shù) SimpleLinkListElemType amp。operator =(const SimpleLinkListElemType amp。copy)。 // 賦值語句重載 }。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 單鏈表中的插入與刪除 ? 插入 newPtr = new NodeElemType(e, tmpPtrnext)。 tmpPtrnext = newPtr。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 template class ElemType StatusCode SimpleLinkListElemType::Insert( int position, const ElemType amp。e) // 操作結(jié)果：在線性表的第 position個位置前插入元素 e // position的取值范圍為 1≤position≤Length()+1 // position合法時返回 SUCCESS, 否則函數(shù)返回 // RANGE_ERROR { if (position 1 || position Length() + 1) { // position范圍錯 return RANGE_ERROR。 // 位置不合法 } 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 else { // position合法 NodeElemType *tmpPtr。 tmpPtr = GetElemPtr(position 1)。 // 取出指向第 position1個結(jié)點的指針 NodeElemType *newPtr。 newPtr = new NodeElemType(e, tmpPtrnext)。 // 生成新結(jié)點 tmpPtrnext = newPtr。 // 將 tmpPtr插入到鏈表中 return SUCCESS。 } } 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 ? 刪除 在單鏈表中刪除含 b的結(jié)點 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 template class ElemType StatusCode SimpleLinkListElemType::Delete(int position, ElemType amp。e) // 操作結(jié)果：刪除線性表的第 position個位置的元素 , 并用 // e返回其值 , position的取值范圍為 // 1≤position≤Length(), position合法時函數(shù)返回 // SUCCESS,否則函數(shù)返回 RANGE_ERROR { if (position 1 || position Length()) { // position范圍錯 return RANGE_ERROR。 } 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 else { // position合法 NodeElemType *tmpPtr。 tmpPtr = GetElemPtr(position 1)。 // 取出指向第 position1個結(jié)點的指針 NodeElemType *nextPtr = tmpPtrnext。 // nextPtr為 tmpPtr的后繼 tmpPtrnext = nextPtrnext。// 刪除結(jié)點 e = nextPtrdata。// 用 e返回被刪結(jié)點元素值 delete nextPtr。 // 釋放被刪結(jié)點 return SUCCESS。 } } 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 循環(huán)鏈表 (Circular List) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 ? 循環(huán)鏈表是單鏈表的變形。 ? 循環(huán)鏈表最后一個結(jié)點的 next指針不為 0 (NULL)，而是指向了表的前端。 ? 為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點。 ? 循環(huán)鏈表的特點是：只要知道表中某一結(jié)點的地址，就可搜尋到所有其他結(jié)點的地址。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 循環(huán)鏈表示例 a1an…h(huán) e a dh e a d( a ) 非 空 循 環(huán) 鏈 表 ( b ) 空 循 環(huán) 鏈 表四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 // 簡單循環(huán)鏈表類 template class ElemType class SimpleCircLinkList { protected: // 循環(huán)鏈表實現(xiàn)的數(shù)據(jù)成員 : NodeElemType *head。 // 頭結(jié)點指針 // 輔助函數(shù) NodeElemType *GetElemPtr(int position) const。 // 返回指向第 position個結(jié)點的指針 void Init()。 // 初始化線性表 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 public: // 抽象數(shù)據(jù)類型方法聲明及重載編譯系統(tǒng)默認(rèn)方法聲明 : SimpleCircLinkList()。 // 無參數(shù)的構(gòu)造函數(shù) virtual ~SimpleCircLinkList()。 // 析構(gòu)函數(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)。 // 設(shè)置指定位置的元素值 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 StatusCode Delete(int position, ElemType amp。e)。 // 刪除元素 StatusCode Insert(int position, const ElemType amp。e)。 // 插入元素 SimpleCircLinkList(const SimpleCircLinkListElemType amp。copy)。 // 復(fù)制構(gòu)造函數(shù) SimpleCircLinkListElemType amp。operator =(const SimpleCircLinkListElemType amp。copy)。 // 賦值語句重載 }。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 用循環(huán)鏈表求解約瑟夫問題 ? 約瑟夫問題的提法 ? n 個人圍成一個圓圈，首先第 1個人從 1開始一個人一個人順時針報數(shù) , 報到第 m個人，令其出列。然后再從下一個人開始，從1順時針報數(shù)，報到第 m個人，再令其出列， … ，如此下去 , 直到圓圈中只剩一個人為止。此人即為優(yōu)勝者。 ? 例如 n = 8 m = 3 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 // 文件路徑名 :s2_5\ void Josephus(int n, int m) // 操作結(jié)果 :n個人圍成一個圓圈，首先第 1個人從 1開始一 // 個人一個人順時針報數(shù) ,報到第 m個人，令其出列。 // 然后再從下一個人開始，從 1順時針報數(shù)報到第 m // 個人，再令其出列， … ，如此下去 , 直到圓圈中只 // 剩一個人為止。此人即為優(yōu)勝者 { SimpleCircLinkListint la。 // 定義空循環(huán)鏈表 int position = 0。 // 報數(shù)到的人在鏈表中序號 int out, winer。 for (int k = 1。 k = n。 k++) (k, k)。 // 建立數(shù)據(jù)域為 1,2,..,n的循環(huán)鏈表 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 cout 出列者 :。 for (int i = 1。 i n。 i++) { // 循環(huán) n1次，讓 n1個個出列 for (int j = 1。 j = m。 j++) { // 從 1報數(shù)到 m position++。 if (position ()) position = 1。 } (position, out)。// 報數(shù)到 m的人出列 cout out 。 } (1, winer)。 // 剩下的一個人為優(yōu)勝者 cout endl 優(yōu)勝者 : winer endl。 } 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 雙向鏈表 (Doubly Linked List) ? 雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷 )的線性鏈表。 ? 雙向鏈表每個結(jié)點結(jié)構(gòu)： ? 前驅(qū)方向 ? ?后繼方向 ? 雙向鏈表通常采用帶表頭結(jié)點的循環(huán)鏈表形式。 bb aa cc kk ((