第二章线性表(2013)

1、数理学院 冯莉第二章 线性表12线性表的概念及运算线性表的顺序存储 34线性表的链式存储顺序表和链表的比较 2.1 线性表的概念及运算（a1, a2, ai-1，ai, ai1 ，, an）1. 线性表的定义：线性表的定义：n(n0)个个相同类型数据元相同类型数据元素素的有限序列。的有限序列。n=0时称为时称为数据元素数据元素开始结点开始结点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即数，即表长表长空表空表终端结点终端结点2.1 线性表的概念及运算 线性结构的逻辑特征线性结构的逻

2、辑特征: : 对于一个非空的线性表对于一个非空的线性表: :1) 1) 有且仅有一个开始结点有且仅有一个开始结点a a1 1, ,它无直接前趋它无直接前趋, ,仅有一个仅有一个直接后继直接后继a a2 2；2) 2) 有且仅有一个终端结点有且仅有一个终端结点a an n, ,它无直接后继它无直接后继, ,仅有一个直仅有一个直接前趋接前趋a an-1n-1； 3) 3) 其余的内部结点其余的内部结点a ai i (1in),(1in),都有且仅有一个直接前趋都有且仅有一个直接前趋a ai-1i-1和一个直接后继和一个直接后继a ai+1 i+1 . .a1a3a4ana22.1 线性表的概念及运

3、算例例1 分析分析26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级2006011810205于春梅于春梅女女 202006级信计级信计011班班2006011810260何仕鹏何仕鹏男男 192006级信计级信计011班班2006011810284王王 爽爽女女 192006级信计级信计012班班2006011810360王亚武王亚武男男 212006级信计级信计012班班： ：例例2 分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都

4、是字母; 元素间关系是线性的。元素间关系是线性的。2.1 线性表的概念及运算2 2 线性表的运算线性表的运算1) 1) SETNULL(L)SETNULL(L) 置空表置空表2) 2) LENGTH(L)LENGTH(L) 求表长求表长3) 3) GET(L,i) GET(L,i) 取表中第取表中第i i个结点个结点(1(1 i i LENGTH(L)LENGTH(L) )4) 4) LOCATE(L,x) LOCATE(L,x) 定位定位: : 若若L L中存在一个值为中存在一个值为x x的结点的结点, ,返回该结点位置返回该结点位置; ; 若若L L中存在多个值为中存在多个值为x x的结点

5、的结点, ,返回首次找到的位置返回首次找到的位置; ; 若若L L中不存在值为中不存在值为x x的结点的结点, ,返回一值表示其不存在返回一值表示其不存在. .5) 5) INSERT(L,x,i)INSERT(L,x,i)在在L L的第的第i i个位置插入一个值为个位置插入一个值为x x的结点的结点. .6) 6) DELETE(L,i) DELETE(L,i) 删除删除L L中第中第i i个结点个结点. .2.2 线性表的顺序存储一一 顺序表顺序表用一组用一组地址连续地址连续的存储单元依次存的存储单元依次存储线性表的元素，可通过静态数组储线性表的元素，可通过静态数组VnVn或动态数或动态数

6、组来实现。组来实现。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻2.2 线性表的顺序存储线性表顺序存储特点：线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元素存放若已知表中首元素在存储器中的位置，则其他元素存

7、放位置亦可求出（位置亦可求出（利用数组下标利用数组下标）。计算方法是（参见存）。计算方法是（参见存储结构示意图）：储结构示意图）：设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为称为基地址基地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为C字节，字节，则表中任一数据元素的则表中任一数据元素的存储地址存储地址为：为： LOC(ai+1) = LOC(ai)+C LOC(ai) = LOC(a1) +（i-1） * C (1 i n)注意：注意：C C语言中数组的下标从语言中数组的下标从0 0开始，开始， 即：即：LnLn的有效范围是的有效范围是

8、L0L0Ln-1Ln-12.2 线性表的顺序存储线性表的顺序存储结构示意图线性表的顺序存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Cb=LOC(a1)b + + C Cb +(i-1)+(i-1)* *C Cb +(n-1)+(n-1)* *C Cb +(max-1)+(max-1)* *C C 顺序表顺序表是一是一种种随机存取随机存取的的存储存储结构结构2.2 线性表的顺序存储一个一维数组，下标的范围是到，每个一个一维数组，下标的范围是到，每个数组元素用相

9、邻的数组元素用相邻的4 4个字节存储。存储器按字节编个字节存储。存储器按字节编址，设存储数组元素址，设存储数组元素 的第一个字节的地址是的第一个字节的地址是，则，则 的第一个字节的地址是的第一个字节的地址是 例例1因此：因此：LOC( M3 ) = 98 + 4 (3-0) =110解：解：地址计算通式为：地址计算通式为：LOC(ai) = LOC(a0) + L *（i-0）2.2 线性表的顺序存储用数组用数组V V来存放来存放2626个英文字母组成的线性个英文字母组成的线性表（表（a a，b b，c c，z z），写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该表的该表的C C语

10、言程序。语言程序。 #define n 26int Vn;voidvoid build() / build() /* *字母线性表的生成，即建表操作字母线性表的生成，即建表操作* */ / int i; int i; V0=a; V0=a; for(i=1;i=n-1;i+) for(i=1;i=n-1;i+) Vi=Vi-1+1;Vi=Vi-1+1; 核心语句：核心语句：法法1 Vi= Vi-1+1;1 Vi= Vi-1+1;法法2 Vi=2 Vi=a a+i;+i;法法3 Vi=97+i;3 Vi=97+i;例例22.2 线性表的顺序存储voidvoid main() / main() /

11、* *主函数主函数* */ / build(); build(); display(); display(); getch(); getch(); voidvoid display() / display() /* *字母线性表的显示，即读表操作字母线性表的显示，即读表操作* */ / int i; int i; for(i=0;in;i+) for(i=0;idatai-1L-datai-1求表长求表长LENGTH(L):LENGTH(L):取第取第i i个结点个结点 GET(L,i):GET(L,i):( (* *L).last+1L).last+1( (* *L).datai-1L).d

12、atai-12.2 线性表的顺序存储二二 基本运算基本运算1 1 插入插入 Insert(Insert(L,x,iL,x,i) ) (i(i从从1 1开始开始) )/在线性表在线性表L L的的第第i i个位置插入值为个位置插入值为x x的的结点结点插入前：插入前：( (a a1, 1, , , aiai-1, -1, aiai, , , , anan) )插入后：插入后：( (a a1, 1, , , aiai-1, -1, x x , , aiai, , , , anan) )ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置

13、反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化2.2 线性表的顺序存储33例：（例：（35，12，24，42），在第），在第i=2的位置上插入的位置上插入33。表满：表满：last+1=MaxSize合理的插入位置：合理的插入位置：1in+1（i指的是元素的序号）指的是元素的序号） 435122442a1a2a3a40 1 2 3 4 表长表长422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件2.2 线性表的顺序存储插入算法：插入算法： 在线性表的第在线性表的第i i个位置插入一个元素个位置插入一个元素实现步骤：实现步骤： 将第将第n至第至第i 位的元素向后

14、移动一个位置；位的元素向后移动一个位置； 将要插入的元素写到第将要插入的元素写到第i个位置；个位置； 表长加表长加1。注意：注意：事先应判断事先应判断: 插入位置插入位置i 是否合法是否合法?表是否已满表是否已满? for (j=(*L).last;j=i-1;j-) (*L).dataj+1=(*L).dataj; (*L). datai-1=x; (*L).last=(*L).last+1;/ /* * 元素后移一个位置元素后移一个位置* */ / /* * 插入插入x */ /* * 表长加表长加1 1* */ / 核心语句：核心语句：共移动（共移动（n-i+1n-i+1）个元素！）个元

15、素！2.2 线性表的顺序存储具体实现：具体实现：int INSERT(sequenlist *L, datatype x, int i) int j; if ( ) /*判断是否溢出？判断是否溢出？*/ printf(“overflow”); return 0; if ( ) /*判断位置是否合法？判断位置是否合法？*/ printf(“error”); return 0; else for (j=(*L).last; j=i-1; j-) (*L).dataj+1=(*L).dataj; (*L).datai-1=x; (*L).last=(*L).last+1; return 1;( (*

16、 *L).last=maxsize-1L).last=maxsize-1i(i(* *L).last+2)L).last+2)(i1)(i1) |2.2 线性表的顺序存储时间复杂度分析：时间复杂度分析： 插入算法时间主要耗费在插入算法时间主要耗费在移动元素移动元素的操作上的操作上 T(n)= O (移动元素次数移动元素次数) 移动元素的次数取决于插入元素的位置。移动元素的次数取决于插入元素的位置。讨论：讨论：若在长度为若在长度为 n 的线性表的第的线性表的第 i 位位 插入一个元素，则向后插入一个元素，则向后移动元素的次数移动元素的次数f(n)为为:f(n) =最好最好情况（情况（ i =n+

17、1）：移动元素次数）：移动元素次数0次，时间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（ i =1）：移动元素次数）：移动元素次数n次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：时间复杂度为）：时间复杂度为O(n)。 + +- -+ += =11)=1(niiinp + +- -+ + += =11)=1(11niinn2nO(n) n i + 12.2 线性表的顺序存储ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化2 2 删除删

18、除 DeleteDelete( (L,iL,i) ) (i(i从从1 1开始开始) )/删除删除线性表线性表L L的的第第i i个位置个位置结点结点删除前：删除前：( (a a1, 1, , , aiai-1, -1, aiai, , , , anan) )删除后：删除后：( (a a1, 1, , , aiai-1, -1, ai+1ai+1, , , , anan) )2.2 线性表的顺序存储例：（例：（35, 33, 12, 24, 42），删除），删除i=2的数据元素。的数据元素。 535a1a2a3a40 1 2 3 4422412334a5122442合理的删除位置：合理的删除位置

19、：1in（i指的是元素的序号）指的是元素的序号）什么时候不能删除什么时候不能删除？2.2 线性表的顺序存储实现步骤：实现步骤： 将第将第i+1 i+1 至第至第n n 位的元素向前移动一个位置；位的元素向前移动一个位置； 表长减表长减1 1。注意：注意：事先应判断事先应判断: : 删除位置删除位置i i 是否合法是否合法? ? 删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素for (j=i;j=(*L).last;j+) (*L).dataj-1=(*L).dataj; (*L).last-;/ /* * 元素前移一个位置元素前移一个位置* */ /*表长减表长减1*/ 核心语

20、句：核心语句：共移动（共移动（n-in-i）个元素！）个元素！2.2 线性表的顺序存储具体实现：具体实现：int DELETE(sequenlist *L, int i) int j; if ( ) /*判断位置是否合法？判断位置是否合法？*/ printf(“error”); return 0; else for (j=i; j(i(* *L).last+1)L).last+1)(i1)(idata=ch; s-next=head;head=s;依次插入每一个结点依次插入每一个结点 csheadbaheadab2.3.2 单链表上的基本运算linklist linklist * *CREAT

21、LISTF() /CREATLISTF() /* *头插法建单链表头插法建单链表* */ / char ch; char ch; linklist linklist * *head,head,* *s;s; head=NULL; / head=NULL; /* *单链表开始为空单链表开始为空* */ / ch=getchar(); / ch=getchar(); /* *读入第一个结点的值读入第一个结点的值* */ / while(ch!=$) while(ch!=$) s=malloc(sizeof(linklist); / s=malloc(sizeof(linklist); /* *生成

22、新结点，分配空间生成新结点，分配空间* */ / s-data=ch; / s-data=ch; /* *给新结点的数据域赋值给新结点的数据域赋值* */ / s-next=head;s-next=head; head=s; head=s; / /* *将新结点插入到表头上将新结点插入到表头上* */ / ch=getchar(); / ch=getchar(); /* *读入下一个结点的值读入下一个结点的值* */ / return head; return head; / /* *返回单链表的头指针返回单链表的头指针* */ / 2.3.2 单链表上的基本运算2）尾插法建表：）尾插法建表：

23、即：将新生成的每一个结点插入到当前链表的表尾上，一即：将新生成的每一个结点插入到当前链表的表尾上，一个一个往后插，直到结束符为止，需增加一个个一个往后插，直到结束符为止，需增加一个尾指针尾指针，使，使其始终指向当前链表的尾结点。其始终指向当前链表的尾结点。eg: eg: 空表，读入空表，读入a b c $a b c $初始化初始化: head=NULL; r=NULL;插入第一个元素结点插入第一个元素结点headrear a2.3.2 单链表上的基本运算插入第二个元素结点插入第二个元素结点csrearhead bsreara依次插入每一个结点依次插入每一个结点rearheadba算法描述：算法

24、描述：s=malloc(sizeof(linklist); s-data=ch; r-next=s;r=s;2.3.2 单链表上的基本运算linklist *CREATLISTR() /*尾插法建单链表尾插法建单链表*/char ch; linklist *head,*s,*r; head=NULL; /*单链表开始为空单链表开始为空*/ r=NULL; /*尾指针初值为空尾指针初值为空*/ch=getchar(); /*读入第一个结点的值读入第一个结点的值*/ while(ch!=$) s=malloc(sizeof(linklist); /*生成新的结点，给其分配空间生成新的结点，给其分配

25、空间*/ s-data=ch; /*给新结点的数据域赋值给新结点的数据域赋值*/ r-next=s; /*非空表，新结点插入尾指针之后非空表，新结点插入尾指针之后*/ r=s; /*尾指针尾指针r指向新的表尾指向新的表尾*/ ch=getchar(); /*读入下一个结点的值读入下一个结点的值*/ r-next=NULL; /*非空表的尾结点的指针域置为空非空表的尾结点的指针域置为空*/ return head; /*返回单链表的头指针返回单链表的头指针*/if(head=NULL) head=s; /*第一个新结点直接插入空表中第一个新结点直接插入空表中*/ elseif(r!=NULL)2

26、.3.2 单链表上的基本运算）建立带头结点的单链表：）建立带头结点的单链表：即：在开始结点之前附加一个结点（即：在开始结点之前附加一个结点（头结点头结点），这样，无），这样，无论链表是否为空，其头指针始终是指向头结点的非空指针。论链表是否为空，其头指针始终是指向头结点的非空指针。利用尾插表建表的方法，可以省去空表和非空表的判断，利用尾插表建表的方法，可以省去空表和非空表的判断，从而简化操作。从而简化操作。头指针头指针是是指向指向链表中链表中第一个结点第一个结点（或为（或为头结点头结点或或为开始结点为开始结点）的的指针指针。头结点头结点是在链表的是在链表的开始结点之前附设开始结点之前附设的一个结

27、点；数据域内只的一个结点；数据域内只放空表标志或表长等信息放空表标志或表长等信息。开始结点开始结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a1 1。 头指针头指针头结点头结点 开始结点开始结点a12.3.2 单链表上的基本运算区别：区别： 无头结点无头结点(链栈常用链栈常用) 有头结点有头结点(链表常用链表常用)a1a2/a4a3heada1a2/a4a3head2.3.2 单链表上的基本运算答：答：讨论讨论1 1. . 在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？讨论讨论2 2. . 如何判别如何判别空表空表？头结点头结点即在链表的开始结点之前

28、附设的一个结点，该结即在链表的开始结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对进行操作时，可以对空表、非空表空表、非空表的情况以及对的情况以及对开始结点开始结点进行进行统一处理，编程更方便统一处理，编程更方便,常用头结点。常用头结点。答：答：无头结点时，无头结点时，当头指针的值为空当头指针的值为空时表示空表；时表示空表；有头结点时，有头结点时，当头结点的指针域为空当头结点的指针域为空时表示空表。时表示空表。头指针头指针头指针头指针头结点头结点无头结点无头结点有头结点有头结点hhh=NU

29、LLh-next=NULL2.3.2 单链表上的基本运算linklist *CREATLISTR1() /*尾插法建带头结点的单链表尾插法建带头结点的单链表*/ char ch; linklist *head,*s,*r; head=malloc(sizeof(linklist); /*生成头结点生成头结点*/ r=head; /*尾指针初值指向头结点尾指针初值指向头结点*/ printf(nplease input the value of linklist :n); ch=getchar(); /*读入第一个结点的值读入第一个结点的值*/ while(ch!=$) s=malloc(siz

30、eof(linklist); /*生成新的结点，给其分配空间生成新的结点，给其分配空间*/ s-data=ch; /*给新结点的数据域赋值给新结点的数据域赋值*/ r-next=s; /*新结点插入尾指针之后新结点插入尾指针之后*/ r=s; /*尾指针尾指针r指向新的表尾指向新的表尾*/ ch=getchar(); /*读入下一个结点的值读入下一个结点的值*/ r-next=NULL; /*尾结点的指针域置为空尾结点的指针域置为空*/ return head; /*返回单链表的头指针返回单链表的头指针*/时间复杂度时间复杂度O(n)2.3.2 单链表上的基本运算2单链表的查找运算单链表的查找

31、运算1)按序号查找按序号查找:查找第查找第i个结点个结点 0 i nv核心操作（关键操作）：核心操作（关键操作）：p指针后移指针后移。从头结点出发，通过。从头结点出发，通过p指针的反复后移而将整个单链表指针的反复后移而将整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）。（或遍历）。v 需要设置一个计数器需要设置一个计数器,随随p的后移一起记数的后移一起记数.heada1pa2panaip查找成功查找成功pin查找失败查找失败顺藤摸瓜顺藤摸瓜p2.3.2 单链表上的基本运算linklist *GET(linklist *head,int i) /*按序号查找按序号查找*/ i

32、nt j; linklist *p; p=head; j=0; while( ) p=p-next; j+; if(i=j) return p; else return NULL;(p-next!=NULL) & (jnext; while( ) if(p-data!=key) p=p-next; else break; return p;p!=NULL平均时间复杂度为平均时间复杂度为O(n)2.3.2 单链表上的基本运算3单链表的插入运算单链表的插入运算 假设假设p指向某一结点指向某一结点, s指向待插入的值为指向待插入的值为x的新的新结点结点,则根据插入位置不同可以有则根据插入位置不同可以

33、有:前插操作前插操作: s插入在插入在p之前之前;后插操作后插操作: s插入在插入在p之后之后;2.3.2 单链表上的基本运算1) 后插操作后插操作pxss=malloc(sizeof(linklist); s-data=x; Step1:s-next=p-next; Step2:p-next=s;插入步骤（即核心语句）：插入步骤（即核心语句）：思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？ 不能互换！不能互换！12平均时间复杂度为平均时间复杂度为O(1)2.3.2 单链表上的基本运算2) 前插操作前插操作pxs12q3分析分析:需要修改需要修改*p的前趋结点的前趋结点*q的指针域的

34、指针域,则需确定则需确定*q的的位置位置.由于单链表没有指向前趋结点的指针由于单链表没有指向前趋结点的指针,则需要从则需要从头指针开始依次找到头指针开始依次找到*p的前趋的前趋*q,然后再改变指针然后再改变指针,做做*q的后插操作的后插操作.2.3.2 单链表上的基本运算void INSERTBEFORE (linklist *head,linklist *p,datatype x) /*前插：将值为前插：将值为x的新结点插入的新结点插入*p之前之前*/ linklist *s,*q; s=malloc(sizeof(linklist); s-data=x; q=head; while( q-

35、next!=p ) q=q-next; s-next=p; q-next=s;2.3.2 单链表上的基本运算时间复杂度分析：时间复杂度分析：最好最好情况（情况（ 在开始结点之前插在开始结点之前插）：）：while执行执行0次，次，O(1)。最坏最坏情况（情况（ 在最后结点之前插）：在最后结点之前插）：while执行执行n次，次，O(n)。平均平均情况（与情况（与p的位置有关）：的位置有关）：时间复杂度为时间复杂度为O(n)。 算法时间主要耗费在算法时间主要耗费在while循环循环操作操作总结：此前插算法性能较差总结：此前插算法性能较差, ,可作进一步改进可作进一步改进! !2.3.2 单链表上

36、的基本运算改进：在改进：在* *p p之之后插后插入入* *s,s,然后然后交换交换* *s s和和* *p p的数据域值的数据域值即可即可. .ps12p345x(1) s=malloc(sizeof(linklist); (2) s-data=p-data; (3) s-next=p-next; (4) p-next=s;(5) p-data=x;平均时间复杂度为平均时间复杂度为O(1)前插操作变为后插操作前插操作变为后插操作!2.3.2 单链表上的基本运算实现实现 INSERT(L,x,i):分析分析:在单链表在单链表L的第的第i个结点之前插入值为个结点之前插入值为x的结点的结点,可转化

37、为可转化为在第在第i-1个结点之后插入个结点之后插入.void INSERT(linklist *L,datatype x,int i) linklist *p; int j; j=i-1; /* 第第j-1个结点之后个结点之后*/ p=GET(L,j); if(p=NULL) printf(errorn); else INSERTAFTER(p,x);平均时间复杂度为平均时间复杂度为O(n)2.3.2 单链表上的基本运算4单链表的删除运算单链表的删除运算 pr分析分析:删除删除*p的后继简单的后继简单,设设r指向被删结点指向被删结点,则则:删除步骤（即核心语句）：删除步骤（即核心语句）：r=

38、p-next; p-next=r-next; free(r);思考：思考： 省略省略free(r); 语句语句行不行？行不行？不行不行! !2.3.2 单链表上的基本运算实现实现 DELETE(L,i):分析分析:删除第删除第i-1个结点的后继个结点的后继.void DELETE(linklist *L,int i) /*删除删除L的第的第i个结点个结点*/ linklist *p; p=GET(L,i-1); if( ) DELETEAFTER(p); else printf(error);(p!=NULL) (p-next!=NULL)&平均时间复杂度为平均时间复杂度为O(n)2.3.2

39、单链表上的基本运算5 5、应用举例：两个链表的归并、应用举例：两个链表的归并算法要求：算法要求：已知：已知：线性表线性表 A A、B B，分别由，分别由单链表单链表 LA , LBLA , LB 存储，存储，其中数据元素按值其中数据元素按值非递减有序非递减有序排列。排列。要求：要求：将将 A A ，B B 归并归并为一个新的线性表为一个新的线性表C , C C , C 的数的数据元素仍按值非递减排列据元素仍按值非递减排列 。设线性表。设线性表 C C 由由单链表单链表 LCLC 存储。存储。假设：假设：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，

40、1111）预测：预测：合并后合并后 C =C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 2 , 3 , 5 , 6 , 8 , 8 , 9 , 1111，11 11 ）2.3.2 单链表上的基本运算用链表可表示为：用链表可表示为： 3 511 / 8 LaLa 2 611 / 8 LbLb 9 2 3 6 5 LcLc 8 811 / 911头结点头结点LaLaLbLbLcLc2.3.2 单链表上的基本运算算法分析：算法分析：算法主要包括：算法主要包括：搜索、比较、插入搜索、比较、插入三个操作：三个操作：搜索：搜索：需要需要两个指针两个指针遍历两个链表；遍历两个链表；比较：

41、比较：比较结点数据域中数据的大小；比较结点数据域中数据的大小；插入：插入：将两个结点中将两个结点中数据小的结点插入新链表数据小的结点插入新链表。2.3.2 单链表上的基本运算3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb， Pc指向新链表当前结点指向新链表当前结点Lc Pa3 PcPa5 Pc11Pc2 PbPcPaLa2.3.2 单链表上的基本运算算法实现：算法实现： linklist *MergeList_L(linklist *La, linklist *Lb, linkList *Lc) linklist *pa,*pb,*pc; fr

42、ee(Lb); /*释放释放Lb的头结点的头结点*/ return Lc; pc-next = pa?pa:pb ; /*插入剩余结点插入剩余结点*/ while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pa=La-next; pb=Lb-next; Lc=pc=La； 思考思考: :若要求不若要求不能有重复的数能有重复的数据元素，如何据元素，如何编程？编程？2.3.3 循环链表特点：特点： 3heada1ai-1anaip2.3.3 循环链表如：带头结点

43、的如：带头结点的空空循环链循环链表样式表样式head注：将单链表的首尾相接，将终端结点的指针域由空指针改为注：将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成指向头结点，构成单循环链表单循环链表，简称，简称循环链表循环链表。reara1ai-1anai开始结点：开始结点：rear-next-next终端结点：终端结点：rear其它形式的循环链表如：带尾指针的循环链表其它形式的循环链表如：带尾指针的循环链表 一元多项式加法一元多项式加法2.3.3 循环链表n次多项式形式次多项式形式: F(x)=a0+a1x+a2x2+a3x3+anxncoefexpnext结点类型说明：结点类

44、型说明：typedef struct pnode float coef; /*系数系数*/ int exp; /*指数指数*/ struct pnode *next;polynode;注：头结点的注：头结点的coef=0,exp=-1coef=0,exp=-1，多项式中只写非多项式中只写非0 0系数的项系数的项。eg:A(x)=1+2x2+3x3+4x4 B(x)=x+3x2-3x3+5x5 求：求：A(x)+B(x)=C(x)? 1 24 / 3 A(X)A(X) 0 -1 0 2 34 1 35 /-3 B(X)B(X) 0 -1 1 2 35 2.3.3 循环链表 运算规则运算规则（1）

45、指数相同的项，将其对应系数相加，若和不）指数相同的项，将其对应系数相加，若和不为为0，则形成和多项式中一项；，则形成和多项式中一项；（2）所有指数不同的项复制到和多项式中。）所有指数不同的项复制到和多项式中。 设设q1,q2分别指向多项式分别指向多项式A，B中当前检测的某一中当前检测的某一结点，结点，q为和多项式中一结点。为和多项式中一结点。则：则：2.3.3 循环链表（1）当当q1-exp=q2-exp，则系数相加；，则系数相加； 若和不为若和不为0:生成和多项式生成和多项式C中一新结点中一新结点q，q1,q2指针后移；指针后移； 若和为若和为0: q1,q2指针后移。指针后移。（2）当当q

46、1-expq2-exp 将将B中当前结点中当前结点q2复制到复制到和多项式和多项式C中，中，q2指针后移。指针后移。（3）当当q1-exp exp 将将A中当前结点中当前结点q1复制到和多项式复制到和多项式C中，中，q1指针后移。指针后移。（4）若）若A、B中有一个已经处理完，则将未处理完的多项式剩中有一个已经处理完，则将未处理完的多项式剩余项复制到和多项式余项复制到和多项式C中。中。2.3.4 双链表priordatanext常用双向循环链表，如空的常用双向循环链表，如空的双向循环链表为：双向循环链表为：双链表的存储结构定义：双链表的存储结构定义：typedef int datatype;

47、typedef struct node datatype data; struct node *prior, *next;dlinklist; dlinklist *head; 2.3.4 双链表ai-1aipai+1p1p2特点：特点： 1. 2. p-prior-next=p=p-next-prior;2.3.4 双链表双向链表的操作双向链表的操作插入实现插入实现(后插后插)apxs注意指针修改的注意指针修改的相对相对顺序顺序核心语句：核心语句： s=malloc(sizeof(dlinklist); s-data=x; s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; bcd2.3.4 双链表双向链表的操作双向链表的操作删除实现删除实现(删删p本身本身)ai-1aipai+1核心语句：核心语句： p-prior-next=p-next; p-next-prior=p-prior; free(p); 2.4 顺序表和单链表的比较存储分配方式比较存储分配方式比较顺序表顺序表采用采用顺序存储顺序存储结构，即用一段地址结构，即用一段地址连续连续的的存储单元存储单元依次依次存储线性表的数据元素，数据元素之存储线性表的数据元素，数据元素之间的逻辑关系通过间的逻辑关系通过存储位