数据结构实验二 线性表及其应用.docx

1、数据结构实验二 线性表及其应用第二章线性表及其应用 【实验目的】1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4. 通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。第一节知识准备一、线性表的逻辑结构线性表是由一组具有相同特性的数据元素组成的有限序列。至于每个数据元素，它可以是一个数，一个符号，也可以是一页书，甚至更复杂的信息。例如：26个英文字母构成一个线性表（A，B，C，Y，Z）一串数字构成另一

2、个线性表（45，45，32，65，123）每个数据元素可以由若干数据项组成，常把此数据元素称为记录。能唯一标识一个记录的数据项的值称为关键字。如：一个学校的学生情况表如表2-1所示，表中每个学生的情况为一个记录，它由学号、姓名、性别、年龄、年级等五个数据项组成。学号 姓名 性别 年龄 年级96001 张平 女 21 大二96002 王极 男 20 大一96003 膨磊 男 23 大三96004 严正英 女 19 大一96005 李强 男 20 大二综上所述，线性表有如下特性：1 除第一个和最后一个元素以外，每个元素有且仅有一个直接前趋和一个直接后继；第一个结点只有直接后继，最后一个结点只有直接

3、前趋。2 线性表中的每个数据元素，其数据类型是一致的。3 数据元素之间的相对位置是线性的，结构中的数据元素之间存在一个对一个的关系。二、线性表的顺序表示和实现计算机的内存是由有限多个存储单元组成的，每个存储单元都有对应的整数地址，各存储单元的地址是连续编号的。对于一个线性表，如果用一组连续的存储单元依次存放它的各个数据元素，这就是线性表的顺序分配。也就是说，在线性表的顺序分配结构中，逻辑结构上相邻的数据元素，其物理位置也是相邻的。若一个数据元素只占用一个存储单元，则这种分配方式如图2-1所示。从图可知，线性表的第i个数据元素的存储地址LOC（ai）=LOC（a1）+（i-1）如果一个数据元素占

4、据k个存储单元，则有LOC（ai）=LOC（a1）+（i-1）k其中，LOC（a1）是线性表的第一个数据元素的存储地址。三、 线性表的链式表示和实现1.单链表线性链表即线性表的链式存储结构是用一组任意的存储单元（它们可以是连续的，也可以是不连续的）来存储线性表的各个数据元素。为了表示每个元素与其直接后继元素之间的逻辑关系，对每个元素来说，除了需要存储元素本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成了一个数据元素的存储结构，称之为一个结点（node），当然每一个结点占用的存储单元应该是连续的。这样，每个结点包括两个域，存储数据元素本身信息的域称之为

5、数据域（data），存储直接后继结点存储位置的域称之为指针域（next），该域内信息为一指针，它指出线性表某一数据元素逻辑上直接后继元素的存储位置。由于线性表的最后一个数据元素没有后继，故相应结点的指针域内容为空NULL（也可以用符号表示）。如图2-2所示为一个不带头结点的单链表。在实际应用中，有时也使用带头结点的单链表，如图2-3所示，虽然浪费了一个结点，但是却换来了其它操作的便利，例如在插入删除操作中，不用判断是否对第一个结点进行。我们称这个结点为“哨兵”，其作用往往是不用判断出界；在以后的学习中，还会经常遇上“哨兵”。2.循环链表循环链表是线性表的一种特殊的链式存储结构，它的特点是线性链

6、表的最后一个结点（即表尾结点）的指针域存放链表中第一个结点的地址，则整个链表形成了一个环。如图2-4所示。3.双向循环链表双向循环链表是对循环链表的改进，当我们需要经常查找某一节点的前驱时，可以增加一个指向前驱的指针域，构成双向循环链表。如图2-5所示。第二节狐狸逮兔子实验【问题描述】围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到号洞找，第二次隔个洞（即3号洞）找，第三次隔个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？这实际上是一个反复查找线性表的过程，用以前学

7、过的程序设计的知识也很容易实现，这里希望读者能体会数据结构的思想。【数据描述】定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。#defineLIST_INIT_SIZE10/线性表存储空间的初始分配量typedefstructElemType*elem;/存储空间基址intlength;/当前长度intlistsize;/当前分配的存储容量（以sizeof(ElemType)为单位）SqList;【算法描述】statusInitList_Sq(SqList&L)/构造一个线性表LL.elem=(ElemType)malloc(LIST_

8、INIT_SIZE*sizeof(ElemType);If(!L.elem)returnOVERFLOW; /存储分配失败L.length=0; /空表长度为0L.listsize=LIST_INIT_SIZE; /初始存储容量returnOK;/InitList_SqstatusRabbit(SqList&L)/构造狐狸逮兔子函数intcurrent=0; /定义一个当前洞口号的记数器，初始位置为第一个洞口for(i=0;iLIST_INIT_SIZE;i+)L.elemi=1; /给每个洞作标记为1，表示狐狸未进之洞L.elemLIST_INIT_SIZE-1=L.elem0=0;/首先进

9、入第一个洞，标记进过的洞为0。for(i=2;i=1000;i+)current=(current+i)%LIST_INIT_SIZE;/实现顺序表的循环引用L.elemi=0; /标记进过的洞为0/第二次隔个洞找，第三次隔个洞找，以后如此类推,经过一千次printf(兔子可能藏在如下的洞中：)for(i=0;iLIST_INIT_SIZE;i+)if(L.elemi=1)printf(“第%d个洞n”,i+1);/输出未进过的洞号returnOK;/end【C源程序】#include#include#defineOK1#defineOVERFLOW-2typedefintstatus;typ

10、edefintElemType;#defineLIST_INIT_SIZE10 /*线性表存储空间的初始分配量*/typedefstructElemType*elem; /*存储空间基址*/intlength; /*当前长度*/intlistsize; /*当前分配的存储容量（以sizeof(ElemType)为单位）*/SqList;statusInitList_Sq(SqList*L)/*构造一个线性表L*/(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem)returnOVERFLOW;/*存

11、储分配失败*/(*L).length=0; /*空表长度为0*/(*L).listsize=LIST_INIT_SIZE; /*初始存储容量*/returnOK;/*InitList_Sq*/statusRabbit(SqList*L)/*构造狐狸逮兔子函数*/inti,current=0; /*定义一个当前洞口号的记数器，初始位置为第一个洞口*/for(i=0;iLIST_INIT_SIZE;i+)(*L).elemi=1; /*给每个洞作标记为1，表示狐狸未进之洞*/(*L).elemLIST_INIT_SIZE-1=0;(*L).elem0=0; /*第一次进入第一个洞，标记进过的洞为0

12、*/for(i=2;i=1000;i+)current=(current+i)%LIST_INIT_SIZE;/*实现顺序表的循环引用*/(*L).elemcurrent=0; /*标记进过的洞为0*/*第二次隔个洞找，第三次隔个洞找，以后如此类推,经过一千次*/printf(n兔子可能藏在如下的洞中：);for(i=0;i=1;i-)if(!(p=(CNode*)malloc(sizeof(CNode)returnoverflow;/存储分配失败p-data=i;p-next=clist;clist=p;if(i=n)q=p;/用q指向链表的最后一个结点q-next=clist;/把链表的最

13、后一个结点的链域指向链表的第一个结点，构成循环链表ok;/endstatusJoseph(intm,intn,intk)if(mn)returnERROR;/起始位置错if(!Create_clist(clist,n)returnERROR;/循环链表创建失败p=clist;for(i=1;inext;/p指向m位置的结点while(p)for(i=1;inext;/找出第k个结点q=p-next;printf(“%d”,q-data);/输出应出列的结点if(p-next=p)p=null;/删除最后一个结点elsep-next=q-next;/删除第K个结点p=p-next;/使P指向第k

14、+1个元素位置free(q);/whileclist=null;/end【C源程序】#include#include#defineNULL0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;typedefintElemtype;/*定义数据元素类型*/typedefstructCnodeElemtypedata;structCnode*next;CNode;CNode*joseph;/*定义一个全局变量*/StatusCreate_clist(CNode*clist,intn)CNode*p,*q;inti;clist=NULL;

15、for(i=n;i=1;i-)p=(CNode*)malloc(sizeof(CNode);if(p=NULL)returnOVERFLOW;/*存储分配失败*/p-data=i;p-next=clist;clist=p;if(i=n)q=p;/*用q指向链表的最后一个结点*/q-next=clist;/*把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表*/joseph=clist;/*把创建好的循环链表头指针赋给全局变量*/returnOK; /*end*/StatusJoseph(CNode*clist,intm,intn,intk)inti;CNode*p,*q;if(mn)

16、returnERROR;/*起始位置错*/if(!Create_clist(clist,n)returnERROR; /*循环链表创建失败*/p=joseph; /*p指向创建好的循环链表*/for(i=1;inext; /*p指向m位置的结点*/while(p)for(i=1;inext; /*找出第k个结点*/q=p-next;printf(%d,q-data);/*输出应出列的结点*/if(p-next=p)p=NULL; /*删除最后一个结点*/elsep-next=q-next;p=p-next;free(q);/*while*/clist=NULL;/*end*/voidmain(

17、)intm,n,k,i;CNode*clist;clist=NULL;/*初始化clist*/printf(n请输入围坐在圆桌周围的人数n：);scanf(%d,&n);printf(n请输入第一次开始报数人的位置m：);scanf(%d,&m);printf(n你希望报数到第几个数的人出列?);scanf(%d,&k);Create_clist(clist,n);/*创建一个有n个结点的循环链表clist*/printf(n出列的顺序如下：n);Joseph(clist,m,n,k);getch();/*main*/【测试数据】1、请输入围坐在圆桌周围的人数n：7请输入第一次开始报数人的位置

18、m：3你希望报数到第几个数的人出列?2出列的顺序如下：46137522、请输入围坐在圆桌周围的人数n：13请输入第一次开始报数人的位置m：5你希望报数到第几个数的人出列?6出列的顺序如下：103941275261181133、请输入围坐在圆桌周围的人数n：21请输入第一次开始报数人的位置m：3你希望报数到第几个数的人出列?9出列的顺序如下：112081871910215941213614121351617【说明】本算法采用一个不带表头的循环链表来处理约瑟夫问题，在此算法中，每次找出需出列结点，要经过k次循环移动定位指针，全部结点出列，需经过n个k次循环，因此，本算法的时间复杂度为O（k*n）。

19、实际问题的处理中，有许多与约瑟夫问题类似，都可以采用此方法完成。【实验题】1. 处理约瑟夫问题也可用数组完成，请读者自己编写使用数组实现约瑟夫问题的算法和程序。2. 猴王问题。某森林中有n只猴子在商量猴王选举问题，所有的猴子都想当猴王，因此大家商量了一个选举办法如下：所有的猴子围成一圈，先从第一个猴子开始报数，报数到13的猴子就出列。紧接着的下一个猴子，又从1开始进行新的一轮报数，报数到12的猴子再出列；依此重复下去，每一轮报数都比上一轮的报数少1，直到报数减为1之后，又从13开始报数。直到原列中只剩下一个猴子为止，这个猴子就是猴王。试设计一个程序求出猴王。第四节思考题1. 假设有两个按元素值

20、递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。（上海交通大学一九九九年硕士生入学考试试题）【简要分析】除了指向线性表C头结点的指针外，还需设置三个指针Pa，Pb，Pc；首先Pa，Pb分别指向线性表A和B的表头，Pc指向A和B的表头值较小的结点，线性表C头节点的指针等于Pc；然后，比较Pa与Pb的值的大小，让Pc的后继指向较小值的指针，接着Pc向后移动，较小值的指针也向后移动，以此类推，直到Pa，Pb中某一个为空，这时，让Pc的后继指向Pa，Pb中非空的指针就完成了

21、C表的建立。2. 给定一个整数数组b0.N-1,b中连续相等元素构成的子序列称为平台.试设计算法,求出b中最长平台的长度.（中科院计算机技术研究所1999年硕士入学考试数据结构与程序设计试题）【简要分析】设置一个平台长度变量Length和一个计数器Sum。初始化Length为1，Sum为1，再设置两下标指针i、j，首先，i指向第一个数组元素，j指向其次的第二个元素，比较i、j指向元素值的大小，若相等，则Sum+，i+，j+，再次比较i、j指向元素值的大小；若不相等，则比较Length与Sum的大小，如果Sum值大于Length，则把Sum的值赋给Length，Sum的值重置为1，同时i，j也向

22、前各移动一位；重复上面的过程，直到i指向最后一个元素为止，此时的Length就是最长平台的长度。3. 参加知识竞赛的n个学校（编号为1n），每个学校派至多m名学生参赛，每个学生的编号有二位学校代码和五位座位编号构成。统计每个学校的参赛学生的平均分，并依次确定学校的名次；查找竞赛的最高分和最低分，并计算它们的方差；给出前三名学生的具体信息。【简要分析】本题解决办法较多。我们可以采用单链表来对所有学生的信息进行存储，至多需要n*m个结点，每个结点至少包含如下几个域：2位学校代码、5位座位编号、学生姓名、竞赛成绩等。也可以采用顺序表来对所有学生的信息进行存储，构造一个结构体数组，至多需要n*m个数组

23、元素，每个数组元素的数据项值与单链表中的结点域值类似。然后再另外构造一个存储学校信息的顺序表或单链表，每个结点至少包含如下几个域：二位学校代码、学校名称、学校取得的平均分、学校名次等。在构造好所有的存储结构之后，就可以编制相应的计算平均分、排序、查找、输出等算法了。ChapterTwoLinear_ListanditsapplicationsObjectives1. TounderstandbasicoperationsofLinear_ListinimplementationofSequence_ListandLink_List.2. TofocusonbasicoperationsofLinear_List,suchas,creation,insertion,deletionandtraversal.3. Tounderstanddefinitionandbasicoperationofdynamicallocationlist.4. TohelpstudentsbetterunderstandapplicationsofCprogramlanguagethroughexperiments.Especially,focusonfunctioncall,applicationofpointertypeandcreationofLink_List,etc.