实现线性表的顺序存储定义,完成顺序表的创建、插入、删除、查找、排序等常用操作,完成两个有序线性表的合并,要求同样的数据元素只出现一次。
时间: 2023-10-19 11:05:40 浏览: 97
线性表的顺序存储的实现
4星 · 用户满意度95%
顺序存储定义:线性表的顺序存储指的是将线性表中的元素按照其逻辑顺序依次存储在一块连续的存储区域中。
具体实现:
```C++
#include<iostream>
using namespace std;
const int MAXSIZE = 100; // 定义线性表的最大长度
typedef struct {
int data[MAXSIZE]; // 线性表存储的数组
int length; // 线性表的长度
} SqList;
// 初始化线性表
void InitList(SqList &L) {
L.length = 0; // 长度为0
}
// 判断线性表是否为空
bool ListEmpty(SqList L) {
return L.length == 0;
}
// 获取线性表中第i个元素的值
bool GetElem(SqList L, int i, int &e) {
if (i < 1 || i > L.length) { // 判断i是否合法
return false;
}
e = L.data[i-1];
return true;
}
// 在线性表中查找值为e的元素,返回其在表中的位置
int LocateElem(SqList L, int e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i+1;
}
}
return 0; // 表示查找失败
}
// 在线性表中插入元素e,将其插入到第i个位置
bool ListInsert(SqList &L, int i, int e) {
if (i < 1 || i > L.length+1 || L.length == MAXSIZE) { // 判断i是否合法,以及线性表是否已满
return false;
}
for (int j = L.length; j >= i; j--) { // 将第i个位置及其后面的元素后移一位
L.data[j] = L.data[j-1];
}
L.data[i-1] = e; // 插入元素e
L.length++; // 线性表长度加1
return true;
}
// 在线性表中删除第i个位置的元素,并将其值存储到e中
bool ListDelete(SqList &L, int i, int &e) {
if (i < 1 || i > L.length) { // 判断i是否合法
return false;
}
e = L.data[i-1]; // 将要删除的元素的值存储到e中
for (int j = i; j < L.length; j++) { // 将第i个位置后面的元素前移一位
L.data[j-1] = L.data[j];
}
L.length--; // 线性表长度减1
return true;
}
// 对线性表进行冒泡排序
void BubbleSort(SqList &L) {
for (int i = 0; i < L.length-1; i++) {
for (int j = 0; j < L.length-i-1; j++) {
if (L.data[j] > L.data[j+1]) { // 如果前面的元素大于后面的元素,交换它们的位置
int temp = L.data[j];
L.data[j] = L.data[j+1];
L.data[j+1] = temp;
}
}
}
}
// 合并两个有序线性表,并去除重复元素
void Merge(SqList A, SqList B, SqList &C) {
int i = 0, j = 0, k = 0;
while (i < A.length && j < B.length) { // A和B都未遍历完
if (A.data[i] < B.data[j]) { // A中的元素小于B中的元素
C.data[k++] = A.data[i++]; // 将A中的元素存入C中
} else if (A.data[i] > B.data[j]) { // A中的元素大于B中的元素
C.data[k++] = B.data[j++]; // 将B中的元素存入C中
} else { // A中的元素等于B中的元素
C.data[k++] = A.data[i++]; // 将A中的元素存入C中
j++; // B中的元素位置后移一位
}
}
while (i < A.length) { // A未遍历完
C.data[k++] = A.data[i++]; // 将A中的元素存入C中
}
while (j < B.length) { // B未遍历完
C.data[k++] = B.data[j++]; // 将B中的元素存入C中
}
C.length = k; // C的长度为k
}
```
注:以上代码仅为示例,实际应用中还需考虑一些异常情况下的处理。
阅读全文