WORD格式可编辑

《数据结构与算法》

实验报告

綦娜娜 编

哈尔滨理工大学荣成学院

专业知识分享

WORD格式可编辑 实验一 顺序表的实现和应用

一、实验目的

1、掌握顺序表的定义；

2、掌握顺序表的基本操作，如查找、插入、删除及排序等。 二、实验内容

1、编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度

2、编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度

3、编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度

4、编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法，并分析算法的时间复杂度

三、实验提示

1、#include #define MAXSIZE 20 typedef struct{

int data[MAXSIZE]; int last; }list;

/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度 */

int locate(list *l,int x) {

//代码 int i;

for(i=0;ilast;i++) if(l->data[i]==x) return i+1; return -1; }

main() {

list b; int x,i,p; b.last=10;

for(i=0;i

printf(\请输入x的值：\ scanf(\ p=locate(&b,x); if(p==-1)

printf(\

专业知识分享

WORD格式可编辑 else

printf(\}

时间复杂度T(n)=O(n);

2、#include #define MAXSIZE 20 typedef struct{

int data[MAXSIZE]; int last; }list;

/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度 */

int delete(list *l,int i) {

int j,k,p; //定义一个用来保存被删原素； if(i>=0&&ilast) //只接受有效输入 {

for(j=0;jlast;j++) //遍历数组 if(j==i-1) //匹配 {

p=l->data[j]; //保存被删原素;

for(k=j;klast;k++) //前进一位； {

l->data[k]=l->data[k+1]; }

break; //退出循环 }

l->last=l->last-1;

return p; //对于此题来说可以输出p; }

return 0; }

main()

专业知识分享

WORD格式可编辑 { }

list b; int x,i; b.last=10;

for(i=0;i

printf(\请输入x的值：\scanf(\if(delete(&b,x)!=0) {

for(i=0;i

printf(\} else

printf(\

//时间复杂度T(n)=O(n); 3、#include #define MAXSIZE 20

typedef struct{

int data[MAXSIZE]; int last; }list;

/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度 */

int insert(list *l,int x,int i) {

int j,k;

if(i<=l->last+1&&i>0) {

if(i==l->last+1) //特殊值last+1 要插入到整个数组之后 {

l->data[l->last]=x; } else {

专业知识分享