数据结构c语言描述(耿国华)第二章-资料下载页

　　

【正文】 LL） { if （ pexp qexp） { … /*将 p结点加入到和多项式中 */} else if ( pexp= =qexp） { … /*若指数相等 ， 则相应的系数相加 。 若系数为 0则删除 p， q节点 */} else{ … /*将 q结点加入到和多项式中 */} } … ../*将多项式 polya或 polyb中剩余的结点加入到和多项式中 */ } 2022/8/26 72 顺序表和链表的比较  1．基于空间的考虑  2．基于时间的考虑  3．基于语言的考虑 2022/8/26 73 线性表链式存储方式的比较 操作名称 链表名称 找表头结点 找表尾结点 找 P结点前驱结点 带头结点单链表 L Lnext 时间耗费 O(1) 一重循环 时间耗费 O(n) 顺 P结点的 next域无法找到 P结点的前驱 带头结点循环单链表（头指针） L Lnext 时间耗费 O(1) 一重循环 时间耗费 O(n) 顺 P结点的 next域可以找到 P结点的前驱 时间耗费 O(n) 带尾指针的循环单链表 R Rnext O(1) R 时间耗费 O(1) 顺 P结点的 next域可以找到 P结点的前驱 时间耗费 O(n) 带头结点双向循环链表 L Lnext O(1) Lprior 时间耗费 O(1) Pprior 时间耗费 O(1) 2022/8/26 74 总结与提高  主要知识点  线性表的特征 ：线性表中每个数据元素有且仅有一个直接前驱和一个直接后继，第一个结点无前驱，最后一个结点无后继。  线性表存储方式 ： – 线性表顺序存储（顺序表）：采用静态分配方式，借助于 C语言的数组类型，申请一组连续的地址空间，依次存放表中元素，其逻辑次序隐含在存储顺序之中。 2022/8/26 75 总结与提高 – 线性表链式存储（链表）：采用动态分配方式，借助于 C语言的指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。当表长度变化时仅需适当变化指针的联接，适合于表中元素个数动态变化。  单链表的操作特点 ： – ⑴顺链操作技术 – ⑵指针保留技术  链表处理中的相关技术 2022/8/26 76 典型题例  例 1： 已知顺序表 L中的数据元素类型为 int。设计算法将其调整为左右两部分，左边的元素（即排在前面的）均为奇数，右边所有元素（即排在后面的）均为偶数，并要求算法的时间复杂度为 O(n)，空间复杂度为 O（ 1）。 2022/8/26 77 例 1【 问题分析 】  初见此题，可能会想到额外申请 1个顺序表空间，之后依次从顺序表 L中选择奇数放入新表前部分，选择偶数放在新表的后半部分。但是题目要求空间复杂度为 O(1),很显然上述方法是不可行的。既然要求空间复杂度为O(1)，说明只能借助 1个辅助空间。分析题目要求，其实我们只需要将位于表左半部分的偶数与位于表右半部分的奇数通过一个辅助变量进行交换即可，为此我们可以设置两个位置指示器 i和 j,i初值为 0， j初值为 Llast,当Lelem[i]为偶数， Lelem[j]为奇数时，则将 Lelem[i] 与 Lelem[j]交换；否则， Lelem[i]为奇数 ,i++, Lelem[j]为偶数， j++。这样既可以保证算法的时间复杂度为 O(n),亦可保证空间复杂度为 O（ 1）。 2022/8/26 78 【 算法描述 】 AdjustSqlist(SeqList *L) /* {int i=0,j=Llast。 while(ij) { while(Lelem[i]%2!=0) i++。 /*从表的左半部分开始检测，若为奇数，则 i加 1,直到找到偶数为止*/ while(Lelem[j]%2= =0) j； /* 从表的右半部分开始检测，若为偶数，则 j减 1,直到找到奇数为止 */ if(ij) {t= Lelem[i]。 Lelem[i]= Lelem[j]。 Lelem[j]=t。}/*交换 */ } }/*end of AdjustSqlist*/ 2022/8/26 79  例 2：算法实现带头结点单链表的就地逆置问题。  【 问题分析 】 逆置就是使得表中内容由原来的（ a1,a2,… ， ai1， ai， ai+1， … ， an）变为（ an,an1,… ， ai+1， ai， ai1， … ， a1）。就地逆置就是不需要额外申请结点空间，只需要利用原有的表中的节点空间。若对顺序表中的元素进行逆置，可以借助于“ 交换 ” 前后相应元素；对单链表中的元素进行逆置，则不能按 “ 交换 ” 思路，因为对于链表中第 i个结点需要顺链查找第 ni+1(链表长度为 n)个结点，逆置链表的时间复杂度将达 O（ n2）。 2022/8/26 80  算法思路： 逆置后的单链表初始为空，表中的结点不是新生成的，而是从原链表中依次 “ 删除 ” ，再逐个头插入到逆置表中（类同算法 ）。设逆置链表的初态为空表， “ 删除 ” 已知链表中的第一个结点，然后将它 “ 插入 ” 到逆置链表的 “ 表头 ” ，即使它成为逆置链表中 “ 新 ” 的第一个结点，如此循环，直至原链表为空表止。  根据单链表的特点，通过头指针 L我们可以顺着每个结点的 next域，依次访问到 a1,a2,a3… an1,an； 2）我们可以借鉴前面讲到过的头插入法建链表的方法，因为头插入法建链表又称为逆序建表法 3）唯一不同的是，我们不需要重新申请结点空间，而只需要从原有单链表上依次 “ 摘下 ” 结点，之后插入到单链表头结点和表中第一个结点之间即可。如图所示 2022/8/26 81 … a1 … an ∧ a2 ai (a)初始状态 L p为原链表当前处理结点 断开 Lnext, 使逆置表初始为空表 (b)将单链表 L初始为空表 … a1 … an ∧ a2 ai ∧ L p q q指向原链表当前处理结点的下一个 p ① ai a2 a1 ∧ L … … an ∧ a3 q (c)将 p指向的结点插入到逆置表 L的表头 ② 2022/8/26 82 例 2【 算法描述 】 void ReverseList(LinkList L) /*逆置带头结点的单链表 L */ { p=Lnext。 /* P为原链表的当前处理结点 */ Lnext=NULL。 /*逆置单链表初始为空表 */ while(p!=NULL) /*当原链表未处理完 */ { q=pnext。 /*q指针保留原链表当前处理结点的下一个结点 */ pnext=Lnext。 Lnext=p。 /*将当前处理结点 p插入到逆置表 L的表头 */ p=q。 /*p指向下一个待插入的结点 */ } /*end of while*/ }/*end of ReverstList*/ 【 思考 】 已知一个带头结点的单链表 L，设计算法实现：以表中第一个元素作为标准，将单链表中所有值小于第一个元素的结点均放在第一个元素结点之前，所有值大于第一个元素的结点均放在第一个元素结点之后。（提示：此题可以利用头插法） 2022/8/26 83  例 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data域存放一个二进制位。并在此链表上实现对二进制数加 1的运算 。  【 问题分析 】 – ① 建链表 ：带二进制数可用带头结点的单链表存储，第一个结点存储二进制数的最高位，依次存储，最后一个结点存储二进制数的最低位。 – ②二进制加法规则 ：实现二进制数加 1运算，方向从低位往高位找到第一个值为 0的位，从该位开始，对后面所有低位进行求反运算。③链表实现二进制加 1时，从高位往低位与运算方向正好相反，从第一个结点开始找，找出最后一个值域为 0的结点，把该结点值域赋为 1，其后所有结点的值域赋为 0。④若在链表中未找到值域为 0的结点，则表示该二进制数各位均为 1，此时，申请一新结点，值域为 1，插入到头结点与原链表的第一个结点之间，成为新链表的第一个结点，其后所有结点的值域赋为 0。 2022/8/26 84 【 算法描述 】 void BinAdd(LinkList l) /*用带头结点的单链表 L存储二进制数，实现加 1运算 */ { Node *q,*r,*temp,*s。 q=lnext。 r=l。 while(q!=NULL) /*查找最后一个值域为 0的结点 */ {if(qdata == 0) r = q。 q = qnext。 } 2022/8/26 85 if (r != l) rdata = 1。 /*将最后一个值域为 0的结点的值域赋为 1*/ else /*未找到值域为 0的结点 */ { temp = rnext。 s=(Node*)malloc(sizeof(Node))。 /*申请新结点 */ sdata=1。 /*值域赋为 1*/ snext=temp。 rnext = s。 /*插入到头结点之后 */ r = s。 } r = rnext。 while(r!=NULL) /*将后面的所有结点的值域赋为 0*/ {rdata = 0。 r = rnext。 } }/*BinAdd结束 */