首页 数据结构(邹永林版)实验报告2-顺序表与链表

数据结构(邹永林版)实验报告2-顺序表与链表

举报
开通vip

数据结构(邹永林版)实验报告2-顺序表与链表实验二顺序表与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点(优缺点)。【实验学时】2学时【实验预习】回答以下问题:1、顺序表的存储表示在顺序表中,任一数据元素的存放位置是从起始位置开始、与该数据元素的位序成正比的对应存储位置,借助LOC(ai)=LOC(a1)+(i-1)*1确定,则顺序表是一种随机存取的存储结构。2、单链表的存储表示线性链表也称单链表,在每一个结点中只...

数据结构(邹永林版)实验报告2-顺序表与链表
实验二顺序 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 与链表【实验目的】1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点(优缺点)。【实验学时】2学时【实验预习】回答以下问 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 :1、顺序表的存储表示在顺序表中,任一数据元素的存放位置是从起始位置开始、与该数据元素的位序成正比的对应存储位置,借助LOC(ai)=LOC(a1)+(i-1)*1确定,则顺序表是一种随机存取的存储结构。2、单链表的存储表示线性链表也称单链表,在每一个结点中只包含一个指针,用于指示该结点的直接后继结点,整个链表通过指针相连,最后一个结点因为没有后继结点,其指针置为空(NULL)。这样,链表中所有数据元素(结点)构成一对一的逻辑关系,实现线性表的链式存储。【实验内容和要求】1、按照要求完成程序exp2_1.c,实现顺序表的相关操作。以下函数均具有返回值,若操作完成,返回OK,操作失败返回ERROR。函数需返回的其他数据,使用函数参数返回。exp2_1.c部分代码如下:#include#include#include#defineERROR0#defineMAXSIZE100#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructslist{ElemType*list;intlistsize;intlength;}Sqlist;Sqlist*L;/*(1)---补充顺序表的存储分配表示,采用定长和可变长度存储均可*//*函数声明*/intInitList_sq(Sqlist*L);intCreateList_sq(Sqlist*L);intListInsert_sq(Sqlist*L,inti,ElemTypee);intPrintList_sq(Sqlist*L);intListDelete_sq(Sqlist*L,inti,ElemType*e);intListLocate(Sqlist*L,ElemTypee,int*pos);intmenu_select();/*(2)---顺序表的初始化*/intInitList_sq(Sqlist*L){L->list=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(L->list==NULL)returnERROR;else{L->length=0;L->listsize=MAXSIZE;}return0;}/*InitList*//*(3)---创建具有n个元素的顺序表*/intCreateList_sq(Sqlist*L){inta,b,c;printf("请输入输入数据的个数n:");scanf("%d",&a);printf("请输入输入的数据:");for(b=0;blist[b]=c;}L->length=L->length+a;return0;}/*CreateList*//*(4)---输出顺序表中的元素*/intPrintList_sq(Sqlist*L){inta;printf("输出数据:");for(a=0;alength;a++)printf("%d",L->list[a]);return0;}/*PrintList*//*(5)---在顺序表的第i个位置之前插入新元素e*/intListInsert_sq(Sqlist*L,inti,ElemTypee){inta=L->length-1;for(;a>=i-1;a--)L->list[a+1]=L->list[a];L->list[i-1]=e;L->length+=1;returnOK;}/*ListInsert*//*(6)---在顺序表中删除第i个元素,e返回删除的元素*/intListDelete_sq(Sqlist*L,inti,ElemType*e){inta=i-1;*e=L->list[i-1];for(;alength;a++)L->list[a]=L->list[a+1];L->length-=1;returnOK;}/*ListDelete_sq*//*(7)---在顺序表中查找指定值元素,pos为返回其位置序号*/intListLocate(Sqlist*L,ElemTypee,int*pos){inta,b=0;for(a=0;alength;a++){if(e==L->list[a]){b=0;*pos=a+1;break;}elseb=1;}if(b==1)return0;elsereturnOK;}/*ListLocate*//*定义菜单字符串数组*/intmenu_select(){char*menu[]={"\n***************MENU******************\n","1.CreateList\n",/*创建顺序表*/"2.GetElement\n",/*查找顺序表中的元素*/"3.Insertdata\n",/*插入数据*/"4.Deletedata\n",/*删除数据*/"0.Quit\n",/*退出*/"\n***************MENU******************\n"};chars[3];/*以字符形式保存选择号*/intc,i;/*定义整形变量*/for(i=0;i<7;i++)/*输出主菜单数组*/printf("%s",menu[i]);do{printf("\nEnteryouchoice(0~4):");/*在菜单窗口外显示提示信息*/scanf("%s",s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/}while(c<0||c>4);/*选择项不在0~4之间重输*/returnc;/*返回选择项,主程序根据该数调用相应的函数*/}/*主函数*/intmain(){intm,k;intpos;intdeldata;Sqlistsl;InitList_sq(&sl);for(;;)/*无限循环*/{switch(menu_select())/*调用主菜单函数,返回值整数作开关语句的条件*/{case1:printf("\n1-CreateSqlist:\n");CreateList_sq(&sl);printf("\nPrintSqlist:\n");PrintList_sq(&sl);break;case2:printf("\n3-GetElemfromSqlist:\n");printf("pleaseinputsearchdata:");scanf("%d",&k);if(!ListLocate(&sl,k,&pos))printf("Notfound");else{printf("foundtheelement,positionis%d\n",pos);printf("\nPrintSqlist:\n");PrintList_sq(&sl);}break;case3:printf("\n4-InsertfromSqlist:\n");printf("\ninputinsertlocationanddata:(location,data)\n");scanf("%d,%d",&m,&k);if(ListInsert_sq(&sl,m,k)){printf("\nOK\n");printf("\nPrintSqlist:\n");PrintList_sq(&sl);}elseprintf("\nERROR!");break;case4:printf("\n5-DeletefromSqlist:\n");printf("\npleaseinputdeletelocation\n");scanf("%d",&k);if(ListDelete_sq(&sl,k,&deldata)){printf("\nOK\n");printf("\nDeletedatais%d\n",deldata);printf("\nPrintSqlist:\n");PrintList_sq(&sl);}elseprintf("\nERROR!");break;case0:exit(0);/*如菜单返回值为0程序结束*/}}return0;}(1)创建一个顺序表(2)查找元素位置(3)插入元素(4)删除元素2、按照要求完成程序exp2_2.c,实现单链表的相关操作。exp2_2.c部分代码如下:#include#include#include#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*//*(1)---线性表的单链表存储表示*/typedefstructLNode{ElemTypedate;structLNode*next;}LNode,*LinkList;LNode*InitList();/*带头结点单链表初始化*/voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/intGetElem(LinkListL,inti,ElemType*e);/*查找第i位置的元素,并由e返回其值*/intInsertElem(LinkListL,inti,ElemTypee);/*在第i个位置插入元素e*/intDeleteElem(LinkListL,inti,ElemType*e);/*删除第i位置的元素,并由e返回其值*/voidDestroyLinkList(LinkListL);/*释放链表及其空间*/LinkListCreateList(intn);/*创建n个结点的单链表*/intmenu_select();/*菜单函数*//*带头结点单链表初始化*/LNode*InitList(){LinkListL;L=(LNode*)malloc(sizeof(LNode));/*申请一个头结点*/if(!L)returnERROR;/*申请失败*/L->next=NULL;/*头结点的指针域置空*/returnL;}/*(1)---输出带头结点单链表的所有元素*/voidPrintList(LinkListL){LNode*p=L->next;inti=0;while(p){i++;printf("\n第%d个元素%d",i,p->date);p=p->next;}}/*PrintList*//*(2)---在单链表的第i个位置插入元素e,若插入成功返回OK,插入失败返回ERROR*/intInsertElem(LinkListL,inti,ElemTypee){LNode*p=L,*s;intj=0;while(p&&jnext;j++;}if(!p||j>i-1)returnERROR;s=(LNode*)malloc(sizeof(LNode));if(!s)returnERROR;s->date=e;s->next=p->next;p->next=s;returnOK;}/*InsertElem*//*(3)---查找第i位置的元素,若存在返回OK并由e返回其值,若不存在返回ERROR*/intGetElem(LinkListL,inti,ElemType*e){LNode*p;intj=1;p=L->next;while(p&&jnext;j++;}if(!p||j>i)returnERROR;*e=p->date;returnOK;}/*GetElem*//*(4)---删除第i位置的元素,成功返回OK,并由e返回其值,若不成功返回ERROR,注意删除的结点必须释放其所占空间*/intDeleteElem(LinkListL,inti,ElemType*e){LNode*p=L,*s;intj=0;while(p&&jnext;j++;}if(!p||j>i-1)returnERROR;s=p->next;p->next=s->next;*e=s->date;free(s);returnOK;}/*DeleteElem*//*(5)---创建具有n个结点的单链表,创建成功返回其头指针*/LinkListCreateList(intn){inti=1;LNode*p,*q,*L;L=InitList();p=L;while(i<=n){q=(LNode*)malloc(sizeof(LNode));printf("输入链表的结点date%d:",i++);scanf("%d",&q->date);q->next=NULL;p->next=q;p=q;}returnL;}/*CreateList*//*释放链表及其空间*/voidDestroyLinkList(LinkListL){LNode*p=L,*q;while(p){q=p->next;free(p);p=q;}}/*DestroyLinkList*/intmenu_select(){char*menu[]={"\n***************MENU******************\n","1.InitLinkList\n",/*初始化链表*/"2.GetElement\n",/*查找元素*/"3.Insertdata\n",/*插入元素*/"4.Deletedata\n",/*删除元素*/"5.CreateLinkList\n",/*创建具有n个元素的链表*/"0.DestroyLinkList&&Quit\n",/*释放链表所占空间&退出*/"\n***************MENU******************\n"};chars[3];/*以字符形式保存选择号*/intc,i;/*定义整形变量*/for(i=0;i<8;i++)/*输出主菜单数组*/{printf("%s",menu[i]);}do{printf("\nEnteryouchoice(0~5):");/*在菜单窗口外显示提示信息*/scanf("%s",s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/}while(c<0||c>5);/*选择项不在0~5之间重输*/returnc;/*返回选择项,主程序根据该数调用相应的函数*/}intmain(){inti,n;ElemTypee;LinkListL=NULL;/*定义指向单链表的指针*/for(;;)/*无限循环*/{switch(menu_select())/*调用主菜单函数,返回值整数作开关语句的条件*/{/*值不同,执行的函数不同,break不能省略*/case1:printf("\n1-InitLinkList:\n");L=InitList(L);if(L!=NULL)printf("\nInitLinkListOK!\n");elseprintf("\nInitLinkListError!\n");break;case2:printf("\n2-GetElemfromLinkList:\n");printf("inputpos=");scanf("%d",&i);if(L!=NULL&&GetElem(L,i,&e)){printf("No%iis%d",i,e);printf("\nPrintfList:\n");PrintList(L);}elseprintf("Error&Notexists!");break;case3:printf("\n3-InserteintoLinkList:\n");printf("inputpos=");scanf("%d",&i);printf("inpute=");scanf("%d",&e);if(L!=NULL&&InsertElem(L,i,e)){printf("\nInsertOK!\n");printf("\nPrintfList:\n");PrintList(L);}elseprintf("\nInsertError!\n");break;case4:printf("\n4-DeletefromLinkList:\n");printf("inputpos=");scanf("%d",&i);if(L!=NULL&&DeleteElem(L,i,&e)){printf("\nOK\n");printf("\nDeletedatais%d\n",e);printf("\nPrintfList:\n");PrintList(L);}elseprintf("\nDeleteError!\n");break;case5:printf("pleaseinputn:");/*输入单链表的元素个数*/scanf("%d",&n);if(n<0){printf("ERROR");break;}printf("\nCreateLinkList......\n");L=CreateList(n);if(L==NULL){printf("Error!\n");break;}printf("\nPrintfList:\n");PrintList(L);break;case0:printf("\nDestroylinklistandfreememory......\n");if(L!=NULL){DestroyLinkList(L);L=NULL;}exit(0);/*如菜单返回值为0程序结束*/}}return0;}实验结果:(1)初始化链表:(2)查找元素:(3)插入数据:(4)删除数据:(5)创建链表:(6)销毁和退出链表:3循环链表的应用(约瑟夫回环问题、)用整数序列1,2,3,…,n表示顺序坐在圆桌周围的人,并采用循环链表作为存储结构。任意位置k开始计数,计到m让此位置的人出局,重复上述过程,直至只剩下最后一个人。依次输出每个出局的人的序号。提示:用一个无头结点的循环单链表来实现n个元素的存储。exp2_3.c部分代码如下:#include#include#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode/*线性表的单链表存储*/{ElemTypedata;structLNode*next;}LNode,*LinkList;/*(1)---创建具有n个结点的无头结点的单向循环链表,返回其头指针*/LinkListCreateList(intn){LinkListL;L=(LinkList)malloc(sizeof(LinkList));LNode*q,*p;printf("输入元素:\n");scanf("%d",&L->data);q=L;inta;for(a=0;adata);q->next=p;q=p;}q->next=L;returnL;}/*CreateList*//*(2)---输出无头结点循环单链表的所有元素*/voidPrintList(LinkListL){printf("输出表中的元素:");LNode*p;printf("%d\n",L->data);p=L->next;while(p!=L){printf("\n%d\n",p->data);p=p->next;}}/*PrintList*//*(3)---约瑟夫问题计算,依次输出出局的元素的序号*/voidJOSEPHUS(intn,intk,intm,LinkListL){L=CreateList(n);PrintList(L);inta,length=n;LNode*q;for(a=1;anext;while(length!=1){for(a=0;anext;q=L->next;L->next=q->next;printf("被删除的数字:%d\n",q->data);free(q);length-=1;}printf("输出最终的一个数字:%d",L->data);}/*JOSEPHUS*/intmain(){intn,m,k;LinkListL=NULL;/*定义指向单链表的指针*/printf("1.输入元素的个数");printf("2.输入位置");printf("3.输入人数");while(scanf("%d%d%d",&n,&k,&m)==3)/*n个元素从k位置开始每m个报数*/JOSEPHUS(n,k,m,L);return0;}.输入1023,表示一共有10个数,从第2个数之后开始数,数到3的人出局实验结果:4、选做实验:设有头单链表, 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 算法将表中值相同的元素仅保留一个结点。提示:指针p从链表的第一个元素开始,利用指针q从指针p位置开始向后搜索整个链表,删除与之值相同的元素;指针p继续指向下一个元素,开始下一轮的删除,直至p==null为至,既完成了对整个链表元素的删除相同值。#include#include#defineERROR0#defineOK1typedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListL=NULL;LNode*InitList(LinkListL);voidPrintList(LinkListL);voidDestroyLinkList(LinkListL);LinkListCreateList(intn);/*带头结点单链表初始化*/LNode*InitList(LinkListL){L=(LNode*)malloc(sizeof(LNode));if(!L)returnERROR;L->next=NULL;returnL;}/*输出带头结点单链表的所有元素*/voidPrintList(LinkListL){LinkListp;p=L->next;inti=1;while(p){printf("\nthe%ddatais%d",i++,p->data);p=p->next;}printf("\n");}/*PrintList*/LinkListCreateList(intn){LNode*p,*q,*head;inti;head=(LinkList)malloc(sizeof(LNode));head->next=NULL;p=head;for(i=0;idata);q->next=NULL;p->next=q;p=q;}returnhead;}/*CreateList*/LinkListSelectList(LinkListL){voidDelete(LinkListL,inti);LinkListp,q,a;p=L->next;a=L->next;while(p!=NULL){q=p->next;while(q!=NULL){if(p->data==q->data){a->next=q->next;}a=q;q=q->next;}p=p->next;}returnL;}voidDestroyLinkList(LinkListL){LNode*p=L,*q;while(p){q=p->next;free(p);p=q;}}/*DestroyLinkList*/intmain(){intn;L=InitList(L);if(L==NULL){printf("\nInitLinkListError!\n");return0;}printf("pleaseinputn:");scanf("%d",&n);if(n<=0){printf("\nError!\n");return0;}L=CreateList(n);if(L==NULL){printf("\nInitLinkListError!\n");return0;}PrintList(L);L=SelectList(L);PrintList(L);if(L!=NULL){DestroyLinkList(L);L=NULL;}return0;}【实验小结】在平时的学习中,主要是老师讲我们听,只有上机的时候才操作一下,对知识的掌握和理解不够。这次课程设计让我认识到自己还有很多的不足,对知识的掌握及熟练运用不够,这让我在程序编写中遇到了很多困难。通过查找资料及向老师请教,我终于编写出了程序。这次实验课,让我学会了做任何事都要细心耐心专心。
本文档为【数据结构(邹永林版)实验报告2-顺序表与链表】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
个人认证用户
wassyy
本人从事施工专职安全员多年,对施工现场安全管理、内业资料管理具有丰富的经验。
格式:doc
大小:61KB
软件:Word
页数:21
分类:
上传时间:2023-03-04
浏览量:0