资源描述：
《严蔚敏数据结构 (7).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第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的指
2、针域。实际上是链栈的概念操作后：（an,…ai+1，ai,ai-1，…,a2,a1）^a1heada2思路：后继变前驱思路：头部变尾部②插入法：扫描a1……an,将每个ai插入到链表首部即可。3p=head->next;//有头结点if(p!=head){q=p->next;p->next=head;p=q};//处理a1while(p!=head)//循环单链表{q=p->next//保存原后继p->next=head->next;head->next=p;p=q;}//准备处理下一结点q=head;p=head
3、->next;//有头结点while(p!=head)//循环单链表{r=p->next;p->next=q;//前驱变后继q=p;p=r;}//准备处理下一结点head->next=q;//以an为首替换法的核心语句：插入法的核心语句：ai-1aiqai+1prheada1heada2pq请上机验证并分析效率！4就地逆置程序段的改进//主程序被降到8行，因为对空表的检测可以不要。q=head->Next;//有头结点pCur=q->Next;q->Next=(List*)head;//第一结点处理while(pC
4、ur!=(List*)head)//空表或只有一个结点均会跳过{q=pCur->Next;//保存原后继pCur->Next=head->Next;head->Next=pCur;pCur=q;}5例4：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。深圳华为公司招聘面试题常见做法：①从前往后扫描，见到0元素则与尾部非0元素互换；②从后往前扫描，见到0元素则后面元素统统前移；③从前往后扫描，见到0元素先计数，再将后续的一个非0元素前移，全
5、部扫完后再把后续部分（长度为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;//表的
6、后部补0return(ok)；}//SortA若表完全不空，也要比较n次？注：L.v[0]中没有存放实际元素值，否则i应从0开始。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-zeros
7、um+1;i<=L.length;i++)L.v[i]=0;//表的后部补0return(ok)；}若考虑表完全非空的情况，则程序要变长很多。8例5：若某种高级语言没有指针类型，能否实现链式存储和运算？如何实现？答：能！虽然链表通常用动态级联方式存储，但也可以用一片连续空间（一维数组）实现链式存储，这种方式称为静态链表。具体实现方法：定义一个结构型数组（每个元素都含有数据域和指示域），就可以完全描述链表，指示域就相当于动态链表中的指针。指示域也常称为“游标”9动态链表样式：静态链表样式：指针数据指针数据指针数据指示
8、数据指示数据指示数据指示数据指示数据数组中每个元素都至少有两个分量，属于结构型数组。常用于无指针类型的高级语言中。10静态单链表的类型定义如下：#defineMAXSIZE1000//预分配最大的元素个数（连续空间typedefstruct{ElemTypedata;//数据域intcur;//指示域}component,SLinkList[MAXSIZE]
