2-4线性表的链式存储

2-4线性表的链式存储结构及实现v第二章线性表单链表的引入静态存储分配顺序表事先确定容量单链表动态存储分配运行时分配空间连续不连续零散分布单链表：线性表的链接存储结构存储思想：用一组任意的存储单元存放线性表单链表的存储结构单链表的实现学什么？双链表循环链表2-4-1单链表的存储结构v第二章线性表0200020803000325…………a1a2a3a4例：(a1,a2,a3,a4)的存储示意图0200

03250300∧存储特点：逻辑次序和物理次序不一定相同2.元素之间的逻辑关系用指针表示单链表的存储方法观察1：单链表由若干结点构成观察2：单链表的结点只有一个指针域datanext单链表的结点结构数据域data：存储数据元素指针域next：存储指向后继结点的地址0200020803000325…………a1a2a3a40200

03250300∧头指针：指向第一个结点的存储地址尾标志：终端结点的指针域为空firsta1a2an∧非空表first=NULL空表空表和非空表不统一，有什么缺点？first单链表的存储方法头结点：在第一个元素结点之前附设一个类型相同的结点firsta1a2an∧first∧非空表空表头结点简化了对边界的处理——插入、删除、构造等头指针：指向第一个结点的存储地址尾标志：终端结点的指针域为空单链表的存储方法structNode{data;structNode*next;}Node;template<typenameDataType>DataType单链表的结点结构定义firsta1a2an∧指针的相关问题如何引用结点p的数据域（指针域）？firsta1a2an∧p该结点用*p来表示，*p为结点变量。将“指针p所指结点”简称为“结点p”p->data*p.datap->next*p.next*p*(p->next)如何表示结点p的下一个结点？设指针p指向某个Node类型的结点2-4-2单链表的实现v第二章线性表单链表的类定义template<typenameDataType>classLinkedList{public:

LinkedList();//无参构造函数，建立只有头结点的空链表LinkedList(DataTypea[],intn);//有参构造函数，建立有n个元素的单链表~LinkedList();//析构函数intLength();//求单链表的长度DataTypeGet(inti);//按位查找。查找第i个结点的元素值intLocate(DataTypex);//按值查找。查找值为x的元素序号voidInsert(inti,DataTypex);//插入操作，第i个位置插入值为x的结点DataTypeDelete(inti);//删除操作，删除第i个结点intEmpty();//判断线性表是否为空voidPrintList();//遍历操作，按序号依次输出各元素private:Node<DataType>*first;//单链表的头指针};单链表的实现——初始化∧first初始化一个单链表要完成哪些工作呢？template<typenameDataType>LinkedList<DataType>::LinkedList(){

first=newNode<DataType>;

first->next=nullptr;}空单链表满足什么条件呢？template<typenameDataType>int

LinkedList<DataType>::Empty(

){if(first->next==nullptr)return1elsereturn0;}单链表的实现——遍历firsta1a2an∧pp核心操作：工作指针后移如何实现工作指针后移？p++能正确实现后移吗？a1a2pp++p->nextp=p->nextfirsta1a2an∧first为什么设置工作指针？通过头指针后移扫描单链表会有什么后果？first修改前：(a1,a2,…,an)first修改后：(a2,…,an)单链表头指针的作用是标识单链表的开始，通常不修改头指针first指向头结点单链表的实现——遍历firsta1a2an∧输入：无功能：遍历单链表PrintList输出：单链表的各个数据元素1.工作指针p初始化;2.重复执行下述操作，直到指针p为空：

2.1输出结点p的数据域;2.2工作指针p后移;如何描述遍历的基本过程？伪代码——梳理思路的好工具！p单链表的实现——遍历template<typenameDataType>voidLinkedList<DataType>::PrintList(){Node<DataType>*p=first->next;//工作指针p初始化while(p!=nullptr){cout<<p->data<<"\t";

p=p->next;//工作指针p后移，注意不能写作p++}cout<<endl;}firsta1a2an∧p单链表的实现——遍历单链表算法的设计模式

访问结点p进行的操作

退出循环的操作firsta1a2an∧p单链表算法的设计模式：通过工作指针的反复后移扫描链表p=first->next;//或p=first;，工作指针p初始化while(p!=nullptr)//或p->next!=nullptr，扫描单链表{}p=p->next;//工作指针后移单链表的实现——长度pintLinkedList<DataType>::Length(){

returncount;}first∧注意count的初值和返回值之间的关系Node*p=first->next;while(p!=nullptr){p=p->next;}intcount=0;count++;firsta1a2an∧pcount=1pcount=2pcount=n单链表的实现——按位查找firsta1aian∧pcount=1pcount=ipi>nDataTypeLinkedList<DataType>::Get(inti){

Node<DataType>*p=first->next;//工作指针p初始化intcount=1;//累加器count初始化

while(p!=nullptr&&count<i){p=p->next;//工作指针p后移count++;}if(p==nullptr)throw"查找位置错误";elsereturnp->data;}firsta1xan∧pppintLinkedList<DataType>::Locate(DataTypex){

Node<DataType>*p=first->next;//工作指针p初始化intcount=1;//累加器count初始化

while(p!=nullptr){if(p->data==x)returncount;//查找成功，结束函数并返回序号p=p->next;count++;}return0;//退出循环表明查找失败}单链表的实现——按值查找单链表的实现——插入pxs如何实现结点ai-1、x和ai之间逻辑关系的变化？s=newNode;s->data=x;firsta1ai-1an∧ai算法描述：s->next=p->next;p->next=s;pxsfirsta1ai-1an∧ai注意分析边界情况——表头、表尾？pxspxs∧单链表没有特殊说明，都带头结点s->next=p->next;p->next=s;单链表的实现——插入如果不带头结点，会怎么样呢？pxsfirsta1ai-1anais->next=first;first=s;xspxss->next=p->next;p->next=s;操作不一致会导致算法增加处理步骤，而且容易出错∧单链表的实现——插入算法：Insert输入：单链表的头指针first，插入位置i，待插值x输出：如果插入成功，返回新的单链表，否则返回插入失败信息1.工作指针p初始化为指向头结点；2.查找第i-1个结点并使工作指针p指向该结点；

3.若查找不成功，说明插入位置不合理，返回插入失败信息；否则，生成元素值为x的新结点s，将结点s插入到结点p之后；pxsfirsta1ai-1an∧aipxspxs∧单链表的实现——插入voidLinkedList<DataType>::Insert(inti,DataTypex){Node<DataType>*p=first,*s=nullptr;//工作指针p初始化intcount=0;while(p!=nullptr&&count<i-1)//查找第i–1个结点{p=p->next;//工作指针p后移count++;}

if(p==nullptr)throw"插入位置错误";//没有找到第i-1个结点else{

s=newNode<DataType>;s->data=x;//申请结点s，数据域为xs->next=p->next;p->next=s;//将结点s插入到结点p之后}}时间复杂度？O(n)O(1)已知指针p单链表的实现——插入单链表的实现——建立操作接口：Node*LinkedList(DataTypea[],intn)数组a3512243342头插法：插在头结点的后面first=newNode;first->next=nullptr;初始化first∧s=newNode;s->data=a[0];s->next=first->next;first->next=s;插入第一个元素结点35s∧操作接口：Node*LinkedList(DataTypea[],intn)数组a3512243342头插法：插在头结点的后面依次插入每一个结点12sfirst35∧单链表的元素顺序有什么特点？s=newNode;s->data=a[i];s->next=first->next;first->next=s;单链表的实现——建立template<typenameDataType>LinkedList<DataType>::LinkedList(DataTypea[],intn){

first=newNode<DataType>;first->next=nullptr;//初始化一个空链表for(inti=0;i<n;i++){Node<DataType>*s=nullptr;s=newNode<DataType>;

s->data=a[i];

s->next=first->next;first->next=s;//将结点s插入到头结点之后}}单链表的实现——建立操作接口：Node*LinkedList(DataTypea[],intn)数组a3512243342尾插法：插在尾结点的后面初始化firstrearfirst=newNode;rear=first;为方便在尾结点后面插入结点，设指针rear指向尾结点单链表的实现——建立操作接口：Node*LinkedList(DataTypea[],intn)尾插法：插在尾结点的后面依次插入每一个结点first

35rear

12ss=newNode;s->data=a[i];rear->next=s;rear=s;∧first

35

42srear数组a3512243342单链表的元素顺序有什么特点？单链表的实现——建立template<typenameDataType>LinkedList<DataType>::LinkedList(DataTypea[],intn){first=newNode<DataType>;//生成头结点Node<DataType>*r=first,*s=nullptr;//尾指针初始化for(inti=0;i<n;i++){s=newNode<DataType>;

s->data=a[i];

r->next=s;r=s;//将结点s插入到终端结点之后}

r->next=nullptr;//单链表建立完毕，将终端结点的指针域置空}单链表的实现——建立循环不变式外提！p如何实现结点ai-1、ai和ai+1

之间逻辑关系的变化？firsta1ai-1an∧aiai+1qq=p->next;x=q->data;p->next=q->next;deleteq;pq注意分析边界情况——删除表头和表尾！

pq表尾的特殊情况：虽然被删结点不存在，但其前驱结点却存在！算法描述：单链表的实现——删除pfirsta1ai-1an∧aiai+1qpqpq算法：Delete输入：单链表的头指针first，删除的位置i输出：如果删除成功，返回被删除的元素值，否则返回删除失败信息1.工作指针p初始化；累加器count初始化；2.查找第i-1个结点并使工作指针p指向该结点；3.若p不存在或p的后继结点不存在，则出现删除位置错误，删除失败；否则，3.1存储被删结点和被删元素值；3.2摘链，将结点p的后继结点从链表上摘下；3.3释放被删结点；单链表的实现——删除DataTypeLinkedList<DataType>::Delete(inti){DataTypex;intcount=0;Node<DataType>*p=first,*q=nullptr;//工作指针p指向头结点while(p!=nullptr&&count<i-1)//查找第i-1个结点{p=p->next;count++;}if(p==nullptr||p->next==nullptr)throw"删除位置错误";else{q=p->next;x=q->data;//暂存被删结点p->next=q->next;//摘链deleteq;returnx;}}单链表的实现——删除将p!=nullptr修改为p->next!=nullptr是否可以？template<typenameDataType>LinkedList<DataType>::~LinkedList(){Node<DataType>*p=first;while(first!=nullptr)//释放单链表的每一个结点的存储空间{

first=first->next;//first指向被释放结点的下一个结点deletep;p=first;//工作指针p后移}}单链表的实现——析构函数单链表需要释放哪些存储空间？为什么？2-4-3双链表v第二章线性表双链表的引入firsta1ai-1an∧aiai+1p从头结点出发，如何求得结点p的直接前驱？如何快速求得结点p的前驱？a2a3first

a1a4∧∧双链表：单链表的每个结点再设置一个指向其前驱结点的指针域双链表的存储结构定义a2a3first

a1a4∧∧priordatanext启示？时空权衡——空间换取时间数据表示template<typename

DataType>sructDLNode{

DataTypedata;DLNode<DataType>*prior,*next;};双链表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;aiai+1pxs注意指针修改的相对顺序s=newDulNode;ai-1aipxss->prior=p->prior;s->next=p;p->prior=s;p->prior->next=s;s=newDulNode;双链表的操作更加灵活ai-1pai+1ai(p-