《数据结构》课程PPT教学课件（2012）第2章 线性表 2.4 应用举例

第2章 线性表 2.1 线性表的逻辑结构 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4应用举例

1

例1：两个链表的归并（教村 微软亚洲研究院 去年来校招聘的 例2：一元多项式的计算 (教 笔试题 例3：试用C或类C语言编写一个高效算法，将一循 环单链表就地逆置。 操作前：（a1,a2.a,a,a+1，,an） 操作后：（a,.a+1,a1,a2a1

2 例1：两个链表的归并（教材P31例） 例2：一元多项式的计算 (教材P39–43) 例3：试用C或类C语言编写一个高效算法，将一循 环单链表就地逆置。 微软亚洲研究院 去年来校招聘的 笔试题 操作前：（a1 , a2 , . ai-1， ai, ai+1 ，., an） 操作后：（ an , . ai+1 ， ai, ai-1 ，., a2 , a1 ）

操作后：（an,.a+1,a,a，,a2ya1 分析： 要想让an指向an-1,a2指向a1,一般有两 种算法 ①替换法：扫描a1.a,将每个a1 的指针域送入 a+1的指针域。 思路：后继变前驱 ②插入法：扫描a1.a 将每个a插入到链表首 部即可。 思路：头部变尾部 实际上是链 head a 栈的概念

3 分析：要想让an指向an-1,.a2指向a1，一般有两 种算法： ①替换法：扫描a1.an, 将每个ai-1的指针域送入 ai+1的指针域。 实际上是链 栈的概念 操作后：（ an , . ai+1 ， ai, ai-1 ，., a2 , a1 ） head a1 ^ a2 思路：后继变前驱 思路：头部变尾部 ②插入法：扫描a1.an, 将每个ai插入到链表首 部即可

替换法的核心语句： 插入法的核心语句： q=head; p=head->next;/有头结点 p=head->next;有头结点 if(p!=head){q=p->next; while(p!=head)循环单链表 p->next=head;p=q;处理a1 r=p->next; while(p!=head)/循环单链表 p->next=q；前驱变后继 {q=p->next保存原后继 q=p; p->next=head->next; p=r;}准备处理下一结点 head->next=p; head->next=q;∥以an为首 D=q}准备处理下一结点 head hea 请上机验证并分析效 率！ a

4 p=head->next; //有头结点 if(p!=head){q=p->next; p->next =head;p=q}; //处理a1 while(p!=head) //循环单链表 { q=p ->next //保存原后继 p ->next= head->next; head->next=p; p=q;} //准备处理下一结点 q=head; p=head->next; //有头结点 while(p!=head) //循环单链表 { r=p->next; p->next=q; //前驱变后继 q=p; p=r; } //准备处理下一结点 head->next=q; // 以an为首 替换法的核心语句： 插入法的核心语句： ai-1 ai q ai+1 p r a1 head head p a2 q 请上机验证并分析效 率！

就地逆置程序段的改进（周小明课后提交） //主程序被降到8行，因为对空表的检测可以不要。 q head->Next; /有头结点 pCur q->Next; q->Next (List*)head; /第一结点处理 while(pCur!=(List*)head)/空表或只有一个结点均会跳过 q-pCur ->Next; //保存原后继 pCur ->Next=head->Next; head->Next=pCur; pCur=q;

5 就地逆置程序段的改进（周小明课后提交） //主程序被降到8行，因为对空表的检测可以不要。 q = head->Next; //有头结点 pCur = q->Next; q->Next = (List*)head; // 第一结点处理 while (pCur!=(List*)head) //空表或只有一个结点均会跳过 { q=pCur ->Next; //保存原后继 pCur ->Next= head->Next; head->Next=pCur; pCur=q; }

例4：试用C或类C语言编写一高效算法，将一顺序 存储的线性表（设元素均为整型量）中所有零元 素向表尾集中，其他元素则顺序向表头方向集中。 (a a2.ai-l,ai ait1.,an 深圳华为公司 去年来校招聘 常见做法： 面试题 ①从前往后扫描，见到0元素则与尾部非0元素互换；X ②从后往前扫描，见到0元素则后面元素统统前移；X ③从前往后扫描，见到0元素先计数，再将后续的一 个非0元素前移，全部扫完后再把后续部分（长度为0 元素的个数)清0

6 例4：试用C或类C语言编写一高效算法，将一顺序 存储的线性表（设元素均为整型量）中所有零元 素向表尾集中，其他元素则顺序向表头方向集中。 深圳华为公司 去年来校招聘 常见做法： 面试题 ①从前往后扫描，见到0元素则与尾部非0元素互换； ②从后往前扫描，见到0元素则后面元素统统前移； ③从前往后扫描，见到0元素先计数，再将后续的一 个非0元素前移，全部扫完后再把后续部分（长度为0 元素的个数）清0。 （a1 , a2 , . ai-1， ai, ai+1 ，., an）

解：void SortA(sqlist&L int i-0,zerosum =0; ifL.length==O)return(O),/空表则结束 else for(i=1;iL.length;i++) if (L.v[i]0)L.v[i-zerosum]=L.v[i]; else zerosum++; for(i=L.length-zerosum+1;i<=L.lengt L.v1=0 /表的后部补0 return(ok); }/∥SortA 若表完全不空，也 要移动n次？

7 解： void SortA(sqlist &L) { int i=0, zerosum =0; if(L.length= =0) return(0); //空表则结束 else { for( i=1; i0) L.v[i- zerosum]= L.v[i]; else zerosum++; } } for( i= L.length-zerosum+1; i<=L.length; i++) L.v[i]=0; //表的后部补0 return(ok)； }// SortA 若表完全不空，也 要移动n次？

若考虑表完全非空的情况，则程序要变长很多。 解：void SortA(sqlist&L) int i-0,zerosum =0: if(L.length==0)return(0); /空表则不执行 for(i;i<=L.length;i++) (if (L.v[i]<0&zerosum!=0)L.v[i-zerosum]=L.v[i] else zerosum++};/适当移动非零元素，是零则增加计数 for(i=L.length-zerosum+1;i<=L.length;i++) L.v[i]=0; /表的后部补0 return(ok):

8 解： void SortA(sqlist &L) { int i=0,zerosum =0; if(L.length= =0) return(0); //空表则不执行 for( i; i0&zerosum!=0)L.v[i- zerosum]= L.v[i]; else zerosum++ }; //适当移动非零元素,是零则增加计数 for( i= L.length-zerosum+1; i<=L.length; i++) L.v[i]=0; //表的后部补0 return(ok)； } 若考虑表完全非空的情况，则程序要变长很多

例5：若某种高级语言没有指针类型， 能否实 现链式存储和运算？如何实现？ 答：能！虽然链表通常用动态级联方式存储，但 也可以用一片连续空间（一维数组）实现链式存 储，这种方式称为静态链表。 具体实现方法：定义一个结构型数组（每个元 素都含有数据域和指示域)，就可以完全描述 链表，指示域就相当于动态链表中的指针。 指示域也常称为“游标

9 例5： 若某种高级语言没有指针类型，能否实 现链式存储和运算？如何实现？ 具体实现方法：定义一个结构型数组（每个元 素都含有数据域和指示域），就可以完全描述 链表，指示域就相当于动态链表中的指针。 指示域也常称为“游标

动态链表样式： 静态链表样式： 数组中每个元素 都至少有两个分 量，属于结构型 数据 指针 数据 指示 数组。 数据 指示 数据 指针 数据 指示 数据 指示 数据 指针 数据 指示 常用于无指针类 型的高级语言中

10 动态链表样式： 静态链表样式： 指针 指针 指针 指示 指示 指示 指示 指示 数组中每个元素 都至少有两个分 量，属于结构型 数组。 常用于无指针类 型的高级语言中