数据结构线性表

1、第二章第二章线性表线性表2.1 线性表的逻辑结构线性表的逻辑结构2.2 线性表的顺序存储结构线性表的顺序存储结构2.3 线性表的链式存储结构线性表的链式存储结构2.4 一元多项式的表示及相加一元多项式的表示及相加通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。 2.1线性表的逻辑结构线性表的逻辑结构第二章 线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继是一种最简单的是一种最简单的线

2、性结构的定义：线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。接后继。 可表示为：（可表示为：（a a1 1 , a, a2 2 , , a, , an n） 简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 的。的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特点特点 除首尾结点外，其他结点只有一个直接前驱和一个除首尾结点外，其他结点只有一个直接前驱和一个直接后继。直接后继。线

3、性结构包括：线性结构包括：线性表、堆栈、队列、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-一对一一对一 (1:1)2.1 线性表的基本概念线性表的基本概念、线性表、线性表它是一种最简单的线性结构。是一种可以在任它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由意位置进行插入和删除数据元素操作的，由n（n0)个相同类型数据元素个相同类型数据元素a0, a1, , an-1组成的线性组成的线性结构。结构。（a0, a1, ai-1，ai, ai1 ，, an-1）n=0时称为时称为数据元素数据元素线性起点线性起点ai

4、的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。空表空表线性终点线性终点 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级012003010622陈建武陈建武男男 192003级电信级电信0301班班012003010704赵玉凤赵玉凤女女 182003级电信级电信0302班班012003010813王王 泽泽男男 192003级电信级电信0303班班012003010906薛薛 荃荃男男 192003级电信级电信0304班班0120030110

5、18王 春男 19 192003级电信级电信0305班班： ：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析： 数据元素都是同类型数据元素都是同类型（字母字母），）， 元素间关系是线性的元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。 强调强调 本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储数据结构？如何在计算机上实现对数

6、据结构的各种操作，为此，我们将用计算机语言来描述数据的存储结构，用计算机语言来描述这些操作的算法，本课程我们用类C语言做为描述语言。 线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。数据结构有两种存储方式: 顺序存储，链式存储， 线性表也可以用这两种方法实现。在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。下面我们分别讨论这两种存储结构以及对应存储结构下实现各操作的算法。线性表的存储结构线性表的存储结构(1)顺序存储结构顺序存储结构: :它是使用一片它是使用一片地址地址连续的有限内存单连续的有限内存单元空间存储数据元素的一

7、种计算机存储数据方法。元空间存储数据元素的一种计算机存储数据方法。特点：特点：( (任意两个在逻辑上相邻的数据元素在物理位置任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻上也必然相邻) )逻辑上相邻的元素，物理上也相邻。逻辑上相邻的元素，物理上也相邻。(2)(2)链式存储结构链式存储结构: :它是把数据元素和指针定义成一个它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。的一种计算机存储数据方法。特点：特点：任意两个在任意两个在逻辑上相邻逻辑上相邻的数据元素在的数据元素在物理上不物理上不一定相邻

8、一定相邻，数据元素的逻辑次序是通过链中的指针，数据元素的逻辑次序是通过链中的指针链接实现的。链接实现的。2.2线性表的顺序存储结构线性表的顺序存储结构2.2.1 顺序表顺序表2.2.2 顺序表上实现的基本运算顺序表上实现的基本运算2.2 线性表的顺序存储和实现如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？2.2.1 顺序表顺序表一、一、 顺序表的存储结构表示顺序表的存储结构表示 1、顺序表顺序表：用一组用一组地址连续地址连续的存储单元依次存储线的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数

9、据元素的存储。表。它通常采用静态数组实现数据元素的存储。可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即： VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-1(1) 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；(2) 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。）。设首元素设首元素a0的存放地址为的存放地址为LOC(a0)（称为称为首地址首地址），），设

10、每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC ( ai+1 ) = LOC( ai ) + L 对上述公式的解释如图所示对上述公式的解释如图所示2 2、线性表顺序存储特点：、线性表顺序存储特点：a a0 0a a1 1a ai ia ai+1i+1a an-1n-1 地址地址 内容内容 元素在表中的位序元素在表中的位序0 0i i1 1n-1n-1空闲区空闲区i+1i+1Lb=LOC(a0)b + + L Lb +i+iL Lb +(n-1)+(n-1)L Lb +(MaxSize-

11、1)+(MaxSize-1)L L3、线性表的顺序存储结构示意图、线性表的顺序存储结构示意图4 4、用、用C C语言描述语言描述 typedef struct DateType listMaxSize; int size; SeqList; /* MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size MaxSize，SeqList是该结构体的名字。*/设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数组元素用相邻的每个数组元素用相邻的个字节个字节存储。存储器存储。存储器按字节编址，设存储数组元素按字节编址

12、，设存储数组元素 的第一个的第一个字节的地址是字节的地址是，则，则 的第一个字节的的第一个字节的地址是多少？地址是多少？113LOC( M3 ) = 98 + 5 3 =113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai) = LOC(a0) + L *i例例1 1 char V30;void build() /*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心语句：核心语句：例例2用数组用数组V来存放来存放26个英文字母组成的线性表个英文字母组成的线性表（a，b，c，z）

13、，写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C语言程序。语言程序。void main(void) /*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/ n=26; /* n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build( );display( );void display( ) /*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/ int i;for( i=0; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一个位置元素后移一个位置/ / 插入插入

14、x x / / 表长加表长加1 1 核核心心语语句：句：2)2)插入插入在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：1213212428304277121321242830427712345678123456789插入插入在一个顺序表中第i个元素之前插入一个元素x的函数： 顺序表的删除：顺序表的删除：n删除操作分为相应两个阶段，只是顺序与前者相反：第一阶段先执行数据元素的删除，第二阶段再移动数据将空挡填上。删除算法示意：将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。 序号123456781094915

15、212830304262514915213030425162删除28后内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2实现步骤：实现步骤：n将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；n表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for ( j=i+1; jdata=; p-next= ; 方式方式3： p指向结点首地

16、址，然后指向结点首地址，然后 (*p).data=； (*p).nextb线性链表31LI43QIAN13SUN1WU37WANGNULLZHAO7ZHENG19ZHOU2517133719253143头指针heada1a2a3an-1an ppdata等于a2 pnextdata等于a3 设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针, ,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址附附1：介绍介绍C的三个有用的库函数的三个有用的库函数/算符（都在算符（都在 中）：中

17、）：sizeof(x)计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(m) 开辟开辟m m字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(p) 释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。sizeof(x)计算计算x x的长度的长度malloc(m) 开开m m字节字节空间空间free(p) 删除一个变量删除一个变量问问1：自定义结构类型变量自定义结构类型变量node的长度的长度m是多少？是多少？问问2：结构变量结构变量node的首地址的首地址(指针指针p）是多少

18、？）是多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长度为m字节字节pmsizeof(node) /单位是字节单位是字节p(node*)malloc(m)free(p) /只能借助只能借助node的指针删除！的指针删除！P-data=a; p-P-data=a; p-next=qnext=q 对于指向结构类型的指针变量，可说明为：对于指向结构类型的指针变量，可说明为： *p, *q; /或用或用 struct *p , *q; /注：上面已经定义了注：上面已经定义了node为用户自定义的为用户自定义的liuyuliuyu类型。类型。 类型定义和变量说

19、明可以合写为：类型定义和变量说明可以合写为： liuyu /liuyu/liuyu是自定义结构类型名称是自定义结构类型名称 char data; /定义数据域的变量名及其类型定义数据域的变量名及其类型 liuyu *next; /定义指针域的变量名及其类型定义指针域的变量名及其类型node，*pointer; /node/node是是liuyuliuyu结构类型的类型替代结构类型的类型替代, , * *pointerpointer是指针型的是指针型的liuyuliuyu结构类型的替代，也是数据类型结构类型的替代，也是数据类型* */ /附附2： 补充结构数据类型的补充结构数据类型的C表示法表示

20、法2.3.1 单链表单链表n实现typedef struct node datatype data; struct node *link;JD;JD *h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD *)malloc(sizeof(JD);系统回收p结点：free(p)总结线性链表n定义：结点中只含一个指针域的链表叫，也叫单链表n 链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，

21、只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。n在C语言中，实现线性表的链式存储结构的类型定义typedef strcut node /结点类型定义 EntryType item; /结点的数据域 struct node *next; /结点的指针域NODE;typedef struct /链表类型 NODE *head;LINK_LIST;请注意：请注意：TypedefTypedef不可能创造不可能创造任何新的数据类型，而仅仅是任何新的数据类型，而仅仅是在原有的数据类型中

22、命名一个在原有的数据类型中命名一个新名字，其目的是使你的程序新名字，其目的是使你的程序更易阅读和移植。更易阅读和移植。2.3.2单链表上的基本运算单链表上的基本运算2.3.2 单链表上的基本运算单链表上的基本运算n线性表的基本运算：建立单链表 单链表查找 单链表插入操作 1.单链表删除 （1） 单链表的建立和输出单链表的建立和输出例：用例：用单链表单链表结构来存放结构来存放26个英文字母组成的线个英文字母组成的线性表（性表（a，b，c，z）,请写出请写出C语言程序。语言程序。实现思路：实现思路：先开辟头指针，然后陆续为每个结点开辟存储先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继

23、结点的地址要空间并及时赋值，后继结点的地址要提前提前送给前面的指针。送给前面的指针。先挖先挖“坑坑”, ,后种后种“萝萝卜卜”！typedef struct nodechar data; struct node *next;node; node *p,*q,*head; /一般需要一般需要3 3个指针变量个指针变量int n ; / / 数据元素的个数数据元素的个数int m=sizeof(node); / /* *结构类型定义好之后，每个变量结构类型定义好之后，每个变量的长度就固定了，的长度就固定了，m m求一次即可求一次即可* */ /将全局变量及函数提前说明：将全局变量及函数提前说明：新

24、手特别容易忘记！新手特别容易忘记！ int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出前面已求出p=head;for( i=1; idata=i+a-1; / 第一个结点值为字符第一个结点值为字符ap-next=(node*)malloc(m); /为后继结点为后继结点“挖坑挖坑”！p=p-next； /让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1; /最后一个元素要单独处理最后一个元素要单独处理p-next=NULL ; / /单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void build( ) /

25、字母链表的生成字母链表的生成。要一个个慢慢链入要一个个慢慢链入p=head;while (p) /当指针不空时循环，仅限于当指针不空时循环，仅限于无头结点无头结点的情况的情况 printf(%c,p-data); p=p-next; /让指针不断让指针不断“顺藤摸瓜顺藤摸瓜” sum+;sum+;sum=0;sum=0;void display() /*字母链表的输出字母链表的输出*/n单链表的基本运算查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL 算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n nOnTpabxs 算法评价插入：

26、在线性表两个数据元素a和b间插入x，已知p指向as-link=p-link;p-link=s; 1OnT 算法描述 算法评价在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xsabp链表插入的核心语句：链表插入的核心语句：p-nexts-nextX X 结点的生成方式：结点的生成方式：s=(node*)malloc(m);s-data=X X ;s-next= ?bapX X （3） 单链表的插入单链表的插入 算法描述pabc 1OnT 算法评价删除：单链表中删除b，设p指向ap-link=p-link-link;在链表中删除某元素在链表中删除某元素b b的示意

27、图如下：的示意图如下：c a bp删除动作的核心语句删除动作的核心语句（要借助辅助指针变量（要借助辅助指针变量q q）：）：q = p-next; /首先保存首先保存b b的指针，靠它才能找到的指针，靠它才能找到c c；p-next=q-next; /将将a a、c c两结点相连，淘汰两结点相连，淘汰b b结点；结点；free(q) ； /彻底释放彻底释放b b结点空间结点空间p-next思考：思考： 省略省略free(q)语句语句行不行？行不行？(p-next) - nextq（4） 单链表的删除单链表的删除 nOnT动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为

28、头指针 算法描述 算法评价h头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0Ch2_3.ch头结点0n单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。链表的运算效率分析链表的运算效率分析（1） 查找查找 因线性链表只能顺序存取，即在查找时要从头指针找起，因线性链表只能顺序存取，即在查找时要从头

29、指针找起，查找的时间复杂度为查找的时间复杂度为 O(n)。时间效率分析时间效率分析（2） 插入和删除插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为间复杂度为 O(1)。但是，如果要在单链表中进行但是，如果要在单链表中进行前前插或删除操作，因为要插或删除操作，因为要从头查找前驱从头查找前驱结点，所耗时间复杂度将是结点，所耗时间复杂度将是 O(n)。空间效率分析空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增链表中每个结点都要增加一个指针空间，相当于总共增加了加了n 个整型变量，空间复杂度为个整型变量，空间

30、复杂度为 O(n)。在在n n个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点* *P P，需找到它，需找到它的的 ，其时间复杂度为，其时间复杂度为 。 O(n)O(n)练习：练习：2.3.3 循环链表循环链表2.3.3 循环链表循环链表循环链表循环链表(Circular Linked List) 是一个首尾相接的链表。 特点特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。 最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 . an 2. 循环链表

31、循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。循环链表(circular linked list)n循环链表是表中最后一个结点的指针指向头结点，使链表构成环状n特点：从表中任一结点出发均可找到表中其他结点，提高查找效率n操作与单链表基本一致,循环条件不同，只是判断链表结束的条件有所不同。单链表p或p-link=NULL循环链表p或p-link=Hhh空表2.3.4 双链表双链表2.3.3 双向循环链表n 在在循环链表循环链表中，访问结点的中，访问结点的特点特点: :访问后继结点，只需要向后走一步，而访问前驱结点，就需访问后继结点，

32、只需要向后走一步，而访问前驱结点，就需要转一圈。要转一圈。n结论结论：循环链表并不适用于经常访问前驱结点的情况。：循环链表并不适用于经常访问前驱结点的情况。n解决方法解决方法：在需要频繁地同时访问前驱和后继结点的时：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。候，使用双向链表。n所谓所谓双向链表双向链表：双向链表就是每个结点有两个指针域。一个指向后继结点，双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。另一个指向前驱结点。双链表的结构定义n双链表的结点结构 后继指针域prior data next前驱指针域数据域例：在双向链表中如何实现插入和删除运算？例：在

33、双向链表中如何实现插入和删除运算？单链表中查找只能从前往后，而不能从后往前查。单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表，一个指针域，用来存结点的直接前驱，这样的链表，称为称为双向链表。双向链表。其其结点的结构结点的结构为：为：prior data nexttypedef struct DuLNode ElemType data; /数据域数据域 struct DuLNode *prior; /前驱指针域前驱指针域 struct DuLNode *next; /

34、后继指针域后继指针域 DuLNode , *DuLinkList ; 双向链表类型的定义如下：双向链表类型的定义如下：双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . an双链表的定义：双链表的定义：n采用C语言描述的双链表，如下： 双链表的定义和特点双链表的定义和特点n双（向）链表双（向）链表（Double Linked List）：有两种不同方向链的链表称为双向循环链表。 n双链表特点：双链表的每一个结点除含数据域外，还有两个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点。可以给双链表加一表头结点。双链表可以循环，也可以不循环 n双链表和单链表相比，每一个结点增加了一

35、个指针域，双向链表虽然多占用了空间，但它给数据运算带来了方便 双向链表（double linked list）单链表具有单向性的缺点n结点定义typedef struct node datatype element; struct node *prior,*next;JD;priorelementnextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;bcaPvoid del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);n删除算法描述算法评价：T(

36、n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;void ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;算法描述算法评价：T(n)=O(1)xSbaPn插入双向链表的操作特点：双向链表的操作特点：“查询查询” ” 和单链表相同。和单链表相同。“插入插入” ” 和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。上述两个算法的

37、时间复杂度均为O(1)。双向链表双向链表 （加一个指向前驱的指针）（加一个指向前驱的指针）n每个结点的后继的前驱就是他本身，前驱的后继也是他本身。n优点：找当前指针的前驱找当前指针的前驱这个基本操作就是常量级的，而不是线性级的了。所以如果在线性表的使用中，不但找后继还要找前驱的情况下就可用双向链表来实现。n插入删除时，不但要修改后继修改后继，还要修改前驱修改前驱。 链式存储结构的优点和缺点n链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。n但是链式存储结构也有不足之处：（1）每个结点中的指针域需额外占用存储空间

38、。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重就显得很大。（2）链式存储结构是一种非随机存储结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。2.3.5顺序表和链表的比较顺序表和链表的比较2.3.5 顺序表和链表的比较顺序表和链表的比较 n1基于空间的考虑 n2基于时间的考虑 顺序表和链表的比较n基于空间的考虑基于空间的考虑 当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。 当线性表的长度变化不大，易于事先确定其大小，为了节约存储空间，宜采用顺序表作为存储结构。 存储密度存储密度（Storage Density）：是指结点

39、数据本身所占的存储量和整个结点结构所占的存储量之比。 基于时间的考虑基于时间的考虑 若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。 对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn)每一项的指数I隐含在他系数pi的序号中一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是

40、否合适？的多项式，上述表示方法是否合适？n但是对于形如S(x) = 1 + 3x10000 2x20000 的多项式，上述表示也就不恰当了。因为只有三个非零项，这样一个一个的写下去，非常浪费内存空间。因为我们只想表示非零项，零项表示出来也没什么用 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 exp与q-expp-exp exp: p结点是和多项式中的一项 p后移,q不动p-exp q-exp: q结点是和多项式中的一项 将q插在p之前,q后移,p不动p-exp =

41、q-exp: 系数相加0：从A表中删去p, 释放p,q，p,q后移0：修改p系数域, 释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可运算规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8

42、 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 Ch2_7.c算法描述两个两个多项式相加算法实现void polyadd(Polylist polya;Polylist polyb) /* p和q分别指向polya和polyb链表中的当前计算结点*/ /* pre指向和多项式链表中的尾结点*/ while p!=NULL & q!=NULL） if （p-expexp） /*将p结点加入到和多项式中*/ else if ( p-exp

43、= =q-exp） /*若指数相等，则相应的系数相加。若系数为0则删除p，q节点*/ else /*将q结点加入到和多项式中*/ ./*将多项式polya或polyb中剩余的结点加入到和多项式中*/本章小结本章小结线性结构线性结构( (包括表、栈、队、数组）的定义和特点：包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。直接后继。2. 2. 线性表线性表逻辑结构逻辑结构：“一对一一对一” ” 或或 “ “1:1”1:1”存储结构存储结构：顺序、链式顺序、链式运运 算：算：修改、插入、删除修改、插入、删除3.

44、3.顺序存储顺序存储特征特征：逻辑上相邻，物理上也相邻；逻辑上相邻，物理上也相邻；优点优点：随机查找修改快随机查找修改快 O(1)O(1)缺点缺点：插入、删除慢插入、删除慢 O(n)O(n)改进方案：改进方案：循环链表的特点：循环链表的特点：双向链表的特点：双向链表的特点：可方便可方便静态链表的特点：静态链表的特点：不用指针也能实现链式存储和运算不用指针也能实现链式存储和运算4.4.链式存储链式存储特征特征：逻辑上相邻，物理上未必相邻；逻辑上相邻，物理上未必相邻；优点优点：插入、删除快插入、删除快 O(1)O(1)缺点：缺点：随机查找修改慢随机查找修改慢 O(n)O(n)5.5.几种特殊链表的

45、特点：几种特殊链表的特点：讨论讨论1 1： 顺序存储和链式存储的区别和优缺点？顺序存储和链式存储的区别和优缺点？顺序存储时，顺序存储时，逻辑上相邻的数据元素，其物理存放地址逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。缺点是插入或删除元素时不方便。链式存储时，链式存储时，相邻数据元素可随意存放，但所占存储空相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优

46、点是插入或删除元素时很方便，关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。使用灵活。缺点是存储密度小，存储空间利用率低。顺序表顺序表适宜于做适宜于做查找查找这样的静态操作；这样的静态操作；链表链表宜于做宜于做插插入、删除入、删除这样的动态操作。若这样的动态操作。若线性表的长度变化不大线性表的长度变化不大，且，且其主要操作是查找，则采用顺序表；若其主要操作是查找，则采用顺序表；若线性表的长度变化线性表的长度变化较大较大，且其主要操作是插入、删除操作，则采用链表。，且其主要操作是插入、删除操作，则采用链表。本章小结本章小结 本章主要介绍了如下一些

47、基本概念： 线性表线性表：一个线性表是n0个数据元素a0，a1，a2，an-1的 有限序列。线性表的线性表的顺序存储结构顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构线性表的线性表的链式存储结构链式存储结构：线性表的链式存储结构就是用一组任意的存储单元结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。 循环链表循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从

48、表中任一结点出发都可找到表中其他的结点。 双向链表双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。 除上述基本概念以外，学生还应该了解： 线性表的基本操作（建立、插入、删除、查找） 线性表的顺序存储结构的表示、 线性表的链式存储结构的表示、 一元多项式Pn(x)， 掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。 第二章 线性表小结 本章学习了线性表的本章学习了线性表的顺序存储结构顺序存储结构顺序表顺序表，链式存链式存储结构储结构线性链表线性链表、循环链表循环链表、 双向链表双向链表，以及在这两种，以及在这两种存储结构下如何实现线性表的存储结构下如何实现线性表的基本操作基本操作。这里再一次需要强。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表，