《数据结构与算法实验指导书(共53页)》由会员分享，可在线阅读，更多相关《数据结构与算法实验指导书(共53页)（53页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上数据结构与算法实验报告綦娜娜 编哈尔滨理工大学荣成学院专心-专注-专业实验一 顺序表的实现和应用一、实验目的 1、掌握顺序表的定义； 2、掌握顺序表的基本操作，如查找、插入、删除及排序等。二、实验内容1、编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度2、编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度3、编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度4、编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主
2、函数验证此算法，并分析算法的时间复杂度三、实验提示1、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度 */int locate(list *l,int x)/代码int i;for(i=0;ilast;i+)if(l-datai=x)return i+1;return -1;main()list b;int x,i,p;b.last=10;for(i=0;ib.last;i+)b.dat
3、ai=i+2;printf(请输入x的值：);scanf(%d,&x);p=locate(&b,x);if(p=-1)printf(no!);elseprintf(position=%dn,p);时间复杂度T(n)=O(n);2、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度 */int delete(list *l,int i)int j,k,p; /定义一个用来保存被删原素；if(i=0&ilast)
4、/只接受有效输入for(j=0;jlast;j+) /遍历数组if(j=i-1)/匹配p=l-dataj;/保存被删原素;for(k=j;klast;k+)/前进一位；l-datak=l-datak+1;break; /退出循环l-last=l-last-1;return p; /对于此题来说可以输出p;return 0;main()list b;int x,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(%3
5、d,b.datai);elseprintf(Error!);/时间复杂度T(n)=O(n);3、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度 */int insert(list *l,int x,int i)int j,k;if(ilast+1&i0)if(i=l-last+1)/特殊值last+1 要插入到整个数组之后l-datal-last=x;elsefor(j=0;jlast;j+)if(
6、j=i-1)/匹配for(k=l-last;kj;k-)/将所选插入位置之后原素后移l-datak=l-datak-1;l-dataj=x;/把x赋值给所选位置break;l-last=l-last+1;/数值长度加一return 1;return 0; /无效位置main()list b;int x,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(Erro
7、r!);/时间复杂度T(n)=O(n);4、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析算法的时间复杂度 */void fun(list *l)/这个代码有点晦涩，但空间时间复杂度是鸡儿低int i,ou=0,temp;/i计数，ou代表偶数个数for(i=0;ilast;i+)/循环if(l-datai%2=0)/判断是不是偶数，如果是偶数的话和当前第ou个位置的原素交换位置temp=l-dataou;l-dat
8、aou=l-datai;l-datai=temp;ou+=1;/偶数个数加一printf(当前数组中偶数有%d个,奇数有%d个:n,ou,l-last-ou);main()list b;int i=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);/时间复杂度为T(n)=O(n);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结。实验二 链表的
9、实现和应用一、实验目的 1、掌握链表的定义； 2、掌握链表的基本操作，如查找、插入、删除、排序等。二、实验内容1、单链表的创建2、单链表的查找3、单链表的排序4、单链表的删除5、链表的应用-约瑟夫环问题三、实验提示1、/创建单链表,要求：结点个数为n个，每个节点数据域的值必须小于m。编辑主函数验证之。#include #include typedef struct aa int data; struct aa *next; NODE;NODE *Creatlink(int n, int m)int i;NODE *tou,*p;/tou 头结点tou=(NODE*)malloc(sizeof(
10、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-next=p;return tou;outlink(NODE *h) NODE *p; p=h-next; printf(nnTHE LIST :nn HEAD ); while(p) printf(-%d ,p-data);
11、 p=p-next; printf(n);main() NODE *head; head=Creatlink(8,22); outlink(head);2、/查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存在返回0#include #include #define N 8typedef struct list int data; struct list *next; SLIST;SLIST *creatlist(char *);void outlist(SLIST *);int fun( SLIST *h, char ch)int i;SLIST *p;p=h-next;/p赋值为寿元节点for(i=0;idata=ch)return i+1;p=p-next;return 0;main() SLIST *head; int k; char ch; char aN=m,p,g,a,
