数据结构1.ppt

第一章 绪 论,计算机是一门研究利用计算机进行信息表示和处理的科学。涉及：信息的表示 信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,1.1 什么是数据结构 众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。什么是数据结构呢？例子：例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)(an，bn)其中(ai，bi)(i=1，2n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。,数据结构含义：就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。,数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。,数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。,数据在计算机中的表示称为数据的物理结构，又称为存储结构。,数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,数据类型：一组值的集合和定义在该值集上的一组操作。整型数据类型：值的集合N2,1,0,1,2一组操作：、x、/、%等数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是-3，-2，-1，0，1，2，3，英文字符类型的数据对象是A，B，C，D，E，F，,1.4 算法和算法分析算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。（3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,1.4.2 算法设计的要求评价一个好的算法有以下几个标准:(1)正确性:算法应满足具体问题的需求。(2)可读性:算法应该好读。以有利于阅读者对程序的理解。(3)健状性:算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。,1.4.3 算法效率的度量 对一个算法要作出全面的分析可分成两种方法：事先分析 求出该算法的一个时间界限函数事后测试 收集此算法的执行时间和实际占用空间的统计资料。,定义：如果f(n)是正整数n的一个函数，若存在两个正常数c和n0，对于所有的nn0，有f(n)cg(n)|，则记作 f(n)=O(g(n)例：f(x)=anxn+an-1xn-1+.+a1x+a0，其中an不等0，n为正整数，则f(x)=O(xn)证明：|f(x)|=|anxn+an-1xn-1+.+a1x+a0|anxn|+|an-1xn-1|+|a1x|+|a0|=|an|*|xn|+|an-1|*|xn-1|+|a1|*|x1|+|a0|*|x0|,当x1=n0，n为正整数时，xn+1xn，所以：,|an|*|xn|+|an-1|*|xn-1|+|a1|*|x1|+|a0|*|x0|an|*|xn|+|an-1|*|xn|+|a1|*|xn|+|a0|*|xn|,=(|an|+|an-1|+|a1|+|a0|)|xn|=c|xn|其中：n0=1,c=|an|+|an-1|+|a1|+|a0|,g(n)=xn,例、for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;,一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度。(最坏，期望）,由于是一个三重循环，每个循环从1到n，则总次数为:nnn=n3，时间复杂度为T(n)=O(n3),频度：是指该语句重复执行的次数例+x;s=0;将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为(1)，即常量阶。例 for(i=1;i=n;+i)+x;s+=x;语句频度为：n其时间复杂度为：O(n)即时间复杂度为线性阶。,i=0:赋值次,i=1:赋值 2 次,i=2:赋值3次,i=n-1:赋值n次,.,1+2+3+n=(1+n)n/2=n2/2+n/2,例 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：n2其时间复杂度为：O(n2)即时间复杂度为平方阶。例 for(i=0;i=n-1;+i)for(j=0;j=i;+j)aij=0;,一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。,以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。,最坏时间复杂性,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而 不同。例如：void bubble-sort(int a，int n)for(i=n-1;i0;i-)for(j=0;jaj+1)aj aj+1;最好情况：0次 最坏情况：每次都换，(n2),例：递归程序的分析int fact(int n)if(n=1)return 1;else return n*fact(n-1);,f(n)=c+f(n-1)=c+(c+f(n-2)=2c+f(n-2)=(n-1)c+f(1)=(n-1)c+c0,注意：时间与空间往往是对矛盾，要综合考虑。,1.4.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n)其中n为问题的规模(或大小),作业：.计算时间复杂度 sum=1;for(i=0;sumn;i+)sum+=i;2.设给定若干n值，比较两函数n2和50nlog2n的增长趋势，并确定在什么范围内，函数n2的值大于50nlog2n的值。,第二章 线性表,2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,2.1 线性表的逻辑结构 线性表：由n(n0)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：(a1，a2，an)这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）,.,.,.,.,.,神经衰弱,17,男,790634,张立立,健康,21,男,790633,刘建平,一般,20,女,790632,陈 红,健康,18,男,790631,王小林,健康情况,年龄,性 别,学 号,姓 名,例3、学生健康情况登记表如下：,从以上例子可看出线性表的逻辑特征是：(1)对非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；(2)有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；(3)其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,2.2 线性表的顺序存储结构2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置作为参考点。则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系：Loc(ai+1)=Loc(ai)+m,线性表的第i个数据元素ai的存储位置为:,Loc(a1),i-1个元素,Loc(ai)=(i-1)*m+Loc(a1),=Loc(a1)-m+i*m,由于Loc(a1)和m都是已知的所以：V0=Loc(a1)-mLoc(ai)=V0+i*m,由于在高级语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，利用C+语言的结构类型来定义顺序表类型。#define ListSize 100/表容量 typedef int DataType;/以int为例 struct Sqlist DataType dataListSize;int lenth;/当前表中元素数;或 struct Sqlist DataType*elem;int listsize;int length/当前表中元素数,Sqlist,data,2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C/C+语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素位置是L.datai-1。线性表的插入和删除两种运算。1、插入 线性表的插入运算是指在表的i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表(a1，a i-1，ai，an)变成长度为n+1的线性表(a1，a i-1，x，ai，an),void InsertList(L,x,i)/在线性表L中第i个位置插入元素x if(iL.length+1)cout=ListSize)溢出处理；else for(j=L.length-1;j=i-1;j-)/第i个元素（下标为i-1)开始 L.dataj+1=L.dataj;/顺序后移 L.datai-1=x;L.length+;,算法分析 设表的长度为n。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此，所需移动结点的次数依赖于(1)表的长度(2)插入位置。当=n+1时，不移动-最好情况；当=1时，需移动表中所有结点-最坏情况，,a1，a i-1，ai，an,算法的平均移动 由于插入可能在表中任何位置上进行，在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。Pi代表在第i个位置插入概率，则 Eis(n)=p1*n+p2*(n-1)+.+pn*1+pn+1*0 若表中任何位置(1in+1)上插入结点的概率是均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下：Eis(n)=1/(n+1)n+(n-1)+1+0=n/2,a1，a i-1，ai，an,结论：在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。2、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表：(a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表(a1，a i-1，a i+1，an),void deleteList(L,i)/表L中删除第i个元素 if(iL.length)cout“删除序号错”endl;return ERROR;for(j=i;j=L.length-1;j+)L.dataj-1=L.dataj;L.length-;,算法分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若i=n，无需移动结点；若i=1，则前移元素n-1个 令Edl表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，pi是删除i个元素的概率，则 Edl=p1*(n-1)+p2(n-2)+.+pn-1*1+pn*0等概率的假设下：p1=p2=p3=pn=1/n Edl=1/n(n-1)+(n-2)+1+0=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。,表溢出问题的说明：,2.3 线性表的链式表示和实现,2.3.1 线性链表 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：,其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于最后一个结点无后继，故结点的指针域为空，即NULL（图示中常用表示)。,例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat),示意图如下：,head:,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。,例如：若头指针名是head，则把链表称为表head。,用C+语言描述的单链表如下：,Typedef char DataType;,struct LNode DataType data;LNode*next;,一旦p所指的结点变量不再需要了，应该通过 delete p；释放所指的结点变量空间。,LNode*p,*head;p为动态变量指针，它可以存放Lnode内存块的首地址，能利用标准函数使得p于一块内存空间关联，即 p=new LNode;/C+p=(struct LNode*)malloc(sizeof(struct LNode);/*C*/new分配了一个类型为LNode的结点变量的空间并将其首地址放入指针变量p中。,一、建立单链表 问题：假设线性表中结点的数据类型是字符，逐个输入这些字符型的数据，并以换行符$为输入结束标记。动态地建立单链表的常用方法有如下两种：1、头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志(比如$）为止。,void CreateList1(LNode*,LNode*CreateList()char ch;LNode*h,*p;h=NULL;cinch;while(ch!=$)p=new LNode;pdata=ch;pnext=h;h=p;cin ch;return h;,#include typedef struct LNode char data;LNode*next;LNode*CreateList()char ch;LNode*h,*p;h=NULL;cinch;while(ch!=$)p=new LNode;pdata=ch;pnext=h;h=p;cin ch;return h;void CreateList1(LNode*,cinch;while(ch!=$)p=new LNode;pdata=ch;pnext=h;h=p;cin ch;void print(LNode*h)LNode*p=h;while(p!=NULL)coutdatanext;coutendl;void main()LNode*h1,*h2;h1=CreateList();CreateList1(h2);print(h1);print(h2);,类表示,#include class List；class LNode char data；LNode*next；friend class List；class ListLNode*head；public:List()head=NULL；void CreateList()；void CreateList1(List while(ch!=$)p=new Lnode；p-data=ch；p-next=head；head=p；cin ch；,void List:CreateList1(List&h)char ch；LNode*p；cinch；while(ch!=$)p=new Lnode；p-data=ch；p-next=head；h.head=p；cin ch；void List:print()LNode*p=head；while(p!=NULL)coutdatanext；coutendl；void main()List h1,h2；h1.CreateList()；h1.print()；h2.CreateList1(h2)；h2.print()；,2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上。为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：,LNode*creat()char ch;LNode*p,*r,*head;head=r=NULL;cinch;while(ch!=$)p=new LNode;pdata=ch;if(head=NULL)head=p;,else r-next=p;r=p;cinch;if(r!=NULL)r-next=NULL;return head;,头结点（哨兵结点）引入：增加一个表头结点，数据域可根据需要使用或不用。,特点：a、表中第一个结点和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点。因此空表和非空表的处理统一。,head,有头结点的空表,LNode*creat()LNode*r,*h;char ch;h=new LNode;r=h;cinch;,while(ch!=$)r-next=new LNode;r=r-next;r-data=ch;cinch;r-next=NULL;,上述算法里动态申请新结点空间时未加错误处理，在实际使用时间，可作下列判定与处理：p=new LNode;if(p=NULL)错误处理；,二、查找运算 1、按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1=i=n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0个结点，其算法如下：,LNode*getnode(head，i)/在链表head中取第i个数据链表有头结点 p=head;j=0;/计数用 while(pnext,struct LNode DataType data;LNode*next;,2、按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：,LNode*locatenode(head，key)LNode*p;p=headnext;while(p,该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找。,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,p-next=q;,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,p-next=q;,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,p-next=q;,定位ai-1并将指针p指向它；,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q=new LNode;q-data=x;q-next=p-next;p-next=q;,定位ai-1并将指针p指向它；,三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q=new LNode;q-data=x;q-next=p-next;p-next=q;,p=getnode(head，i-1);,三、插入运算,void insertnode(head，x，i)LNode*p，*q;p=getnode(head，i-1);if(p=NULL)coutdata=x;qnext=pnext;pnext=q;,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,问题：链表的逻辑结构已正确了，但结点ai空间丢了。,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,r=p-next;p-next=r-next;delete r;,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,r=p-next;p-next=r-next;delete r;,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,r=p-next;p-next=r-next;delete r;,四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,p=getnode(head，i-1);r=p-next;p-next=r-next;delete r;,四、删除运算,void deletelist(head，i)LNode*p，*r;p=getnode(head，i-1);if(p=NULL|pnext=NULL)return ERROR;r=pnext;pnext=rnext;delete r;,从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。,作业：（1）链表是有序的，现在插入数据x，要求插入后仍然有序（2）链表是有序的，现在删除数据x，若x不存在，输出一段提示信息。要求：按链表有头结点和无头结点两种情况分别写出。,五、静态链,1、静态链表的概念 用一维数组来实现线性链表，这种用一维数组表示的线性链表，称为静态链表。静态：体现在表的容量是一定的。（数组的大小）链表：插入与删除同前面所述的动态链表方法相同2、静态链表的类型定义,#define MAXSIZE 1000/链表的最大长度struct Component ElemType data;int cur;Component VListMAXSIZE;,SLinkList类型的数组变量是结构数组，每一数组分量包括两个域：data：用于存储线性表元素；cur：用于存储直接后继元素在数组中的位置,静态链表图示,0,h=5,数组下标,线性链表图示,地址,1,2,3,4,5,6,7,8,9,10,h=1020,例：静态链表的操作 设插入和删除只在表的头上进行（栈）,h=7（5，7，2，3）,（8，5，7，2，3）,h=0,表中加入x,01234,7,9,3,-1,5,1,2,3,5678910,2.(1)VListi.data=x;,1.在VList中找空位置 i(比如0),(2)VListi.cur=h;,x,7,(3)h=i;,空位置的标识：将所有空位置构成链表，用av表示链首,av=0,删除：,if(h!=-1)x=VListh.data;i=h;h=VListi.cur;VListi.cur=av;av=i;,h=7,空表初始化：,开始，表是空的，所以：for(i=0;in-1;i+)ai=i+1;an-1=-1;av=0;,2.3.2 循环链表 循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：,非空表,空表,在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n),在很多实际问题中，表的操作常常是在表的尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是rearnextnext和rear，显然，查找时间都是O(1)。因此，实际中也常采用尾指针表示单循环链表.。,由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。,2.3.3 双向链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：struct DuLNode datatype data;DuLNode*prior，*next;,结点,存储前趋结点 的地址,存储数据元素,存储后继结点 的地址,双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：ppriornext=p=pnextprior,双向链表结点p前的插如数据x的操作：,p,x,q=new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;,双向链表结点p前的插如数据x的操作：,p,x,q=new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;,双向链表结点p前的插如数据x的操作：,p,x,q=new DuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;,ppriornext=pnext;pnextprior=pprior;delete p;,p,删除p指针所指的结点：,ppriornext=pnext;pnextprior=pprior;delete p;,p,删除p指针所指的结点：,ppriornext=pnext;pnextprior=pprior;delete p;,p,删除p指针所指的结点：,双向链表的插入、删除灵活；链表维护的工作量大，所需的存储空间较大。,24 一元多项式的表示及相加,P n(x)=pn xn+pn-1 xn-1+p1 x+p0 Q m(x)=qm xm+qm-1 xm-1+q1x+q0,一、一元多项式的表示 多项式的操作是表处理的典型用例。数学上,一元多项式可按降幂写成：（指数为正整数的情况）,其中：pn、qm不为0,存储结构：用线性链表表示。增加头结点，每个结点有coef:系数 exp指数 next：指针其中，头结点的exp为-1。,多项式 A(x)=5 x 17+9 x 8+3x+7,例：求两多项式的和多项式 A(x)=5 x 17+9 x 8+3x+7 B(x)=9 x 8+22 x 7+8 x,二、一元多项式的相加算法,一元多项式相加运算规则：指数相同的项系数相加,A(x)B(x)相加的和多项式为 C(x)=A(x)+B(x)=5 x 17+22 x 7+11x+7,设多项式A(x)，B(x)分别用带表头结点的线性链表pa,pb表示,完成:ha=ha+hb,一元多项式加法算法主要步骤 分别对两个链表ha、hb进行扫描，设 工作指针pa、pb分别指向两个多项式当前进行比较的结点，q指针指向pa的前驱，初始：q=ha;pa=ha-next;pb=hb-next;若pa,pb都不为空：则比较两者指数：pa-exp pb-exp：q,pa后移；pa-exp=pb-exp：将pb所指结点的系数“加”到pa所指结点 的系数上；若和为0，则pa所指结点删除。q,pa,pb调整pa-exp exp：从表hb中复制pb所指结点的coef,exp，并将其插入到 ha表pa所指结点之前；,若pb不空：hb表中从pb开始的结点插入到ha表尾上,int