c語言兩個線性表la lb,假設有兩個集合A和B分别用兩個線性表LA和LB表示,即.ppt

假設有兩個集合A和B分别用兩個線性表LA和LB表示,即.ppt

循環連結清單是單連結清單的變形。 循環連結清單最後一個結點的link指針不為 0 (NULL)，而是指向了表的前端。 為簡化操作，在循環連結清單中往往加入表頭結點。 循環連結清單的特點是：隻要知道表中某一結點的位址，就可搜尋到所有其他結點的位址。 循環連結清單的示例 帶表頭結點的循環連結清單 用循環連結清單求解約瑟夫問題 約瑟夫問題的提法 n 個人圍成一個圓圈，首先第2個人從1開始一個人一個人順時針報數, 報到第m個人，令其出列。然後再從下一個人開始，從1順時針報數，報到第m個人，再令其出列，…，如此下去, 直到圓圈中隻剩一個人為止。此人即為優勝者。 例如 n = 8 m = 3 例如 n = 8 m = 3 多項式及其相加 在多項式的連結清單表示中每個結點增加了一個資料成員link，作為連結指針。 優點是： 多項式的項數可以動态地增長，不存在存儲溢出問題。 插入、删除友善，不移動元素。 雙向連結清單 (Doubly Linked List) 雙向連結清單是指在前驅和後繼方向都能遊曆(周遊)的線性連結清單。 雙向連結清單每個結點結構： 前驅方向? ?後繼方向 雙向連結清單通常采用帶表頭結點的循環連結清單形式。 結點指向p == p→lLink→rLink == p→rLink→lLink 順序表與連結清單的比較 基于空間的比較 存儲配置設定的方式 順序表的存儲空間是靜态配置設定的 連結清單的存儲空間是動态配置設定的 存儲密度 = 結點資料本身所占的存儲量/結點結構所占的存儲總量 順序表的存儲密度 = 1 連結清單的存儲密度 < 1 順序表與連結清單的比較 基于時間的比較 存取方式 順序表可以随機存取，也可以順序存取 連結清單是順序存取的 插入/删除時移動元素個數 順序表平均需要移動近一半元素 連結清單不需要移動元素，隻需要修改指針 若插入/删除僅發生在表的兩端，宜采用帶尾指針的循環連結清單 線性表小結 * 假設:有兩個集合 A 和 B 分别用兩個線性表 LA 和 LB 表示，即：線性表中的資料元素即為集合中的成員。 現要求一個新的集合A＝A∪B。 例 要求對線性表作如下操作： 擴大線性表 LA，将存在于線性表LB 中而不存在于線性表 LA 中的資料元素插入到線性表 LA 中去。 上述問題可演繹為： 1．從線性表LB中依次察看每個資料元素; 2．依值線上性表LA中進行查訪; 3．若不存在，則插入。 Get(LB, i, x) Locate(LA, x) Insert(LA, n+1, x) 操作步驟： x=Get(Lb, i); if (!Locate(La, x) ) Insert(La, ++La_len, x); void union(List &La, List Lb) { La_len = Length(La); Lb_len = Length(Lb); for (i = 1; i <= Lb_len; i++) { } } // union 靜态連結清單結構 利用數組定義，運算 過程中存儲空間大小不變 配置設定節點： j = avil; avil = A[avil].link; 釋放節點： A[i].link = avil; avil = i; 循環連結清單 (Circular List) 約瑟夫問題的解法 #include #include “CircList.h” void Josephus ( int n, int m ) { for ( int i=0; i clist; int n, m; cout << “Enter the Number of Contestants?”; cin >> n >> m; for ( int i=1; i<=n; i++ ) clist.insert (i); //形成約瑟夫環 clist.Josephus (n, m); //解決約瑟夫問題 } 多項式(polynomial)類的連結清單定義 str