数据结构第二章线性表

1、 数据结构课程本章内容2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加中国科大数据结构2-3 线性结构分类p直接访问型直接访问型( direct access )p顺序访问型顺序访问型(sequential access) p目录索引型目录索引型(directory access) 中国科大数据结构2-4 线性结构分类中国科大数据结构2-5 2.1 线性表的逻辑结构p定义定义：线性表：线性表(Linear List)是由是由n个数据元素的有限序列组成。其中数据个数据元素的有限序列组成。其中数据元素的个数元素的个数n 定义为表的长

2、度。当定义为表的长度。当 n=0 时称为空表，常常将非空的线性时称为空表，常常将非空的线性表表(n0)记作：记作：(a1，a2，an)这里的数据元素这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况只是一个抽象的符号，其具体含义在不同的情况下可以不同。下可以不同。p性质性质：线性表（：线性表（N , r）：）：a)结点集结点集N中有唯一的开始结点，它没有前驱，但有唯一的后继；中有唯一的开始结点，它没有前驱，但有唯一的后继；b)有限集有限集N它存在唯一的终止结点，该结点有唯一的前驱而没有后继；它存在唯一的终止结点，该结点有唯一的前驱而没有后继；c)其它的结点皆称为内部结点，每

3、一个内部结点既有一个唯一的前驱，其它的结点皆称为内部结点，每一个内部结点既有一个唯一的前驱，也有一个唯一的后继；也有一个唯一的后继；d)线性表所包含的结点个数称为线性表的长度，长度为线性表所包含的结点个数称为线性表的长度，长度为0的线性的线性表称为空表；表称为空表；e)线性表的关系线性表的关系r，简称前驱关系，应具有反对称性和传递性。，简称前驱关系，应具有反对称性和传递性。中国科大数据结构2-6 2.1 线性表的逻辑结构例例1、26个英文字母组成的字母表个英文字母组成的字母表 (A，B，C、Z) 是一个线性是一个线性表，其中的元素是单个字母字符。表，其中的元素是单个字母字符。例例2、某校从、某

4、校从1978年到年到1983年各种型号的计算机拥有量的变化情况，年各种型号的计算机拥有量的变化情况，可以用线性表的形式给出：可以用线性表的形式给出： （6，17，28，50，92，188）更为复杂的线性表中，一个数据元素可以有若干个数据项更为复杂的线性表中，一个数据元素可以有若干个数据项(item)组组成。在这种情况下，长把数据元素称为记录成。在这种情况下，长把数据元素称为记录(record)，含有大量记，含有大量记录的线性表又称为文件录的线性表又称为文件(file)。中国科大数据结构2-7 姓名姓名学号学号性别性别年龄年龄班级班级王小林王小林790631790631男男1818计算机计算机0

5、808陈红陈红790632790632女女2020计算机计算机0808刘建平刘建平790633790633男男2121计算机计算机0808张立立张立立790634790634男男1717计算机计算机08082.1 线性表的逻辑结构例例3 3、学生健康情况登记表如下表。表中每一个学生的情况为一、学生健康情况登记表如下表。表中每一个学生的情况为一个记录，它由姓名、学号、性别、年龄和班级等个记录，它由姓名、学号、性别、年龄和班级等5 5个数据项组成。个数据项组成。中国科大数据结构2-8 2.1 线性表的逻辑结构以上几个例子都是线性表的例子，都满足线性表的性质。以上几个例子都是线性表的例子，都满足线性

6、表的性质。p线性表是一种典型的线性结构。线性表是一种典型的线性结构。n数据的运算是定义在逻辑结构上的，而运算的具体实现则是在数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。存储结构上进行的。n抽象数据类型的定义为：抽象数据类型的定义为：P19中国科大数据结构2-9 线性表类模板template class list /线性表类模板线性表类模板list，模板参数，模板参数ELEM/1. 线性表的取值类型：线性表的取值类型：/元素的类型为元素的类型为ELEM，是本，是本list类模板的类模板的模板参数模板参数ELEM。/本线性表用的最大长度为本线性表用的最大长度为Max_l

7、ength；/2. 名字空间，使用变量访问线性表的方名字空间，使用变量访问线性表的方法：法：/用用curr +或或 curr-控制线性表游标控制线性表游标curr的前后游走。的前后游走。/用公共变量用公共变量curr_len指示线性表的尾部，指示线性表的尾部，/并导出表的当前长度，并导出表的当前长度，等。等。/ 3. 运算集：请参看下面的成员函数运算集：请参看下面的成员函数private: /私有变量，线性表的存储空间私有变量，线性表的存储空间 /Max_length线性表的最大长度线性表的最大长度public:int curr_len; /线性表的当前长度线性表的当前长度int curr;

8、/线性表的当前指针线性表的当前指针list(); / 创建一个空的新线性表创建一个空的新线性表list(); /从计算机存储空间删去整个线性表从计算机存储空间删去整个线性表 /将该线性表的全部元素清除，成为空表将该线性表的全部元素清除，成为空表 void clear() ;/ 尾附算子，在表的尾部添加一个新元素，尾附算子，在表的尾部添加一个新元素，参参/数数value作为元素内容（数据类型为作为元素内容（数据类型为/ELEM），表的长度加），表的长度加1void append(ELEM value) ;/插入算子，整数插入算子，整数i指出第指出第i号位置，参数号位置，参数value/作为元素内

9、容（数据类型为作为元素内容（数据类型为T），该位），该位置上置上/插入一个新结点，表的长度加插入一个新结点，表的长度加1。第。第i号号位置后位置后/的元素后移的元素后移void insert(int i, ELEM value) ;/删除算子，删去第删除算子，删去第i号元素，表的长度减号元素，表的长度减1，其后元素前移，其后元素前移void remove(int i); /读取，返回第读取，返回第i个元素的值个元素的值ELEM fetch(int i); 中国科大数据结构2-10 2.1 线性表的逻辑结构p算法算法2.12.1例例2-1 2-1 利用两个线性表利用两个线性表LALA和和LBLB

10、分分别表示两个集合别表示两个集合A A和和B B，现要求一，现要求一个新的集合个新的集合A=ABA=AB。1.1. 初值初值 获取线性表获取线性表LALA和和LBLB2.2. 合并线性表合并线性表 对于对于LBLB中的中的每一个元素每一个元素x x做如下操作：做如下操作： 若若(x(x不属于不属于LALA） 则将则将x x插入到插入到LALA的末尾的末尾3.3. 算法结束算法结束 void union(List &La，List Lb) La_len = Listlength(La); Lb_len = Listlength(Lb); for (i=1;i=Lb_len;i+) Get

11、Elem(Lb，i，e); if (!LocateElem(La，e，equal) ListInsert(La，+La_len，e); 中国科大数据结构2-11 2.1 线性表的逻辑结构p算法算法2.22.2例例2-2 2-2 巳知线性表巳知线性表LALA和线性表和线性表LBLB中的数据元素按值非递减有序排中的数据元素按值非递减有序排列，现要求将列，现要求将LALA和和LBLB归并为一个新的线性表归并为一个新的线性表LCLC，且，且LCLC中的元素仍按中的元素仍按值非递减有序排列。值非递减有序排列。p此问题的算法：此问题的算法：1.初值初值 获取线性表获取线性表LA和和LB，并构造空线性表，并

12、构造空线性表LC2.选择插入元素选择插入元素 对于线性表对于线性表LA和和LB，都从其第一个元素开始做如，都从其第一个元素开始做如下操作直到其中一个线性表元素全部遍历完毕：下操作直到其中一个线性表元素全部遍历完毕： 若若 （LA的元素的元素a=LB的元素的元素b） 则则 将元素将元素a插入到插入到LC的末尾，并选择的末尾，并选择LA中的下一个元素中的下一个元素a 否则否则 将元素将元素b插入到插入到LC的末尾，并选择的末尾，并选择LB中的下一个元素中的下一个元素b3.补充剩下的元素补充剩下的元素 若若 （LA还有剩余元素）还有剩余元素） 则则 将将LA的剩余元素全部插入到的剩余元素全部插入到L

13、C末尾末尾 若若 （LB还有剩余元素）还有剩余元素） 则则 将将LB的剩余元素全部插入到的剩余元素全部插入到LC末尾末尾4.算法结束算法结束中国科大数据结构2-12 void MergeList(List La, List Lb, List &Lc) InitList(Lc); i=j=1;k=0; La_len=ListLength(La); Lb_len=ListLength(Lb); while ( (i=La_len) & (j=Lb_len) ) GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai=bj) ListInsert

14、(Lc, +k, ai);+i; else ListInsert (Lc, +k, bj); +j; while (i=La_len) /若（若（LA还有剩余元素）则还有剩余元素）则 将将LA的剩余元素全部插入到的剩余元素全部插入到LC末尾末尾 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j=Lb_len) /若若 （LB还有剩余元素）还有剩余元素） 则则 将将LB的剩余元素全部插入到的剩余元素全部插入到LC末尾末尾 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); 2.1 线性表的逻辑结构中国

15、科大数据结构2-13 算法复杂性分析p算法算法2.1 n外重循环为外重循环为ListLength(LB)n循环内语句循环内语句LocateElem()的时间复杂度为的时间复杂度为O(ListLength(LA)n总为总为O(ListLength(LA)*ListLength(LB)p算法算法2.2 n根据算法的执行过程，算法访问根据算法的执行过程，算法访问LA和和LB的每个元素有仅只有一的每个元素有仅只有一次次nO(ListLength(LA)+ListLength(LB)中国科大数据结构2-14 2.2 线性表的顺序存储结构p2.2.1 2.2.1 线性表线性表 把线性表的结点按逻辑顺序依次

16、存放在一组地址连续的存储把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。单元里。用这种方法存储的线性表简称顺序表。 假设线性表的每个元素需占用假设线性表的每个元素需占用l l个存储单元，并以所占的第一个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第个单元的存储地址作为数据元素的存储位置。则线性表中第I+1I+1个个数据元素的存储位置数据元素的存储位置LOC( a LOC( a i+1i+1) )和第和第i i个数据元素的存储位置个数据元素的存储位置LOC(aLOC(ai i) )之间满足下列关系：之间满足下列关系： L

17、OC(aLOC(a i+1i+1)=LOC(a)=LOC(a i i)+l)+l 线性表的第线性表的第i i个数据元素个数据元素a ai i的存储位置为：的存储位置为： LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)* *l l中国科大数据结构2-15 2.2 线性表的顺序存储结构p由于由于C C语言中的一维数组也是采用顺序存储表示，故可以用数组类语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为顺序表还应该用一个变量来表示线性表的型来描述顺序表。又因为顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类

18、型。长度属性，所以我们用结构类型来定义顺序表类型。#define LIST_INIT_SIZE 100 /初始分配量初始分配量#define LISTINCREMENT 10/分配增量分配增量typedef int ElemType;typedef struct ElemType *elem; /基址基址 int length; /当前长度当前长度 int listsize; /当前分配的存储容量当前分配的存储容量 Sqlist;中国科大数据结构2-16 2.2 线性表的顺序存储结构初始化操作：初始化操作：Status InitList_Sq(Sqlist &L)L.elem = (E

19、lemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;中国科大数据结构2-17 2.2 线性表的顺序存储结构p2.2.2 2.2.2 顺序表上实现的基本操作顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第表的构造、第i i个元素的访问。个元素的访问。 注意：注意：C C语言中的数组下标从语言中的数组下标从“0”

20、0”开始，因此，若开始，因此，若L L是是SqlistSqlist类类型的顺序表，则表中第型的顺序表，则表中第i i个元素是个元素是L.elemi-1L.elemi-1。 以下主要讨论线性表的插入和删除两种运算。以下主要讨论线性表的插入和删除两种运算。1 1、插入、插入 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i(1in+1i(1in+1个位置上，插入一个个位置上，插入一个新结点新结点x x，使长度为使长度为n的线性表的线性表 (a1, a i-1, ai, ，an) 变成长度为变成长度为n+1的线性表的线性表(a1, a i-1, x，ai, , an)见见P23图图2.3中

21、国科大数据结构2-18 2.2 线性表的顺序存储结构1.初值初值 获取线性表获取线性表L，插入位置，插入位置i，插入元素，插入元素e2.检查参数检查参数 若若 （插入位置超出线性表长度范围）（插入位置超出线性表长度范围） 则则 输出错误输出错误 3.检查空间检查空间 若若 （线性表空间不足）（线性表空间不足） 则则 分配新空间分配新空间 若若 （分配成功）（分配成功） 则则 修改线性表的容量修改线性表的容量 否则否则 输出溢出错误输出溢出错误4.插入元素插入元素 将插入位置将插入位置 i 以及其后的以及其后的 L 中的元素全部后移一格中的元素全部后移一格 将元素将元素e插入位置插入位置I, 线

22、性表长度增加线性表长度增加15.算法结束算法结束中国科大数据结构2-19 2.2 线性表的顺序存储结构p算法的复杂度分析算法的复杂度分析这里的问题规模是表的长度，设它的值为这里的问题规模是表的长度，设它的值为n n。该算法的时间主。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是的次数）是n-i+1n-i+1。由此可看出，所需移动结点的次数不仅依赖于。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。表的长度，而且还与插入位置有关。当当i=n+1i=n+1时，由于循环变量的终值大于

23、初值，结点后移语句将时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度不进行；这是最好情况，其时间复杂度O(1)O(1)；当当i=1i=1时，结点后移语句将循环执行时，结点后移语句将循环执行n n次，需移动表中所有结点，次，需移动表中所有结点，这是最坏情况，这是最坏情况，其时间复杂度为其时间复杂度为O（n）。）。中国科大数据结构2-20 2.2 线性表的顺序存储结构 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。在长度为在长度为n的线性表中第的线性表中第i个位置上插入一个结点，令个位置上

24、插入一个结点，令Eis(n)表示移动结点的表示移动结点的期望值（即移动的平均次数），设期望值（即移动的平均次数），设pi是在第是在第i个位置插入元素的概率，则在个位置插入元素的概率，则在第第i个位置上插入一个结点的移动次数为个位置上插入一个结点的移动次数为n-i+1。故。故 不失一般性，假设在表中任何位置不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，上插入结点的机会是均等的，则则 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情况下，因此，在等概率插入的情况下，中国科大数据结构2-21 2.2 线性表的顺序存储结构也就是说，在顺序表上做插入运算，平均

25、要移动表上一半结点。也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长当表长 n n较大时，算法的效率相当低。虽然较大时，算法的效率相当低。虽然E Eisis(n(n) )中中n n的系数较小，的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为为O(nO(n) )。中国科大数据结构2-22 2.2 线性表的顺序存储结构2、删除、删除 线性表的删除运算是指将表的第线性表的删除运算是指将表的第i(1in)结点删除，使长度为结点删除，使长度为n的线性表：的线性表：(a1，a i-1，ai，a i+1，an)

26、变成长度为变成长度为n-1的线性表的线性表(a1，a i-1，a i+1，an)1.初值初值 获取线性表获取线性表L，删除位置，删除位置i；2.检查参数检查参数 若若 （删除位置超出线性表长度范围）（删除位置超出线性表长度范围） 则则 输出错误输出错误3.删除元素删除元素 获取删除位置获取删除位置i的元素的元素e 将删除位置将删除位置i之后的之后的L中的元素全部前移一格中的元素全部前移一格 线性表长度减线性表长度减14.算法结束算法结束中国科大数据结构2-23 2.2 线性表的顺序存储结构 该算法的时间分析与插入算法相似，结点的移动次数也是由表长该算法的时间分析与插入算法相似，结点的移动次数也

27、是由表长n 和位和位置置i决定。决定。 若若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；结点； 若若i=1，则前移语句将循环执行，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为结点。这两种情况下算法的时间复杂度分别为O(1)和和O(n)。 删除算法的平均性能分析与插入算法相似。在长度为删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结的线性表中删除一个结点，令点，令Ede(n)表示所需移动结点的平均次数，删除表

28、中第表示所需移动结点的平均次数，删除表中第i个结点的移动次数个结点的移动次数为为n-i，故，故式中，式中，qi表示删除表中第表示删除表中第i个结点的概率。个结点的概率。中国科大数据结构2-24 2.2 线性表的顺序存储结构在等概率的假设下，在等概率的假设下，p1=p2=p3=pn=1/n由此可得：由此可得：即在顺序表上做删除运算，平均要移动表中约一半的结点，平即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是均时间复杂度也是O(n)。中国科大数据结构2-25 2.3 线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结线性表的顺序表示的特点是用物理位

29、置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表表(Linked List)。2.3.1 线性链表线性链表 链表是指用一组任意的存储单元来依次存放线性表的结点，这组链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分

30、布在存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针个信息称为指针(pointer)或链或链(link)。这两部分组成了链表中的结。这两部分组成了链表中的结点结构：点结构：中国科大数据结构2-26 其中其中:data:data域

31、是数据域，用来存放结点的值；域是数据域，用来存放结点的值； nextnext是指针域，用来存放结点的直接后继的地址（或位置）。是指针域，用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的链表正是通过每个结点的链域将线性表的n n个结点按其逻辑次序链接在个结点按其逻辑次序链接在一起。由于上述链表的每一个结只有一个链域，故将这种链表称为单链一起。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（表（Single Linked)Single Linked)，或线性链表。，或线性链表。 显然，单链表中每个结点的存储地址是存放在其前趋结点显然，单链表中每个结点的存储地

32、址是存放在其前趋结点nextnext域中，域中，而开始结点无前趋，故应设头指针而开始结点无前趋，故应设头指针headhead指向开始结点。同时，由于指向开始结点。同时，由于 终端结点无后继，故终端结点的指针域为空，即终端结点无后继，故终端结点的指针域为空，即nullnull（图示中也可用（图示中也可用 表示表示) )。 例例1 1、线性表、线性表:(bat:(bat，catcat，eateat，fatfat，hathat，jatjat，latlat，mat)mat)datanext2.3 线性表的链式表示和实现单链表示意图如下： 165160lat205jat110fat130batNullm

33、at.170eat135cat.200hat110130135160165170200205头指针p单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。p例如：若头指针名是例如：若头指针名是headhead，则把链表称为表，则把链表称为表headhead。p用用C C语言描述的单链表如下：语言描述的单链表如下：bat cat eat mat Headtypedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;中国科大数据结构2-29 2.3

34、线性表的链式表示和实现LNode *p;LinkList head;注意区分指针变量和结点变量这两个不同的概念。指针变量注意区分指针变量和结点变量这两个不同的概念。指针变量P P（其值为结点地址）和结点变量（其值为结点地址）和结点变量* *P P之间的关系。之间的关系。P P为动态变量，它为动态变量，它是通过标准函数生成的，即是通过标准函数生成的，即 p=(LNodep=(LNode* *)malloc(sizeof(LNode)malloc(sizeof(LNode););函数函数mallocmalloc分配了一个类型为分配了一个类型为LNodeLNode的结点变量的空间，并将其首的结点变量

35、的空间，并将其首地址放入指针变量地址放入指针变量p p中。一旦中。一旦p p所指的结点变量不再需要了，又可通所指的结点变量不再需要了，又可通过标准函数过标准函数 free(pfree(p) )释放所指的结点变量空间。释放所指的结点变量空间。中国科大数据结构2-30 2.3 线性表的链式表示和实现在这样的结构里，第一个结点，有别于其他结点，它的生成与在这样的结构里，第一个结点，有别于其他结点，它的生成与删除都要进行特殊的处理。有时，我们在单链表的第一个结点之前删除都要进行特殊的处理。有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点，那么会带来以下两个优点：附设一个结点，称之为头结点，

36、那么会带来以下两个优点：n由于开始结点的位置被存放在头结点的指针域中，所以在链表由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；需进行特殊处理；n无论链表是否为空，其头指针是指向头结点无论链表是否为空，其头指针是指向头结点 的非空指针的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。就统一了。头结点的数据域可以不存储任何信息，也可以存放线性表的长头结点的数据域可以不存储任何信息，也可以存放

37、线性表的长度信息。度信息。中国科大数据结构2-31 2.3 线性表的链式表示和实现p查找运算查找运算在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，也不能象顺序表中，也不能象顺序表中那样直接按序号那样直接按序号i i访问结点，而只能从链表的头指针出发，顺链域访问结点，而只能从链表的头指针出发，顺链域nextnext逐个结点往下搜索，直到搜索到第逐个结点往下搜索，直到搜索到第i i个结点为止。因此，链表个结点为止。因此，链表不是随机存取结构。不是随机存取结构。设单链表的长度为设单链表的长度为n n，要查找表中第，要查找表中第i i个结点，仅当个结点，仅当1in1in时

38、，时，i i的值是合法的。但有时需要找头结点的位置，故我们将头结点看的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第做是第0 0 个结点。个结点。中国科大数据结构2-32 2.3 线性表的链式表示和实现算法算法2.8的基本操作是比较的基本操作是比较j和和i并后移指针，并后移指针，while循环体中的语句频循环体中的语句频度与被查元素在表中位置有关，若度与被查元素在表中位置有关，若1=inext; j=1; while(p & jnext; j+; if (!p | j i) return ERROR; e= p-data; return OK;中国科大数据结构2-33 2

39、.3 线性表的链式表示和实现p插入运算插入运算插入运算是将值为插入运算是将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上，个结点的位置上，即插入到即插入到a ai-1i-1与与a ai i之间。因此，我们必须首先找到之间。因此，我们必须首先找到a ai-1i-1的存储位置，的存储位置，然后生成一个数据域为然后生成一个数据域为x x的新结点的新结点s s，并令新结点，并令新结点s s的指针域指向结的指针域指向结点点a ai i ，结点，结点a ai-1i-1的指针域指向新结点的指针域指向新结点s s。从而实现三个结点。从而实现三个结点a ai-1i-1，s s和和a ai

40、 i之间的逻辑关系的变化。具体算法如下之间的逻辑关系的变化。具体算法如下: :Status ListInsert _L(LinkList &L, int i, ElemType e) p=L; j=0; while (p & jnext; +j; if (!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(LNode); sdata=e; snext=pnext; pnext=s; return OK; 中国科大数据结构2-34 2.3 线性表的链式表示和实现设链表的长度为设链表的长度为n n，合法的插入位置是，合法的插入位置是1i

41、n+11in+1。注意当。注意当i=1i=1时，找到的是头结点，当时，找到的是头结点，当i=n+1i=n+1时，找到的是结点时，找到的是结点a an n。算法的时间。算法的时间主要耗费在查找操作主要耗费在查找操作whilewhile语句上，故时间复杂度为语句上，故时间复杂度为O(nO(n) )。中国科大数据结构2-35 2.3 线性表的链式表示和实现p删除运算删除运算删除运算是将表的第删除运算是将表的第i i个结点删去。因为在单链表中结点个结点删去。因为在单链表中结点a ai i的的存储地址是在其直接前趋结点存储地址是在其直接前趋结点a a i-1i-1的指针域的指针域nextnext中，所以

42、我们必须中，所以我们必须首先找到首先找到a a i-1i-1的存储位置的存储位置p p。然后令。然后令pnextpnext指向指向a ai i的直接后继结的直接后继结点，即把点，即把a ai i从链上摘下。最后释放结点从链上摘下。最后释放结点a ai i的空间，将其归还给的空间，将其归还给“存存储池储池”。此过程见书。此过程见书P30P30算法算法2.102.10。具体算法如下：。具体算法如下：Status ListDelete_L(LinkList &L, int i, ElemType &e) p=L; j=0; while (p-next) & jnext; +j

43、; if( !( pnext) | j i-1) return ERROR; q=pnext; pnext=qnext; e=q-data; free( q ) ; return OK; 中国科大数据结构2-36 2.3 线性表的链式表示和实现设单链表的长度为设单链表的长度为n n，则删去第，则删去第i i个结点仅当个结点仅当1in1in时是合法时是合法的。注意，的。注意，p p是指向待删结点的前一个结点。当是指向待删结点的前一个结点。当i=n+1i=n+1时，虽然被删时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点结点不存在，但其前趋结点却存在，它是终端结点。因此被删结

44、点的直接前趋的直接前趋* *p p存在并不意味着被删结点就一定存在，仅当存在并不意味着被删结点就一定存在，仅当（pnext!=NULLpnext!=NULL）时，才能确定待删结点存在。）时，才能确定待删结点存在。 显然，此算法的时间复杂度也是显然，此算法的时间复杂度也是O(nO(n) )。 从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。点，仅需修改指针。中国科大数据结构2-37 2.3 线性表的链式表示和实现p建立单链表建立单链表动态地建立单链表的常用方法有如下几种：动态地建立单链表的常用方法有如下几种：

45、1 1、头插法建表（无头结点）、头插法建表（无头结点） 该方法从一个空表开始，重复读入数据，生成新结点，将读该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。表头上，直到读入结束标志为止。Status CreateList(LinkList L) /输入创建线性链表输入创建线性链表 char ch; LNode *p; L=NULL; ch=getchar( ); while (ch!= n) p=(LNode*)malloc(sizeof(LNo

46、de); pdata=ch; pnext=L; L=p; ch=getchar( ); return OK; 中国科大数据结构2-38 2.3 线性表的链式表示和实现Status CreateList(ListLink L, int n) /创建创建n个元素的线性链表个元素的线性链表 LNode *p; L=NULL; for (i=n; i0; -i ) p=(LNode*)malloc(sizeof(LNode); scanf(“%d”，&pdata); pnext=L; L=p; return OK;中国科大数据结构2-39 2.3 线性表的链式表示和实现2 2、尾插法建表（无头

47、结点）、尾插法建表（无头结点） 头插法建立链表虽然算法简单，但生成的链表中结点的次序和头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r r，使其始终指向当前链表的尾结点。，使其始终指向当前链表的尾结点。Status CreateList(ListLink L ) char ch;LNode *p，*r; L=NULL;r=NULL; while( (ch=g

48、etchar( ) ) !=n) p=(LNode *) malloc(sizeof(LNode); pdata=ch; if(L=NULL) / /生成第一个结点生成第一个结点 L=p;r=p; else /生成其他结点 rnext=p; r=p; if (r!=NULL) rnext=NULL; /生成结点时，为rnext赋空值 return OK; 中国科大数据结构2-40 2.3 线性表的链式表示和实现3 3、建带头结点链表、建带头结点链表逆序输入逆序输入n n个数据创建带头结点链表的算法：个数据创建带头结点链表的算法： Status CreateList_L(LinkList &am

49、p;L, int n) L=(LinkList) malloc(sizeof(LNode); L-next=NULL; /先建立头结点先建立头结点 for (i=n; i0; -i) p=(LinkList) malloc(sizeof(LNode); scanf(&p-data); pnext = L-next; Lnext = p; 中国科大数据结构2-41 2.3 线性表的链式表示和实现p有时候，也可以用一维数组来描述链表，这种链表称为有时候，也可以用一维数组来描述链表，这种链表称为静态链表。它的形式定义为它的形式定义为#define MAXSIZE 1000#define MA

50、XSIZE 1000typedef structtypedef struct ElemType ElemType data; data; / /数据数据 intint cur; cur; / /指示下一项的数组索引指示下一项的数组索引 component, SLinkListMAXSIZE component, SLinkListMAXSIZE; ;如图如图2.10，数组的第一个分量可以看成头结点，假设，数组的第一个分量可以看成头结点，假设S为为SLinkList型变量，则型变量，则i=Si.cur相当于指针的后移。定位函数见算相当于指针的后移。定位函数见算法法2.13，类似可以写出插入和删除

51、的操作。所不同的是，用户必须，类似可以写出插入和删除的操作。所不同的是，用户必须自己实现自己实现malloc和和free两个函数。为了辨明数组中哪些分量未被使两个函数。为了辨明数组中哪些分量未被使用，解决的办法是建立一个备用结点链表，每当进行插入操作时从用，解决的办法是建立一个备用结点链表，每当进行插入操作时从备用链表上取得第一个结点作为新结点，在删除时将被删除的结点备用链表上取得第一个结点作为新结点，在删除时将被删除的结点链接到备用链表上。链接到备用链表上。中国科大数据结构2-42 2.3 线性表的链式表示和实现void InitSpace_SL(SlinkListvoid InitSpac

52、e_SL(SlinkList &space) &space) / space/ space为备用链表，为备用链表，space0.curspace0.cur为头指针为头指针 for (i=0; iMAXSIZE-1; +i)for (i=0; inext) next(rearnext) next和和rearrear，显然，查，显然，查找时间都是找时间都是O(1)O(1)。因此，实际中多采用尾指针表示单循环链表。因此，实际中多采用尾指针表示单循环链表。 由于循环链表中没有由于循环链表中没有NULLNULL指针，故涉及遍历操作时，其终止条指针，故涉及遍历操作时，其终止条件就不再像非循

53、环链表那样判断件就不再像非循环链表那样判断p p或或pnextpnext是否为空，而是判断是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。它们是否等于某一指定指针，如头指什或尾指针等。中国科大数据结构2-46 2.3 线性表的链式表示和实现p例、在链表上实现将两个线性表例、在链表上实现将两个线性表(a(a1 1，a a2 2，a a3 3，aan n) )和和(b(b1 1，b b2 2，b3b3，bbn n) )链接成一个线性表的运算。链接成一个线性表的运算。 LinkList Connect(LinkList reara，LinkList rearb) LinkList p

54、=rearanext; rearanext=(rearbnext)next free(rearbnext); rearbnext=p; return (rearb); 中国科大数据结构2-47 2.3 线性表的链式表示和实现2.3.32.3.3 双链表双链表双向链表双向链表(Double linked list):(Double linked list):在单链表的每个结点里再增在单链表的每个结点里再增加一个指向其直接前趋的指针域加一个指向其直接前趋的指针域priorprior。这样就形成的链表中有两。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：个方向不同的链，故称为双向

55、链表。形式描述为： typedef struct DuLNode ElemType data; struct DuLNode *prior，*next; DuLNode, *DuLinkList;中国科大数据结构2-48 2.3 线性表的链式表示和实现和单链表类似，双链表一般也是由头指针唯一确定的，增加头和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。起来也能构成循环链表，并称之为双向链表。 设指针设指针p p指向某一结点，则双向链表

56、结构的对称性可用下式描指向某一结点，则双向链表结构的对称性可用下式描述：述： (pprior)next=(pnext)prior =p(pprior)next=(pnext)prior =p即结点即结点* *p p的存储位置既存放在其前趋结点的存储位置既存放在其前趋结点* *(pprior)(pprior)的直接的直接后继指针域中，也存放后继指针域中，也存放 在它的后继结点在它的后继结点* *(pnext)(pnext)的直接前趋指的直接前趋指针域中。针域中。中国科大数据结构2-49 2.3 线性表的链式表示和实现Status ListInsert_DuL(DuLinkListStatus L

57、istInsert_DuL(DuLinkList p p，ElemTypeElemType e) e) DuLinkList s=malloc(sizeof(DuLNode DuLinkList s=malloc(sizeof(DuLNode);); sdata=e; sdata=e; sprior=pprior; sprior=pprior; ppriornext=s; ppriornext=s; snext=p; snext=p; pprior=s; pprior=s; return OK; return OK; 插入操作插入操作中国科大数据结构2-50 2.3 线性表的链式表示和实现p删

58、除删除p指针所指的结点指针所指的结点注意：与单链表的插入和删除操作不同的是，在双链表中插入和删注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为为O(1)O(1)。 ppriornext=pnext; pnextprior=pprior; free(p);中国科大数据结构2-51 2.4 一元多项式的表示及相加p一元多项式按升幂可以表示为一元多项式按升幂可以表示为 P Pn n(x(x)=p)=p0 0+p+p1 1x+px+p2 2x x2 2+p pn nx xn

59、n 1.1.多项式的几种存储结构多项式的几种存储结构12.3X7 -4.5X5 +4X2 -33.2-33.2042-4.5512.37系数系数指数指数中国科大数据结构2-52 2.4 一元多项式的表示及相加p结构定义（以链表实现的线性表为例）结构定义（以链表实现的线性表为例）struct PolyNode double c; int e; PolyNode *next; typedef PolyNode *Poly;中国科大数据结构2-53 2.4 一元多项式的表示及相加多项式相加算法的实现多项式相加算法的实现设设：1）多项式采用非零系数单链表结构；）多项式采用非零系数单链表结构； 2）多项

60、式）多项式A(x)和和B(x)相加，相加，“和多项式和多项式”C(x)的结点不另外申请的结点不另外申请存储空间；存储空间； 3）p,q分别指向分别指向A(x)和和B(x)中中的某结点。的某结点。 运算规则运算规则：指数相同，系数相加。：指数相同，系数相加。 若若p-exp exp，则，则p结点为结点为C(x)的一项，移动的一项，移动p； 若若p-exp q-exp，则，则q结点插入在结点插入在p结点之前，移动结点之前，移动q； 若若p-exp = q-exp，则，则p-coef:= p-coef+ q-coef; 释放释放q结点结点; 当和为时，释放当和为时，释放p结点结点; 移动移动p和和q；中国科大数据结构2-54 2.4 一元多项式的表示及相加p例例 A(x) = 7 + 3x + 9x8 +