Chap 29-6

第2章 线性表 2.1 线性表的定义和抽象数据类型 2.1.1 线性表的定义 定义 线性表(Linear List)是具有相同属性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示。当n=0时，说明线性表是一个空表，即表中不包含任何元素。线性表的例子： B= ( a, b , c , d, e ) C= ( 25, 38, 12, 49, 63, 54 ) D= ( “BASIC”, “PASCAL”, “FORTRAN”, “C+” )设线性表中的第i个元素为ai (1in)，则线性表的一般表示为： ( a1 , a2 , , ai-1, ai, ai+1, , an ) 其中 al 为第一个元素，又称做表头元素， an 为最后一个元素，又称为表尾元素。 一个线性表可以用一个标识符来命名，当用A命名上面的线性表时，则A= (a1 , a2 , , ai, , an ) 线性表的数据结构 线性表中的元素在位置上是有序的，即第i个元素ai 处在第i-1个元素ai-1的后面和第i+1个元素ai+1的前面。这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构，用二元组表示为： linear_list =(A，R) A= ai | 1 i n, n 0, aiElemType R= r r = | 1in-1 这里ElemType为每个元素所属的数据类型。元素类型ElemType是一种通用数据类型标识符，可以通过typedef 语句在使用前把它定义为任何一种具体类型。若把它定义为整数类型，则为： typedef int ElemType；一般的，一个线性表的元素均为记录类型。 线性表的逻辑结构图：aiai+1ana1a2 线性表的特点： （1）线性表的长度是可变的。当向线性表中插入一个元素时，其长度就增加1，当从线性表中删除一个元素时，其长度就减少1。 （2）线性表是一种线性结构，反过来，任何线性数据结构都可以用线性表的形式表示出来。这只要按照元素之间的逻辑关系把它们顺序排列即可。 因此，以后对线性表的讨论就代表了对任何线性数据结构的讨论。（3）有序表与无序表。 在一个线性表中若存在着按值的升序或降序排列的字段，则称该字段为有序字段，该线性表为有序表；否则若不存在任何有序字段，则为无序表。例如对学生纪录，若按“成绩”字段的升序来排列每条纪录，则构成有序表。而对线性表C= 25, 38, 12, 49, 63, 54 则为无序表。 2.1.2 线性表的抽象数据类型 线性表的抽象数据类型包括数据和操作两个部分。数据部分为一个线性表（假定用标识符 L 来表示），它可以采用顺序、链接、散列等任一种方式存储到计算机中；其存储类型用标识符 ListType 来表示。操作部分为对线性表所做的各种操作（运算），例如向线性表插入一个元素，从线性表中删除一个元素，求线性表长度，判断线性表是否为空等。例如，在下面所定义的线性表抽象数据类型中，只给出了对线性表的一些基本操作；没有给出其所有操作。ADT LinearList is Data： 一个具有 ListType 类型的线性表 L ； Operation： void InitList( ListType &L)；/ 初始化线性表 L，即把它设置为一个空表。L 前面的符号&表示 L 是一个引用形参，调用时不需要为 L 分配存储空间，对 L 的操作实际上就是对被传送的实参的操作。 void ClearList( ListType &L)；/ 清除线性表 L 中的所有元素，使之成为一个空表。 int LenthList( ListType &L)；/ 返回 L 的长度，即 L中所含元素的个数，若 L 为空则返回整数 0。 int EmptyList( ListType &L)；/ 判断 L 是否为空，若为空则返回真(即整数1)，否则返回假(即整数0) ElemType GetList( ListType &L, int pos)；/ 返回 L中第pos个元素的值，1posn，若pos超出该范围，则打印出错信息并停止程序运行。 void TraverseList( ListType &L)； / 遍历 L，即按照L 中元素的逻辑顺序访问每一个元素，并且每一个元素仅被访问一次。bool FindList( ListType &L，ElemType &item)；/ 从 L 中查找并返回元素 bool UpdateList( ListType &L, const ElemType &item)； / 修改 L 中的元素 bool InsertList( ListType &L，ElemType item，int pos)/ 向 L 中 插入元素 bool DeleteList( ListType &L，ElemType &item，int pos)； / 从 L 删除元素 void SortList(ListType &L)； / 对L中的所有元素重新按给定条件排序 end LinearList线性表操作的例子: 设线性表L1=( 25, 38, 19, 42, 33).令 i=2，x=60，y=42;则对L1的一组操作及结果如下: LenthList(L1)； / 返回L1的长度5 EmptyList(L1)； / L1非空，返回 False GetList(L1, i)； / 返回Ll 中第i个元素的值，因i=2，所以返回值38 InsertList(L1，x，6)； /向L1的末尾插入x，L1变为(25，38，19，42，33，60) InsertList(L1，54，1)； / 向L1的表头插入元素54，L1变为(54，25，38，19，42，33，60) DeleteList(Ll，y，0)； /删除L1中值为y的元素，L1变为(54，25，38，19，33，60) DeleteList(L1，y，3)； /删除L1中第3个元素，L1变为(54，25，19，33，60) SortList(L1)； /L1被改变为(19，25，33，54，60) InsertList(Ll，35，0)；/ 插入35后L1变为(19，25，33，35，54，60)2.2 线性表的顺序存储和操作实现2.2.l 线性表的顺序存储 线性表的顺序存储结构就是：把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。 这样，线性表中第一个元素的存储位置就是被指定的存储位置，第 i 个元素 ai 的存储位置紧接在第 i-1 个元素ai-1的存储位置的后面。设线性表的元素类型为ElemType，则每个元素所占用存储空间的大小(即字节数)为sizeof(ElemType)，整个线性表所占用存储空间的大小为：n*sizeof(ElemType)，其中n为线性表的长度。线性表的顺序存储结构是利用数组来实现的，数组的基本类型就是线性表中元素的类型。线性表中的第一个元素被存储在数组的起始位置，即下标为0的位置上，第n个元素被存储在下标为n-1的位置上。用MaxSize表示线性表的最大长度，它一般被定义为一个整型全局常量。例如估计一个线性表不会超过50个元素，则可把MaxSize定义为50。 const int MaxSize=50；在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用listMaxSize表示，整型变量用size表示，则元素类型为FlemType的线性表的顺序存储类型可描述为： ElemType listMaxSize； int size； 为了便于线性表的操作，可以把这两项放在一个记录类型中，定义如下： struct List ElemType listMaxSize； int size；这就定义了线性表的记录类型。若有语句： List L;则定义了线性表 L 的元素为： L.list0, L.list1, L.list2, , L.listL.size-1并定义了线性表L的长度为：L.size 若要对存储线性表的数组空间采用动态分配，并且其数组长度能够按需要增加，则可以定义出如下的List类型： struct List ElemType *list； / list 用于存放线性表元素的动态存储空间的指针； int size； / 存线性表长度 int MaxSize；/ 规定list数组的长度 ； 当初始化此类型的一个线性表时，要使list指针指向大小为MaxSize的动态数组空间。2.2.2 顺序存储下的线性表操作的实现 下面论述在顺序存储方式下，在线性表抽象数据类型中所列出的每一个操作的具体实现。1初始化线性表 初始化线性表就是将它设置为一个空表，即将L的长度域置为0。 void InitList(List &L) L.size=0; 当采用动态存储空间时,初始化线性表需要完成动态存储空间的初始分配，并且把线性表置为空。 void lnitList( List &L) L.MaxSize=10； / 初始定义数组长度为10，以后可以增减。 L.1ist = new ElemTypeL.MaxSize； if( L.1ist = NULL) cout动态可分配的存储空间用完,退出运行!”endl； exit(1)； L.size=0； / 置线性表长度为o，即为空表 2删除线性表中的所有元素 首先需要释放动态存储空间，之后把线性表的长度置为0。void ClearList( List &L) if(L.list !=NULL) delete L.list; L.list=NULL; L.maxSize=0;L.size=0; 3得到线性表的长度 该函数就是返回线性表L的size域的值。int LenthList( List &L ) return L.size; 4检查线性表是否为空 若线性表L为空表，即长度为0时，则返回真，否则返回假(即数值0)。bool EmptyList( List &L ) return (L.size= =0); 5得到线性表中指定序号为pos的元素 ElemType GetList( List &L，int pos) if( posL.size) / 若pos越界则退出程序 cerr “pos is out range！”endl； exit(1)； return L.1istpos-1；/ 返回线性表中第pos个元素的值，注意L的第pos个元素与数组L.1ist的第pos个元素相差的编号为1。 6遍历一个线性表 遍历一个线性表就是从线性表的第一个元素起，按照元素之间的逻辑顺序，依次访问每一个元素，并且每个元素只被访问一次，直到访问完所有元素为止。当访问一个元素时，可根据需要做任意处理，在下面的算法中以打印该元素的值代之。 void TraverseList ( List &L ) for( int i=0；i L.size；i+) cout L.1isti ； cout endl； 若线性表中的元素类型为记录类型，则打印元素的值需要有对该类型重载操作符()。 若在cout输出语句中是依次输出元素的每一个域的值，而不是把元素作为整体输出，则不需要重载。7从线性表中查找具有给定值的第一个元素 bool Find( List &L，ElemType &item )for ( int i=0；i L.size；i+)if ( L.1isti = = item ) item = L.1isti； return true； return false； 当从线性表L中查找到具有item值或其域值相对应的元素时，则由item返回该元素的整体值，并由该函数返回真，表明查找成功，否则由函数返回假，表明查找失败。 当元素类型ElemType为记录类型时，调用此函数必须要有对该类型进行等于(= =)的重载。8更新线性表中具有给定值的第一个元素 在查找成功后，用item的值修改对应元素的值。bool UpdateList ( List &L, const ElemType & item ) for ( int i=0；i L.size；i+ ) if ( L.1isti= = item ) L.1isti = item； /进行修改（更新）赋值操作return true; return false； 当元素类型ElemType为记录类型时，调用此函数要有对该类型进行等于(= =)的重载。 * 向线性表的末尾添加一个元素void InsertRear ( List &L，ElemType &item) if(L.size = MaxSize) / 若表已满，则停止插入，退出程序运行 cerr “List overflow!” endl； exit(1)； L.1istL.size = item；/ 把item的值插入到表尾，即写入到最后一个元素的后一个位置上 L.size+； / 线性表的长度增加1 * 向线性表的表头插入一个元素 该操作过程分为四步： (1) 检查线性表的存储空间是否已被占满，若是则停止插入，退出程序运行； (2) 从表尾元素向前至表头元素止，使每一个元素均后移一个存储位置。把下标为 0 的位置空出，以便插入新元素； (3) 将新元素写入到表头，即下标为 0 的位置； (4) 修改线性表的长度，使其增加 1。void InsertFront ( List &L, ElemType & item) if ( L.size = MaxSize) cerr “List overflow!”= 0；i - -) L.1isti+1 = L.1isti； L.1ist0 = item； L.size + +；* 向线性表中满足条件的位置插入一个元素 该插入操作经常用在有序表上，使得插入后仍然有序。为寻找插入位置所使用的比较条件通常是对有序字段上的值进行比较。 例如，假定一个有序表为A=(15，36，40，48，55，70，83)当向其中插入 50 时，其插入位置为 55 元素的位置；当向其中插入100时，其插入位置在表尾，即最后一个元素 83 的后面。 此插入操作的过程分为以下五步： (1) 检查表是否已满，若是则停止运行； (2) 采用顺序查找的方法查找出item的插入位置； (3) 从插入位置起，把它和后面所有位置上的元素均后移一个位置； (4) 把新元素写入到空出的位置上； (5) 线性表的长度增1。void Insert( List &L，ElemType & item) if( L.size = MaxSize) cerr“List overflow!”endl；exit(1)； for( int i=0；i L.size；i+) if( item =i ; j - -) L.1istj+1 = L.1istj;L.1isti=item；L.size+；在此算法中，语句 if(item L.1isti) 中的 需要重载。9向线性表中按给定条件插入一个元素( P56 )bool InsertList( List &L，ElemType item，int pos)当 pos = 0 时，则需要实现在有序表上的插入，并且要保证插入新元素后仍为个有序表。当 pos = -1 时，要求把 item 插入到线性表的表尾，即第 L.size+1个元素的位置上。当 pos 的值 大于等于1 时，同时小于等于线性表的长度加 1 时，则直接把 item 插入到线性表的第 pos 个元素的位置上。实现这个函数需要注意如下三点:（1）在线性表的第 pos 个元素的位置插入一个新元素前，需要检查存储线性表的动态数组空间是否具有空闲位置，若没有，则要扩大原有的空间。 （2）为了实现在第 pos 个元素的位置插入新元素，需要把从该位置开始的其后的所有元素均后移一个位置，以便空出第 pos 个元素的位置，用于写入新元素。 （3）完成新元素的插入后，要使线性表的长度域增加 1。 根据以上分析编写出的算法如下。bool InsertList( List &L，ElemType item，int pos) / 检查pos值是否有效，若无效则无法插入，返回假 if ( pos L.size +1 ) cout “pos的值无效!”endl； return false； / 求出按值有序插入时item的插入位置，使把该插入位置的值保存到变量 pos 中。int i ；if ( pos = = 0) for ( i=0；i L. Size；i+ ) if ( item L.listi ) break； pos = i+l； / pos中保存新插入的元素的序号 / 当在表尾插入时，pos中保存新插入的元素的序号else if (pos = = -1) pos = L.size + 1； / 判断线性表的存储空间是否已用完，若已用完，则重新分配大一倍的存储空间。if( L.size = = L.MaxSize ) int k = sizeof ( ElemType)； / 计算每个元素占用存储空间的长度/ 线性表动态存储空间扩展为原来的2倍，原内容不变 L.1ist = ( ElemType * ) realloc( L.1ist，2*L.MaxSize*k)； if ( L.1ist = NULL ) cout“动态可分配的存储空间用完，退出运行！”= pos -1；i - -) L.1isti+1 = L.1isti； / 把 item 的值赋给已空出的、下标为 pos-1 的位置，它为第 pos 个元素位置 L.1istpos-1 = item； L.size + +； / 线性表长度增加 1 return true； / 返回真表示插入成功 * 从线性表中删除表头元素 删除过程如下： (1) 检查线性表是否为空，若是则给出错误信息并中止执行； (2) 把表头元素赋给一个临时变量暂存起来； (3) 从第2个元素起至最后一个元素止，依次使每一个元素前移一个位置； (4) 使线性表的长度减1； (5) 返回暂存在临时变量中的原表头元素。 ElemType DeleteFront(List&L) if(L.size= =0) cerr“Deleting from an empty list!”endl；exit(1)；ElemType temp=L.1ist0； for(int i=1；iL.size；i+) L.1isti-1=L.1isti； L.size-； return temp； * 从线性表中删除等于给定值的第一个元素 删除过程为： (1) 检查线性表是否为空，若是则显示出表空信息并返回假； (2) 从线性表中顺序查找其值等于给定值的第一个元素，直到查找成功或失败为止； (3) 若查找失败则返回假； (4) 若查找成功，则删除被查找到的那个元素，并使它后面的所有元素均前移一个位置； (5) 使线性表的长度减 1； (6) 算法最后返回真，表明删除成功。int Delete(List&L，const ElemType &item) if(L.size= =0) cerr“L is an empty list!”endl； return 0； for( int i=0；i L.size；i+) if( L.1isti = = item) break； if( i= =L.size) cerr“Deleted element is not exist!”endl； return 0； for( int j = i+1; jL.size; j+) L.1isti-1 = L.1isti； L.size - -； return 1; 10从线性表中删除符合给定条件的第 1 个元素bool DeleteList( List &L，ElemType & item，int pos)当 pos = 0 时，则需要实现在有序表上的删除，并且要保证在删除元素后仍为个有序表。当 pos = -1 时，要求删除表尾元素。当 pos 的值 大于等于1 时，同时小于等于线性表的长度加 1 时，则直接删除线性表中第 pos 个位置上的元素。 被删除元素的值，是由 item 来带回。 此算法同插入元素的算法类似，具体描述如下。bool DeleteList ( List &L，ElemType &item，int pos) / 检查线性表是否为空，若是则无法删除，返回假 if( L.size = = 0 ) cout “线性表为空，删除无效!” endl； return false； / 检查pos的值是否有效，若无效则无法删除，返回假 if ( pos L.size ) cout pos的值无效！”endl；return false； /求出按值删除时item的删除位置，使之保存到pos中 int i； if ( pos = =0 ) for ( i =0；i L.size；i +) if ( item =L.1isti ) break； if ( i =L.size) return false； /无元素可删, 返回假 pos = i+l； / 若删除的是表尾元素，则用 pos 保存该元素的序号 else if ( pos = = -1) pos=L.size； item = L.1istpos-1；/把被删除元素的值赋给变参item带回 / 将待删除元素位置后面的所有元素，从前向后依次前移一个位置for ( i = pos；i L.size；i + ) L.1isti-1 = L.1isti ； L.size - -； / 线性表长度减 1 / 若线性表存储空间空余太多，则进行适当削减if ( float (L.size)L.MaxSize 10 ) int k = sizeof (ElemType)；/计算每个元素存储空间的长度/ 线性表动态存储空间缩减为原来的一半 L.1ist= ( ElemType * ) realloc( L.1ist，L.MaxSize*k2)； L.MaxSize = L.MaxSize2； / 把线性表空间大小修改为新的长度 return true； / 返回真表示删除成功 11对线性表进行排序 对线性表进行排序就是按照元素的值或某个域的值的升序(或降序)排列元素，使之成为一个有序表。对线性表(数组)进行排序的方法很多，这里只介绍插入排序方法。方法是：把线性表 list0 listn-1 中共n个元素看作一个有序表和一个无序表；开始时有序表中只有一个元素 list0，一个元素总认为是有序的；无序表中包含有 n-1个元素 list1listn-1； 以后每次从无序表中取出第1个元素，把它插入到前面有序表中的合适位置，使之成为一个新的有序表。这样有序表就增加了一个元素，无序表就减少了一个元素，经过 n-1 次后，有序表中包含有 n 个元素，无序表变为一个空表，整个线性表就成为了一个有序表。例如：假定一个线性表为(42，65，80，74，28，44，36，65)则插入排序的过程为： 42 65 80 74 28 44 36 65 (1) 42 65 80 74 28 44 36 65 (2) 42 65 80 74 28 44 36 65 (3) 42 65 74 80 28 44 36 65 (4) 28 42 65 74 80 44 36 65 (5) 28 42 44 65 74 80 36 65 (6) 28 36 42 44 65 74 80 65 (7) 28 36 42 44 65 65 74 80方括号内表示每次排序后得到的有序表，方括号后面为待排序的无序表。void SortList( List & L) int i，j； ElemType x； for(i=l；i=0; j- -) /向前顺序进行比较和移动 if(xL.1istj) L.1istj+1=L.1istj； else break； L.1istj+1=x； /把x写入到已经空出的第j+1位置 此外，利用现成的向线性表插入元素的 InsertList 算法，也可以很方便地编写出 Sort 排序算法。该算法需要首先定义一个临时线性表并进行初始化，接着将形参线性表L中的每一个元素通过Insert算法依次插入到临时线性表中，最后把临时线性表赋给L即可。void SortList(List&L) List a； InitList(a)； for( int i = 0；i L.size；i +) InsertList( a，L.1isti, 0 )； L=a； 使用线性表操作函数的一个完整例子：# include # includetypedef int ElemType;struct List ElemType *list；/ 存线性表元素的动态存储空间的指针 int size； / 存线性表长度 int MaxSize； / 规定 list 数组的长度 ；void main( ) / 添加上面介绍的 11 个算法 int a12 = 3，6，9，12，15，18，21，24，27，30，33，36； int i ；ElemType x ； List t ； InitList( t )； for ( i=0；i 12；i +) InsertList ( t，ai，i+1)； InsertList ( t，48，13)；InsertList ( t，40，0)； cout GetList ( t，4) GetList ( t，9 ) endl； TraverseList ( t )； cout x； if ( FindList ( t，x ) ) cout 查找成功! ” endl； else cout 查找失败!” endl； cout x； if ( DeleteList (t，x，0) ) cout删除成功!”endl； else cout 删除失败!”endl； for ( i=0；i6；i+) DeleteList( t，x，i+1)； TraverseList(t)； coutx； if ( InsertList( t，x，0) cout 插入成功!” endl； else cout “插入失败!” endl； TraverseList ( t )； cout 线性表长度:” LenthList( t ) endl； if ( EmptyList( t ) ) cout 线性表为空!” endl； else cout线性表不空!”endl； ClearList(t)； 运行这个程序，得到的一次运行结果如下:12 273 6 9 12 15 18 21 24 27 30 33 36 40 48输入待查找的元素值：21查找成功!输入待删除元素的值：15删除成功!6 12 21 27 33 40 48按值插入，输入待插入元素的值：8插入成功!6 8 12 21 27 33 40 48线性表长度：8线性表不空! 2.3 线性表应用举例利用线性表来管理一个商品库存表。假定商品库存表已经保存在文本文件a: goods.dat”中。每个商品记录有四项内容：商品代号、商品名称、最低库存量、当前库存量。商品库存表中的具体内容如下表所示。 商品代号 商品名称 最低库存量 当前库存量 Y-12 Tooth brush 10 25 F-13 soap 20 48 W-01 Toilet paper 10 36 M-48 towel 15 90 C-24 China cup 10 52 S-05 School bag 5 20对商品库存表的管理就是首先把它读人到内存线性表中，接着对它进行必要处理，然后再把处理后的结果写回到文件中。这包括以下选项： (1) 打印(遍历)库存表； (2) 按商品代号修改记录的当前库存量，若查找到对应的记录，则从键盘上输入其修正量，把它累加到当前库存量域后，再把该记录写回原有位置，若没有查找到对应的记录，则表明是一条新记录，应接着从键盘上输入该记录的商品名称、最低库存量和当前库存量的值，然后把该记录追加到库存表中； (3) 按商品代号删除指定记录； (4) 按商品代号对库存表中的记录排序。 用户可以事先通过调用下面的函数在A盘上建立库存表文件：void SetupGoodsFile( char *fname)ofstream ofstr(fname);if(!ofstr) cerr“File goods no create!”endl； exit(1)； char a30； for(int i=0；i6；i+) / 每循环一次从键盘上读人一条商品记录(即一行数据，每个域值用空格分开，最后以按下回车键结束)到字符数组a中，然后再把它写入文件中 cin.getline(a, 30)； ofstr a endl； ofstr.close( )； 根据商品库存表中商品记录的结构，定义记录类型如下： struct goods / 商品记录类型 char code5； / 商品代号 char name15； / 商品名称 int minq； / 最低库存量 int curq； / 当前库存量； 通过 typedef 语句把该类型定义为线性表的通用元素类型：typedef goods ElemType； 假定在商品库存表中，以商品代号域作为查找字段域，则定义重载（= =）等于运算符的操作函数为：bool operator =(const ElemType &e1, const ElemType &e2) return(strcmp(e1.code，e2.code)= =0)； 在插入和排序中使用的小于号操作符重载如下： bool operator (const ElemType&e1, const ElemType&e2) return(strcmp(e1.code，e2.code)= = -1)； 用于打印输出的操作符也需要进行重载： ostream &operator (ostream &ostr, const ElemType &x) ostr.setf(ios:left); / 设置每个区域内按左对齐显示ostr setw(6) x.code setw(12) ;ostr setw(4) x.minq setw(4)x.curqendl； return ostr； 对商品库存表的管理就是首先把它读入到内存线性表中，接着对它进行必要的处理，然后再把处理后的结果写回到文件中。这包括以下选项： (1) 打印(遍历)库存表； (2) 按商品代号修改记录的当前库存量，若查找到对应的记录，则从键盘上输入其修正量，把它累加到当前库存量域后，再把该记录写回原有位置，若没有查找到对应的记录，则表明是一条新记录，应接着从键盘上输入该记录的商品名称、最低库存量和当前库存量的值，然后把该记录追加到库存表中； (3) 按商品代号删除指定记录； (4) 按商品代号对库存表中的记录排序。 假定在顺序存储方式下对线性表的各种操作函数包含在list.cpp”头文件中，则实现库存表管理的完整程序如下：/ 程序2-1# include# include# include# include# include# include “list.cpp” struct goods / 商品记录类型 char code5； / 商品代号 char name15； / 商品名称 int minq； / 最低库存量 int curq； / 当前库存量 typedef goods ElemType； struct List ElemType *list；/存线性表元素的动态存储空间的指针int size； / 存线性表长度int MaxSize； / 规定 list 数组的长度 int operator = = (const ElemType&e1, const ElemType&e2) return( strcmp(e1.code，e2.code )=0)；int operator (const ElemType&e1, const ElemType&e2) return(strcmp(e1.code，e2.code)= = -1)；ostream&operator(ostream&ostr，const ElemType&x) ostr.setf(ios:left); /设置每个区域内按左对齐显示ostr setw(6) x.code setw(12) ;ostr setw(4) x.minq setw(4)x.curqendl； return ostr；void SetupGoodsList ( List &L，char *fname ) / 将文件fname中所存商品表顺序读入内存的线性表 L 中，以便处理。 ifstream ifstr(fname，ios:in | ios:nocreate)； if(!ifstr) ce