数据结构第三周.pptVIP

单链表 (Singly Linked List) 特点 每个元素(表项)由结点(Node)构成， 结点由 两部分组； 线性结构 结点可以不连续存储 表可扩充 单链表中的插入与删除 插入 第一种情况：在第一个结点前插入 newNode→Next = first ; first = newNode； 第二种情况：在链表中间插入 newNode→Next = p→Next; p→Next = newNode； 第三种情况：在链表末尾插入 newNode→Next = p→Next; p→Next = last = newNode； 删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素 带表头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。 void TraverseList( LNode * H) { LNode * p = H ?next; while( p != NULL) { cout p ?data‘ ‘; p = p ?next; } } void InitList( LNode * H) { H = new LNode; if(H==NULL) { cout“ 分配失败！”; exit(1); } H ?next = NULL; } 单链表的类模板 类模板将类的数据成员和成员函数设计得更完整、更灵活。 类模板更易于复用。 在单链表的类模板定义中，增加了表头结点。 链表的游标类 (Iterator) 游标类主要用于单链表的有哪些信誉好的足球投注网站。 游标类的定义原则： Iterator类是List类和ListNode类的友元类。 Iterator对象引用已有的List类对象。 Iterator类有一数据成员current，记录对单链表最近处理到哪一个结点。 Iterator类提供若干测试和有哪些信誉好的足球投注网站操作 循环链表 (Circular List) 循环链表是单链表的变形。 循环链表最后一个结点的 Next 指针不 为 0 (NULL)，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。 循环链表的示例 带表头结点的循环链表 循环链表类的定义 用循环链表求解约瑟夫问题 约瑟夫问题的提法 n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数, 报到第 m 个人，令其出列。然后再从下一 个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。 例如 n = 8 m = 3 多项式及其相加 在多项式的链表表示中每个结点增加了一个数据成员Next，作为链接指针。 优点是： 多项式的项数可以动态地增长，不存在存储溢出问题。 插入、删除方便，不移动元素。 双向链表 (Doubly Linked List) 双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点结构： 前驱方向 ? ? 后继方向 双向链表通常采用带表头结点的循环链表形式。 结点指向p == p→lLink→rLink == p→rLink→lLink  稀疏矩阵 在矩阵操作(+、-、*、/)时矩阵非零元素会发生动态变化，用稀疏矩阵的链接表示可适应这种情况。 稀疏矩阵的链接表示采用正交链表：行链表与列链表十字交叉。 行链表与列链表都是带表头结点的循环链表。用表头结点表征是第几行，第几列。 稀疏矩阵的结点 稀疏矩阵的删除 为执行稀疏矩阵的删除，需要使用可利用空间表来管理回收的空间。 可利用空间表是单链表结构，只允许在表头插入或删除，其表头指针为av。 使用可利用空间表，可以高效地回收循环链表。 如果需要建立新的稀疏矩阵，还可以从可利用空间表中分配结点。 小结 需要复习的知识点 单链表 单链表的结构和类定义； 单链表中的插入与删除； 带表头结点的单链表； 用模板定义的单链表类； 静态链表 单链表的递归算法 有哪些信誉好的足球投注网站含 x 结点 删除含 x 结点 统计单链表中结点个数 循