文章目录
- 一【题目类别】
- 二【题目来源】
- 三【题目描述】
- 四【解题思路】
- 五【时间频度】
- 六【代码实现】
- 七【程序测试】
一【题目类别】
二【题目来源】
- 本题目选自王道2023考研计算机数据结构复习指导18页中二、综合应用题之06题
三【题目描述】
- 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
四【解题思路】
- 这道题目需要注意的是题目给的是有序顺序表，也就是值相同的元素在连续的相邻位置上，所以我们设置两个指针，假设第一个元素视为非重复的有序表，那么第一个指针就指向非重复元素的有序表的最后一个位置，那么第二个指针为工作指针，向后依次寻找不重复的元素，如果遇到了，就将不重复的元素移动到前面，否则就继续向下寻找
五【时间频度】
- 时间复杂度：
O
(
n
)
O(n)
O(n)，其中
n
n
n为顺序表长度
- 空间复杂度：
O
(
1
)
O(1)
O(1)
六【代码实现】
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define MaxSize 50
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
void Delete_Same(SqList L)
{
if (L.length == 0)
{
return 0;
}
int index = 0, cur = 1;
while (cur < L.length)
{
if (L.data[index] != L.data[cur])
{
index++;
L.data[index] = L.data[cur];
}
cur++;
}
L.length = index + 1;
printf("删除重复元素后的顺序表为：");
for (int i = 0; i < L.length; i++)
{
printf("%d ", L.data[i]);
}
printf("n");
}
int main()
{
SqList L;
L.length = 0;
int len;
printf("请输入顺序表长度（长度应≤50）：");
scanf("%d", &len);
printf("请输入顺序表元素：");
for (int i = 0; i < len; i++)
{
scanf("%d", &L.data[i]);
L.length++;
}
printf("初始顺序表为：");
for (int i = 0; i < L.length; i++)
{
printf("%d ", L.data[i]);
}
printf("n");
Delete_Same(L);
system("pause");
return 0;
}
七【程序测试】
