南邮《数据结构A》——.pptVIP

数据结构 第2章 线性表 2.3 线性表的链接表示 2.3.1 单链表 链接存储表示 单链表的结点结构 单链表结构 2.3.2 带表头结点的单链表 2.3.3 单循环链表 2.3.4 双向链表 Data Structures in C++ 内容提要 定义线性表抽象数据类型； 讨论线性表的顺序存储表示方法； 讨论单链表、循环链表等链接存储表示方法； 线性表的应用实例——多项式的算术运算 2.3.1 单链表 2.3.2 带表头结点的单链表 2.3.3 单循环链表 2.3.4 双向链表 element link a0 a1 a2 an-1 … first ∧ 非空单链表 first ? 空单链表 ? = NULL 指针变量的存储单元 红色为结点的指针域 注意事项 头指针first是指向单链表的头结点的指针 最后一个结点的指针域为?，地址值为0 逻辑上相邻的元素在物理上不一定相邻 不能出现“断链”现象 结点类 #include linearlist.h template class T class SingleList；//超前声明 template class T class Node { private: T element; NodeT *link; friend class SingleListT; }; //指针和动态存储分配 element link 单链表类 template class T class SingleList:public LinearListT { public: SingleList(){ first=NULL; n=0; } ~SingleList(); bool Find(int i,T x) const; int Search(T x) const; bool Insert(int i,T x); bool Delete(int i); …… ……. private: NodeT* first; }; 顺序表类SeqList、单链表类SingleList是抽象线性表类LinearList类的派生类。 SingleList LinearList SeqList Node friend 构造函数 SingleList(){ first=NULL; n=0; } 析构函数 template class T SingleListT:: ~SingleList() { NodeT *p; while (first){ p=first-link; delete first; first=p; } } 有哪些信誉好的足球投注网站运算 必须从头指针开始沿链逐个计数查找，称为顺序查找 有哪些信誉好的足球投注网站运算的平均、最坏的渐近时间复杂度：O(n) templateclass T bool SingleListT::Find(int i,T x)const { //在(a0,a1,...,an?1)中找下标为i的元素ai if (i0 || in?1){ //对i进行越界检查 cout Out Of Bounds; return false; } NodeT *p=first; for (int j=0; ji; j++) p=p-link; x=p-element; return true; } 插入运算 修改两个指针域的值插入渐近时间复杂度：O(1) q-link=p-link; p-link=q； 能否交换上面两个语句的次序？ 插入运算步骤： 生成数据域为x的新结点，q指向新结点; 从first开始找第i+1个结点，p指向该结点； 将q插入p之后。 表长加1。 templateclass T bool SingleListT::Insert(int i,T x) { if (i?1 || in?1){ cout Out Of Bounds; return false; } NodeT * q=new NodeT;q-element=x; NodeT *p=first; // 找ai元素所在的结点p for (int j=0; ji; j++) p=p-link; first a0 a1 a2 an-1 … ∧ 非空单链表 first ? 空单