1、2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示及相加一元多项式的表示及相加2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象知识点：知识点：重点：重点：难点：难点：线性表、顺序表、链表、有序表 顺序表与链表的描述方法；在两种存储结构上实现线性表的基本运算的算法。线性表在两种存储结构上的插入、删除算法及动态链表的建立和查找算法。课前思考：课前思考：抽象数据抽象数据类型的定型的定义由哪几部分由哪几部分组成？成？按数据元素之按数据元素之间的的逻辑关系不同，数据关系不同，数据结构有哪几构有哪几类？你能你能举出几个你熟悉
2、的出几个你熟悉的序列序列的例子来的例子来吗？数据数据对象、数据关系和基本操作三部分。象、数据关系和基本操作三部分。线性性结构、构、树型型结构、构、图状状结构和集合四构和集合四类。如：如：0，1，2，9,A，B，C，Z。1、线性表的定义：、线性表的定义：一个线性表（Linear List）是由n(n0)个数据元素（结点）所构成的有限序列。线性表逻辑地表示为：（a1,a2,an)。其中，n为线性表的长度，n=0时为空表。称i为ai在线性表中的位序。2、线性表的结构（逻辑结构）特点：、线性表的结构（逻辑结构）特点：a.它由n个同类型的元素组成；（一般）b.有且仅有一个第一个元素和最后一个 元素；c.
3、每个元素除第一个元素和最后一个元 素之外,有仅只有一个前驱和一个后继。2.1 2.1 线性表的类型定义线性表的类型定义3 3、抽象数据类型、抽象数据类型线性表线性表的定义：的定义：ADT List 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 基本操作：基本操作：ADT List InitList(&L)1 1）初始化操作：）初始化操作：4 4、线性表的基本操作：、线性表的基本操作：2 2）结构销毁操作：结构销毁操作：DestroyList(&L)ListEmpty(L)3 3）线性表判空操作：）线性表判空
4、操作：ListLength(L)4）求线性表的长度：）求线性表的长度：PriorElem(L,cur_e,&pre_e)5）求数据元素的前驱：）求数据元素的前驱：NextElem(L,cur_e,&next_e)6）求数据元素的后继：）求数据元素的后继：GetElem(L,i,&e)7）取线性表中某个数据元素：）取线性表中某个数据元素：LocateElem(L,e,compare()8）定位操作：）定位操作：ListTraverse(L,visit()9）遍历线性表：）遍历线性表：ClearList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)10）线性表置
5、空操作：）线性表置空操作：11）插入操作：）插入操作：12）删除操作：）删除操作：假设上述基本操作已经实现，则可以利用上述定义的线性表基本操作，来基本操作，来实现其它更复杂的操作例例 2-2例例 2-1注注：这是P20-21页的部分的内容，先跳过。略略 用一组地址连续地址连续的存储单元 依次存放依次存放 线性表中的数据元素的存储结构线性表的线性表的起始地址起始地址称作线性表的基地址基地址 a1 a2 ai-1 ai an一一.概念概念顺序存储：顺序存储：顺序表：顺序表：用顺序存储的线性表就称为顺序表n为表的长度为表的长度2.2 2.2 线性表类型的实现线性表类型的实现-顺序映象顺序映象以“存储
6、位置相邻存储位置相邻”表示有序对即：即：LOC(ai)=LOC(ai-1)+C 一个数据元素所占存储量一个数据元素所占存储量 所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)C 基地址基地址三、地址计算公式三、地址计算公式存储地址存储地址 内在状态内在状态 数据元素在线性表的位序数据元素在线性表的位序a1a2aianb(基地址）基地址）b+Cb+(i-1)*cb+(n-1)*cb+(maxlen-1)*c12in空闲二二.特点：特点：1.逻辑上相邻的数据元素，赋以相邻的逻辑上相邻的数据元素
7、，赋以相邻的 存储位置；存储位置；2.存储密度高；存储密度高；存储密度存储密度 ：数据元素的值所需的存储空间数据元素的值所需的存储空间d=该元素实际所需的存储空间该元素实际所需的存储空间3.便于便于随机存取；随机存取；4.不便于不便于插入、删除操作。插入、删除操作。（会引起大量结点的移动）（会引起大量结点的移动）例如例如四四.线性表的线性表的静态顺序存储结构静态顺序存储结构的的 C 语言描述语言描述(补充内容）补充内容）#define MAXLEN 80 /线性表的最大长度typedef struct ElemType elemMAXLEN;int length;SqListtp;/俗称静态顺
8、序表静态顺序表C语言中用一维数组一维数组来描述：说明一个静态顺序表L：Sqlisttp L;(1)查找：查找：在顺序表L中查找第i个元素。(2)求长度：求长度：求顺序表L中元素的个数。(3)插入：插入：在顺序表L中第i个元素前插入元素b。五五.基本操作在基本操作在静态静态顺序表上的实现顺序表上的实现L.elemi-1L.lengthfor(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj;/第i及其之后的所有元素后移一位,以空出插入位置 L.elemi-1=b;/插入 L.length+;/表长加1（4）删除：）删除：在顺序表L中删除第i个元素。for(j=i;j
9、=L.length-1;j+)L.elemj-1=L.elemj;/将第i元素之后的所有元素前移一位 L.length-;六六.线性表的线性表的动态顺序存储结构动态顺序存储结构的的 C 语言描述语言描述typedef struct SqList;/俗称 动态顺序表动态顺序表#define LIST_INIT_SIZE 80 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量Elemtype*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /(以sizeof(ElemType)为单位)P
10、22InitList(&L)/构造一个空表构造一个空表LocateElem(L,e,compare()/查找查找ListInsert(&L,i,e)/插入元素插入元素ListDelete(&L,i)/删除元素删除元素七、基本操作在动态顺序表上的实现七、基本操作在动态顺序表上的实现1.构造一个空线性表：构造一个空线性表：InitList(&L)1）申请分配）申请分配“足够应用足够应用”的线性表的存储空间的线性表的存储空间2）若分配失败，则结束函数的执行）若分配失败，则结束函数的执行3）若分配成功，则置：）若分配成功，则置：a)表的当前长度为表的当前长度为0 b)当前分配的存储容量为预分配空间的大
11、小当前分配的存储容量为预分配空间的大小 L.elem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype)if(!L.elem)exit(OVERFLOW)L.length=0L.listsize=LIST_INIT_SIZEP23/算法算法2.3Status InitList_Sq(SqList&L)/构造一个空的线性表 /InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem=(ElemType*)malloc(LIST_ INIT_SIZE sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L
12、.length=0;L.listsize=LIST_INIT_SIZEreturn OK;P23/算法算法2.3例如：顺序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee=38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。2.定位操作：定位操作：LocateElem(L,e,compare()P25/算法算法2.6 int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的
13、数据元素，在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0/LocateElem_Sq O(ListLength(L)算法的算法的时间复杂度时间复杂度为：为：i=1;/i i 的初值为第的初值为第 1 1 元素的位序元素的位序p=L.elem;/p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;*p+!=e;P25/算法算法2.63.插入操作 ListInser
14、t(&L,i,e)的实现：首先分析首先分析:1）要求：）要求：在第i个元素之前插入一个值为e的元素 问题：问题：插入元素时，线性表的 逻辑结构逻辑结构发生什么变化发生什么变化？P24/算法算法2.4(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加21 18 30 75 42 56 8721 18 30 75例如：例如：ListInsert_Sq(&L,5,66)L.length-10pppq87564266pL.length-1011for（;p=q;-p)q=&(L.elemi-1);/q
15、 指示插入位置p=&(L.elemL.length-1)*(p+1)=*p;/后移后移*q=e;/将e插入插入到q所指示的位置L.elem a.检测参数检测参数i是否合法及空间是否足够是否合法及空间是否足够 b.插入位置及之后的所有元素后移一位插入位置及之后的所有元素后移一位2）操作步骤：）操作步骤：q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;）若）若i L.length+1，插入位置，插入位置不合法不合法，算法结束；算法结束；）若）若L.length=L.listsize，则无空的，则无空的存储空存储空
16、 间，间，需增加分配。需增加分配。c.插入插入 d.修正表长修正表长*q=e;/插入插入e+L.length;/表长增表长增1 Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq 算法时间复杂度算法时间复杂度为为:O(ListLength(L)q=&(L.elemi-1);/q 指示插入位置指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移元素右移*q=e;/
17、插入插入e+L.length;/表长增表长增1return OK;元素右移元素右移3）算法：）算法：P24/算法算法2.4if(L.length=L.listsize)/当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量if(i L.length+1)return ERROR;/插入位置不
18、合法考虑移动元素的平均情况考虑移动元素的平均情况:假设在第 i 个元素之前插入的概率为 ，则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：首先分析：问题问题：删除元素时，线性表的逻辑 结构发生什么变化？4.删除删除操作操作 ListDelete(&L,i,&e)的实现：1）要求：）要求：将第i个位置上的元素删除P24/算法算法2.5(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的
19、长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 21 18 30 75 42 56 87 L.length-10pppqpp56 87p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;q=&L.elemL.length-1;/q为表尾元素的位置为表尾元素的位置for(;p=q;-p)*(p+1)=*p;/后移一位 若若i L.length，删除删除位置位置不合法不合法，算法结束；算法结束；3.3.修正表长修正表长修正表长修正表长 （表长减（表长减（表长减（表长减1 1）-L.length;/表长减1Status ListDelete_Sq
20、 (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被删除元素之后的元素左移-L.length;/表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为:O(ListLength(L)p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置if(i L.length)return ERROR;/删除位置不合法删除位置不合法元素左移元素左移
21、3）算法：）算法：P24/算法算法2.5考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第 i 个元素的概率为 ,则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：所以，若表长为所以，若表长为n,则插入和删除则插入和删除算法的时间复杂度都为：算法的时间复杂度都为：O(n)思考题：思考题：(P26/算法算法2.7)有两个有序的顺序表有两个有序的顺序表L（有（有m个个元素）和元素）和L（有（有n个元素）其元素均个元素）其元素均以从小到大的升序排列，编写一个函以从小到
22、大的升序排列，编写一个函数将它们合并成一个顺序表数将它们合并成一个顺序表LC，并，并要求要求LC仍保持其有序性。仍保持其有序性。分析：分析：假设假设LA=（6,7,10,21），），LB=（3,11,13,15,23,25,27)pa pb合并后得合并后得LC=（3,6,7,10,11,13,15,21,23,25,27)方法：方法：引进两个指针引进两个指针pa,pb分别指向分别指向LA和和LB中的某中的某个元素个元素,pc指示指示LC中当前插入元素的位置。中当前插入元素的位置。*pa 当*pa*pb时操作步骤操作步骤：(算法见教材P26/算法算法2.7)1.置初值置初值：1)pa=La.el
23、em;pb=Lb.elem;2)为Lc分配足够的存储空间;2.当当pa=La.elem+La.length-1和和 pb=Lb.elem+Lb.length-1时时,重复执行：重复执行：1）当*pa=*pb，将*pa插入到Lc中pc指针所指示的位置,pa指针后移;否则，将*pb插入到Lc中pc指针所指示的位置,pb指针后移。2）pc指针后移3.pa=La.elem+La.length-1，将La中的剩 余元素全部顺序插入到Lc 的尾部4.pbnext;j=1;/p p指向第一个结点，指向第一个结点，j j为计数器为计数器while(p&jnext;+j;/顺指针向后查找，直到顺指针向后查找，直
24、到 p p 指向第指向第 i i 个元素个元素 /或或 p p 为空为空if(!p|ji)return ERROR;/参数参数i i不合法不合法 e=p-data;/取得第取得第 i i 个元素个元素return OK;P29/算法算法2.8问：问：能否将变量初始化改为能否将变量初始化改为p=L;j=0;?ai-1 2、线性表的插入操作 ListInsert(&L,i,e)在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-1P29/算法算法2.9 a.查找第查找第i个结点的前驱结点个结点的前驱结点(或确定待插入的位置或确定待插入的位置)b.产生新结点产生新结点S c.将将S插入到
25、链表指定的位置插入到链表指定的位置2）算法基本步骤：）算法基本步骤：s=(LinkList)malloc(sizeof(LNode);S-data=e;p=L;j=0;while(p&j next;+j;s-next=p-next;p-next=s;eai-1aiai-1sp(能否改为能否改为:p=L-next;j=1;)Status ListInsert_L(LinkList&L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 /在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e /LinstInsert_L
26、算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p&j next;+j;/寻找第寻找第 i-1 个结点个结点if(!p|j i-1)return ERROR;/i 大于表长或者小于大于表长或者小于1 P29/算法算法2.9 问：如果单链表不带头结点，应如何问：如果单链表不带头结点，应如何修改此算法？修改此算法？s=(LinkList)malloc(sizeof(LNode);/生成新结点生成新结点s-data=e;s-next=p-next;p-next=s;/插插入入return OK;3、线性表的删除操作ListDelete(&L,i,&e)在
27、链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1P30/算法算法2.10 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pqe Status ListDelete_L(LinkList&L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点 /ListDelete_L算法的算法的时间复杂度时间复杂度为
28、:O(ListLength(L)p=L;j=0;while(p-next&j next;+j;/寻找第 i 个结点，并令 p 指向其前趋if (!(p-next)|j i-1)return ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;P30/算法算法2.10 问：如果单链表不带头结点，应如何问：如果单链表不带头结点，应如何修改此算法？修改此算法？4、操作 ClearList(&L)在链表中的实现:void ClearList(Linklist&L)/将单链表重新置为一个空表 while(L-ne
29、xt)p=L-next;L-next=p-next;/ClearListfree(p);算法时间复杂度：O(ListLength(L)如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需链表是一个动态的结构，它不需要予分配空间，因此要予分配空间，因此生成链表的过生成链表的过程程是一个结点是一个结点“逐个插入逐个插入”的过程。的过程。5、链表的、链表的建立建立操作操作方法一、方法一、头插法头插法要求：要求：逆位序逆位序输入输入 n n 个数据元素的值，个数据元素的值，建立带头结点的单链表。建立带头结点的单链表。操作步骤操作步骤一、建立一个一、建立一个“空表空表”；二、输入
30、数据元素二、输入数据元素an，建立结点并插入在表头；建立结点并插入在表头；三、输入数据元素三、输入数据元素an-1，建立结点并插入在表头；建立结点并插入在表头；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。P30/算法算法2.11操作步骤实现的主要语句：操作步骤实现的主要语句：L=(LinkList)malloc(sizeof(LNode);/申请空间L-next=NULL;/先建立一个带头结点的空单链表一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素ai (i=n1),建立结点并插入在表头；建立结点并插入在表头；for(i=n;i
31、0;-i)p=(LinkList)malloc(sizeof(LNode);/申请结点空间 scanf(&p-data);/输入元素值 p-next=L-next;L-next=p;/插入void CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的空单链表for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(
32、LNode);scanf(&p-data);/输入元素值 p-next=L-next;L-next=p;/插入P30/算法算法2.11思考：若思考：若顺位序顺位序输入输入 n n 个数据元素的值，个数据元素的值，如何建立带头结点的单链表？如何建立带头结点的单链表？操作步骤操作步骤一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素a1，建立结点并插入在表尾；建立结点并插入在表尾；三、输入数据元素三、输入数据元素a2，建立结点并插入在表尾；建立结点并插入在表尾；a1a1a2五、最后，将五、最后，将a an n结点的指针域置空。结点的指针域置空。四、依次类推，直至输入四、依次类推
33、，直至输入a an n为止。为止。方法二方法二、尾插法尾插法操作步骤实现的主要语句：操作步骤实现的主要语句：L=(LinkList)malloc(sizeof(LNode);/申请结点空间L-next=NULL;/先建立一个带头结点的空单链表一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素ai (i=1n),建立结点并插入在表尾；建立结点并插入在表尾；q=L;/q始终指向表尾结点for(i=0;i data);/输入元素值 q-next=p;/插入 q=p;/q指向新表尾结点算法：算法：学生课堂（或课后）自行完成学生课堂（或课后）自行完成三、将三、将a an n结点的指针
34、域置空。结点的指针域置空。q-next=NULL;void CreateList_L(LinkList&L,int n)/顺序输入 n 个数据元素，建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的空单链表q=L;/q始终指向表尾结点for(i=0;i data);/输入元素值 q-next=p;/插入新结点于表尾（即q结点之后）q=p;/q指向新表尾结点 q-next=NULL;/置尾部结点的指针域为空 以上对链表的各种
35、操作的讨论可知，以上对链表的各种操作的讨论可知，链式存储结构的链式存储结构的优势优势在于：在于：(1)能有效利用存储空间；能有效利用存储空间；(2)用用指针指针指示数据元素之间的指示数据元素之间的后继关系，后继关系，便于进行便于进行插入插入、删除删除等等操作；操作；而其而其劣势劣势则是则是不能随机存取不能随机存取数据元数据元素素,只能顺序存取只能顺序存取数据元素。数据元素。四、有序表四、有序表1.有序表有序表类型类型类型定义类型定义2.应用举例应用举例例：将两个有序单链表合并成一个有例：将两个有序单链表合并成一个有 序单链表序单链表.分析：分析：算法思想：算法思想：a1 .am LaLb b1
36、 .bn Pa（初始位置）（初始位置）pb（初始位置）（初始位置）LC pc（初始位置）（初始位置）引进引进3个指针个指针pa,pb和和pc，其中，其中pa,pb分别指向分别指向La和和Lb表中当前待比较插入的结点，而表中当前待比较插入的结点，而pc指向指向Lc表当前最后一个表当前最后一个结点，若结点，若pa-datadata,则将则将pa所指结点链接到所指结点链接到pc所指结点之后，否则将所指结点之后，否则将pb所指结点链接到所指结点链接到pc所指结点之后。所指结点之后。当其中一个表为空时，则只要将另一个表的剩余段链接在当其中一个表为空时，则只要将另一个表的剩余段链接在pc所指的结点之后即可
37、所指的结点之后即可P31/算法算法2.12操作步骤操作步骤：1.置初值置初值：2.当当pa和和pb皆为非空时，重复执行：皆为非空时，重复执行：否则，将pb所指结点插入到pc 所指结之后，pc后移，再pb后移；3.当当pa或或pb非空时非空时，将La或Lb中的剩余段链接到pc所指的结点之后若pa-datadata,则将pa所指结点插入到所指结点插入到pc 所指所指结点之后，结点之后，再pc后移，pa后移；pc-next=pa;Pc=pa;pa=pa-nextpc-next=pb;Pc=pb;pb=pb-nextpc-next=pa?pa:pbpa=La-next;pb=Lb-next;Lc=Pc
38、=La /用La的头结点作为c的头结点动画演示动画演示:Void Mergelist_L(Linklist&La,Linklist&Lb,Linklist&Lc)/已知单链线性表a和b的元素按值非递增减排列/归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列/MergList_LPa=La-next;pb=Lb-next;Lc=pc=La /用用La的头结点作为的头结点作为c的头结点的头结点While(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=
39、pa?pa:pb;/将La或Lb的剩余段链接到Pc的结点之后 free(Lb);/释放Lb的头结点P31/算法算法2.12用上述定义的单链表实现线性表的操作时，用上述定义的单链表实现线性表的操作时，存在的存在的问题问题：改进链表的设置：改进链表的设置：1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值；1增加增加“表长表长”、“表尾指针表尾指针”和和“当前当前位置的位置的 指针指针”三个数据域；三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时，需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结
40、点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i”改变为改变为“指针指针 p”。五五*、一个带头结点的线性链表类型、一个带头结点的线性链表类型typedef struct LNode /结点类型结点类型 ElemType data;struct LNode *next;*Link,*Position;typedef struct /链表类型链表类型 Link head,tail;/分别指向头结点和分别指向头结点和 /最后一个结点的指针最后一个结点的指针 int len;/指示链表长度指示链表长度 Link current;/指向当前被访问的结点指向当前被访问的
41、结点 /的指针，初始位置指向头结点的指针，初始位置指向头结点 LinkList;P37 1.双向链表双向链表六、其它形式的链表六、其它形式的链表typedef struct DuLNode ElemType data;/数据域 struct DuLNode *prior;/指向前驱的指针域 struct DuLNode *next;/指向后继的指针域 DuLNode,*DuLinkList;最后一个结点的指针域的指针又指回第一个结点的链表2.循环链表循环链表 a1 a2 .an 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。也就是说：也就是
42、说：单循环链表的操作和线性单链表单循环链表的操作和线性单链表基本一致，差别仅在于算法中的基本一致，差别仅在于算法中的循环循环条件条件不是不是p或或p-next是否为空是否为空,而应是而应是p或或p-next是否为是否为head。L空表：空表：判空条件：判空条件：L-next=L单循环链环特点：单循环链环特点：1）从任一结点出发都可访问到表中所有结点）从任一结点出发都可访问到表中所有结点2）用头指针表示的单循环链找开始结点的时间是）用头指针表示的单循环链找开始结点的时间是O（1）用头指针表示的单循环链找终端结点的时间是用头指针表示的单循环链找终端结点的时间是O（n）3）用尾指针表示的单循环链找开
43、始结点的时间是）用尾指针表示的单循环链找开始结点的时间是O（1）用尾指针表示的单循环链找终端结点的时间是用尾指针表示的单循环链找终端结点的时间是O（1）例：在单循环链表上实现将线性表不得例：在单循环链表上实现将线性表不得 (a1,a2,an)和（和（b1,b2,bm)合成一个线合成一个线 性表性表(a1,a2,an,b1,b2,bm)的运算。的运算。用尾指针用尾指针ra和和rb分别表示两个单循分别表示两个单循环链表，则仅需将一个的环链表，则仅需将一个的表尾表尾和另一个和另一个表的表的表头表头相接。相接。分析：分析：a1 a2 .an b1 b2 .bm rarb:p=rb-next rb-ne
44、xt=ra-next:ra-next=p-nextp:free(p)Linklist union(Linklist ra,Linklist rb)/将表将表rb链到表链到表ra之后，返回新链表尾指针之后，返回新链表尾指针 p=rb-next;rb-next=ra-next;ra-next=p-next;free(p);return rb;双向循环链表双向循环链表空表空表非空表非空表 a1 a2 .an判空条件：判空条件：L-prior=L-next=L双向链表的操作特点：双向链表的操作特点：“查询查询”和单链表相同。和单链表相同。“插入插入”和和“删除删除”时需要同时修时需要同时修改两个方向上
45、的指针。改两个方向上的指针。ai-1aies-next=p-next;p-next=s;s-next-prior=s;s-prior=p;psai-1ai插入插入ai-1删除删除aiai+1p-next=p-next-next;p-next-prior=p;pai-1算法题：题集算法题：题集P17/2.13、2.14;P18/2.22作业作业2：实验题：实验题：1.实验一链表的基本操作（验证性实验）实验一链表的基本操作（验证性实验）实验课之前并且在课外完成实验课之前并且在课外完成 2.实验一链表的基本操作（设计性实验）实验一链表的基本操作（设计性实验）实验课完成实验课完成附加题附加题:编写算法
46、删除链表中编写算法删除链表中“多余多余”的数据元的数据元素，即使操作之后的顺序表中所有元素的值素，即使操作之后的顺序表中所有元素的值都不相同。都不相同。在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示:P=(p0,p1,，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x)=1+3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？2.42.4一元多项式一元多项式 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x)=p1xe1+p2xe2+pmxem其中其中：pi 是指数为ei 的项的非零系数，0 e1 e2 em=n
47、可以下列线性表表示：（p1,e1）,(p2,e2),(pm,em)）P999(x)=7x3-2x12-8x999例如例如:可用线性表 (7,3),(-2,12),(-8,999)表示ADT Polynomial 数据对象数据对象：数据关系数据关系：抽象数据类型一元多项式的定义如下：D ai|ai TermSet,i=1,2,.,m,m0 TermSet 中的每个元素包含一个每个元素包含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1|ai-1,aiD,i=2,.,n 且ai-1中的指数值中的指数值ai中的指数值中的指数值 CreatPolyn(&P,m)DestroyP
48、olyn(&P)PrintPolyn(&P)基本操作基本操作：操作结果操作结果：输入 m 项的系数和指数，建立一元多项式 P。初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：销毁一元多项式 P。初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：打印输出一元多项式 P。PolynLength(P)AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)ADT Polynomial初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：返回一元多项式 P 中的项数。初始条件初始条件：一元多项式 Pa 和 Pb 已存在。操作结果操作结果：完成多项式相加
49、运算，即：Pa=PaPb，并销毁一元多项式 Pb。一元多项式在计算机中的实现：一元多项式在计算机中的实现：typedef struct /项项的表示 float coef;/系数系数 int expn;/指数指数 term,ElemType;typedef struct polynode ElemType data;struct polynode*next polynode,*polynomial /用带表头结点的有序链表表示多项式用带表头结点的有序链表表示多项式结点的数据元素类型定义为:typedef struct polynode /项项的表示 float coef;/系数系数 int e
50、xpn;/指数指数 struct pnode*next polynode,*polynomial;链的结点类型也可定义为链的结点类型也可定义为Coef expn next结点类型形如：结点类型形如：多项式的加法：A=2+3x+5x3+2x4B=3-3x+4x2 实现：A=A+B 2 0 3 1 5 3 2 4 ha 3 0 -3 1 4 2 hb 5 0 4 2 ha5 3 2 4 方法方法:对所有指数对应相同的项对所有指数对应相同的项,将其对应系数相加将其对应系数相加,指数不变，指数不变，若和不为零若和不为零,则构成多项式中的则构成多项式中的一项。将所有指数不同的项复一项。将所有指数不同的项
