线性结构部分习题幻灯片.ppt

栈与队列 线性结构 习题 综合应用题 例1 铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问： （1）设有编号为1，2，3，4，5，6的六辆车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？ （2）若进站的六辆列车顺序如上所述，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到（即写出“进站”或“出站”的序列）。 综合应用题 编号大的车开出后，编号比其小的车反序开出，即编号大的车开出后，编号比其小的车只能由大到小依次开出（中间可以插入编号更大的车，但此车后面编号比其小的车也要遵守此规则） 出栈序列种数： 综合应用题 例6 写出将单链表逆置的算法，即由单链表A产生单链表B，使得A的最后一个元素是B的第一个元素，依次类推。 单链表反转（方法一：非递归算法） struct ListNode{ EIEM element; ListNode *link; }; Typedef ListNode *ListPtr; ListPtr invert(ListPtr head){ ListPtr middle,trail; middle=NULL; while(head){ trail=middle; middle=head; head=head-link; middle-link=trail; } return middle; } 单链表反转（方法二：递归算法） void DLList::reverse( DLLNode * n ){ DLLNode * t1 = n, * t2 = n -next; if ( t2 -next != 0 ) reverse( t2 ); t2 - next = t1; } 综合应用题 例7 递归算法求： (1)求链表的结点个数 int List :: Num(ListNode * f) { if (f==0) return 0; return 1+Num(f-link); } 综合应用题 (2)求链表中的最大整数 int List :: Max(ListNode * f) { if (f-link==0) return f-data; //递归结束条件 /*在当前结点的后继链表中求最大值*/ int temp=Max(f-link); /*如果当前结点值大，返回当前结点值*/ if (f-data temp) return f-data; else return temp; //否则返回后继链表中的最大值 } 综合应用题 (3)求所有整数的平均值 float List :: Avg (ListNode *f, int n){ if (f-link==0) { n=1; return (float)(f-data); } else{ float sum=Avg(f-link,n)*n; n++; return(f-data + sum)/n; } } 数据结构与算法 For 软件学院09级本科生 2010-2011秋 本节重点 复习要点 单项选择题 综合应用题 线性表-复习要点（1） 1.线性表的概念 线性表的定义和特点 线性表的基本操作 2.线性表的存储表示 顺序表的定义及基本运算的实现 单链表的定义及基本运算的实现 3.线性表的特殊链接表示 循环链表的特殊遍历方式 双向链表的方向性 线性表-复习要点（2） 4.线性表的应用（1） 在一维数组上的算法，如原地逆置、非零元素压缩、成块元素移动等。 在一维数组上的递归算法，如求和平均值等。 在顺序表上的查找、插入、删除、合并、求交等算法及性能分析。 在单链表上的迭代求解算法及性能，包括统计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、链表逆转等。 线性表-复习要点（3） 4.线性表的应用（2） 带表头结点的单链表上的迭代算法，包括统计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、两个有序链表的合并