devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构实验报告 实验一 顺序表实验 【个人复盘】_数据结构顺序表实验报告

作者：凡人多烦事01 | 2024-06-05 01:15:14

赞

踩

数据结构顺序表实验报告
  1. 实验目标
  1. 熟练掌握线性表的顺序存储结构。
  2. 熟练掌握顺序表的有关算法设计和实现。
  3. 根据具体问题的需要，设计出合理的表示数据元素的顺序结构，并设计相关算法。

  1. 实验要求
  1. 顺序表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；比如存储、算法实现放入文件：seqList.h
  2. 程序有适当的注释，程序的书写要采用缩进格式。
  3. 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；
  4. 程序要具有一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。
  5. 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
  6. 程序运行、测试正确；

根据实验报告模板详细书写实验报告。

  1. 实验内容

编写算法实现下列问题的求解。

  1. 在第i个结点位置插入值为x的结点。

实验测试数据基本要求：

第一组数据：顺序表长度n≥10，x=100,  i分别为5,n,n+1,0,1,n+2

第二组数据：顺序表长度n=0，x=100，i=5

  1. 删除顺序表中第i个元素结点。

实验测试数据基本要求：

第一组数据：顺序表长度n≥10，i分别为5,n,1,n+1,0

第二组数据：顺序表长度n=0， i=5

  1. 在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性。

实验测试数据基本要求：

顺序表元素为 （10,20,30,40,50,60,70,80,90,100）,

x分别为25，85，110和8

  1. 将顺序表Ｌ中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的顺序表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果。

实验测试数据基本要求：

第一组数据：顺序表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）

第二组数据：顺序表元素为 （10,20,30,40,50,60,70,80,90,100）

  1. 求两个递增有序顺序表L1和L2中的公共元素，放入新的顺序表L3中。

实验测试数据基本要求：

第一组

第一个顺序表元素为 （1，3，6，10，15，16，17，18，19，20）

第二个顺序表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30）

第二组

第一个顺序表元素为 （1，3，6，10，15，16，17，18，19，20）

第二个顺序表元素为 （2，4，5，7，8，9，12，22）

第三组

第一个顺序表元素为 （）

第二个顺序表元素为 （1，2，3，4，5，6，7，8，9，10）

  1. 删除递增有序顺序表中的重复元素，并统计移动元素次数，要求时间性能最好。

实验测试数据基本要求：

第一组数据：顺序表元素为 （1,2,3,4,5,6,7,8,9）

第二组数据：顺序表元素为 （1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,9）

第三组数据：顺序表元素为 （1,2,3,4,5,5,6,7,8,8,9,9,9,9,9）

1.4* 顺序表扩展实验

（非必做内容，有兴趣的同学选做）1.（递增有序）

  1. #include<iostream>
  2. #include"标头.h"//include"seqList.h"
  3. using namespace std;
  4.  
  5. int main() {
  6.     int i = 1;
  7.     int nums = 0;
  8.     seqList ll;
  9.     seq l = &ll;
  10.     seqList ss;
  11.     seq s = &ss;
  12.     initialList3(s);
  13.     
  14.     ss.data[0] = 1;
  15.     ss.data[1] = 3;
  16.     ss.data[2] = 6;
  17.     ss.data[3] = 10;
  18.     ss.data[4] = 15;
  19.     ss.data[5] = 16;
  20.     ss.data[6] = 17;
  21.     ss.data[7] = 18;
  22.     ss.data[8] = 19;
  23.     ss.data[9] = 20;
  24.     ss.len += 10;
  25.  
  26.     seqList ee;
  27.     initialList(ee);
  28.  
  29.     while (i) {
  30.         cout << "********************************************************************************************" << endl;
  31.         cout << "*                 欢迎您来到测试页面，现在开始您的测试                                     *" << endl;
  32.         cout << "*-----------------------------  功能页面 --------------------------------------------------*" << endl;
  33.         cout << "*	          1.新建一个顺序表并进行初始化                                             *" << endl;
  34.         cout << "*                 2.在第i个结点位置插入值为x的结点                                         *" << endl;
  35.         cout << "*                 3.删除顺序表中第i个元素结点                                              *" << endl;
  36.         cout << "*                 4.打印输出当前顺序表                                                     *" << endl;
  37.         cout << "*                 5.往顺序表加入n个数                                                      *" << endl;
  38.         cout << "*                 6.在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性     *" << endl;
  39.         cout << "*                 7.将顺序表Ｌ中的奇数项和偶数项结点分解开                                 *" << endl;
  40.         cout << "*                 8.两个递增有序顺序表L1和L2中的公共元素，放入新的顺序表L3中               *" << endl;
  41.         cout << "*                 9.删除递增有序顺序表中的重复元素，并统计移动元素次数                     *" << endl;
  42.         cout << "*                 10.附加题：1.1C=A∪B                                                     *" << endl;
  43.         cout << "*                 11.附加题：1.2C=A∩B                                                     *" << endl;
  44.         cout << "*                 12.附加题：1.3C=A-B                                                      *" << endl;
  45.         cout << "*                 13.附加题：1.4A=A∩B                                                     *" << endl;
  46.         cout << "*                 14.附加题：1.5A = A∪B                                                   *" << endl;
  47.         cout << "*                 15.附加题：1.6A=A-B                                                      *" << endl;
  48.         cout << "*                 16.附加题：2                                                             *" << endl;
  49.         cout << "*                 17.附加题：3                                                             *" << endl;
  50.         cout << "*                 0.退出功能页面                                                           *" << endl;
  51.         cout << "********************************************************************************************" << endl;
  52.         cout << "输入你要选择的功能序号:" << endl;
  53.         int num;
  54.         cin >> num;
  55.         switch (num) {
  56.         case 0:
  57.             i = 0;
  58.             break;
  59.         case 1:
  60.             initialList3(l);
  61.             break;
  62.         case 2:
  63.             cout << "请输入你想加入的元素和位置" << endl;
  64.             elementType x;
  65.             cin >> x;
  66.             int y;
  67.             cin >> y;
  68.             listInsert3( l, x, y);
  69.             if (l->ifError == 1) {
  70.                 cout << "溢出无法插入" << endl;
  71.             }
  72.             else if (l->ifError == 2) {
  73.                 cout << "边界错误，无法插入" << endl;
  74.             }  
  75.             l->ifError = 0;
  76.             break;
  77.         case 3:
  78.             cout << "请输入你要删除的元素的位置" << endl;
  79.             int yy;
  80.             cin >> yy;
  81.             listDelete3(l, yy);
  82.             if (l->ifError == 1) {
  83.                 cout << "溢出无法删除" << endl;
  84.             }
  85.             else if (l->ifError == 2) {
  86.                 cout << "边界错误，无法删除" << endl;
  87.             }
  88.             break;
  89.         case 4:
  90.             cout << "输出的元素为：" << "  ";
  91.             for (int i = 0; i < l->len; i++) {
  92.  
  93.                 cout << l->data[i] << " ";
  94.                
  95.             }
  96.             cout << endl;
  97.             break;
  98.         case 5:
  99.             cout << "想要加入的数：" << endl;
  100.             int c;
  101.             cin >> c;
  102.             for (int g = 1; g <= c; g++) {
  103.                 listInsert3(l, g, g);
  104.             }
  105.  
  106.             break;
  107.         case 6:
  108.             cout << "想要添加的值" << endl;
  109.             elementType val;
  110.             cin >> val;
  111.             listInsertInTurn(l, val);
  112.             break;
  113.         case 7:
  114.             cout << "原表输出的元素为：" << "  ";
  115.             for (int i = 0; i < l->len; i++) {
  116.  
  117.                 cout << l->data[i] << " ";
  118.  
  119.             }
  120.             cout << endl;
  121.             ss=listDepart(ll);
  122.             cout << "单数表输出的元素为：" << "  ";
  123.             for (int i = 0; i < l->len; i++) {
  124.                 cout << l->data[i] << " ";
  125.             }
  126.             cout << endl;
  127.             cout << "双数表输出的元素为：" << "  ";
  128.             for (int i = 0; i < s->len; i++) {
  129.                 cout << s->data[i] << " ";
  130.             }
  131.             break;
  132.         case 8:
  133.             cout << "原第一表输出的元素为：" << "  ";
  134.             for (int i = 0; i < l->len; i++) {
  135.  
  136.                 cout << l->data[i] << " ";
  137.  
  138.             }
  139.             cout << endl;
  140.             cout << "原第二表输出的元素为：" << "  ";
  141.            
  142.             for (int i = 0; i < s->len; i++) {
  143.  
  144.                 cout << s->data[i] << " ";
  145.  
  146.             }
  147.             cout << endl;
  148.             ee=listThree(ll, ss);
  149.             cout << "现在第一表输出的元素为：" << "  ";
  150.             for (int i = 0; i < l->len; i++) {
  151.  
  152.                 cout << l->data[i] << " ";
  153.  
  154.             }
  155.             cout << endl;
  156.             cout << "现在第二表输出的元素为：" << "  ";
  157.             for (int i = 0; i < s->len; i++) {
  158.  
  159.                 cout << s->data[i] << " ";
  160.  
  161.             }
  162.             cout << endl;
  163.             cout << "现在第三表输出的元素为：" << "  ";
  164.             for (int i = 0; i < ee.len; i++) {
  165.  
  166.                 cout << ee.data[i] << " ";
  167.  
  168.             }
  169.             cout << endl;
  170.             break;
  171.         case 9:
  172.             cout << "原表输出的元素为：" << "  ";
  173.             for (int i = 0; i < l->len; i++) {
  174.  
  175.                 cout << l->data[i] << " ";
  176.  
  177.             }
  178.             cout << endl << "移动次数为：" << listDeleteTheSame( ll) << endl;
  179.             cout << "现表输出的元素为：" << "  ";
  180.  
  181.             for (int i = 0; i < l->len; i++) {
  182.  
  183.                 cout << l->data[i] << " ";
  184.  
  185.             }
  186.             break;
  187.         case 10:
  188.             cout << "原第一表输出的元素为：" << "  ";
  189.             for (int i = 0; i < l->len; i++) {
  190.  
  191.                 cout << l->data[i] << " ";
  192.  
  193.             }
  194.             cout << endl;
  195.             cout << "原第二表输出的元素为：" << "  ";
  196.  
  197.             for (int i = 0; i < s->len; i++) {
  198.  
  199.                 cout << s->data[i] << " ";
  200.  
  201.             }
  202.             cout << endl;
  203.             ee = unionSet(ll, ss);
  204.             cout << "现在第三表输出的元素为：" << "  ";
  205.             for (int i = 0; i < ee.len; i++) {
  206.  
  207.                 cout << ee.data[i] << " ";
  208.  
  209.             }
  210.             cout << endl;
  211.             system("pause");
  212.             break;
  213.         case 11:
  214.             cout << "原第一表输出的元素为：" << "  ";
  215.             for (int i = 0; i < l->len; i++) {
  216.  
  217.                 cout << l->data[i] << " ";
  218.  
  219.             }
  220.             cout << endl;
  221.             cout << "原第二表输出的元素为：" << "  ";
  222.  
  223.             for (int i = 0; i < s->len; i++) {
  224.  
  225.                 cout << s->data[i] << " ";
  226.  
  227.             }
  228.             cout << endl;
  229.             ee = intersectSet(ll, ss);
  230.             cout << "现在第三表输出的元素为：" << "  ";
  231.             for (int i = 0; i < ee.len; i++) {
  232.  
  233.                 cout << ee.data[i] << " ";
  234.  
  235.             }
  236.             cout << endl;
  237.             system("pause");
  238.             break;
  239.         case 12:
  240.             cout << "原第一表输出的元素为：" << "  ";
  241.             for (int i = 0; i < l->len; i++) {
  242.  
  243.                 cout << l->data[i] << " ";
  244.  
  245.             }
  246.             cout << endl;
  247.             cout << "原第二表输出的元素为：" << "  ";
  248.  
  249.             for (int i = 0; i < s->len; i++) {
  250.  
  251.                 cout << s->data[i] << " ";
  252.  
  253.             }
  254.             cout << endl;
  255.             ee = diffSet(ll, ss);
  256.             cout << "现在第三表输出的元素为：" << "  ";
  257.             for (int i = 0; i < ee.len; i++) {
  258.  
  259.                 cout << ee.data[i] << " ";
  260.  
  261.             }
  262.             cout << endl;
  263.             system("pause");
  264.             break;
  265.         case 13:
  266.             cout << "原第一表输出的元素为：" << "  ";
  267.             for (int i = 0; i < l->len; i++) {
  268.  
  269.                 cout << l->data[i] << " ";
  270.  
  271.             }
  272.             cout << endl;
  273.             cout << "原第二表输出的元素为：" << "  ";
  274.  
  275.             for (int i = 0; i < s->len; i++) {
  276.  
  277.                 cout << s->data[i] << " ";
  278.  
  279.             }
  280.             cout << endl;
  281.             intersectSetTheFirst(ll, ss);
  282.             cout << "现在第三表输出的元素为：" << "  ";
  283.             for (int i = 0; i < ll.len; i++) {
  284.  
  285.                 cout << ll.data[i] << " ";
  286.  
  287.             }
  288.             cout << endl;
  289.             system("pause");
  290.             break;
  291.         case 14:
  292.             cout << "原第一表输出的元素为：" << "  ";
  293.             for (int i = 0; i < l->len; i++) {
  294.  
  295.                 cout << l->data[i] << " ";
  296.  
  297.             }
  298.             cout << endl;
  299.             cout << "原第二表输出的元素为：" << "  ";
  300.  
  301.             for (int i = 0; i < s->len; i++) {
  302.  
  303.                 cout << s->data[i] << " ";
  304.  
  305.             }
  306.             cout << endl;
  307.             unionSetTheFirst(ll, ss);
  308.             cout << "现在第三表输出的元素为：" << "  ";
  309.             for (int i = 0; i < ll.len; i++) {
  310.  
  311.                 cout << ll.data[i] << " ";
  312.  
  313.             }
  314.             cout << endl;
  315.             system("pause");
  316.             break;
  317.         case 15:
  318.             cout << "原第一表输出的元素为：" << "  ";
  319.             for (int i = 0; i < l->len; i++) {
  320.  
  321.                 cout << l->data[i] << " ";
  322.  
  323.             }
  324.             cout << endl;
  325.             cout << "原第二表输出的元素为：" << "  ";
  326.  
  327.             for (int i = 0; i < s->len; i++) {
  328.  
  329.                 cout << s->data[i] << " ";
  330.  
  331.             }
  332.             cout << endl;
  333.             DeleteSetTheFirst(ll, ss);
  334.             cout << "现在第三表输出的元素为：" << "  ";
  335.             for (int i = 0; i < ll.len; i++) {
  336.  
  337.                 cout << ll.data[i] << " ";
  338.  
  339.             }
  340.             cout << endl;
  341.             system("pause");
  342.             break;
  343.         case 16:
  344.             cout<<"A是B的子集吗："<<isSubset(ll, ss);
  345.             cout << endl;
  346.             system("pause");
  347.             break;
  348.         case 17: 
  349.             cout << "两个顺序表的中位数为：" << listFindTheMiddel(ll, ss);
  350.             cout << endl;
  351.             system("pause");
  352.             break;
  353.         }
  354.         
  355.         
  356.        // system("pause");
  357.         //system("cls");
  358.  
  359.     }
  360.  
  361.  
  362. 	return 0;
  363. }
  364.  
  365. #define MAXLEN 200
  366. #define elementType int
  367.  
  368. typedef struct  seqList
  369. {
  370. 	elementType data[MAXLEN];//顺序表
  371. 	int len;//记录表的长度
  372. 	int ifError = 0;//判断接下来的操作的错误种类
  373.  
  374. }se,*seq;//起别名并定义指针
  375.  
  376. void initialList(seqList&l) {
  377. 	l.len = 0;
  378. }
  379.  
  380. void initialList3(seqList* l) {
  381. 	l->len = 0;
  382. }
  383.  
  384. /*void listInsert(seqList& l, elementType x, int y) {
  385. 	int k;
  386. 	if (l.len == MAXLEN) {
  387. 		l.ifError = 1;//溢出无法插入
  388. 	}
  389. 	else if (y<1 || y>l.len + 1) {//边界错误，无法插入
  390. 		l.ifError = 2;
  391. 	}
  392. 	else {
  393. 		for (int k = l.len - 1; k >= y - 1; k--) {
  394. 			l.data[k + 1] = l.data[k];
  395. 			l.data[k] = x;
  396. 			l.len++;
  397. 		}
  398. 	}
  399. }*/
  400. void listInsert3(seq l, elementType x, int y) {
  401. 	int k;
  402. 	if (l->len == MAXLEN) {
  403. 		l->ifError = 1;//溢出无法插入
  404. 	}
  405. 	else if (y<1 || y>l->len + 1) {//边界错误，无法插入
  406. 		l->ifError = 2;
  407. 	}
  408. 	else {
  409. 		l->len++;
  410. 		for (int k = l->len - 1; k >= y - 1; k--) {
  411. 			l->data[k + 1] = l->data[k];
  412. 			l->data[k] = x;
  413. 			
  414. 		}
  415. 		
  416. 	}
  417. }
  418.  
  419.  
  420. /*void listInsert2(int a[], int& b, elementType x, int y, seqList l) {
  421. 	int k;
  422. 	if (b == MAXLEN) {
  423. 		l.ifError = 1;//溢出无法插入
  424. 	}
  425. 	else if (y<1 || y>b + 1) {//边界错误，无法插入
  426. 		l.ifError = 2;
  427. 	}
  428. 	else {
  429. 		for (int k = b - 1; k >= y - 1; k--) {
  430. 			a[k + 1] = a[k];
  431. 			a[k] = x;
  432. 			b++;
  433. 		}
  434. 	}
  435. }*/
  436.  
  437. void listDelete(seqList& l,int y) {
  438. 	if (l.len <=0) {
  439. 		l.ifError = 1;//溢出无法删除
  440. 	}
  441. 	else if (y<1 || y>l.len + 1) {//边界错误，无法删除
  442. 		l.ifError = 2;
  443. 	}
  444. 	else {
  445. 		for (int i = y - 1; i <= l.len - 1; i++) {
  446. 			l.data[i - 1] = l.data[i]; 
  447. 			
  448.  
  449. 		}
  450. 		l.len--;
  451. 	}
  452. }
  453.  
  454. void listDelete3(seqList* l, int y) {
  455. 	if (l->len <= 0) {
  456. 		l->ifError = 1;//溢出无法删除
  457. 	}
  458. 	else if (y<1 || y>l->len) {//边界错误，无法删除
  459. 		l->ifError = 2;
  460. 	}
  461. 	else {
  462. 		for (int i = y - 1; i < l->len - 1; i++) {
  463. 			l->data[i] = l->data[i+1];
  464. 			
  465. 		}
  466. 		l->len--;
  467. 	}
  468. }
  469.  
  470.  
  471.  
  472.  
  473. /*void listInsertInTurn(seqList& l, elementType val) {
  474. 	if (l.len == 0) {
  475. 		l.data[0] = val;
  476. 	}
  477. 	else {
  480. 		int le = 0;
  481. 		int r = l.len - 1;
  482. 		int k;
  483. 		while (le < r) {
  484. 			int mid = le + r >>2;
  485. 			if (l.data[mid] > val) {
  486. 				r = mid-1;
  487. 			}
  488. 			else if (l.data[mid] < val) {
  489. 				le = mid+1;
  490. 			}
  491. 			else {
  492. 				k = mid;
  493. 				break;
  494. 			}
  495. 		}
  496. 		if (l.data[r] > val)k = r ;
  497. 		else {
  498. 			k = r ;
  499. 		}
  500. 		listInsert(l, val, k);
  501. 	}
  502. }*/
  503.  
  504. void listInsertInTurn(seq l, elementType x) {
  505. 	for (int i = l->len - 1; i > 0; i--) {
  506. 		if (x <= l->data[i]) {
  507. 			if (x >= l->data[i - 1]) {
  508. 				listInsert3(l, x, i+1);  //插入元素
  509. 				break;
  510. 			}
  511. 		}
  512.  
  513. 	}
  514. 	if (x > l->data[l->len - 1]) {
  515. 		listInsert3(l,  x, l->len + 1);
  516. 	}
  517. 	else if (x < l->data[0]) {
  518. 		listInsert3(l, x, 1);
  519. 	}
  520. 	
  521.  
  522. }
  523.  
  524.  
  525. int listLength(seqList &l) {
  526. 	return  l.len;
  527. }
  528.  
  529. seqList listDepart(seqList & l) {
  530. 	seqList thenew;
  531. 	seq t = &thenew;//创建一个新指针
  532. 	//int len = l.len;
  533. 	initialList(thenew);
  534. 	for (int j = 0; j < l.len; j++) {
  535. 		if (l.data[j] % 2 == 1) {//判断奇偶数
  536. 			continue;
  537. 		}
  538. 		else {
  539. 			listInsert3(t, l.data[j], thenew.len+1);//在新顺序表插入
  540. 			listDelete3(&l, j+1);//从原顺序表删除
  541. 			j--;
  542. 			
  543. 		}
  544. 	}
  545. 	return thenew;
  546. }
  547.  
  548. seqList listThree(seqList&l,seqList&dou) {
  549. 	seqList thenew;
  550. 	seq t = &thenew;//构建指针指向结构体
  551. 	initialList(thenew);//初始化
  552. 	int up = 0;
  553. 	int down = 0;
  554. 	while (up != l.len && down != dou.len) {//采用双指针
  555. 		if (l.data[up] > dou.data[down]) {
  556. 			down++;
  557. 		}
  558. 		else if (l.data[up] < dou.data[down]) {
  559. 			up++;
  560. 		}
  561. 		else {
  562. 			listInsert3(t, l.data[up], thenew.len+1);//插入到新顺序表中
  563. 			up++;
  564. 			down++;
  565. 		}
  566. 		
  567. 	}
  568. 	return thenew;//返回一个新顺序表
  569. }
  570.  
  571. /*int listDeleteTheSame(seqList& l) {
  572. 	int r = 0;
  573. 	int ll = 0;
  574. 	int count = 0;
  575. 	int temp = l.len;
  576. 	if (l.len = 0 || l.len == 1) {
  577. 		return count;
  578. 	}
  579. 	else {
  581. 		while (r != l.len) {
  582. 			if (l.data[ll] == l.data[r]) {
  583. 				r++;
  584. 			}
  585. 			else {
  586. 				l.data[ll + 1] = l.data[r];
  587. 				ll++;
  588. 				r++;
  589. 				count++;
  590. 			}
  591. 		}
  592. 		
  593. 			l.len = r-1;
  594. 		
  595. 	}
  596. 	return count;
  597. }*/
  598.  
  599. int listDeleteTheSame(seqList &list) {
  600. 	int count = 0;//统计移动次数
  601. 	
  602. 		if (list.len == 0||list.len==1) {
  603. 		return 0;		
  604. 	}
  605.     int pre = 0, last = 1;//pre为位于前面的下标，last为位于后面的下标
  606. 	int temp = list.len;//temp用于统计删除重复元素后的顺序表长度
  607. 	while (last < list.len) {
  608. 	//如果pre和last指代元素相同时,temp减一,last向后移动一位
  609. 	if (list.data[last] == list.data[pre]) {
  610. 	temp--;
  611. 	last++;
  612. 		}
  613. 	//如果pre和last不相邻时，证明中间含有重复元素，且该重复元素值与pre指代元素相同
  614. 	else if (pre + 1 != last) {
  615. 	//pre后移一位后，并用last指代元素覆盖pre指代元素，然后last后移一位
  616. 	list.data[++pre] = list.data[last++];
  617. 	count++;//元素移动次数加一
  618. 		}
  619. 	else
  620. 	 {  //pre和last相邻时，二者均后移一位
  621. 			pre++;
  622. 			last++;
  623. 		}
  624. 	}
  625. 	list.len = temp;
  626. 	return count;//返回计数值
  627. }
  628.  
  629.  
  630.  
  631. seqList unionSet(seqList&a,seqList&b) {//C=A∪B
  632. 	int i=0, j=0;  
  633. 	seqList thenew;
  634. 	initialList(thenew);//初始化新顺序表
  635. 	/*for (i = 0; i < lenB; i++) {
  636. 		for (j = 0; j < lenA; j++) { 
  637. 			if (B[i] == A[j]) { 
  638. 				thenew.data[thenew.len++] = B[i];
  639. 				break; 
  640. 			} 
  641. 		}       
  642. 		if (j == lenA) { 
  643. 			thenew.data[thenew.len++] = B[i];//储存数据
  644. 		} 
  645. 	}
  646. 	for (i = 0; i < lenA; i++) {
  647. 		for (j = 0; j < lenB; j++) {
  648. 			if (B[i] == A[j]) {
  649. 				break;//之前已经存过一回数据，现在不用再存了
  650. 			}
  651. 		}
  652. 		if (j == lenB) {
  653. 			thenew.data[thenew.len++] = B[i];//储存数据
  654. 		}
  655. 	}
  656. 	listDeleteTheSame(thenew);//删除相同元素
  657. 	thenew.len--;*/
  658. 	while (i != a.len && j != b.len) {
  659. 		if (a.data[i] < b.data[j]) {//将较小元素加入表中
  660. 			thenew.data[thenew.len++] = a.data[i];
  661. 			i++;
  662. 			break;
  663. 		}
  664. 		else if (a.data[i] > b.data[j]) {
  665. 			thenew.data[thenew.len++] = b.data[i];
  666. 			j++;
  667.  
  668. 		}
  669. 		else {
  670. 			thenew.data[thenew.len++] = b.data[i];
  671. 			i++; j++;
  672. 		}
  673. 	}
  674. 	if (i != a.len) {//判断双指针不同时结束时，剩下的元素接到新表尾
  675. 		for (int q = i; q < a.len; q++) {
  676. 			thenew.data[thenew.len++] = a.data[q];
  677. 		}
  678. 	}
  679. 	else if (i != b.len) {
  680. 		for (int q = i; q < b.len; q++) {
  681. 			thenew.data[thenew.len++] = b.data[q];
  682. 		}
  683. 	}
  684. 	return thenew;
  685. }
  686.  
  687. seqList intersectSet(seqList&a,seqList&b) {//C=A∩B
  688. 	int i=0, j = 0;
  689. 	seqList thenew;
  690. 	initialList(thenew);
  691. 	while (i != a.len && j != b.len) {
  692. 		if (a.data[i] < b.data[j]) {
  693. 			i++;
  694. 			
  695. 		}
  696. 		else if (a.data[i] > b.data[j]) {
  697. 			j++;
  698. 			
  699. 		}
  700. 		else {
  701. 			thenew.data[thenew.len++] = b.data[j];//两个元素相同时，将该值赋给新顺序表
  702. 			i++; j++;
  703. 		}
  704. 	}
  705. 	
  706. 	return thenew;
  707. }
  708.  
  709. seqList diffSet(seqList& a, seqList& b) {//C=A-B
  710. 	int i=0, j = 0;
  711. 	seqList thenew;
  712. 	initialList(thenew);//初始化新表
  713. 	while (i != a.len && j != b.len) {
  714. 		if (a.data[i] < b.data[j]) {
  715. 			thenew.data[thenew.len++] = a.data[i];//只有a的值小于b的值时，才将值赋给新顺序表
  716. 			i++;
  717. 		}
  718. 		else if (a.data[i] > b.data[j]) {
  719. 			j++;
  720. 			
  721. 		}
  722. 		else {
  723. 			
  724. 			i++; j++;
  725. 		}
  726. 	}
  727. 	return thenew;
  728. }
  729.  
  730. void intersectSetTheFirst(seqList& a,seqList b) {//A∩B
  731. 	int i = 0;//双指针
  732. 	int j = 0;
  733. 	while (i != a.len) {
  734. 		if (a.data[i] < b.data[j]) {
  735. 			listDelete3(&a, i+1);//从A中删除该元素
  736.  
  737. 		}
  738. 		else if (a.data[i] > b.data[j]) {
  739. 			j++;
  740.  
  741. 		}
  742. 		else {
  743. 			i++; j++;//同时移动指针
  744. 		}
  745. 	}
  746.  
  747. }
  748.  
  749. void unionSetTheFirst(seqList&a,seqList b) {
  750. 	//A = A∪B
  751. 	int i = 0;//双指针
  752. 	int j=0;
  753. 	while (i != a.len && j != b.len) {
  754. 		if (a.data[i] < b.data[j]) {
  755. 			i++;
  756.  
  757. 		}
  758. 		else if (a.data[i] > b.data[j]) {
  759. 			listInsert3(&a, b.data[j], i + 1);//从A中插入该元素
  760. 			j++;
  761.  
  762. 		}
  763. 		else {
  764. 			i++; j++;//同时移动指针
  765. 		}
  766. 	}
  767. 	listDeleteTheSame(a);
  768. }
  769.  
  770. void DeleteSetTheFirst(seqList& a, seqList b) {
  771. 	//A=A-B
  772. 	int i = 0;//双指针
  773. 	int j = 0;
  774. 	while (i != a.len && j != b.len) {
  775. 		if (a.data[i] < b.data[j]) {
  776. 			i++;
  777.  
  778. 		}
  779. 		else if (a.data[i] > b.data[j]) {
  780. 			
  781. 			j++;
  782.  
  783. 		}
  784. 		else {
  785. 			listDelete3(&a, i+1);//从A中删除该元素
  786. 			j++;//同时移动指针
  787. 		}
  788. 	}
  789. 	
  790. }
  791.  
  792.  
  793. bool isSubset(seqList A, seqList B) {
  794. 	int i, j;
  795. 	for (i = 0; i < A.len; i++) {
  796. 		for (j = 0; j < B.len; j++) {
  797. 			if (A.data[i] == B.data[j]) {//当两者值相同时，结束循环
  798. 				break;
  799. 			}
  800. 		}
  801. 		if (j == B.len) {
  802. 			return 0;//循环结束时，j=B.len则未搜索到，返回false
  803. 		}
  804. 	}
  805. 	return 1;
  806. }
  807.  
  808. /*一个长度为L（L≥1）的升序序列S，处在第          个位置的数称为S 的中位数。例如，若序列S1 = (11, 13, 15, 17, 19)，则S1 的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2 = (2, 4, 6, 8, 20)，则S1 和S2 的中位数是11。
  809. 现有两个等长升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：
  810. （1）给出算法的基本设计思想。
  811. （2）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
  812. （3）说明你所设计算法的时间复杂度和空间复杂度。*/
  813.  
  814. elementType listFindTheMiddel(seqList a,seqList b) {
  815. 	int i = 0, j = 0;
  816. 	int L1 = a.len;
  817. 	int L2 = b.len;
  818. 	int res = (L1 + L2) % 2 == 0 ? (L1 + L2)/2: (L1 + L2) / 2+1 ;//返回中间值
  819. 	int count = 0;
  820. 	int kind =0;
  821. 	while (i != a.len && j != b.len) {//从小到大搜索到对应下标的值
  822. 		if (a.data[i] <= b.data[j]) {
  823. 			count++;
  824. 			i++;
  825. 			kind = 1;
  826.  
  827.  
  828. 		}
  829. 		else if (a.data[i] > b.data[j]) {
  830. 			count++;
  831. 			j++;
  832. 			kind = 2;
  833.  
  834. 		}
  835. 		if (count == res) {
  836. 			return kind == 1 ? a.data[i - 1] : b.data[j - 1];
  837. 		}
  838. 		
  839. 	}
  840. 	if (i != a.len && count != res) {//对一个顺序表到头，但是另一个顺序表，且未搜索到对应值未到头的情况进行查找
  841. 		i++;
  842. 		count++;
  843. 		if (count == res) {
  844. 			return a.data[i - 1] ;
  845. 		}
  846. 	}
  847. 	else if (j != b.len && count != res) {
  848. 		j++;
  849. 		count++;
  850. 		if (count == res) {
  851. 			return b.data[j - 1];
  852. 		}
  853. 	}
  854. 	return -1;
  855. }

2.（递增有序）顺序表表示集合A、B，判定A是否B的子集。

3. (2011)（15 分）一个长度为L（L≥1）的升序序列S，处在第          个位置的数称为S 的中位数。例如，若序列S1=(11, 13, 15, 17, 19)，则S1 的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2, 4, 6, 8, 20)，则S1 和S2 的中位数是11。

    现有两个等长升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/674235
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号