数据结构与算法实验指导书

.......专业word可编辑.《数据结构与算法》实验报告綦娜娜编.......专业word可编辑.哈尔滨理工大学荣成学院.......专业word可编辑.实验一顺序表的实现和应用一、实验目的1、掌握顺序表的定义；2、掌握顺序表的基本操作，如查找、插入、删除及排序等。二、实验内容1、编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度2、编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度3、编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度4、编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析算法的时间复杂度三、实验提示1、#includestdio.h#defineMAXSIZE20typedefstruct{intdata[MAXSIZE];intlast;}list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度*/.......专业word可编辑.intlocate(list*l,intx){//代码inti;for(i=0;il-last;i++)if(l-data[i]==x)returni+1;return-1;}main(){listb;intx,i,p;b.last=10;for(i=0;ib.last;i++)b.data[i]=i+2;printf(请输入x的值：);scanf(%d,&x);p=locate(&b,x);if(p==-1)printf(no!);else.......专业word可编辑.printf(position=%d\n,p);}时间复杂度T(n)=O(n);2、#includestdio.h#defineMAXSIZE20typedefstruct{intdata[MAXSIZE];intlast;}list;/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度*/intdelete(list*l,inti){intj,k,p;//定义一个用来保存被删原素；if(i=0&&il-last)//只接受有效输入{.......专业word可编辑.for(j=0;jl-last;j++)//遍历数组if(j==i-1)//匹配{p=l-data[j];//保存被删原素;for(k=j;kl-last;k++)//前进一位；{l-data[k]=l-data[k+1];}break;//退出循环}l-last=l-last-1;returnp;//对于此题来说可以输出p;}return0;}main(){listb;intx,i;b.last=10;for(i=0;ib.last;i++)b.data[i]=i+2;.......专业word可编辑.printf(请输入x的值：);scanf(%d,&x);if(delete(&b,x)!=0){for(i=0;ib.last;i++)printf(%3d,b.data[i]);}elseprintf(Error!);}//时间复杂度T(n)=O(n);3、#includestdio.h#defineMAXSIZE20typedefstruct{intdata[MAXSIZE];intlast;}list;/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算.......专业word可编辑.法，并分析算法的时间复杂度*/intinsert(list*l,intx,inti){intj,k;if(i=l-last+1&&i0){if(i==l-last+1)//特殊值last+1要插入到整个数组之后{l-data[l-last]=x;}else{for(j=0;jl-last;j++){if(j==i-1)//匹配{for(k=l-last;kj;k--)//将所选插入位置之后原素后移{l-data[k]=l-data[k-1];}l-data[j]=x;//把x赋值给所选位置break;.......专业word可编辑.}}}l-last=l-last+1;//数值长度加一return1;}return0;//无效位置}main(){listb;intx,i;b.last=10;for(i=0;ib.last;i++)b.data[i]=i+2;printf(请输入x的值：);scanf(%d,&x);if(insert(&b,66,x)!=0){for(i=0;ib.last;i++)printf(%3d,b.data[i]);.......专业word可编辑.}elseprintf(Error!);}//时间复杂度T(n)=O(n);4、#includestdio.h#defineMAXSIZE20typedefstruct{intdata[MAXSIZE];intlast;}list;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析算法的时间复杂度*/voidfun(list*l){//这个代码有点晦涩，但空间时间复杂度是鸡儿低inti,ou=0,temp;//i计数，ou代表偶数个数.......专业word可编辑.for(i=0;il-last;i++)//循环{if(l-data[i]%2==0)//判断是不是偶数，如果是偶数的话和当前第ou个位置的原素交换位置{temp=l-data[ou];l-data[ou]=l-data[i];l-data[i]=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);.......专业word可编辑.scanf(%d,&b.data[i]);}fun(&b);for(i=0;ib.last;i++)printf(%3d,b.data[i]);}//时间复杂度为T(n)=O(n);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。.......专业word可编辑.实验二链表的实现和应用一、实验目的1、掌握链表的定义；2、掌握链表的基本操作，如查找、插入、删除、排序等。二、实验内容1、单链表的创建2、单链表的查找3、单链表的排序4、单链表的删除5、链表的应用--约瑟夫环问题三、实验提示1、//创建单链表,要求：结点个数为n个，每个节点数据域的值必须小于m。编辑主函数验证之。#includestdio.h#includestdlib.htypedefstructaa{intdata;structaa*next;}NODE;NODE*Creatlink(intn,intm){.......专业word可编辑.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;in;i++)//头插法{p=(NODE*)malloc(sizeof(NODE));scanf(%d,&p-data);if(p-data=m){printf(输入的第%d个数据大于%d,GG\n,i+1,m);exit(0);//程序强制中断，好像是在头文件stdlib.h里}p-next=tou-next;tou-next=p;}returntou;}outlink(NODE*h).......专业word可编辑.{NODE*p;p=h-next;printf(\n\nTHELIST:\n\nHEAD);while(p){printf(-%d,p-data);p=p-next;}printf(\n);}main(){NODE*head;head=Creatlink(8,22);outlink(head);}2、//查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存在返回0#includestdio.h#includestdlib.h.......专业word可编辑.#defineN8typedefstructlist{intdata;structlist*next;}SLIST;SLIST*creatlist(char*);voidoutlist(SLIST*);intfun(SLIST*h,charch){inti;SLIST*p;p=h-next;//p赋值为寿元节点for(i=0;iN;i++){if(p-data==ch)returni+1;p=p-next;}return0;}main(){SLIST*head;intk;charch;.......专业word可编辑.chara[N]={'m','p','g','a','w','x','r','d'};head=creatlist(a);outlist(head);printf(Enteraletter:);scanf(%c,&ch);k=fun(head,ch);if(k==0)printf(\nNotfound!\n);elseprintf(Thesequencenumberis:%d\n,k);}SLIST*creatlist(char*a){inti;SLIST*tou,*p;tou=(SLIST*)malloc(sizeof(SLIST));//创建并初始化头结点tou-data=N;tou-next=NULL;for(i=0;iN;i++)//前叉法{p=(SLIST*)malloc(sizeof(SLIST));p-data=a[i];p-next=tou-next;tou-next=p;.......专业word可编辑.}returntou;}voidoutlist(SLIST*h){SLIST*p;p=h-next;if(p==NULL)printf(\nThelistisNULL!\n);else{printf(\nHead);do{printf(-%c,p-data);p=p-next;}while(p!=NULL);printf(-End\n);}}3、//去偶操作,链表中各节点按数据域递增有序链接，函数fun的功能是，删除链表中数据域值相同的节点，使之只保留一个.......专业word可编辑.#includestdio.h#includestdlib.h#defineN8typedefstructlist{intdata;structlist*next;}SLIST;voidfun(SLIST*h){SLIST*p,*shanchu;//用于遍历的指针p,用于删除的指针shanchup=h-next;/p为寿元节点while(p-next!=NULL)//终止条件{if(p-data==p-next-data)//判断是否有重复原素{shanchu=p-next;p-next=shanchu-next;free(shanchu);}elsep=p-next;}.......专业word可编辑.}SLIST*creatlist(int*a){SLIST*h,*p,*q;inti;h=p=(SLIST*)malloc(sizeof(SLIST));for(