《数据结构与算法实验指导书》由会员分享，可在线阅读，更多相关《数据结构与算法实验指导书（48页珍藏版）》请在金锄头文库上搜索。
1、.专业.专注.数据结构与算法实验报告基娜娜编word可编辑哈尔滨理工大学荣成学院实验一顺序表的实现和应用一、实验目的1、掌握顺序表的定义；2、掌握顺序表的基本操作，如查找、插入、删除及排序等。二、实验内容1、编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度2、编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度3、编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度4、编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析
2、算法的时间复杂度二、实验提不1、#include#defineMAXSIZE20typedefstructintdataMAXSIZE;intlast;list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度*/intlocate(list*l,intx)代码inti;for(i=0;ilast;i+)if(l-datai=x)returni+1;return-1;main()listb;intx,i,p;b.last=10;for(i=0;iosition43ressanykeytocontini_ue请输入硝胭100.no
3、!Pressanykeytocontinue.时间复杂度T(n)=O(n)；2、#include#defineMAXSIZE20typedefstructintdataMAXSIZE;intlast;list;/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度*/intdelete(list*l,inti)intj,k,p;定义一个用来保存被删原素；if(i=0&ilast)/只接受有效输入for(j=0;jlast;j+)/遍历数组if(j=i-1)匹配p=l-dataj;/保存被删原素；for(k=j;klast;k+)/前进一位；l-data
4、k=l-datak+1;break;/退出循环l-last=l-last-1;returnp;/对于此题来说可以输出p;return0;main()listb;intx,i;b.last=10;for(i=0;ib.last;i+)b.datai=i+2;printf(请输入x的值：)；scanf(%d,&x);if(delete(&b,x)!=0)for(i=0;ib.last;i+)printf(%3d,b.datai);elseprintf(Error!);青输入苫的值士5-234578910UPressanykeytocantinueterror!Pressanykeytocontin
5、ue时间复杂度T(n)=O(n)；3、#include#defineMAXSIZE20typedefstructintdataMAXSIZE;intlast;list;/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度*/intinsert(list*l,intx,inti)intj,k;if(ilast+1&i0)if(i=l-last+1)特殊值last+1要插入到整个数组之后l-datal-last=x;elsefor(j=0;jlast;j+)if(j=i-1)/匹配for(k=l-last;kj;k-)/将所选插入位置之后原素后移l
6、-datak=l-datak-1;l-dataj=x;/把x赋值给所选位置break;l-last=l-last+1;/数值长度加一return1;return0;/无效位置main()listb;intx,i;b.last=10;for(i=0;ib.last;i+)b.datai=i+2;printf(请输入x的值：)；scanf(%d,&x);if(insert(&b,66,x)!=0)for(i=0;ib.last;i+)printf(%3d,b.datai);elseprintf(Error!);情输入x的值；5234566678910HPressanykeytocontinueEr
7、ror!Pressanykeytocontinue时间复杂度T(n)=O(n)；4、#include#defineMAXSIZE20typedefstructintdataMAXSIZE;intlast;list;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法并分析算法的时间复杂度*/voidfun(list*l)这个代码有点晦涩，但空间时间复杂度是鸡儿低inti,ou=0,temp;/i计数，ou代表偶数个数oufor(i=0;ilast;i+)if(l-datai%2=0)个位置的原素交换位置temp=l-dataou;l-dataou=l-datai;l-d
8、atai=temp;ou+=1;循环判断是不是偶数，如果偶数的话和当前第/偶数个数加一printf(当前数组中偶数有%d个,奇数有%d个:n,ou,l-last-ou);main()listb;inti=0,m=0;b.last=10;printf(请输入数组元素的值：n);for(i=0;ib.last;i+)printf(b.data%d=,i);scanf(%d,&b.datai);fun(&b);for(i=0;ib.last;i+)printf(%3d,b.datai);I,data,data,data.data.data.data.data.data.data.dataL=22=3
9、=4L4=5L-15：67：8g=6=7=S=9=10当前数组中偶数有5个,奇毅有5个：246S10371g5Preganykeytocontinue-时间复杂度为T(n)=O(n)；四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结实验二链表的实现和应用一、实验目的1、掌握链表的定义；2、掌握链表的基本操作，如查找、插入、删除、排序等。二、实验内容1、单链表的创建2、单链表的查找3、单链表的排序4、单链表的删除5、链表的应用-约瑟夫环问题二、实验提不1、创建单链表，要求：结点个数为n个，每个节点数据域的值必须小于m。编辑主函数验证之。#include#includetyp
10、edefstructaaintdata;structaa*next;NODE;NODE*Creatlink(intn,intm)inti;NODE*tou,*p;/tou头结点tou=(NODE*)malloc(sizeof(NODE);/创建并初始化头结点tou-next=NULL;tou-data=n;printf(请输入d个小鱼d的数，中间用空格隔开：n,n,m);for(i=0;idata);if(p-data=m)printf(输入的第%d个数据大于%d,GGn,i+1,m);exit(0);程序强制中断，好像是在头文件stdlib.h里p-next=tou-next;tou-nex
11、t=p;returntou;outlink(NODE*h)NODE*p;p=h-next;printf(nnTHELIST:nnHEAD);while(p)printf(-%d,p-data);p=p-next;printf(n);main()NODE*head;head=Creatlink(8,22);outlink(head);12345678pHELIST:HEAD-8-7-6-5-4-3-2-1Pressanykeytocontinue1231005678输人的第4个数据大于2多GGPressanyksytocontinue2、查找值为ch的节点在链表中是否出现，如果存在，返回在链表中
12、位序，如果不存在返回0#include#include#defineN8typedefstructlistintdata;structlist*next;SLIST;SLIST*creatlist(char*);voidoutlist(SLIST*);intfun(SLIST*h,charch)inti;SLIST*p;p=h-next;/p赋值为寿元节点for(i=0;idata=ch)returni+1;p=p-next;return0;main()SLIST*head;intk;charch;charaN=m,p,g,a,W,x,r,d;head=creatlist(a);outlist(head);printf(Enteraletter:);scanf(%c,&ch);k=fun
