数据结构第2章线性表.ppt

* 在单链表的表尾插入新的结点 // 在链表linkList的末尾插入新的元素e templateclass ElemType bool LinkListElemType::Append(const ElemType e) { LinkNodeElemType *q; q = new LinkNodeElemType ; q-data = e; tail-next = q; // 尾部插入q结点 tail = q; tail-next = NULL; ++len; // 表长增1 return true; } //时间复杂度O(1) 2.3.1 单链表 在单链表中删除第i个结点 有序对 ai-1, ai, ai, ai+1 变为 ai-1, ai+1 分三步实施：先找到第i-1个结点；再修改它的后继指针，删除结点；最后释放空间 。 2.3.1 单链表 在单链表中删除第i个结点 // 在单链表中删除第i个数据元素并用数据变量e返回其值（i的合法值为1≤i≤Len） templateclass ElemType bool LinkListElemType::IndexDelete(ElemType e,int i) { if (i1 || ilen) return false; // 删除位置i值不合法 LinkNodeElemType *p,*q; int k = 1; 查找第i-1个结点； q=p-next; p-next=q-next; // 删除q结点 if (q == tail) tail = p; e=q-data; delete q; //释放空间 --len; // 表长减1 return true; //时间复杂度为O(n) } 2.3.1 单链表 查找第i-1个结点 p = head ; while (k i) { // 将p指针定位在第i-1个结点上 p = p-next; k++; } 2.3.1 单链表 删除结点的基本操作 ? q = p-next; ? p-next = q-next; ? e = q-data; delete q; ? ai-1 ai ai-1 p q ? ? 2.3.1 单链表 单链表的遍历 // 依序对单链表中的每个数据元素调用函数visit()一次且仅一次 templateclass ElemType void LinkListElemType ::Traverse(void(*visit)(const ElemType e)) const { LinkNodeElemType *p = head-next; while (p) { visit(p-data); p = p-next; } } 2.3.1 单链表 赋值运算符=的重载 // 重载=运算符 templateclass ElemType LinkListElemType LinkListElemType::operator=(const LinkListElemType r) { Clear(); CopyFrom(r); return *this; } 2.3.1 单链表 拷贝函数 // 从现有的一个链表中复制所有的结点 template class ElemType void LinkListElemType::CopyFrom(const LinkListElemType r) { len = 0; head = tail = new LinkNodeElemType; head-next = NULL; LinkNodeElemType *p = r.head-next; while (p){ Append(p-data); p = p-next; } } 2.3.1 单链表 单链表的特点 它是一种动态结构，不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢 插入删除结点，只需移动指针，操作方便 理论上不存在溢出问题 2.3.2其它形式的链表 循环单链表 循环链表是表中最后一个结