线性表 课件.ppt

07:00,数据结构,第二章 线性表,07:00,第2章 线性表第3章 栈和队列第4章 串、数组和广义表,线性结构,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。,可表示为：（a1 , a2 , , an）,线性结构的定义：,（逻辑、存储和运算）,07:00,线性结构的特点：, 只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是,线性表,简言之，线性结构反映结点间的逻辑关系是 一对一 的,07:00,第2章线性表,1. 了解线性结构的特点2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合,教学目标,07:00,2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 线性表的应用,教学内容,07:00,L=（a1, a2, ai-1，ai, ai1 ，, an）,线性表的定义：由n（n=0）个类型相同的数据元素组成的有限序列,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,2.1 线性表的类型定义,07:00,例1 分析26 个英文字母组成的英文表,（ A, B, C, D, , Z）,例2 分析学生情况登记表,数据元素都是记录; 元素间关系是线性,数据元素都是字母; 元素间关系是线性,同一线性表中的元素必定具有相同特性,1:1,07:00,例3 某校从1978年到1983年各种型号的计算机拥有量的变化情况。,（6，17，28，50，92，188）,例4一副扑克的点数,数据元素都是字符; 元素间关系是线性,同一线性表中的元素必定具有相同特性,数据元素都是数字; 元素间关系是线性,（2，3，4，J，Q，K，A）,线性表特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个直接前驱除最后一个外，集合中的每个数据元素均只有一个直接后继,相邻结点间的关系,07:00,线性表的基本操作初始化线性表L InitList(L)构造一个空的线性表L，即表的初始化。 销毁线性表L DestoryList(L) 其作用是销毁当前线性表L 清空线性表L ClearList(L) 清空L使之成为空表 求线性表L的长度 ListLength(L)返回L的长度，即线性表中数据元素的个数判断线性表L是否为空 IsEmpty(L) 判断L是否为空表，是返回true,否返回false获取线性表L中的某个数据元素内容 GetElem(L,i,&e)将L中第i个数据元素的值返回到变量e中,抽象数据类型的定义为,07:00,检索值为e的数据元素 LocateELem(L,e)判断线性表L中是否存在值为e的结点 在线性表L中插入一个数据元素 ListInsert(&L,i,e)向线性表L的第i个位置之前插入一个值为e的数据元素删除线性表L中第i个数据元素 ListDelete(&L,i,&e)删除线性表L的第i个数据元素，并将该数据元素的值返回e中10.返回前驱结点 PriorElem(L,cur_e,&pri_e)返回L中当前数据元素cur_e的前驱结点11.返回后继结点NextElem(L,cur_e,&next_e)返回L中当前数据元素cur_e的的后继结点,07:00,2.2 线性表的顺序表示和实现,线性表的顺序表示又称为顺序存储结构或顺序映像。,简言之，逻辑上相邻，物理上也相邻,顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组Vn来实现。,顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,07:00,Loc(元素i)=Loc(元素1)+（i-1)*m,起始地址Lo,顺序表：定义：用一组地址连续的存储单元存放一个线性表元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*m / 任意两个相邻元素间地址相差mLOC(ai+1)=LOC(ai)+m特点：实现逻辑上相邻物理地址相邻实现随机存取,起始地址，基地址,第i个元素的地址,每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数，因此只要确定了起始位置，线性表中任一数据元素都可随机存取。 顺序表可以随机存取，高级程序设计语言中的数组也有随机存取的特性。,实现：可用C语言的一维数组实现,07:00,#define MAXSIZE 100 /预定义最大长度typedef struct ElemType ElemMAXSIZE; /指向数据元素的基地址 int length; /线性表的当前长度 SqList；,顺序表的类型定义,线性表基本运算操作有：查找、插入、删除,由于线性表的长度是可变的，所需的存储空间不同，所以在C语言中，可用动态分配的一维数组来描述。,07:00,#define LIST_INIT_SIZE 100#define LISTINCREMENT 10Typedef struct ElemType * elem; int length;SqList;,数据元素不是简单类型时,可定义结构体数组,动态申请内存L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);,线性表存储空间初始分配量,线性表存储空间分配增量,存储空间基址,预定义,07:00,malloc(m)：开辟m字节长度的地址空间，并返回这段空间的首地址sizeof(x)：计算变量x的长度free(p)：释放指针p所指变量的存储空间，即彻底删除一个变量,补充：C语言的动态分配函数（ ）,07:00,线性表的基本操作1. 初始化线性表L InitList(L) 2. 销毁线性表L DestoryList(L) 3. 清空线性表L ClearList(L) 4. 求线性表L的长度 ListLength(L)5. 判断线性表L是否为空 IsEmpty(L) 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 7. 检索值为e的数据元素 LocateELem(L,e) 8. 在线性表L中插入一个数据元素 ListInsert(L,i,e)9. 删除线性表L中第i个数据元素 ListDelete(L,i,e),抽象数据类型的定义为,07:00,典型操作的算法实现,初始化线性表L （参数用引用）Status InitList_Sq(SqList ,07:00,2. 销毁线性表Lvoid DestroyList(SqList ,3. 清空线性表Lvoid ClearList(SqList /将线性表的长度置为0,07:00,4. 求线性表L的长度int GetLength(SqList L) return (L.length); ,5.判断线性表L是否为空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0;,07:00,按序号查找（位置）按值查找,查找,07:00,251247893614,123456789,L.elem0,e=L.elem3 /取第4个元素赋给变量e,查找第 i 个元素（假设i=4）,序号,若下标从0开始,L.elem1,L.elem2,L.elem3,07:00,6. 获取线性表L中的某个数据元素的内容/根据指定位置i，获取相应位置数据元素的内容int GetElem(SqList L,int i,ElemType ,07:00,查找元素e（根据指定数据查找，返回其所在的位置）,顺序查找图示,25 34 57 16 48 09,0 1 2 3 4 5,data,查找 16,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,查找成功,07:00,25 34 57 16 48,0 1 2 3 4,data,查找 50,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,查找失败,07:00,7. 在线性表L中查找值为e的数据元素(找到返回其位序，否则返回ERROR)int LocateELem(SqList L, ElemType e) for (i=0;i L.length;i+) if (L.elemi=e) return i; return ERROR;,07:00,251247893614,123456789,25124799893614,99插入,251247893614,251247893614,251247893614,插第 4 个结点之前，移动 64+1 次插在第 i 个结点之前，移动 n-i+1 次,插入（插在第 i 个结点之前）先看i=4,依次赋值,07:00,（1）判断插入位置i 是否合法。（2）判断顺序表的存储空间是否已满。 （3）将第n至第i 位的元素依次向后移动一个位置，空出第i个位置。（4）将要插入的新元素e放入第i个位置。（5）表长加1，插入成功返回OK。,【算法思想】,07:00,8. 在线性表L中第i个数据元素之前插入数据元素e Status ListInsert_Sq(SqList ,【算法描述】,07:00,若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？,算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,假设在线性表的任何位置上插入、删除元素都是等概率的，则,07:00,251247893614,123456789,2512473614,2512473614,2512473614,删除,删除（删除第 i 个结点）先看i=4,删除第 4 个结点，移动 64 次删除第 i 个结点，移动 n-i 次,07:00,（1）判断删除位置i 是否合法（合法值为1in）。（2）将欲删除的元素保留在e中。 （3）将第i+1至第n 位的元素依次向前移动一个位置。（4）表长减1，删除成功返回OK。,【算法思想】,07:00,9. 将线性表L中第i个数据元素删除Status ListDelete_Sq(SqList ,【算法描述】,07:00,若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中n-1个元素全部前移（特别慢）；若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？,【算法分析】,算法时间主要耗费在移动元素的操作上,算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：,07:00,查找、插入、删除算法的平均时间复杂度为O(n),故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低,例：已知顺序表La和Lb的数据元素按值非递减排列，归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列,Ch2_3.c,合并有序顺序表,算法思想： 基本操作是“复制”，设2个下标i和j，分别指向2个表当前处理的元素，比较它们的值，当i所指向的值不大于j所指向的值时，复制i所指元素到Lc中，否则复制j所指元素到Lc中。 反复进行上述操作，直到LA或LB结束之后，再把尚未结束的LB或LA的剩余各元素依次复制到LC中 。,07:00,void Mergelist(SqList La, SqList Lb, SqList /LA的当前项较小，将它复制到LC中,07:00,07:00,else ListInsert_Lc( Lc,k+,bj ); j+; /LB的当前项较小，将它复制到LC中 while (in) /LA还有剩余GetElem(La,i+, ai); ListInsert_Lc(Lc,k+,ai); /将LA的剩余各元素依次复制到LC中 while (jm) /LB还有剩余，GetElem(Lb,j+, bj); ListInsert_Lc(Lc,k+,bj); /将LB的剩余各元素依次复制到LC中 ,07:00,（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致,顺序表（顺序存储结构）的特点,这种存取元素的方法被称为随机存取法,（2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等,07:00,顺序表的优缺点,缺点：在插入、删除某一元素时，需要移动大量元素按最大空间预先分配，浪费存储空间属于静态存储形式，数据元素的个数不能自由扩充,优点：存储密度大（结点本身所占存储量/结点结构所占存储量）可以随机存取表中任一元素,07:00,2.3 线性表的链式表示和实现,链式存储结构结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻,线性表的链式表示又称为非顺序映像或链式映像。,特点：用一组任意的存储单元存储线性表的数据元素（可以连续，可以不连续）利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：数据元素本身信息指针域：指示直接后继的存储位置,07:00,如何实现？,通过指针来实现,单链表的存储映像,free,(a) 可利用存储空间,a0,a2,a1,a3,free,first,(b) 经过一段运行后的单链表结构,07:00,与链式存储有关的术语,1、结点：数据元素的存储映像。由数据域和指针域两部分组成2、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构,为方便用户理解所画的图示,07:00,循环链表示意图：,3、单链表、双链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表有两个指针域的链表，称为双链表首尾相接的链表称为循环链表,07:00,4、头指针、头结点,头指针是指向链表中第一个结点的指针头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息,数据域,指针域,结点,直观化的描述方法：,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。,head,(a) 非空表,head=NULL,(b) 空表,线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,头指针,07:00,上例链表的逻辑结构示意图有以下两种形式：,区别： 无头结点 有头结点,07:00,讨论1. 如何表示空表？,有头结点时，当头结点的指针域为空时表示空表,head-next=NULL,07:00,讨论2. 在链表中设置头结点有什么好处？,便于首元结点(第一个结点)的处理首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;,便于空表和非空表的统一处理无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。,07:00,讨论3. 头结点的数据域内装的是什么？,头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。,头结点的数据域,07:00,（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻,链表（链式存储结构）的特点,（2）单链表中，任何两个元素的存储位置之间没有固定的联系，每个元素的存储位置都包含在其直接前驱结点的信息中。（3）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点(顺藤摸瓜)，所以寻找第一个结点和最后一个结点所花费的时间不等,这种存取元素的方法被称为顺序存取法,07:00,优点数据元素的个数可以自由扩充插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高,链表的优缺点,07:00,缺点存储密度小存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）,链表的优缺点,07:00,练习,1.链表的每个结点中都恰好包含一个指针。 2.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。3.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。4.线性表若采用链式存储时，结点之间和结点内部的存储空间都是可以不连续的。 5.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型,07:00,2.3.1 单链表的定义和实现,非空表,空表,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名若头指针名是L，则把链表称为表L,07:00,typedef struct LNode ElemType data; /数据域 struct LNode *next; /指针域LNode,*LinkList; / *LinkList为Lnode类型的指针,单链表的存储结构定义,07:00,LNode *p,注意区分指针变量和结点变量两个不同的概念指针变量p：表示结点地址结点变量*p：表示一个结点,注意：LinkList和LNode *是不同名字的同一个指针类型，LinkList类型的指针变量head表示它是单链表的头指针,LNode *类型的指针变量p表示它是指向某一结点的指针。,typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;,(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域,生成一个新结点：p=(LinkList) malloc ( sizeof ( Lnode );系统回收p结点：free(p),若当前结点由p指向，那么它的下一个结点可表示为p-next,p-next,同理，下下个结点可表示为p-next-next,07:00,若p-data=ai, 则p-next-data=ai+1,指针p后移，p=p-next,p-next,07:00,初始化线性表L InitList(L) 2. 清空线性表L ClearList(L) 3. 求线性表L的长度 ListLength(L)4. 判断线性表L是否为空 IsEmpty(L) 5. 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 6. 检索值为e的数据元素 LocateELem(L,e) 7. 在线性表L中插入一个数据元素 ListInsert(L,i,e)8. 删除线性表L中第i个数据元素 ListDelete(L,i,e),2.3.2 单链表基本操作的实现,07:00,1.初始化(构造一个空表 )【算法思想】（1）生成新结点作头结点，用头指针head指向头结点。（2）头结点的指针域置空。,【算法描述】Status InitList_L(LinkList *L) L-head=(LinkList)malloc(sizeof( LNode); if(L-head) L-head-next=NULL; reurn OK;return ERROE; ,07:00,2. 判断表是否为空Status ListEmpty(LinkList L) /若L为空表，则返回TURE，否则返回FALSE Status flag=FALSE; /flag初值状态为FALSE if(L-head-next=NULL) /空 flag=TRUE; return flag; ,07:00,3.求表长int ListLength_L(LinkList L)/返回L中数据元素个数 int i=0; p=L.head; while(p-next!=NULL) /遍历单链表,统计结点数 i+; p=p-next; return i; ,07:00,4.清空Void ClearList(LinkList * L) / 将L重置为空表 Lnode* p; while(L-head-next) /没到表尾 p=L-head-next; /p指向头结点后的第一个结点 L-head-next=p-next；/删除P结点 free(p); /释放p结点占据的存储空间,07:00,按序号查找按值查找,查找,07:00,思考：顺序表里如何找到第i个元素？链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构,按序号查找,07:00,head,a2,a3,a1,j=1,i=3,j=2,j=3,e=p-data,While ( p!=Null & ji ),p=p-next; j+; ,查找第i个元素,指针p后移，计数器j加1,07:00,从第1个结点（L.head-next）顺链扫描，用指针p指向当前扫描到的结点，p初值p=L.head-next。用j做计数器，累计当前扫描过的结点数，j初值为1。当p指向扫描到的下一结点时，计数器j加1。当j=i时，p所指的结点就是要找的第i个结点。,【算法思想】,按序号查找,07:00,5.获取线性表L中的某个数据元素的内容Status GetElem_L(LinkList L, int i, ElemType /GetElem_L,按序号查找,【算法描述】,07:00,head,b,e,a,While (p!=Null & p-data!=e),按值(e)查找,p=p-next; ,指针p后移,07:00,从第一个结点起，数据域依次和e相比较。如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”；如果查遍整个链表都没有找到其值和e相等的元素，则返回“NULL”。,【算法思想】,按值查找,07:00,6.在线性表L中查找值为e的数据元素LNode *LocateELem_L (LinkList L，Elemtype e) p=L.head-next; while(p /返回L中值为e的数据元素的位置，查找失败返回NULL ,按值查找,【算法描述】,07:00,插入（第 i 个结点之前）,ai-1,ai-1,ai,x,ai,p,插入前,插入后,将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间,插入新结点S后， ai-1和ai之间关系发生变化。ai-1的直接后继变成x， ai的直接前驱变成x。,指针的指向发生了变化,x,生成新结点,1.s=(LinkList)malloc(sizeof( LNode); 2. s-data=x;,s-next=p-next;,p-next=s;,1.s-next=p-next; 2. p-next=s,思考：步骤1和2能互换么？,修改指针,p-next,?,07:00,【算法思想】,（1）找到ai-1存储位置p（2）生成一个新结点*s（3）将新结点*s的数据域置为x（4）新结点*s的指针域指向结点ai（5）令结点*p的指针域指向新结点*s,07:00,8.在L中第i个元素之前插入数据元素e Status ListInsert_L(LinkList /ListInsert_L,【算法描述】,07:00,删除（删除第 i 个结点）,ai-1,ai-1,ai,ai,ai+1,ai+1,p,q,删除前,删除后,1.p-next=q-next; 2. free(q),?,07:00,【算法思想】,（1）找到ai-1存储位置p（2）临时保存结点ai的地址在q中，以备释放（3）将ai的值保留在e中（4）令p-next指向ai的直接后继结点（5）释放ai的空间,07:00,9.将线性表L中第i个数据元素删除 Status ListDelete_L(LinkList /ListDelete_L,【算法描述】,07:00,删除（删除第 i 个结点）,p-next = p-next-next ?,ai-1,ai-1,ai,ai,ai+1,ai+1,p,删除前,删除后,?,?,p-next,p-next-next,07:00,1. 查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。,2. 插入和删除: 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。,链表的运算时间效率分析,07:00,单链表的建立（尾插法）,从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的尾端,07:00,初始时，r同L均指向头结点。每生成一个新结点(p)把它插入到尾结点后 / / r-next=p; r指向新的尾结点/ / r=p;,单链表的建立（尾插法）,p=(LinkList)malloc(sizeof( LNode)pdata=ai; pnext=NULL;,07:00,void CreateList_L(LinkList /r指向新的尾结点 /CreateList_L,【算法描述】,07:00,从一个空表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端,单链表的建立（前插法）,07:00,单链表的建立（前插法）,每次新插入的结点都作为链表的第一个结点,07:00,void CreateList_F(LinkList /插入到表头 /CreateList_F,【算法描述】,07:00,如果把单链表最后一个结点的Next域存储的值由NULL改为指向表的起始结点，使整个表的结点首尾相接，形成一个环，这样的链表被称为“循环链表”。,2.3.3 循环链表,07:00,特点：从表中任一结点出发均可找到表中其他结点，提高查找效率.单链表中某个结点p是表中最后一个结点的特征是p-next=NULL。对于一个循环单链表，若首指针为head，表中的某个结点p是最后一个结点的特征应该是p-next=head。,操作与单链表基本一致,循环条件不同单链表p或p-next=NULL循环链表p或p-next=h,07:00,2.3.3 循环链表,07:00,Lnode *LocateElem(LinkList L, ElemType e)Lnode *p; p=L.head-next;While(p!=L.head)/没找到，返回空,循环链表中查找值为e的结点,07:00,前面的各种链式表中，一个结点的指针域是指向它的后继结点的，如果需要找一个结点p的前驱结点，则必须从表首指针开始查找，当某个结点pre的指针域指向的是结点p时，即pre-next=p时，则说明pre是p的前驱结点。 如果常常需要知道一个结点的前驱和后继结点，上述的链式表是不适合的。那自然地想到再增设一个指针域指向它的前驱结点，这就构成了双链表。,2.3.4 双向链表,双链表的结点包括三个域，一个是存放数据信息的data域，另外两个是指针域，这里用prior和next表示，prior指向它的前驱结点，next指向它的后继结点。,双链表的一般情形如图所示：,2.3.4 双向链表,07:00,2.3.4 双向链表,双链表结点的定义,在双向链表中有些操作如ListLength,GetElem,LocateElem等仅需要涉及一个方向的指针，因此它们的算法和线性链表的操作相同，但在插入、删除时有很大的不同，在双向链表中需要同时修改两个方向上的指针。,07:00,(a) 空双向循环链表,(b) 非空双向循环链表,d-next-prior = d-prior-next = d,07:00,2.4 线性表的应用,1,2,3,07:00,2.4.3 一元多项式的表示及相加,A17(x)=7+3x+9x8+5x17B8(x)=8x+22x79x8,自学,只有一个变量x,和为：C(x)=7+11x+ 22x7 +5x17,一元多项式的表示：,可用线性表P表示,其中每一项的指数i隐含在其系数pi的序号里。 显然我们可以使用顺序存储结构来存储多项式，使多项式的相加算法很简洁。 然而，在通常的应用中，多项式的次数可能很高，变化很大，使得顺序存储结构的最大长度很难确定。,比如S(x)这样的多项式,如果顺序存储，就要用一个长度为20001的线性表来表示，而表中仅有3个非零的元素，非常浪费内存。若只是存储非零系数项则显然必须同时存储相应的指数。,用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构，也可以用单链表,系数、指数,单链表的结点定义,typedef struct node int coef, exp; struct node *next;JD;,一元多项式相加,一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。,、q指向当前待比较结点pre始终指向计算结果中最新的结点最后结果是存在了第一个链表中,每次比较两个结点的指数,设qa,qb分别指向A,B中某一结点，qa,qb初值是第一结点，结果保存在A中,运算规则,07:00,问题描述： 已知线性表La 和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列.,La=(1 ,7, 8)Lb=(2, 4, 6, 8, 10, 11)Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) .,2.4.2 有序表的合并,07:00,(1) 创建一个空表Lc,(2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止,(3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后,【算法思想】有序的顺序表合并,07:00,void MergeList_Sq(SqList LA,SqList LB,SqList /LA表已到达表尾，依次将LB的剩余元素插入LC表的最后 /MergeList_Sq,T(n)=,【算法描述】有序的顺序表合并,S(n)=,07:00,将这两个有序链表合并成一个有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。,有序链表合并重点掌握,07:00,La,1,7,8,2,4,6,8,10,11,有序链表合并重点掌握,07:00,(1)Lc指向La,(2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止,(3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后,(4) 释放 Lb 表的表头结点,【算法思想】有序的链表合并,07:00,有序链表合并（初始化）,pa,La,1,7,8,2,4,6,8,10,11,pb,07:00,pa,La(Lc ,pc),1,7,8,2,4,6,8,10,11,pb,有序链表合并( pa-data data ),pc-next = pa;,07:00,Pa,La(Lc),1,7,8,2,4,6,8,10,11,pb,有序链表合并( pa-data data ),pc-next = pa;,pc= pa;,Pc,07:00,La(Lc),1,7,8,2,4,6,8,10,11,pb,有序链表合并( pa-data data ),pc-next = pa;,pc= pa;,Pc,07:00,La(Lc),1,7,8,2,4,6,8,10,11,pb,有序链表合并( pa-data pb-data ),pc-next = pb;,Pc,pa,07:00,La(Lc),1,7,8,4,6,8,10,11,pb,有序链表合并( pa-data pb-data ),pc-next = pb;,pa,07:00,La(Lc),1,7,8,4,6,8,10,11,有序链表合并( pa-data pb-data ),pc-next = pb;,pa,07:00,La(Lc),1,2,4,6,7,8,8,10,11,有序链表合并,pc- next=pa?pa:pb;,pa(NULL),pb,pc,07:00,La(Lc),1,2,4,6,7,8,8,10,11,合并后,有序链表合并,07:00,void MergeList_L(LinkList /释放Lb的头结点,T(n)=S(n)= O(1),【算法描述】有序的链表合并,07:00,思考1：要求合并后的表无重复数据，如何实现？,提示：要单独考虑pa-data = =pb-data,La(Lc),1,2,4,6,7,8,8,10,11,07:00,1、掌握线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。2、熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。,小结,07:00,3、熟练掌握顺序表的查找、插入和删除算法 4、熟练掌握链表的查找、插入和删除算法5、能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合,小结,07:00,（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。,算法设计题,07:00,北京林业大学信息学院,参考算法2.16,要单独考虑pa-data = =pb-data,La(Lc),1,2,4,6,7,8,8,10,11,07:00,北京林业大学信息学院,（2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。,算法设计题,07:00,北京林业大学信息学院,(1)Lc指向La,(2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的表头结点之后，直至其中一个表变空为止,(3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后,(4) 释放 Lb 表的表头结点,【算法思想】,07:00,北京林业大学信息学院,La,Lb,Lc,第（2）题实现过程动态演示,07:00,北京林业大学信息学院,（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。,【算法思想】类似于求n个数中的最大数可假设第一个结点最大，用指针pmax指向。然后用pmax依次和后面的结点进行比较，发现大者则用pmax指向该结点。这样将链表从头到尾遍历一遍时，pmax所指向的结点就是最大者。其中的比较语句形式如下：if(p-data pmax-data) pmax=p;,算法设计题,07:00,北京林业大学信息学院,（7）设计一个算法，通过一趟遍历，将链表中所有结点的链接方向逆转，且仍利用原表的存储空间。,算法设计题,【算法思想】从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部,07:00,北京林业大学信息学院,a1,a2,a3,L,p,a1,a2,a3,标志后继结点q修改指针（将p插入在头结点之后）重置结点p（p重新指向原表中后继）,