21世纪高等学校计算机专业核心课程规划教材数据结构(C语言描述)(第2版)/徐孝凯

第3章线性表 3．1线性表的定义和运算 1． 线性表的定义 线性表(linear list)是具有相同属性的数据元素的一个有限序列，该序列中的元素值允许出现重复，各元素之间存在着线性关系。该序列中元素的个数称为线性表长度。线性表长度可以为0，表明它是一个空表，即不含有任何元素。若线性表为一个非空表，则一般表示为： (a1,a2,…,ai,ai+1,…,an) 一个线性表用一对圆括号括起来，线性表中的**个元素a1称为表头元素，an称为表尾元素，线性表长度n大于等于0。 通常可以为一个线性表命名，即用一个标识符表示，此标识符通常采用大写。如可把上面这个线性表用A表示，即A=(a1,a2,…,ai,ai+1,…,an)。 线性表中的元素通常是按照其值或某个域的值(如关键字域的值)有序排列的，也就是说，线性表元素是按照前后位置线性有序的，即第i个元素ai在逻辑上是第i+1个元素ai+1的前驱，而反过来，第i+1个元素ai+1又是第i个元素ai的后继(1≤i＜n)。线性表中的**个元素只有后继没有前驱，而*后一个元素则只有前驱没有后继，其余每个元素既有一个前驱也有一个后继。 线性表中的元素是线性有序的，用二元组表示为 linear_list=(A,R) 其中 A={ai|1≤i≤n, n≥0, ai∈ElemType} R={ | 1≤i≤n-1} 对应的逻辑图如图31所示。 图31线性表的逻辑结构示意图 线性表的逻辑结构是线性结构，它是线性结构数据的一种简略表示。如对于第1章中讨论的线性数据结构linear可用线性表表示为： (05，01，03，08，02，07，04，06，09，10) 因此，以后对线性表的讨论就代表了对任何线性结构数据的讨论。 在日常生活中所见到的各种各样的表都是线性表的例子，如人事档案表、职工工资表、学生成绩表、图书目录表、列车时刻表、产品目录表等。每一种这样的表通常都以记录登记的先后次序排列，或以关键字(即某个域的值)升序或降序排列。如职工工资表按职工号字段的升序排列，学生成绩表按学生号字段的升序排列，列车时刻表按开出时间字段的升序排列等。 线性表中的元素个数和内容通常是变化的，但元素之间的逻辑关系应保持不变，当从一个位置上删除一个元素后，其后的所有元素都要依次前移一个位置，同样，当向一个位置插入一个元素前，该位置及以后的所有元素都要依次后移一个位置。保持元素之间的次序不变是线性表同集合的根本区别所在，从集合中删除一个元素后，不需依次移动元素，只需简单地用*后一个元素来填补； 向集合插入元素不需要考虑插入位置，因而不需要移动任何元素，只要简单地放到顺序存储的末尾或链接存储的表头即可。 2． 线性表的抽象数据类型 线性表的抽象数据类型同样由数据和操作这两个部分组成。数据部分为一个线性表，假定用标识符L表示，它可以采用任一种存储结构实现，为了算法需要和便于参数传递，假定将把它定义为一种指针类型。操作部分包括插入、删除、查找、修改、排序、遍历输出等对线性表的典型运算。利用这些典型运算的算法，可以很容易编写出对线性表的其他任何运算的算法。 线性表的抽象数据类型可定义如下。 ADT LIST is Data: 一个指向线性表的指针L，假定用标识符List表示线性表的抽象存储类型 Operation: void initList(List* L int ms); //初始化线性表为空 int getList(List* L, ElemType* item, int pos); //带回表中第pos个元素值 int findList(List* L, ElemType* item); //从表中查找元素并带回 int modifyList(List* L, ElemType item); //修改表中的元素值 int insertList(List* L, ElemType item, int k); //向表中指定位置插入元素 int deleteList(List* L, ElemType* item); //从表中删除元素并带回 int emptyList(List* L); //判断线性表是否为空 int lengthList(List* L); //求出线性表长度 void outputList(List* L); //遍历输出线性表 List* sortList(List* L); //返回按值有序排列的表 void clearList(List* L); //清除线性表中的所有元素 end LIST 3． 线性表运算举例 假定一个整型数组a［5］={25,38,19,42,33},x=60,y=19，则对线性表L可进行如下运算。 initList(L,10); //初始化L为一个空表，其存储表数组的长度为10 for(i=0; i insertList(L,a［i］,0); //假定参数k的值为0，表示向线性表末尾插入元素 deleteList(L,&y); //从线性表L中删除元素19，L变为{25,38,42,33} insertList(L,x,2,); //向L中第2个位置插入x，L变为{25,60,38,42,33} R=sortList(L); //对L中的元素按值排序生成一个新的有序表返回 //返回后赋给R，则R为{25,33,38,42,60}，L不变 clearList(L); //清除L中的所有元素，使之变为空表 3．2线性表的顺序存储结构和操作实现 同集合的顺序存储结构一样，线性表的顺序存储结构也是利用一个数组来实现的，为了保存线性表的长度也需要定义一个整数变量，同样也需要定义一个符号常量来存储数组长度，亦即所能表示的线性表的*大长度。这三个对象可以定义如下： #define MaxSize 20 //定义存储线性表元素的数组长度 ElemType list［MaxSize］; //定义存储线性表所有元素的数组 int len; //定义保存线性表当前长度的变量 线性表中的每个元素将依次被存入到一维数组list中，具体地说，线性表中**个元素a1被存入到list［0］中，第二个元素a2被存入到list［1］中，以此类推，*后一个元素an被存入到list［n-1］中。在这种顺序存储结构中，线性表元素之间的线性关系就通过存储位置之间的先后下标关系自然地反映出来，即list［i］的前驱元素是它的前一个存储位置上的元素list［i-1］，后继元素是它的后一个存储位置上的元素list［i+1］，下标为0的元素没有前驱，下标为len-1的元素没有后继。 为了对线性表操作方便，通常把上面的三个量用一个结构类型来定义，并要求对存储线性表的数组存储空间采用动态分配，假定结构类型名用SequList表示，则具体定义类型如下。 struct SequList { //定义顺序存储线性表的结构类型 ElemType *list; //指向动态数组空间的指针 int len; //保存线性表的当前长度 int MaxSize; //保存list数组的长度 }; 通过下面的类型重定义语句，可以把线性表的抽象存储类型List具体定义为struct SequList类型，即顺序存储线性表的结构类型。 typedef struct SequList List; 下面依次给出在线性表的顺序存储的情况下，对线性表的每种运算的算法(即操作实现)。 1． 初始化线性表为空 同对集合进行初始化的操作一样，对线性表的初始化操作也要为保存线性表动态分配数组存储空间，并由list指针所指向，同时设置线性表长度len的值为0，表示当前为一个空表。初始化线性表算法的具体定义如下。 void initList(List* L, int ms) {//初始化线性表，分配动态存储和置为空表 if(msMaxSize=10; //若ms的值小于10，则设置数组长度为10 else L->MaxSize=ms; //若ms的值大于等于10，则设置其为ms的值 L->list=calloc(L->MaxSize,sizeof(ElemType)); //动态分配线性表空间 if(!L->list) {printf("动态空间用完!＼n"); exit(1);} //分配失败退出 L->len=0; //初始把线性表置为空 } 2． 得到线性表中第pos个元素的值 线性表中的第pos个元素被对应存储在list数组中下标为pos-1的位置上，此算法的pos的有效值应大于等于1和小于等于线性表的实际长度，若超出此范围则返回空指针，否则，由第pos个元素值生成一个动态元素结点，返回该结点指针。 int getList(List* L, ElemType* item, int pos) {//通过参数item带回线性表L中第pos个元素值并返回1，否则返回0 //检查pos值是否在有效范围内 if(posL->len) return 0; //用参数item带回线性表中第pos个元素的值 else {*item=L->list［pos-1］; return 1;} } 3． 从线性表中查找与item值相匹配的**个元素并由参数带回 从线性表中查找元素分为顺序查找和二分查找(又称折半查找、对分查找等，待以后介绍)两种。若线性表中的元素不是按其值或关键字有序排列，则只能采用顺序查找，否则可以采用二分查找。若采用顺序查找，它将从表头开始依次比较每个元素，当找到与item值或某个域的值相匹配的**个元素时表明查找成功，则用item带回其值并返回1； 若比较完所有元素后没有找到待查元素，则表明查找失败，应返回0。 在顺序存储的线性表上进行顺序查找的算法描述为： int findList(List* L, ElemType* item) {//从L中查找与item相匹配的**个元素，并由参数带回 //顺序查找值为item的元素，若查找成功则退出循环 int i=0; L->list［L->len］=*item;//将待查值保存到线性表末尾作为"岗哨" while(L->list［i］!=*item) i++; //当元素类型为结构时应比较其关键字域 //当查找成功时带回该元素值并返回1，否则返回0 if(ilen) {*item=L->list［i］; return 1;} else return 0; } 4． 修改线性表中与item值相匹配的**个元素值 此运算操作要求从顺序存储的线性表中首先查找出与item值相匹配的**个元素，通常是通过关键字是否相等的比较来查找相匹配的元素，然后用新值item修改原有值。利用此算法时，其线性表中的元素类型是包含多个成员域的记录结构类型，如对于一个保存学生成绩记录的线性表来说，要按照学生号作为关键字修改某个学生记录中的成绩值，就需要调用此算法，用该学生新的成绩记录值作为实参，算法执行结束后，该学生的原有记录将被新记录所取代，从而达到修改学生记录成绩的目的。此运算操作的算法描述如下。 int modifyList(List* L, ElemType item) {//修改线性表中与item值相匹配的**个元素值 int i=0; L->list［L->len］=item; //将修改值保存到线性表末尾作为"岗哨" while(L->list［i］!=item) i++; //当元素类型为结构时应比较其关键字域 //比较表达式可能被修改为L->list［i］.key!=item.key if(ilen) {L->list［i］=item; return 1;} else return 0; } 5． 向线性表中给定位置插入一个元素 向线性表L中的指定位置k插入一个元素item时，若给定值k在有效范围以内，则可以进行插入，否则不能进行插入，当插入成功时返回1，否则返回0。参数k的有效值范围是［0,L>len+1］，假定k的值取0或L>len+1时，则把item值插入到表尾，而当k取1~L>len之间任一个值时，则把item值插入到线性表L中的第k个元素的位置上，原来第k个元素及后面所有元素均需要后移一个位置。当然在插入时，若原有的动态数组空间即将用完，则需要重新分配更大的动态数组空间。 下面给出在顺序存储的线性表中按给定位置插入新元素的算法。