数据结构练习题1

时间：2021-03-20 00:15:05

1.顺序表的基本定义

#define MAXSIZE 50
#define ElemType int
typedef struct{
ElemType data[MAXSIZE];
int length;
}SqList;

顺序表的基本操作:(1)插入元素(2)删除元素(3)查找元素

(1)插入元素

bool Insert(SqList &L, ElemType value, int x) //插入操作
{
int i;
if (x >= L.length) return false; //插入位置大于表长
if (x < 0) return false;//
for (i = L.length; i>x; i--)//x为插入线性表的位置
{
L.data[i] = L.data[i - 1];
}
L.data[x- 1] = value;
L.length++;
return true;
}

(2)删除元素

bool DeleteElem(SqList &L, int x, ElemType &e)//删除第x个位置，并将该数据通过e返回
{
if (x >= L.length)return false;
if (x < 0) return false;
e = L.data[x - 1];
for (int i = L.length; i > x; i++)
L.data[i] = L.data[i - 1];
L.length--;
return true;
}

(3)查找元素

ElemType Search_Elem(SqList &L, int x){//查找第x个位置的元素，并将该数据通过元素返回
if (x >= L.length)return false;
if (x < 0) return false;
return L.data[x-1];
}

...


综合应用题

(1)顺序表中删除具有最小元素的值(假设唯一)，函数返回被删元素的值，空出位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

ElemType Delete_Min_Elem(SqList &L)
{
ElemType data_min;
int min = 0;//记录最小元素的下标
if (L.length == 0) {
printf("ERROR! The list is NULL\n");
return NULL;
}
for (int  i = 0; i < L.length; i++)
{
if (L.data[i] < L.data[min]) min = i;//遍历整个顺序表找到最小元素的下标
}
data_min = L.data[min];
L.data[min] = L.data[L.length - 1];
L.length--;//删除最小值
return data_min;//返回最小元素的值
}
(2)设计一个高效的算法将所有元素逆置，要求空间复杂度为O(1) 

bool Reverse_Elem(SqList &L){
if (L.length == 0) {//表空 错误
printf("ERROR! The list is NULL\n");
return NULL;
}
ElemType temp;
for (int i = 0; i < L.length / 2; i++)
{
temp = L.data[i];//交换首尾俩个元素的位置
L.data[i] = L.data[L.length - i - 1];
L.data[L.length - i - 1]=temp;
}
return true;
}

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

有两种解法，可以将删除的操作看做为1保留下不等于x的元素或者是2.记录等于x的节点数然后执行替换操作

bool delete_elem1(SqList &L, ElemType x){//删除元素x
int k = 0; //k用于记录当前操作元素位置
if (L.length == 0) return false;//表空删除失败
for (int i = 0; i < L.length; i++)
{
if (L.data[i] != x) L.data[k++]=L.data[i];//只保留不等于x的节点
}
L.length = k;//保留下不等于x的元素个数
return true;
}
bool delete_elem2(SqList &L, ElemType x){//删除元素x
int k = 0; //k用于记录当前操作元素位置
if (L.length == 0) return false;//表空删除失败
for (int i = 0; i < L.length; i++)
{
if (L.data[i] == x) k++;//记录等于x节点的个数
else
{
L.data[i - k] = L.data[i];
}
}
L.length -= k;//删除k个节点
return true;
}

4.从有序表中删除给定值在s和t之间的元素(s<t),st不合理或者表为空输出错误并返回。

bool delete_elem_betweenst(SqList &L, ElemType s, ElemType t){
if (s >= t || L.length == 0) return false;//s>t 不合理或者表空
int i = 0, j = 0;//i,j分别指明两个值为s和t的下标，然后通过赋值，替换掉第i个之后的元素。
while (i < L.length)
{
if (L.data[i] > s) break;//找到第一个大于等于s的元素，并用i记录位置
i++;
}
if (i >= L.length) return false;
while (j < L.length)
{
if (L.data[j] > t) break;//找到第一个大于等于t的元素，并用j记录位置
j++;
}
if (j >= L.length) { 
L.length = i;//表后元素都大于s小于t ，返回；
return true;
}
else{
for (;j < L.length; i++,j++)
{
L.data[i] = L.data[j]; //大于s之后的元素都赋值为第j个之后开始的元素
}
}
L.length = i;
return true;
}

5.从有序表中删除给定值在s和t之间的元素(s<t)包含st,st不合理或者表为空输出错误并返回。 

bool delete_elem_betweenst2(SqList &L, ElemType s, ElemType t){
if (s>t) return false;//s和t的取值不合法
if (L.length == 0) return false; //表空 删除错误
int i, j;
int k = 0;
for (i = 0; i < L.length; i++)
if (L.data[i]>=s&&L.data[i] <= t)
{
k++;//用k记录在s和t之间的元素个数
}
else
{
L.data[i - k] = L.data[i];//前移大于t的元素，填补被删除的元素
}
L.length -= k;
return true;
}
6.有序表中删除所有值重复的元素，使得表中的元素值不同 

bool delete_same_elem(SqList &L){
if (L.length == 0) return false;
int i, j;
for (i = 0,j=1; j< L.length;j++)
if (L.data[i] != L.data[j])//前一个元素和后一个元素不等
L.data[++i] = L.data[j];//将后面的元素保留下来，以此类推
L.length = i;
}

7.将两个有序表合成为一个新的表，函数返回结果顺序表 

bool Merga(SqList &L, SqList &A, SqList &B){
if (A.length + B.length>MAXSIZE) return false;
int i, j, k;//i，j，k分别操作L，A，B
for (i = 0; i < A.length + B.length; i++)
{
if (A.data[j]<B.data[k])//取小的数进入L表中
{
L.data[i] = A.data[j++];
}
else
{
L.data[i] = B.data[k++];
}
}
L.length = i;
return true;
}

8.已知在一维数组A[m+n]中依次存放着两个线性表(a1,a2,a3,...,am)和(b1,b2,b3,...,bn),编写程序将(b1,b2,b3,...,bn)放在a1,a2,a3,...,am)前面。 

bool change_position(ElemType A[],int arraysize_m, int arraysize_n){
ElemType B[arraysize_m + arraysize_n];
int k;
for (int i = 0; i < arraysize_n; i++)
{
B[i] = A[arraysize_m + i - 1];//B数组存储第A数组第m之后的元素
}
for (int i = arraysize_n; i < arraysize_m; i++)
{
B[i] = A[k++];//B数组存储第A数组前m个元素
}
for (int i = 0; i < arraysize_m + arraysize_n; i++)
{
A[i] = B[i];
}
}

9












标签：

相关文章