第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; }