实验一线性表的基本操作实现及其应用

《实验一线性表的基本操作实现及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。二、实验内容«1、单链表的表示与操作实现（*）2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。2、力旷杆题目必做，其他题目任选；多选者并且保质保量完成适当加分。3、严格按照数据结构实验报告模板和规范，及时完成实验报告。!1!实验步骤（说明：依据实验内容分别说明实验程序屮用到的数据类

2、型的定义、主程序的流程以及每个操作（函数）的伪码算法、函数实现、程序编码、调试与分析。附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序屮每个模块或函数应加注释，说明两数功能、入口及出口参数）1、单链表的最大长度#defineMAXSIZE1002、单链表的结点类型定义/*定义elemtype为int类型*/typedefintelemtype;/*单链表的结点类型*/typedefstructSTD{clcmtypcc1cm;STD*next;}list,*1inklist;3、初始化单链表参数：链表(1inklistL)成功

3、初始化返回1,否则返回0*/intinit(linklist&L)(L=(linklist)malloc(sizeof(1ist));//头结点申请内存。if(!L)〃判断有无申请到空间。return0;//没有申请到内存，参数失败返回0L->next=NULL;L->elem=0;//单链表中有多少元素return1;//成功参数返回1}4、清空单链表/*函数功能：把链表清空参数:链表(1inklistL)成功清空链表返回1*/intmakeemptj^(1inklist&L){1inklistp,q;p=L->next;while(

4、p)//当p非空时，删除pq=P；p=p->next;free(q);//只剩头指针，所以L->next=NULL//清空后链表中元素为0//淸空后返回1}L->next=NULL;L->elem=0;return1;求链表长度/*函数功能:返回链表的长度参数;链表(1inklistL)函数返回链表的长度intgetlength(1inklistL)1inklistp;p=L->next;intj=0;whi1c(p)j++;p=p->next;//统计链表中元素}//最后返回链表长度.returnj;判断链表是否为空*函数功能:判断链

5、表是否为空*/参数;链表(1inklistL)链表为空时返回0,不为空返回1intisempty(1inklistL)//头结点后有元素表示链表不空则返回1//头结点后没有元素表示链表不空则返回0if(L->next)return1;elsereturn0;)7、检查链表是否为满/*函数功能:判断链表是否为满参数;链表(linklistL)链表为满时返回0,不为满返回1intisful1(linklistL)<=MAXSIZE)1；//头结点的elem储存的为链表的长度。//其小于MAXSIZE表示链表不满if(L->elemretur

6、nelsereturn0；//否则返回08、遍历链表/*函数功能:遍历链表，输出每个节点的elem值参数;链表(linklistL)通过循环逐个输出节点的eleni值voidshow(linklistL)1inklistp;p=L-〉next;//当链表为空时则输出链表为空if(isempty(L)==0)cout«H链表为空!while(p)//当链表为不空时则输出链表每个节点的elem值cout<elem<next;cout«cndl;9、从链表中查找元素/*函数功能：从链表中查找有无给定元素参数;链表(lin

7、klistL),给定元素(inti)如果链表中有给定元素⑴则返回1,否则返回0intfind(1inklistL,inti)1inklistp;p=L->next;whi1e(p){if(p->elem==i)//判断有无元素I,有返回1return1;p=p->next;}10、从链表中查找与给定元素值相同的元素在表中的位置/*函数功能：从链表中查找给定元素的位置参数;链表(linklistL),给定元素(inti)如果链表中有给定元素i则返回元素的位置，没有则返回0*intlocation(linklistL,inti)(1inkl

8、istp;intj=0;p=L->next;while(p){j++；if(p->elem==i)//判断有无元素i,有返回其的位置jreturnj;p=p->next;}return0;//没有则返回0}