当前位置：首页 > news >正文

数据结构与算法编程题3

news 2025/8/26 3:50:15

长度为n的顺序表，删除线性表所有值为x的元素，使得时间复杂度为O(n)，空间复杂度为O(1)

#include <iostream>
using namespace std;typedef int ElemType;
#define Maxsize 100
#define	OK 1
#define  ERROR 0
typedef struct SqList
{ElemType data[Maxsize];int length;
}SqList;void Init_SqList(SqList& L)
{L.length = 0;
}void Delete_x1(SqList& L, int x)
{int k = 0;for (int i = 0; i < L.length; i++){if (L.data[i] != x)L.data[k++] = L.data[i];}L.length = k;
}void Delete_x2(SqList& L, int x)
{int count = 0;for (int i = 0; i < L.length; i++){if (L.data[i] == x)count++;elseL.data[i - count] = L.data[i];}L.length = L.length - count;
}//0 1 2 3 4 
//5 3 3 1 10
/*长度为n的顺序表，删除线性表所有值为x的元素，使
得时间复杂度为O(n)，空间复杂度为O(1)*/
int main(void)
{SqList L;Init_SqList(L);cout << "--------------测试情况1--------------" << endl;L.data[0] = 5;L.data[1] = 3;L.data[2] = 3;L.data[3] = 1;L.data[4] = 10;L.length = 5;for (int i = 0; i < L.length; i++)cout << L.data[i] << "     ";cout << endl;//Delete_x1(L, 3);Delete_x2(L, 3);for (int i = 0; i < L.length; i++)cout << L.data[i] << "     ";cout << endl;cout << "--------------测试情况2--------------"<<endl;L.data[0] = 5;L.data[1] = 3;L.data[2] = 3;L.data[3] = 1;L.data[4] = 10;L.data[5] = 11;L.length = 6;for (int i = 0; i < L.length; i++)cout << L.data[i] << "     ";cout << endl;//Delete_x1(L, 3);Delete_x2(L, 3);for (int i = 0; i < L.length; i++)cout << L.data[i] << "     ";cout << endl;return 0;
}