第2章线性表 (1)「颗日分析木瓶其类上面第7期不同之外有一。一是带斗结占 二是分解后的两个链表，一个是数据值小于0，另 个是数据值大于O。由于没明确要求用类PA SCAL书写算法，故用C书写如下。 void D isC reatl (LinkedL istA ∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C,B中结点的数据小于零，C中结点 的数据大于零。 B=A ode):∥为C申请结点空间 D=A 。为丁作 B->next :∥B表初始化 whie(p=nul =p>nex七∥暂存p的后继 p->daa<0)∥小于0的放入B表 Dnex卡B->next:B->nextp;}∥将小于O的结点链入B表。 eke (p p=r∥p指向新的得 处理结 ∥算法结束雨 [算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素 之前)。 ) 本题同上面第7题，除个别叙述不同外，本质上完全相同，故不再另作解答。 (3)愿 分 群成移 解后的A表含有原表中序号为奇数的元素，B表含有 元素。由于要求分解后两表中元素结点的相对顺序不变，故采用在链表尾插入比较方便，这使用一指向表 n edL istA) ∥A是带头结点的单链 本算法将其分解成两个带头结占的单解表，A表中含原表中序号为奈制 川的结占 B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。 作0：∥记链表中结点的序号 B=(LnkedL ist)m albc(sizeof0Node:∥创建B表表头 B->nexnu止∥B表的飞 LinkedL istra,:∥a和b将分别指向将创建的A表和B表的尾结点。 a-A A->nex 链素作指针指向待分解的结点。 新的A while(pu eD-)next∥暂存D的后继 武2=0) ∥处理原序号为偶数的链表结点。 >nexp:b=p/b指 ∥外理原序号为奇数的结占 p->nex卡m->nextm>n 0=11 ∥将恢复为指向新的待处理结点。 }算法结束 目分折具娶求重排个元素具以顺序存储结枸存储的线性表使得所有值为负数的元素移到正数元素的前而：这可采用 快速排序 思想来实 只、是提出暂存的一个元茶（区袖）并不作为以后的比标准，比的标准是元茶是杏为数 是具 nge (S ,以顺序存储结构存储，线性表的元素是整数。本算法重排线性表， ,正数的新的 仁0：n1:∥1为工作指针（下标)，初始指向线性表a的第1个和第n个元素。 a[0]: ∥暂存枢轴元素。 wh正e(仪) h正(&a[》=0)广：∥若当前元素为大于等于零，则指针前移。 元素为负数时指针后移 ∥正数后移 h中人wy.bong00 fauora0图nentkaovan月amO2h每（第10/24页）201045110108
第2章 线性表 （1）[题目分析]本题基本类似于上面第7题，不同之处有二。一是带头结点，二是分解后的两个链表，一个是数据值小于0，另一 个是数据值大于0。由于没明确要求用类PASCAL书写算法，故用C书写如下。 void DisCreat1(LinkedList A) ∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点 的数据大于零。 {B=A; C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null ∥C初始化为空表。 p=A->next; ∥p为工作指针。 B->next=null; ∥B表初始化。 while(p!=null) {r=p->next; ∥暂存p的后继。 if (p->data<0)∥小于0的放入B表。 {p->next=B->next; B->next=p; }∥将小于0的结点链入B表。 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点。 } }∥算法结束。 [算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素 之前）。 （2）本题同上面第7题，除个别叙述不同外，本质上完全相同，故不再另作解答。 （3）[题目分析]本题中的链表有头结点，分解成表A和表B，均带头结点。分解后的A表含有原表中序号为奇数的元素，B表含有 原A表中序号为偶数的元素。由于要求分解后两表中元素结点的相对顺序不变，故采用在链表尾插入比较方便，这使用一指向表 尾的指针即可方便实现。 void DisCreat3(LinkedList A) ∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号为奇数 ∥的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。 {i=0;∥i记链表中结点的序号。 B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。 B->next=null; ∥B表的初始化。 LinkedList ra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。 ra=A;rb=B; p=A->next; ∥p为链表工作指针，指向待分解的结点。 A->next=null; ∥置空新的A表 while(p!=null) {r=p->next; ∥暂存p的后继。 i++; if(i%2==0) ∥处理原序号为偶数的链表结点。 {p->next=rb->next;∥在B表尾插入新结点； rb->next=p; rb=p;∥rb指向新的尾结点； } else∥处理原序号为奇数的结点。 {p->next=ra->next; ra->next=p; ra=p; } p=r; ∥将p恢复为指向新的待处理结点。 }∥算法结束 8．[题目分析]题目要求重排n个元素且以顺序存储结构存储的线性表，使得所有值为负数的元素移到正数元素的前面。这可采用 快速排序的思想来实现，只是提出暂存的第一个元素（枢轴）并不作为以后的比较标准，比较的标准是元素是否为负数。 int Rearrange（SeqList a; int n) ∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重排线性表a， ∥使所有值为负数的元素移到所有值为正数的数的前面。 {i=0; j=n-1; ∥ i,j为工作指针（下标），初始指向线性表a的第1个和第n个元素。 t=a[0]; ∥暂存枢轴元素。 while(i<j) {while(i<j && a[j]>=0) j-; ∥ 若当前元素为大于等于零，则指针前移。 if(i<j){a[i]=a[j];i++;} ∥ 将负数前移。 while(i<j &&a[i]<0)i++; ∥ 当前元素为负数时指针后移。 if(i<j) a[j-]=a[i]; ∥ 正数后移。 } http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 10／24 页）2010-4-15 11:01:08
第2章线性表 a[t∥将原第一元素放到最终位置。 [算法讨论]本算法时间复杂度为0()。算法只是按题目要求把正负数分开，如要求统计负数和大于等于零的个数，则最后以t 来定。如t负数，则0至共计1个负数，n-1-个正数（包括零） 。另外，题目并未提及零的问题，笔者将零放到正数一边。对此问 趣的扩充是若元素包含正数、负数和零，并要求按负数、零、正数的顺序重排线性表，统计负数、零、正数的个数。请读者利用 上面解题思想自行解答。 ①寄的不的，架为参考元素，将线性表分成左右两部分左半部分的元素都小于等于，右半部分的元 选了5 素都大于a,a位于分界位置上。其算法主要片段语句如下： ∥暂存参考元素 wh正仪汲&a[l<=)t+:∥当前元素不大于参考元素时，指针诟移 ifK)a[上a[l: ∥将大于参考元素的元素后移 wh(Kj逃&a[i>0广：∥当前元素大于参考元素时指针前移。 fK）ait+]=aG: ∥将小于参考元茶的当前元素前移。 浅性表A分成B和C两个表，表B和表C不另占空间，而是利用表A的空间，其算法与第8题相同。这里仅 把表B和表C另设空间的算法解答如 void rear 2(intA D.BO.C O) 线性表A有n个整型元素，顺序存储。本算法将A拆成B和C两个表，B中存放大于 ∥等于零的元素 作0： 指针，分别指向A、B和C表的当前元素。 ∥jk初始化为-1。 元素放入C表。 B4+=A[t+ [算法讨论]本题用一维数组存储线性表，结果线性表B和C中分别有1和+1个元素。若采用教材中的线性表，则元素的表示 作相应改变，例如A.em[司，而最后B和C表应置上表的长度，如B.上ngh=和C.ngh=k。 )本题与第8题本质上相同，第8题要求分开正数和负数，这里要求分开奇数和偶数，判别方式是[%2==0，满足时为偶 ④)本题 述算 瓷不得之处在于这里的分界元素是整数9（链表中并不要一定有9）。木题要求用标 =ARRA Y[1.1000]0F in teger: VAR PRO CEDURE Rearrange5 (VAR a: am) a是n 数凌100)个整数组成的线性表，用一维数组存储。本算法将n个元素中所有大手等手1©的整 6五eger ta]:∥i指示顺序表的首尾元素的下标，商存分界元素 WHLE <KD DO BEG I W HLE (K)AND (a[il>=19)DO: F (KD TH EN BEG N A[=A Li:i=1 EN D: WHLE (KD AND () D0i计1： F(K TH EN BEG N ALi=A [END: ND: -G [算法讨论]分界元素放入[1，而不论它的值如何。算法中只用了一个中间变量，符合空间复杂度0)的要求。算法也满足时间 复杂度0)的要求。 .商不求变素整岛责股老装将不位及新，装 ,单链表中别除结点，为使结点删除后不出现“断链”，应知道被别结点的前 hw,bon20aurm0cMDym/月au02h年（第1/24）2010-4-511010
第2章 线性表 a[i]=t; ∥将原第一元素放到最终位置。 } [算法讨论] 本算法时间复杂度为O（n）。算法只是按题目要求把正负数分开，如要求统计负数和大于等于零的个数，则最后以t 来定。如t为负数，则0至i共i+1个负数，n-1-i个正数（包括零）。另外，题目并未提及零的问题，笔者将零放到正数一边。对此问 题的扩充是若元素包含正数、负数和零，并要求按负数、零、正数的顺序重排线性表，统计负数、零、正数的个数。请读者利用 上面解题思想自行解答。 类似本题的选了5 个题，其解答如下： （1）与上面第8题不同的是，这里要求以an 为参考元素，将线性表分成左右两部分。左半部分的元素都小于等于an ，右半部分的元 素都大于an ，an 位于分界位置上。其算法主要片段语句如下: i=1;j=n; t=a[n]; ∥暂存参考元素。 while(i<j) {while(i<j && a[i]<=t) i++; ∥当前元素不大于参考元素时，指针i后移。 if(i<j) a[j-]=a[i]; ∥将大于参考元素的元素后移。 while(i<j && a[j]>t) j-; ∥当前元素大于参考元素时指针前移。 if(i<j) a[i++]=a[j]; ∥将小于参考元素的当前元素前移。 } a[i]=t; ∥参考元素置于分界位置。 (2) [题目分析]本题要求将线性表A分成B和C两个表，表B和表C不另占空间，而是利用表A的空间，其算法与第8题相同。这里仅 把表B和表C另设空间的算法解答如下： void Rearrange2(int A[],B[],C[]) ∥线性表A有n个整型元素，顺序存储。本算法将A拆成B和C 两个表，B中存放大于 ∥等于零的元素，C中存放小于零的元素。 {i=0; ∥i，j，k是工作指针，分别指向A、B和C表的当前元素。 j=k=-1; ∥j，k初始化为-1。 while(i<n) {if(A[i]<0) C[++k]=A[i++]; ∥将小于零的元素放入C表。 else B[++j]=A[i++]; ∥将大于零的元素放入B表。 [算法讨论]本题用一维数组存储线性表，结果线性表B和C中分别有j+1和k+1个元素。若采用教材中的线性表，则元素的表示 作相应改变，例如A.elem[i]，而最后B和C表应置上表的长度，如B.length=j和C.length=k。 (3) 本题与第8题本质上相同，第8题要求分开正数和负数，这里要求分开奇数和偶数，判别方式是a[i]%2==0，满足时为偶 数，反之为奇数。 (4) 本题与第8题相同，只是叙述不同。 (5) 本题与第8题基本相同，不同之处在于这里的分界元素是整数19（链表中并不要求一定有19）。本题要求用标准pascal描 述算法，如下所示。 TYPE arr=ARRAY[1.1000] OF integer； VAR a：arr； PROCEDURE Rearrange5（VAR a：arr）； ∥a是n（设n=1000）个整数组成的线性表，用一维数组存储。本算法将n个元素中所有大于等于19的整数放在所有小 于19的整数之后。 VAR i,j,t：integer； BEGIN i:=1；j:=n；t:=a[1] ；∥i,j指示顺序表的首尾元素的下标，t暂存分界元素 WHILE（i<j）DO BEGIN WHILE （i<j）AND（a[j]>=19） DO j:=j-1； IF（i<j）THEN BEGIN A[i]:=A[j]；i:=i+1 END； WHILE （i<j）AND（a[i] <19） DO i:=i+1； IF（i<j）THEN BEGIN A[j]:=A[i]；j:=j-1 END； END； a[i]:=t； END; [算法讨论] 分界元素t放入a[i]，而不论它的值如何。算法中只用了一个t中间变量，符合空间复杂度O(1)的要求。算法也满足时间 复杂度O(n)的要求。 9．[题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前 驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 11／24 页）2010-4-15 11:01:08
第2章线性表 刑除损作 红是带头结占的单特表， 本算法删除其最小值结点。 p=L->next: ∥为工作指针。指向待处理的结点。假定链表非空。 pre=L: ∥pe指向最小值结点的前驱。 ∥q指向 最小值结点，初始假定第一元素结点是最小值结点。 'nu Dep:qFp->next}∥查最小值结点 ∥指针后移。 pe->nex仁a->next∥从链表上刑除最小值结点 ∥释放最小信结点空间 }∥结束算法dekte 函数头是按本教材类C 描述语 书写的。原题中void deete(mkst&L),是按C+的“引用”来写的，目的是 目分析 首先要查找最小值结点。将其移到链表最前面，实质 ∥st是非空线性链表，链结点结构是(daa,nk),daa是数据域，nk是链域。 ∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 p=ist>nk:∥p是链表的工作指 pre=list: 域最小值结点的前驱 据域最小值结点，初始假定是第一结点 -P2 nk->daa<q->daa)p=p:q=p->mk:}∥找到新的最小值结点 f(q=ist>nk)∥若最小值是第 元素结点，则不需再操作 pe〉nk=q>k: 将最小值结点从链表上摘下： q>k=st>k:∥将q结点插到链表最前面。 ist〉lnk=q: 图流园密》骑超装餐莫年的界结费人黄皮胎个结结点，前结点，前的前结点，后集结太 >lnk=list:lis 六条链。 void Exchange (LnkedListp ∥p是双向循环链表中的一个结点，本算法将所指结点与其前驱结点交换。 p p与其前交换 p->rlink->llink=q: ∥p的后继的前驱指向原p的前驱 ->rnk=a: ∥D的后继指向其原来的前驱 }∥算法ex ge结宋 存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元 o 0 ∥a是具有n个元素的递增有序线性表 到，则插入表中，且使表仍递增有序。 :网程储不算法在表中查找数值为x的元素，如查到则与其后继交换位置：如查不 hw=0.hih=n-1. ∥bw和h动指向线性表下界和上界的下标 while (bw<=hgh) (bw+hg)2： ∥找中间位置 7找到 中 出Wn ∥到中点■的左部去 h中hwv.bong0omaM m月amH02h每（第12/24页）201045110108
第2章 线性表 删除操作。 LinkedList Delete（LinkedList L） ∥L是带头结点的单链表，本算法删除其最小值结点。 {p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。 q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null） {if（p->next->data<q->data）{pre=p；q=p->next；} ∥查最小值结点 p=p->next； ∥指针后移。 } pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。 [算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void delete（linklist &L），是按C++的“引用”来写的，目的是 实现变量的“传址”，克服了C语言函数传递只是“值传递”的缺点。 10．[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质 上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。 LinkedList delinsert（LinkedList list） ∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。 ∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link；∥p是链表的工作指针 pre=list； ∥pre指向链表中数据域最小值结点的前驱。 q=p； ∥q指向数据域最小值结点，初始假定是第一结点 while （p->link!=null） {if（p->link->data<q->data）{pre=p；q=p->link；} ∥找到新的最小值结点； p=p->link； } if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作 {pre->link=q->link； ∥将最小值结点从链表上摘下； q->link= list->link；∥将q结点插到链表最前面。 list->link=q； } }∥算法结束 [算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。 11．[题目分析] 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点） 六条链。 void Exchange（LinkedList p） ∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink； q->llink->rlink=p； ∥p的前驱的前驱之后继为p p->llink=q->llink； ∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink； ∥p的前驱的后继为p的后继。 q->llink=p； ∥p与其前驱交换 p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱 p->rlink=q； ∥p的后继指向其原来的前驱 }∥算法exchange结束。 12．[题目分析] 顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元 素”，这里应使用折半查找方法。 void SearchExchangeInsert（ElemType a[]；ElemType x） ∥a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到则与其后继交换位置；如查不 到，则插入表中，且使表仍递增有序。 { low=0；high=n-1； ∥low和high指向线性表下界和上界的下标 while（low<=high） {mid=（low+high）/2； ∥找中间位置 if（a[mid]==x） break； ∥找到x，退出while循环。 else if （a[mid] <x） low=mid+1；∥到中点mid的右半去查。 else high=mid-1； ∥到中点mid的左部去查。 } http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 12／24 页）2010-4-15 11:01:08
第2章线性表 1 若最后 dn) +17 f(b>h 查找失败， 入数据 6r(卡n-l:hh:一)a[+1]=a:∥后移元素。 a[it1]=x:∥插入x。 ∥结束插入 ∥结束本算 时论]首先是线性 表的描述 算法中使用 灭表定夫使用包含数据 系的 维数 成无素 个元素的下标应是n1。第三， 本算法以写成个函数其查找函数，交换后继 数显得逻辑清味 3。目分析]判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访 问到链表的 个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一 元素与栈中再弹出元素比较，直至链表 到尾。这时若栈是空栈，则得出链表中心对称的结论：否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称， 结束算法的执行。 nt dc (LnkedL it h ntn h是带头结点的个元素单链表，链表中结点的数据域是字符。本算法判断链表是否是中心 hars几：nt亡1：记结点个数 字 符栈 ∥p是链表的工作指针 指向待处理的当前元素 :n2+)/链表前 一半元素进栈。 (s[i=p->data: p=p->next: >next】∥若n是奇数，后移过中心结点 wh(p上 =p->data 对 >next}∥测试是否中心对称。 法结束 链表不中心对称 [算法讨论]算法中先将“链表的前一半”元素（字符）进栈。当为偶数时，前一半和后一半的个数相同：当为奇数时，链表中 心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等时，立即退出wh止循环，不再进行比较。 ，分在单链表中制除自第个元素起的共如个元素应从第1个元素起开始计数， 记到第个时开始数m个，然后将第H 正素的后继 的m 这 应 A的 点，得到别除 元系 连表 长的第个元素，将A鞋表插入、插入和除平应注查前驱后雅无系，不能使链表 断 另外，算法中 nti ian】 heada和headb均是带头结点的单链表。本算法 除heada链表中自第个元素起的共n个元素，然后将单链表heada插入到headb的 第个元素之前。 {f(K1ln<1l1)pmf(“参数错误n”)： xt(0):}∥参数错，退出算法。 p=heada:∥D为链表A的 作指针，初始化为A的头指针，查到第个元素时，D指向第】个元素 k=0:∥计数 whe(pnu&&kKH)∥查找第个结点。 “给的d太大n” nex∥q为工作指针， 初始指 品茶不结达大退出算法 1k=0. whi正(q=nul&&k<知)k++: q=q一>next:free(u)：}∥别除结点，后移指针。 芷(k<n)prmf(“给的%d太大n ,n):exit(0):】 ∥A链表别除了ln个元素。 ex卡nu说明链表中结点均已除，无需往B表插入 wh正(p>ne if(heada->next找 为链表郑的 A的尾结点 “作指 0.计数 whe(a上nul&&k(H)∥查找第个结点 k:a=a->next: ∥查找成功时，q指向第H个结点 f(q=null prnt世(“给的%d太大n”,):exit(0):】 ∥将A链表链入 >nex=heada->next∥A的第一元素结点链在B的第l个结点之后 M// h/w.biion200mauMH0nMDym月au02h（第13/24）2010-4-511010
第2章 线性表 if（a[mid]==x && mid!=n）∥ 若最后一个元素与x相等，则不存在与其后继交换的操作。 {t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；} ∥ 数值x与其后继元素位置交换。 if（low>high） ∥查找失败，插入数据元素x {for（i=n-1；i>high；i-） a[i+1]=a[i]；∥后移元素。 a[i+1]=x；∥插入x。 } ∥结束插入 }∥结束本算法。 [算法讨论] 首先是线性表的描述。算法中使用一维数组a表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构 体。若使用结构体，对元素的引用应使用a.elem[i]。另外元素类型就假定是ElemType，未指明具体类型。其次，C中一维数组下标 从0开始，若说有n个元素的一维数组，其最后一个元素的下标应是n-1。第三，本算法可以写成三个函数，查找函数，交换后继函 数与插入函数。写成三个函数显得逻辑清晰，易读。 13．[题目分析] 判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访 问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下一元素与栈中再弹出元素比较，直至链表 到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中一元素与栈中弹出元素不等时，结论为链表非中心对称， 结束算法的执行。 int dc（LinkedList h，int n） ∥ h是带头结点的n个元素单链表，链表中结点的数据域是字符。本算法判断链表是否是中心 对称。 {char s[]; int i=1；∥i记结点个数， s字符栈 p=h->next；∥p是链表的工作指针，指向待处理的当前元素。 for（i=1；i<=n/2；i++）∥ 链表前一半元素进栈。 {s[i]=p->data；p=p->next；} i-; ∥恢复最后的i值 if（n%2==1）p=p->next；} ∥若n是奇数，后移过中心结点。 while（p!=null && s[i]==p->data）{i-；p=p->next；} ∥测试是否中心对称。 if（p==null）return（1）；∥链表中心对称 else return（0）； ∥链表不中心对称 }∥算法结束。 [算法讨论] 算法中先将“链表的前一半”元素（字符）进栈。当n为偶数时，前一半和后一半的个数相同；当n为奇数时，链表中 心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等时，立即退出while循环，不再进行比较。 14．[题目分析] 在单链表中删除自第i个元素起的共len个元素，应从第1个元素起开始计数，记到第i个时开始数len个，然后将第i-1 个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结点。这时应继续查到A的尾结点，得到删除元素 后的A链表。再查B链表的第j个元素，将A链表插入之。插入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中 应判断i，len和j的合法性。 LinkedList DelInsert（LinkedList heada，headb，int i，j，len） ∥heada和headb均是带头结点的单链表。本算法删除heada链表中自第i个元素起的共len个元素，然后将单链表heada插入到headb的 第j个元素之前。 {if（i<1 || len<1 || j<1）{printf（“参数错误\n”）；exit（0）；}∥参数错，退出算法。 p=heada；∥p为链表A的工作指针，初始化为A的头指针，查到第i个元素时，p指向第i-1个元素 k=0；∥计数 while（p!=null && k<i-1）∥查找第i个结点。 {k++；p=p->next；} if（p==null）{printf（“给的%d太大\n”,i）；exit（0）；} ∥i太大，退出算法 q=p->next；∥q为工作指针，初始指向A链表第一个被删结点。 k=0； while（q!=null && k<len）{k++；u=q，q=q->next；free（u）；} ∥删除结点，后移指针。 if（k<len）{printf（“给的%d太大\n”,len）；exit（0）；} p->next=q；∥A链表删除了len个元素。 if (heada->next!=null) ∥heada->next=null说明链表中结点均已删除，无需往B表插入 {while（p->next!=null）p= p->next；∥找A的尾结点。 q=headb；∥q为链表B的工作指针。 k=0；∥计数 while（q!=null && k<j-1） ∥查找第j个结点。 {k++；q= q->next；} ∥查找成功时，q指向第j-1个结点 if（q==null）{printf（“给的%d太大\n”,j）；exit（0）；} p->next=q->next； ∥将A链表链入 q->next=heada->next； ∥A的第一元素结点链在B的第j-1个结点之后 }//if http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 13／24 页）2010-4-15 11:01:08
第2章线性表 ee(heada):∥释放A表头结点。 法结审 与本题类似的题的解答如下： (1)本题与第14题基本相同，不同之处仅在于插入B链表第个元素之前的，不是删除了个元素的A链表，而是被删除的n个元 素。按照上题，这n个元素结点中第一个结点的指针p>nxt,查找从第个结点开始的第m个结点的算法修改为： k<en) ∥查找成功时，q指向自起的第n个结点 k+:q=q-> k<n)f(“给的%d太大n”, exit (0) 5.「目分析1在递增有序的顺序表中插入 首先应查找待插入元素的位置。因顺序表元素递增有序，采用折半查找法 比顺序查找效率要高。查到插入位置后，从此位置直到线性表尾依次向后移动一个元素位置，之后将元素x插入即可。 voidl Insert (Ekm TypeA 0,ntsize,Ekm Typex) ∥A是有s©个元素空间目前仅有加un(mum〈s)个元素的线性表。本算法将元素x插入到线性表中，并保持线性表的有序性。 w=1:h动=num； 从1开 、=ng 对分查找元素x的插入位置 2 A[ eke if (Am ]x)high=m d1:else bw=m or(Fnum:D=bw:一)A[t1A[l:∥元素后移 A[+1]小上x:∥将元素x插入。 ( 有值的特注意不能 找性表中无元素时 r 变的有生 移动元素从开始去直到 故安排在A广n 用 而插入时的移动操作时间复杂度为0() 类似本题的其它题的解答： (1)[题目分析]本题与上面15题类似，不同之处是给出具体元素值，且让编写urbo pascal程序，程序如下： PROGRAM exam ple (input,output) TYPE pointer node: EN D: VAR head,q:pointer; PROCEDURE create (VAR h:pointer): VAR x:iteger: BEC o (h)h'.next 健立头结点。 用指 HEN0E0F00健立表 BEG IN new (p):p".data=x:p'.next=q'.next q".next=p:q=p;read (x); EN D: END: BEG o und. p=h'.next p为工作指针。) =h: 为D的前驱指针。} ound =fake W H LE (p<>NL)AND NOT found 广END :锵结点插入链衣) EN D :hext= htp/w.biliong.co■/a/oya/domy/2hn(第14/24页)2010H51101S
第2章 线性表 free（heada）；∥释放A表头结点。 }∥算法结束。 与本题类似的题的解答如下： （1）本题与第14题基本相同，不同之处仅在于插入B链表第j个元素之前的，不是删除了len个元素的A链表，而是被删除的len个元 素。按照上题，这len个元素结点中第一个结点的指针p->next，查找从第i个结点开始的第len个结点的算法修改为： k=1；q=p->next； //q指向第一个被删除结点 while（q!=null && k<len） ∥查找成功时，q指向自i起的第len个结点。 {k++；q= q->next；} if（k<len） {printf（“给的%d太大\n”,len）；exit（0）；} 15．[题目分析] 在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因顺序表元素递增有序，采用折半查找法 比顺序查找效率要高。查到插入位置后，从此位置直到线性表尾依次向后移动一个元素位置，之后将元素x插入即可。 void Insert（ElemType A[]，int size, ElemType x） ∥ A是有size个元素空间目前仅有num（num<size）个元素的线性表。本算法将元素x插入到线性表中，并保持线性表的有序性。 {low=1；high=num； //题目要求下标从1开始 while（low<=high）∥对分查找元素x的插入位置。 {mid=（low+high）/2； if（A[mid]==x）{low=mid+1；break；} else if（A[mid]>x）high=mid-1 ；else low=mid+1 ； } for（i=num；i>=low；i-） A[i+1]=A[i]；∥元素后移。 A[i+1]=x； ∥将元素x插入。 }算法结束。 [算法讨论] 算法中当查找失败（即线性表中无元素x）时，变量low在变量high的右面（low=high+1）。移动元素从low开始，直到 num为止。特别注意不能写成for（i=low；i<=num；i++）A[i+1]=A[i]，这是一些学生容易犯的错误。另外，题中未说明若表中已 有值为x的元素时不再插入，故安排在A[mid]= =x时，用low（=mid+1）记住位置，以便后面统一处理。查找算法时间复杂度为O （logn），而插入时的移动操作时间复杂度为O（n），若用顺序查找，则查找的时间复杂度亦为O（n）。 类似本题的其它题的解答： （1）[题目分析] 本题与上面15题类似，不同之处是给出具体元素值，且让编写turbo pascal程序，程序如下： PROGRAM example（input，output）； TYPE pointer=^node； node=RECORD data：integer； next：pointer； END； VAR head，q：pointer； PROCEDURE create（VAR la：pointer）； VAR x：integer； p,q：pointer； BEGIN new（la）；la^.next:=NIL；{建立头结点。} read（x）；q:=la；{q用以指向表尾。} WHILE NOT EOF DO {建立链表} BEGIN new（p）；p^.data:=x；p^.next:=q^.next；q^.next:=p；q:=p; read(x); END； END； PROCEDURE insert（VAR la：pointer；s：pointer）； VAR p,q：pointer；found：boolean； BEGIN p:= la^.next；{p为工作指针。} q:=la；{q为p的前驱指针。} found:=false； WHILE（p<>NIL）AND NOT found IF（p^.data<x）THEN BEGIN q:=p；p:= p^.next； END ELSE found:=true； s^.next:=p；{将s结点插入链表} q^.next:=s； END； http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/da02.htm（第 14／24 页）2010-4-15 11:01:08