线性表-顺序存储-删除重复元素

思路：遍历线性表，将不重复的元素依次存放在前面的位置上，记录不重复元素的个数，最后将多余的元素删除。

具体实现：

1. 初始化一个变量count表示不重复元素的个数，初始值为1，因为第一个元素一定不重复。

2. 从下标为1的元素开始遍历线性表，判断当前元素是否与前一个元素相同，如果不同，则将该元素存放在下标为count的位置上，并将count加1。

3. 如果相同，则继续遍历下一个元素。

4. 遍历完整个线性表后，将下标为count及其后面的元素删除，即将线性表的长度设为count。

代码实现：

void deleteDuplicate(ElemType A[], int& n)
{
    int count = 1; // 不重复元素的个数
    for (int i = 1; i < n; i++) {
        if (A[i] != A[i-1]) { // 当前元素不重复
            A[count++] = A[i]; // 存放在下标为count的位置上，并将count加1
        }
    }
    n = count; // 将线性表的长度设为count
}

时间复杂度：O(n)，其中n为线性表的长度。

空间复杂度：O(1)。

相关问题

实现线性表的顺序存储结构。实现线性表在顺序存储结构下的插入和删除操作。并用该存储结构实现集合A和集合B的并集和交集操作，要求最终结果存储于集合A当中。

在计算机科学中，线性表的顺序存储结构通常是指数组这种数据结构。它通过连续的一段内存空间来存储元素，每个元素都有一个确定的索引位置。以下是基本的顺序存储结构以及插入、删除和并集、交集操作的实现：

1. **实现顺序存储结构：**
- 创建一个固定大小的数组 `list` 和两个指针 `head` 和 `tail` 分别指向列表的起始和结束位置。

   class SequentialList:
       def __init__(self, size):
           self.size = size
           self.list = [None] * size
           self.head = 0
           self.tail = 0

2. **插入操作（Insertion）：**
- 如果还有空余的位置，将新元素插入到 `tail+1` 的位置，然后更新 `tail` 指针。

   def insert(self, value):
       if self.tail < self.size - 1:
           self.list[self.tail + 1] = value
           self.tail += 1
       else:
           print("List is full and cannot insert.")

3. **删除操作（Deletion）：**
- 如果要删除的是第一个元素（即 `head` 指向），则将 `head` 移动到下一个元素；如果要删除的是最后一个元素，则仅当 `head` 不等于 `tail` 时才进行。

   def remove(self, value):
       while self.head < self.tail and self.list[self.head] != value:
           self.head += 1
       if self.head == self.tail:
           print("Value not found in the list.")
       else:
           self.head += 1

4. **并集操作（Union）：**遍历两个列表，将非重复的元素添加到集合A中。

   def union(self, other_list):
       for value in other_list.list:
           if value not in self.list:
               self.insert(value)

5. **交集操作（Intersection）：**同样遍历两个列表，找到同时出现在两个列表中的元素，并只将它们添加到集合A中。

   def intersection(self, other_list):
       intersection_set = set()
       for value in self.list:
           if value in other_list.list:
               intersection_set.add(value)
       # 将集合转换回顺序列表
       for value in intersection_set:
           self.insert(value)

现在，你可以创建两个 `SequentialList` 对象 A 和 B，并分别执行上述操作。

假设线性表采用顺序存储结构,试实现函数(int delrepeat()),用以删除所有重复元素,

在顺序存储结构的线性表中，每个元素的位置是连续的，可以通过下标来直接访问。为了实现删除所有重复元素的功能，可以按照以下步骤编写函数(int delrepeat())：

1. 首先创建一个空数组temp[]用于存储不重复的元素。同时创建一个变量count用于记录temp[]数组的元素个数，初始值为0。

2. 使用一个循环遍历原始线性表，从第一个元素开始逐个进行比较。

3. 对于每个元素，使用另一个循环遍历temp[]数组，判断当前元素是否与temp[]中的某个元素相等。如果相等，则跳过当前元素，继续下一个元素的比较。

4. 如果当前元素与temp[]中的所有元素都不相等，则将当前元素存入temp[]中，并将count加1。

5. 循环结束后，temp[]数组中存储的即为不重复的元素。

6. 最后，将temp[]数组中的元素再依次存回原始线性表中的相应位置。

具体的实现代码如下：

int delrepeat()
{
    int temp[MAX_SIZE];
    int count = 0;
    
    for(int i=0; i<size; i++) // 遍历原始线性表
    {
        bool isDuplicate = false;
        
        for(int j=0; j<count; j++) // 遍历temp[]数组
        {
            if(data[i] == temp[j]) // 判断当前元素是否与temp[]中的某个元素相等
            {
                isDuplicate = true;
                break;
            }
        }
        
        if(!isDuplicate) // 如果当前元素与temp[]中的元素都不相等
        {
            temp[count] = data[i]; // 将当前元素存入temp[]
            count +=1; // temp[]数组的元素个数增加
        }
    }
    
    // 将temp[]数组中的元素存回原始线性表的相应位置
    for(int i=0; i<count; i++)
    {
        data[i] = temp[i];
    }
    
    size = count; // 更新线性表的大小
    
    return size; // 返回删除重复元素后的线性表大小
}

这样，调用delrepeat()函数后，原始线性表中所有的重复元素都会被删除，线性表的大小也会相应更新。返回值为删除重复元素后的线性表大小。