数据结构（实验一）

article/2025/10/4 18:37:00

第一次写报告，虽然有点简单，但还是要勉励自己再接再厉。加油

继续努力。

1.实验目的（结出本次实验所涉及并要求掌握的知识点）

1.掌握顺序表的存储结构形式及描述方法和基本运算的实现；

2.掌握用顺序表设计合理的数据结构,编写有关运算的算法。

2.实验内容（结出实验内容具体描述）

1.编写算法函数reverse（sque* l),实现顺序表的倒置；

2.编写算法函数spirt（sque *l1,sque* l2,sque* l3),将顺序表l1中的数据分类,奇数放在l2中，偶数放在l3中;

3.已知顺序表l1,l2均由从下到大排好序,请用尽可能快的方法将l1,l2中的数据合并到l3中,使数据在l3中按升序排列,编写函数merge(sque *l1,sque* l2,sque* l3 ).

4.假设顺序表la和lb分别存放在两个整数集合，编写函数inter(sque *l1,sque* l2,sque* l3)将l1,l2的交集存放到l3中.

5.编写函数partion(sque* l),尽可能快的将顺序表*l中的奇数调整到表的左边，偶数在右边，并分析算法的时间复杂度.

3.算法描述及实验步骤（用适当的形式表达算法设计思想与算法实现步骤）

#include <iostream>#include <cstdio>#define maxsize 100using namespace std;typedef int datatype;typedef struct{datatype a[maxsize];int size;} sque;void init(sque *st){st->size = 0;}void input(sque *st){init(st);datatype x;cout << "输入一组数据,最多100个数,以0位结束符" << endl;cin >> x;while (x){st->a[st->size++] = x;cin >> x;}}void output(sque *st){for (int i = 0; i < st->size; i++){cout << st->a[i] << ' ';if ((i + 1) % 10 == 0)cout << endl;}cout << endl;}void reverse(sque *st)//采用以中间为界首尾交换，依次向中间靠拢的思想{int temp = st->size;for (int i = 0; i < (st->size) / 2; i++)swap(st->a[i], st->a[--temp]);}void sprit(sque *l1, sque *l2, sque *l3)//采用从头到尾直接遍历判断并分类的思想{init(l2);init(l3);for (int i = 0; i < l1->size; i++){if ((l1->a[i]) % 2 == 1)l2->a[l2->size++] = l1->a[i];elsel3->a[l3->size++] = l1->a[i];}}void merge(sque *l1, sque *l2, sque *l3)//采用两顺序表从头开始比较大小小的进新表并进入下一个位置，大的不变,一表读完另一表直接进新表.{init(l3);for (int i = 0, j = 0; i < l1->size || j < l2->size;){if (l1->size != i && l2->size != j){if (l1->a[i] < l2->a[j])l3->a[l3->size++] = l1->a[i++];else if (l1->a[i] > l2->a[j])l3->a[l3->size++] = l2->a[j++];else{l3->a[l3->size++] = l1->a[i++];l3->a[l3->size++] = l2->a[j++];}}if (l1->size == i)l3->a[l3->size++] = l2->a[j++];else if (l2->size == j)l3->a[l3->size++] = l1->a[i++];}}void inter(sque *l1, sque *l2, sque *l3)//二重循环依次寻找相同的数，找到后判断新表中是否有这个数,没有则存入这个数{init(l3);for (int i = 0; i < l1->size; i++)for (int j = 0; j < l2->size; j++)if (l1->a[i] == l2->a[j]){int flag = 1;for (int k = 0; k < l3->size; k++)if (l3->a[k] == l1->a[i]){flag = 0;break;}if (flag == 1)l3->a[l3->size++] = l1->a[i];}}void partion(sque *l){for (int i = 0, j = l->size - 1; i < j;)//从两端开始判断首为偶数，尾为奇数则交换，其余视情况做相应加减.//时间复杂度为O(n);{if ((l->a[i]) % 2 == 1){if ((l->a[j]) % 2 == 0)j--;i++;}else if ((l->a[i]) % 2 == 0){if ((l->a[j]) % 2 == 1)swap(l->a[i++], l->a[j]);j--;}}}int main(){// sque l;// input(&l);// output(&l);// reverse(&l);// output(&l);// sque l1, l2, l3;// input(&l1);// sprit(&l1, &l2, &l3);// output(&l1);// output(&l2);// output(&l3);// sque l1, l2, l3;// input(&l1);// input(&l2);// merge(&l1, &l2, &l3);// output(&l3);// sque l1, l2, l3;// input(&l1);// input(&l2);// inter(&l1, &l2, &l3);// output(&l3);// sque l;// input(&l);// partion(&l);// output(&l);system("pause");return 0;}