数据结构 (特详细2)课件

第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例1例1：两个链表的归并（教材P31例）例2：一元多项式的计算

(教材P39–43)例3：试用C或类C语言编写一个高效算法，将一循环单链表就地逆置。

微软亚洲研究院去年来校招聘的笔试题操作前：（a1,a2,…ai-1，ai,ai+1，…,an）操作后：（an,…ai+1

，ai,ai-1，…,a2,a1）2分析：要想让an指向an-1,……a2指向a1，一般有两种算法：①替换法：扫描a1……an,将每个ai-1的指针域送入ai+1的指针域。实际上是链栈的概念操作后：（an,…ai+1

，ai,ai-1，…,a2,a1）^a1heada2思路：后继变前驱思路：头部变尾部②插入法：扫描a1……an,将每个ai插入到链表首部即可。3就地逆置程序段的改进（周小明课后提交）//主程序被降到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例4：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。深圳华为公司去年来校招聘面试题常见做法：①从前往后扫描，见到0元素则与尾部非0元素互换；②从后往前扫描，见到0元素则后面元素统统前移；③从前往后扫描，见到0元素先计数，再将后续的一个非0元素前移，全部扫完后再把后续部分（长度为0元素的个数）清0。××√（a1,a2,…ai-1，ai,ai+1，…,an）6解：voidSortA(sqlist&L){inti=0,zerosum=0;if(L.length==0)return(0);//空表则结束else{for(i=1;i<=L.length;i++){if(L.v[i]<>0)L.v[i-zerosum]=L.v[i];elsezerosum++;}}for(i=L.length-zerosum+1;i<=L.length;i++)L.v[i]=0;//表的后部补0return(ok)；}//SortA若表完全不空，也要移动n次？7解：

voidSortA(sqlist&L){inti=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];elsezerosum++};//适当移动非零元素,是零则增加计数for(i=L.length-zerosum+1;i<=L.length;i++)L.v[i]=0;//表的后部补0return(ok)；}若考虑表完全非空的情况，则程序要变长很多。8动态链表样式：静态链表样式：指针数据指针数据指针数据指示数据指示数据指示数据指示数据指示数据数组中每个元素都至少有两个分量，属于结构型数组。常用于无指针类型的高级语言中。10前例2：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？——教材P32例题data0123456…1000cur说明1：假设S为SLinkList型变量，则S[MAXSIZE]为一个静态链表；S[0].cur则表示第1个结点在数组中的位置。说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；S[i].cur表示第k+1个结点(即k的直接后继)的位置。i头结点12例6：在双向链表中如何实现插入和删除运算？单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表，称为双向链表。其结点的结构为：typedefstructDuLNode{

ElemTypedata;//数据域

structDuLNode*prior;

//前驱指针域structDuLNode*next;//后继指针域}DuLNode,*DuLinkList;

双向链表类型的定义如下：14双向链表的插入操作：设p已指向第i元素，请在第i元素前插入元素x①ai-1的后继从ai(指针是p)变为x（指针是s):s->next=p;

p->prior->next=s;

②ai的前驱从ai-1(指针是p->prior)变为x(指针是s);s->prior=p->prior;p->prior=s;

注意：要修改双向指针！x

sai-1

ai

p指针域的变化：15指针域的变化：后继方向：ai-1的后继由ai(指针p)变为ai+1(指针p->next

);

p->prior->next

=

p->next;前驱方向：ai+1的前驱由ai(指针p)变为ai-1(指针p->prior

);

p->next->prior

=p->prior;

ai-1

ai+1

ai

p双向链表的删除操作：设p指向第i个元素，删除第i个元素注意：要修改双向指针！16本章小结线性结构(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。2.线性表逻辑结构：“一对一”或“1:1”存储结构：顺序、链式运算：修改、插入、删除[查找和排序另述]3.顺序存储特征：逻辑上相邻，物理上也相邻；优点：随机查找修改快

O(1)缺点：插入、删除慢O(n)改进方案：链表存储结构17循环链表的特点：从任一结点出发均可找到表中其他结点双向链表的特点：可方便找到任一结点的前驱静态链表的特点：不用指针也能实现链式存储和运算4.链式存储特征：逻辑上相邻，物理上未必相邻；优点：插入、删除快

O(1)缺点：随机查找修改慢O(n)5.几种特殊链表的特点：18讨论2：什么是指针？指针的作用？指针—即变量的内存地址。指针主要功能有二：①提供了一种快速访问数组单元的途径；②使C语言函数可以修改其调用的参数。

&---指针操作符（单目），返回操作数地址；

*---运算符（单目），是对&的补充，返回位于这个地址内的变量之值。例：q=*m意即“q取地址m中的值”。如果数值100存储在内存地址2000中，而这一地址又存在m中，则q=(2000)=100讨论3：与指针有关的符号&和*之间有何区别？20P43程序中，switch(*cmp(a,b))的cmp(a,b)一定是个特殊变量，它的值是一个内存地址，而-1,0,+1这三种可能的执行结果会放入该地址中，所存结果再由*cmp来寻址。那么，P42定义为intcmp(a,b)又怎么理解？意即cmp中地址（指针）存储的是一个整型变量讨论4：

P43程序中，switch(*cmp(a,b))的意思？21编制递归算法要注意些什么？递归进行是有条件的。一般常把判断语句加在递归语句以前。递归的最底层应该有返回值，以供上层递归的调用。否则会死循环。递归调用需要利用堆栈。参量的初始化应该在递归以前。 每次调用要把本次调用的参数和局部变量保存在栈顶。每次从下一层调用返回到上一层调用时，从栈顶恢复本层调用的参数和局部变量的值。23例2：设正整数a的前驱为PRIOR(a)，后继为NEXT(a)，用递归算法计算a+b。

平常我们可以用循环来实现，但根据本题题意不能用循环，而要用递归。设计要点有二：①递归算法的形式化描述；②不能