数据结构课程讲稿第2章课件

数据数据结构构课程程讲稿第稿第2章章第 1章 绪 论 第第2章章 线性表线性表线性结构的特点：线性结构的特点：在数据元素的非空有限集中，在数据元素的非空有限集中，1.存在唯一的一个被称做“第一个”的数据元素；2.存在唯一的一个被称做“最后一个”的数据元素；3.除第一个之外，集合中的每个数据元素均只有一个前驱；4.除最后一个之外，集合中每个数据元素均只有一个后继。简单来讲，线性结构中简单来讲，线性结构中相邻数据元素相邻数据元素存在存在一对一一对一的组织关系。的组织关系。第 1章 绪 论 2.1 线性表的类型定义线性表的类型定义1.线性表的定义线性表的定义是n个数据元素的有限序列。其逻辑结构如下：图2.1 线性表的逻辑结构 第 1章 绪 论 在一个线性表中，数据元素可以代表很在一个线性表中，数据元素可以代表很广泛的事物，例如：广泛的事物，例如：英文字母表(A,B,Z)学生成绩表、车辆登记表等表2-1 车辆登记表 第 1章 绪 论 2.1 线性表的类型定义线性表的类型定义尽管数据元素的多样性，但是：尽管数据元素的多样性，但是：1.同一线性表中的元素必定具有相同特性属于同一数据对象数据对象2.相邻元素之间存在序偶关系一对一的关系即满足线性结构的唯一前驱和唯一后继的关系。第 1章 绪 论 2.1 线性表的类型定义线性表的类型定义线性表的形式化定义：线性表的形式化定义：线性表(Linear List)是由n(n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记作（a1,a2,，ai-1，ai，ai+1，an）。数据元素ai(1in)只是一个抽象的抽象的符号。n被定义为线性表的长度；n=0时称为空表。ai中的下标i亦标明该元素在线性表中的位序第 1章 绪 论 2.1 线性表的类型定义线性表的类型定义2.线性表的基本操作线性表的基本操作线性表可以根据需要变长或变短这种特点意味着：可以增加元素，也可以删除元素除了这两种操作外，还可以访问、定位、获得前驱、获得后继、判断是否为空等操作。用用ADT描述如下：描述如下：第 1章 绪 论 ADT LinearList 数据对象数据对象：D=ai|ai ElemSet,i=1,2,，n,n0 关系：关系：RL|ai,ai+1D，i=1,2,n-1 基本操作：基本操作：在这种线性结构上面，我们可以定义哪些操作？如何描述这样的操作？第 1章 绪 论（1）InitList（&L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(&L)操作前提：线性表L已存在。操作结果：将L销毁。第 1章 绪 论（3）ClearList(&L)操作前提：线性表L已存在。操作结果：将表L置为空表。（4）ListEmpty（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。第 1章 绪 论（5）ListLength（L）操作前提：线性表L已存在。操作结果：返回表中的元素个数。（6）LocateElem(L,e,condition)操作前提：表L已存在，e为合法元素值,condition是数据元素需要满足的条件。操作结果：返回L中第1个与e满足条件condition的数据元素的位序。若这样的数据元素不存在，则返回值为0。（7）GetElem(L,i，&e)操作前提：表L存在，且i值合法，即1iListLength(L).操作结果：通过e返回线性表L中第i个元素的值。第 1章 绪 论（8）PriorElem(L,cur_e,&pre_e)操作前提：线性表L已存在。操作结果：如果cur_e是L中元素，且不是第一个，则用pre_e返回cur_e的前驱，否则操作失败。（9）NextElem(L,cur_e，&next_e)操作前提：表L已存在。操作结果：如果cur_e是L中元素，且不是最后一个，则用next_e返回cur_e的后继，否则操作失败。第 1章 绪 论（10）ListInsert(&L,i,e)操 作 前 提：表 L已 存 在，e为 合 法 元 素 值 且1iListLength(L)+1。操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。（11）ListDelete(&L,i,&e)操作前提：表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ADT LinearList 第 1章 绪 论 线性表的抽象数据类型定义线性表的抽象数据类型定义注意：注意：对线性表的操作的定义不仅仅于此！可以通过复用现有操作，定义新的操作！也可以定义新的操作。操作的定义，一切根据你的需要。第 1章 绪 论 例例2-1 假设利用两个线性表假设利用两个线性表LA和和LB分别分别表示两个集合（即线性表中的数据元素表示两个集合（即线性表中的数据元素即为集合中的成员），现要求一个新的即为集合中的成员），现要求一个新的集合集合A=A U B.分析：分析：扩大线性表LA，将存在于LB中且不存在于LA中的数据元素插入到LA中去。只要从LB中依次取得每个数据元素，并依值在LA中查访，若不存在，则插入之。第 1章 绪 论 伪代码算法描述如下：伪代码算法描述如下：void union(List&La，List Lb)La_len=ListLength(La)；Lb_len=ListLength(Lb)；for(i=1,i=Lb_len,i+)GetElem(Lb,i,&e);if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e);/union第 1章 绪 论 算法的时间复杂度分析算法的时间复杂度分析此算法的时间复杂度该如何计算呢？此算法的时间复杂度该如何计算呢？程序的主体是长度为Lb_length的循环，其复杂度为O(Lb_length)在每一次循环中，其执行体的复杂度依赖于LocateElem操作因为LocateElem操作与表La的长度成正比，所以其复杂度为O(La_length)因此，算法复杂度为：O(O(Lb_length)x O(La_length)=O(Lb_length x La_length)第 1章 绪 论 例例2-2 已知线性表已知线性表LA和和LB中的数据元素中的数据元素按值非递减有序排列，现要求将按值非递减有序排列，现要求将LA和和LB归并为一个新的线性表归并为一个新的线性表LC，且，且LC中的数中的数据元素仍按照值非递减有序排列。据元素仍按照值非递减有序排列。例如：例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)LC=(2,3,5,6,8,8,9,11,11,15,20)第 1章 绪 论 void MergeList(List La,List Lb,List&Lc)InitList(Lc);i=j=1;k=0La_len=ListLength(La);Lb_len=ListLength(Lb)While(i=La_len)&(j=Lb_len)/La和Lb均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);i+elseListInsert(Lc,+k,bj);+jWhile(i=La_len)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);While(j=Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/MergeList第 1章 绪 论 算法复杂性分析算法复杂性分析此算法中，有三个此算法中，有三个while循环，其复杂度为：循环，其复杂度为：第一个循环有几种情况：第一个循环有几种情况：（1）交替向LC中插入一个LA中一个元素，然后LB中的一个元素（2）可能先插入LA中的所有元素，然后插入LB中的所有元素；或者相反的顺序其它两个循环的执行要依赖于第一个循环的结果其它两个循环的执行要依赖于第一个循环的结果最终的算法复杂度为：最终的算法复杂度为：O(La_length+Lb_length)第 1章 绪 论 2.2 线性表的顺序表示和实现线性表的顺序表示和实现数据结构的几个基本的内容：数据结构的几个基本的内容：1.逻辑结构组织形式2.操作或运算的定义、描述：算法3.物理结构数据表示4.算法的实现第 1章 绪 论 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的数据表示有两种方式：线性表的数据表示有两种方式：1.顺序存储表示：分配连续存储空间2.链式存储表示：可离散、可连续两种不同的存储结构两种不同的存储结构相同的算法相同的算法的实的实现方式是不同的！现方式是不同的！第 1章 绪 论 1.线性表的顺序表示线性表的顺序表示顺序表示是用一组地址连续的存储单元依次存储线性表的数据元素。特点：特点：用存储位置相邻来表示线性表中数据元素的逻用存储位置相邻来表示线性表中数据元素的逻辑相邻。辑相邻。2.顺序表示的特点：顺序表示的特点：LOC(ai+1)=LOC(ai)+l一般来说，顺序表示中任何一个元素的位置可以通过偏移量偏移量来定位LOC(ai)=LOC(a1)+(i-1)*lLOC(a1)为基址，(i-1)为元素ai相对于基址的偏移量。第 1章 绪 论 图2.2 顺序表存储示意图 第 1章 绪 论 2.2 线性表的顺序表示和实现线性表的顺序表示和实现“顺序表示”方便随机存取随机存取。因此，线性表的顺序存储结构是一种随机存随机存取的存储结构取的存储结构。3.线性表的顺序表示的实现线性表的顺序表示的实现数组C语言中的数组的局限性一旦分配，长度固定，不能满足线性表的动态变化的特点。第 1章 绪 论 2.2 线性表的顺序表示和实现线性表的顺序表示和实现C语言中的动态连续分配的实现方式：语言中的动态连续分配的实现方式：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10Typedef struct ElemType*elem；int length;/线性表逻辑长度 int listsize;/实际分配的存储空间的大小SqList由于由于C语言数组的局限性，在算法描述和实现中：语言数组的局限性，在算法描述和实现中：malloc函数连续存储空间（动态）第 1章 绪 论 2.2 线性表的顺序表示和实现线性表的顺序表示和实现4.采用顺序表示的线性表各种操作的实现采用顺序表示的线性表各种操作的实现1）初始化操作）初始化操作Status InitList_Sq(SqList&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/分配失败L.length=0;/逻辑结构为空L.listsize=LIST_INIT_SIZE;/实际分配的存储空间Return OK;/InitList_Sq注意：在注意：在C语言中，数组下标是从语言中，数组下标是从“0”开始；而线性表定开始；而线性表定义的下标是从义的下标是从“1”开始！开始！第 1章 绪 论 2）插入操作的实现）插入操作的实现插入前后的数据元素逻辑关系逻辑关系的变化：插入前：(e1，ei-1，ei，en)插入后：（e1，,ei-1，e，ei，en）顺序表示的特点是：用相邻的位置关系来表示数据元素的逻辑关系在插入一个元素后，线性表中数据元素实际的存储位置关系发生了哪些变化？第 1章 绪 论 例如：已知线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”，如图2.3所示。图2.3 顺序表中插入元素 在实现时，请注意区分元素的序号和数组的下标。实在实现时，请注意区分元素的序号和数组的下标。实现如下：现如下：第 1章 绪 论 Status ListInsert_Sq(SqList&L,int i,ElemType e)/i是在线性表是在线性表中的位置编号，中的位置编号，i从从1开始开始if(i L.length+1)return ERROR;/i不合法if(L.length=L.listsize)/逻辑表大于已分配空间newbase =(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);/追加分配存储空间if(!newbase)exit(OVERFLOW);L.elem=newbase;/新基址L.listsize+=LISTINCREMENT;q=&(L.elemi-1);/q为插入位置指针，数组中下标从0开始for(p=&(L.elemL.length-1);p=q;-p)/此处亦可用下标形式实现*(p+1)=*p/移动数据元素*q=e;/插入元素+L.length;return OK/ListInsert_Sq第 1章 绪 论 3）删除操作的实现）删除操作的实现删除操作可以看作插入操作的逆操作；删除操作可以看作插入操作的逆操作；两者有很多相似的地方。两者有很多相似的地方。删除前后删除前后逻辑关系逻辑关系的变化的变化删除前：(e1，,ei-1，ei，ei+1，en)删除后：(e1，,ei-1，ei+1，en)我们看一个顺序存储的线性表删除的例子第 1章 绪 论 例如：线性表(4,9,15,21,28,30,30,42,51,62)删除第5个元素，如图2.4所示。删除算法的实现如下所示：图2.4 顺序表中删除元素 第 1章 绪 论 Status ListDelete_Sq(SqList&L,int i,ElemType&e)if(i L.length+1)return ERROR;p=&(L.elemi-1);/p为被删除元素的位置指针e=*p/获取被删除数据q=L.elem+L.length-1 /表尾元素位置for(+p;p=q;+p)*(p-1)=*p;/前移被删除元素后面的数据-L.lengthreturn OK/ListDelete_Sq第 1章 绪 论 4）插入和删除操作的算法复杂度分析）插入和删除操作的算法复杂度分析在时间上，两种操作算法的实现主要耗费在移动元素上；而移动元素的个数取决于插入或删除元素的位置！这意味着：很难用确定的量来衡量移动个数即问题的实际规模！如何计算其时间复杂度？第 1章 绪 论 假设假设pi是在第是在第i个元素之前插入一个元素个元素之前插入一个元素的概率的概率在第在第i个元素之前插入一个元素，需要移个元素之前插入一个元素，需要移动多少个元素？动多少个元素？n(i-1)则移动元素个数的期望是：则移动元素个数的期望是：第 1章 绪 论 同理，假设是删除第同理，假设是删除第i个元素的概率，则个元素的概率，则删除一个元素需要移动的元素个数的期删除一个元素需要移动的元素个数的期望值为：望值为：这两个结果说明：这两个结果说明：在顺序结构顺序结构的线性表中，插入或删除一个数据元素，平均移动表中一半元素！其时间复杂度为O(n)，n为表长。第 1章 绪 论 2.3 线性表的链式表示和实现线性表的链式表示和实现顺序表示的实质是用物理位置相邻来表顺序表示的实质是用物理位置相邻来表示逻辑上的相邻关系。示逻辑上的相邻关系。优点是：可是实现随机访问。优点是：可是实现随机访问。访问元素的时间开销小访问元素的时间开销小缺点是：插入和删除元素需要移动大量缺点是：插入和删除元素需要移动大量的数据元素。的数据元素。如何克服顺序表示的缺点呢？如何克服顺序表示的缺点呢？第 1章 绪 论 2.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 线性链表线性链表1.基本的概念基本的概念另一种方法：采用另一种方法：采用链式链式的存储结构！的存储结构！线性链表：用一组线性链表：用一组任意的任意的存储单元存储线性表的存储单元存储线性表的数据元素。数据元素。注意：注意：“任意的任意的”的存储单元可以的存储单元可以连续连续的，也可的，也可以是以是离散离散的！的！即使是连续的存储单元，其逻辑关系不一定是通即使是连续的存储单元，其逻辑关系不一定是通过位置相邻来体现。过位置相邻来体现。第 1章 绪 论 在链表中，如何体现元素之间的逻辑关系呢？在链表中，如何体现元素之间的逻辑关系呢？在存储每一个数据元素的存储单元中：在存储每一个数据元素的存储单元中：除了存储数据元素本身以外，还需要存储一个指示其直接后继的信息这个信息通常是后继元素的地址信息在C语言中，地址信息通过指针来实现数据元素在内存中，通过这些指针来维护它们之数据元素在内存中，通过这些指针来维护它们之间的间的逻辑关系逻辑关系形象地讲：这些指针就像一个链条一样把各个数形象地讲：这些指针就像一个链条一样把各个数据元素链接起来据元素链接起来这是链式表示名字的由来！这是链式表示名字的由来！第 1章 绪 论 在链表中，存储数据元素和指针的存储在链表中，存储数据元素和指针的存储单元称之为：结点（单元称之为：结点（node）结点的结构：结点的结构：数据域：存储数据元素指针域：存储后继结点后继结点的位置（地址）-指指针针或链链n个结点链结成一个链表，即为线性表的个结点链结成一个链表，即为线性表的链式存储结构。链式存储结构。当前，由于每个结点只包含一个指针域，当前，由于每个结点只包含一个指针域，故称为故称为线性链表线性链表或或单链表单链表第 1章 绪 论 例如，线性表例如，线性表(A,B,C,D,E,F,G,H)，其，其可能的一种链式存储结构如下：可能的一种链式存储结构如下：图2.6 单链表的示例图 第 1章 绪 论 图2.7 单链表的逻辑状态 图2.8 带头结点单链表图示 第 1章 绪 论 2.链表在链表在C语言中的实现语言中的实现typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList3.链表的基本操作的算法描述链表的基本操作的算法描述在顺序表中：当前位置+相对偏移量数据元素在链表中，随机访问特点不存在！第 1章 绪 论 1）GetElem操作（获得第操作（获得第i个元素）个元素）图2.8 带头结点单链表图示 第 1章 绪 论 Status GetElem_L(LinkList L,int i,ElemType&e)/L带头结点带头结点p=Lnext;j=1;/p为工作指针while(p&j i)return ERROR;/此条件是对whie循环条件的取反，除了j=ie=p data;return OK;/GetElem_L第 1章 绪 论 GetElem的算法分析的算法分析观察点是while循环While循环的语句频度与谁有关？与i的位置最坏情况，原操作的语句频度是n因此，其时间复杂度为O(n)第 1章 绪 论 2)ListInsert_L操作操作在第i个结点插入元素的逻辑关系变化情况图2.9 在单链表第i个结点前插入一个结点的过程 插入步骤和的顺序能否更改？第 1章 绪 论 Status ListInsert_L(LinkList&L,int i,ElemType e)p=L;j=0;while(p&j i-1)return ERROR;s=(LinkList)malloc(sizeof(Lnode);sdata=e;snext=p next;/注意这两个语句的顺序！p next=s;return OK;/ListInsert_L注意：此算法中可以复用注意：此算法中可以复用GetElem_L操作，但是需要做什么操作，但是需要做什么修改？修改？第 1章 绪 论 3)ListDelete_L操作操作图2.10 单链表的删除过程 第 1章 绪 论 Status ListDelete_L(LinkList&L,int i,ElemType&e)p=L;j=0while(pnext&j i-1)return ERROR;r=pnext;pnext=rnext;e=rdata;free(r);return OK;/ListDelete_L第 1章 绪 论 ListInsert_L和和ListDelete_L复杂度分析复杂度分析其时间复杂度的消耗主要还是定位的第i或i-1个元素上。因此，其时间复杂度与GetElem_L的相同T(n)=O(n)在在C语言中，数组是静态结构！语言中，数组是静态结构！在链表操作中，链表是动态结构：在链表操作中，链表是动态结构：在使用链表结构时，不需要预先分配充足的空间，可以根据需要动态增加或删除。第 1章 绪 论 4）CreateList_L操作操作根据链表动态性的特点，创建链表的过程是：创建空表，然后向链表中逐渐插入元素的过程建立链表的方式有两种：1.从表头向表尾方向建立链表2.从表尾向表头方向建立链表下面，我们给出第二种建立链表方式的算法第 1章 绪 论 Status CreateList_L(LinkList&L,int n)L=(LinkList)malloc(sizeof(LNode);Lnext=NULL;for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(Lnode);scanf(&pdata);pnext=Lnext;Lnext=p;/CreateList_L很明显，其时间复杂度为很明显，其时间复杂度为O(n)第 1章 绪 论 5)MergeList_L操作操作将有序链表LA和有序链表LB按照有序的方式合并到LC中。Status MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)pa=Lanext;pb=Lbnext;Lc=pc=La;while(pa&pb)if(padata=pbdata)pcnext=pa;pc=pa;pa=panext;elsepcnext=pb;pc=pb;pb=pbnext;pcnext=pa?pa:pb;free(Lb)/释放头结点/MergeList_L第 1章 绪 论 4.静态链表静态链表根据链表的定义：线性链表：用一组任意的存储单元存储线性表的数据元素。注意：“任意的”的存储单元可以连续的，也可以是离散的！如何在连续的存储空间（例如数组）上实现链表呢？第 1章 绪 论 分析：分析：1.链表的特点是插入和删除元素不需要移动后面的元素2.因此，我们用数组（或动态分配连续空间malloc）实现链表也要保证这个特点3.在数组中，存储位置相邻不代表逻辑位置相邻！4.把数组元素仍然看作结点5.在结点中，应该包含表示逻辑相邻的信息类似指针的东西。看一个例子第 1章 绪 论 图2.11 静态链表的插入和删除操作示例 第 1章 绪 论 静态链表的存储结构设计：静态链表的存储结构设计：#define MAXSIZE 1000Typedef structElemType data;int cur;/cursorcomponent,SLinkListMAXSIZE;第 1章 绪 论 图2.11 静态链表的插入和删除操作示例 第 1章 绪 论 静态链表的操作设计静态链表的操作设计int LocateElem_SL(SLinkList S,ElemType e)i=S0.cur;while(i&Si.data!=e)i=Si.cur;return i;/LocateElem_SL第 1章 绪 论 静态链表的操作设计静态链表的操作设计静态链表的其它操作静态链表的其它操作自学完成自学完成静态链表的一个实例就是静态链表的一个实例就是FAT表表第 1章 绪 论 2.3.2 循环链表（循环链表（circular linked list）单向链表的特点：每个结点都包含一个指单向链表的特点：每个结点都包含一个指向其后继的指针。向其后继的指针。其存在的问题：其存在的问题：从已知结点出发，它只能访问其后面的结点；如果想从已知结点出发，想访问链表中的如果想从已知结点出发，想访问链表中的任何结点，该如何做？任何结点，该如何做？把单链表中最后一个结点的把单链表中最后一个结点的next指向表头！指向表头！第 1章 绪 论 2.3.2 循环链表（循环链表（circular linked list）图2.12 带头结点循环单链表 第 1章 绪 论 2.3.2 循环链表（循环链表（circular linked list）在具体操作上：在具体操作上：在链表上进行遍历时，循环条件不是p或pnext是否为空，而是它们是否等于遍历起点的指针！第 1章 绪 论 2.3.3 双向链表双向链表单向链表的优点是：单向链表的优点是：插入和删除不需要移动其它元素缺点：缺点：失去随机访问的特点链表的普遍缺点访问当前结点下一个位置的复杂度为O(1)但是访问当前结点前一个位置的复杂度为O(n)如何克服这样的缺点？如何克服这样的缺点？第 1章 绪 论 2.3.3 双向链表双向链表2.3.3 双向链表（双向链表（double linked list）图2.13 双链表的结点结构 第 1章 绪 论 2.3.3 双向链表双向链表存储结构设计：存储结构设计：typedef struct DuLNodeElemType data;struct DuLNode *prior;struct DuLNode *next;DuLNode,*DuLinkList;第 1章 绪 论 2.3.3 双向链表双向链表在结构上：在结构上：可以有双向的循环链表。图2.14 双向循环链表图示 第 1章 绪 论 2.3.3 双向链表双向链表对于一般的双向链表，其结构上的特点，对于一般的双向链表，其结构上的特点，决定了如下关系：决定了如下关系：ppriornext=p=pnextprior第 1章 绪 论 2.3.3 双向链表双向链表在操作上：在操作上：和单链表类似，插入和删除结点，需要修改指针来表示逻辑关系的变化；但是修改的数量增加。和单链表类似，在修改指针时，要保证指针不丢失。对于其它的线性操作，例如：ListLength、GetElem和LocateElem等仅涉及一个方向的指针，其算法描述与单链表相同。第 1章 绪 论 1）双向表的插入操作）双向表的插入操作指针更改顺序由工作指针位置决定！指针更改顺序由工作指针位置决定！图2.15 双向链表插入操作 第 1章 绪 论 Status ListInsert_DuL(DuLinkList&L,int i,ElemType e)if(!(p=GetElemP_Dul(L,i)return ERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode)return ERROR;sdata=e;sprior=pprior;ppriornext=s;snext=p;pprior=s;return OK;/ListInsert_DuL第 1章 绪 论 2）双向链表的删除操作）双向链表的删除操作图2.16 双向链表的删除操作 第 1章 绪 论 Status ListDelete_DuL(DuLinkList&L,int i,ElemType&e)if(!(p=GetElemP_Dul(L,i)return ERROR;e=pdata;ppriornext=p next;pnextprior=p prior;free(p);return OK;/ListDelete_DuL第 1章 绪 论 链表总结链表总结优点：优点：1.空间的合理利用2.插入、删除时不需要移动元素缺点：缺点：实现某些操作代价大，例如：求线性表长度。第 1章 绪 论 2.4 一元多项式的表示和相加一元多项式的表示和相加大家自学教材中大家自学教材中2.4节中的内容节中的内容从以下几个方面考虑：从以下几个方面考虑：1.如何把多项式用线性表抽象出来2.如何进行顺序表示和链接表示3.在两种表示上，如何实现相加操作谢谢大家！结结 语语