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