线性表类型的实现链式映像教学PPT.pptx

用一组地址任意的存储单元存放线性表中的数据元素。,一、单链表,这样：就以“结点的序列”来表示线性表 称作链表,0200,0250,0300,数据元素,下一个地址,2.3 线性表类型的实现链式映象,尾标志,一、单链表,抽象得知： 元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点(表示数据元素及其映象),以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时， 头结点的指针域为空,template /模版实现 struct node t data; / 数据域 node *next; / 指针域 ;,二、结点的 c+ 语言描述,2.2 线性表类型的实现顺序映象,二、结点的 c+ 语言描述,2.2 线性表类型的实现顺序映象,p,p为指针变量，简称指针； pdata（*p.data）， 值为数据元素； pnext （*p.next） ， 值为一个指针.,三、单链表的 c+ 语言描述,2.2 线性表类型的实现顺序映象,四、单链表操作的实现按位查找,t get(int i) / 取第i个数据元素,j,1,2,3,在单链表中的实现: i=,基本操作为： 移动指针， 比较 j 和 i,3,四、单链表操作的实现按位查找,t get(int i) / 取第i个数据元素,算法分析,算法时间复杂度为:,o(n),算法实现,template t linklist : get(int i) p=firstnext; j=1; while(p ,四、单链表操作的实现插入,void insert(int i，t x) / 在i位置插入x,在单链表中的实现:,基本操作: 查找线性表中第i-1个结点，再修改其后继指针,四、单链表操作的实现插入,void insert(int i，t x) / 在i位置插入x,算法分析,算法实现,template void linklist : insert(int i,t x) p=first; j=0;/初始化 while(p /赋值 pnext=s ,算法时间复杂度为:,o(n),有序对 和 改变为 ,四、单链表操作的实现删除,t delete(int i) / 删除i位置的元素,基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,p,q,基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。 具体操作：,q = p-next; p-next = q-next; e = q-data; /暂存被删掉结点 delete(q);,四、单链表操作的实现删除,算法分析,t delete(int i) / 删除i位置的元素,时间复杂度:,o(n),template t linklist:delete(int i) p=first; j=0;/p指针初始化 while(p ,算法实现,如何建有n个元素的单链表？,链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。,四、单链表操作的实现建表,linklist(t a, int n);/建立有n个元素的单链表,linklist（）/建立只有头节点的空链表 first=new node(t);firstnext=null,例如：在尾部插入元素，建立带头结点的单链表。,操作步骤：,1）建立一个“空表”；,2）输入数据元素a1， 建立结点并插入；,3）输入数据元素a2， 并在a1后面插入；,a1,4）依次类推，直至输入an为止。,a1,a2,template linklist:linklist(t a, int a) ,算法的时间复杂度为:,o(n),first=new node; node *last, *s; firstnext = null; / 先建立一个带头结点的单链表 last=first;,for (i = 0; i n; i+) s=new node; sdata=ai / 建立结点 lastnext =s; last= s;/ 插入 lastnext=null;,例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。,操作步骤：,1）建立一个“空表”；,2）输入数据元素an， 建立结点并插入；,3）输入数据元素an-1， 建立结点并插入；,an,an,an-1,4）依次类推，直至输入a1为止。,template linklist:linklist(t a, int a) ,算法的时间复杂度为:,o(n),first=new node; firstnext = null; / 先建立一个带头结点的单链表,for (i = 0; i n; i+) s=new node; sdata=an-i; / 建立结点 snext =firstnext ; firstnext = s;/ 插入 ,最后一个结点的指针域的指针又指回第一个结点的链表,a1 a2 . an,1. 循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,四、其它形式的链表,2. 双向链表,四、其它形式的链表,template struct dulnode t data; / 数据域 dulnode *prior; /指向前驱的指针 dulnode *next;/指向后继的指针 ;,便于找到前驱结点,双向循环链表,空表,非空表,a1 a2 . an,双向链表的操作特点：,“查询” 和单链表相同。,“插入” 和“删除”时需要同时修改两个方向上的指针。,s-next = p-next; p-next = s; s-next-prior = s; s-prior = p;,p,s,双向链表插入,双向链表删除,p-next = p-next-next; p-next-prior = p;,p,双向链表删除,p-prior -next = p-next; p-next-prior = p-prior ;,p,在计算机中，可以用一个线性表来表示: p = (p0, p1, ，pn),一元多项式,但是对于形如 s(x) = 1 + 3x10000 2x20000 的多项式，上述表示方法是否合适？,2.3 线性表类型的应用 一元多项式相加,2.3 线性表类型的应用,一般情况下，一元稀疏多项式可写成 pn(x) = p1xe1 + p2xe2 + + pmxem 其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n,可用如下线性表表示： （p1, e1), (p2, e2), , (pm,em) ）,如：p999(x) = 7x3 - 2x12 - 8x999,用线性表可表示为： ( (7, 3), (-2, 12), (-8, 999) ) 其单链表存储结构？如何实现多项式的加法运算？,2.3 线性表类型的应用,结点结构：,conf ：系数域，存放非零项的系数； exp：指数域，存放非零项的指数； next: 指针域，存放指向下一结点的指针。,算法思路： 两个多项式求和实质是比较两个单链表的工作指针的指数域是否相等。,2.3 线性表类型的应用,a = 7+12x3 + (-2)x8 + 5x12,b = 4x+6x3 + 2x8 + 5x20+ 7x28,a=a+b =7+ 4x+18x3 + 5x12 + 5x20+ 7x28,a,b,a,2.3 线性表类型的应用,伪代码： 1. 工作指针p,q初始化；/两个单链表的指针。 2. while(p存在且q存在)执行下列三种情况： 1)当pexpqexp,则在p之前插入q结点，并使q指向原结点的下一个结点； 3)当pexp=qexp,则 pcoef= pcoef +qcoef ； (1) pcoef=0,删除结点p，并指向下一结点。 (2)删除结点q，q指向下一结点。 3. 如果q不为空，将结点q链到第一个表后面。,2.3 线性表类型的应用,作业：补充一元多项式相加的程序代码。 void add(linklist a, linklist b) pre=a.first; p=prenext;/前驱为pre qre=b.first; q=qrenext;/ 前驱为qre while(p &q) ,while(p /释放第二个单链表的头结点所占的内存。 ,本章小结,1.了解线性表的逻辑结构特性；了解两类不同的存储结构：顺序存储结构和链式存储结构。掌握顺序表和链表联系。,2.熟练掌握两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,线性表逻辑结构特点是，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的。,问1：线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？,答：,顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。,链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。,巩固练习,顺序存储的优点是存储密度大，存储空间利用率高。缺点是插入或删除元素时不方便。 链式存储的优点是插入或删