顺序表的基本操作

线性表的顺序存储

1、顺序表的原理

顺序表存储是将数据元素放到一块连续的内存存储空间,相邻数据元素的存放地址也相邻(逻辑与物理统一)。

2、顺序表的特点

1、空间连续;

2、支持随机访问;

3、在中间或前面部分的插入或删除时间复杂度为O(n),效率低;

4、根据下标随机访问时间复杂度为O(1),更适合频繁访问第n个元素,读取效率高

3、基本存储结构

#include <stdio.h>
#define MAXSIZE 100		//线性表的最大长度
typedef int DataType;

typedef struct Node {
    DataType data[MAXSIZE];
    int length;
} SeqList;

4、基本功能

  • 顺序表的初始化功能 void InitList(SeqList *L)
  • 顺序表的判空 int ListEmpty(SeqList L)
  • 获取顺序表指定位置的元素 int GetElement(SeqList L, int i)
  • 在顺序表的指定位置上插入元素 int InsertList(SeqList *L, int i, int e)
  • 删除顺序表中指定位置的元素 int DeleteList(SeqList *L, int i, int *e)
  • 返回指定元素在顺序表中的位置 int LocateElement(SeqList L, int e)
  • 合并两个非递减的顺序表,新的顺序表保持非递减 void MerGeList(SeqList La, SeqList Lb, SeqList *Lc)
  • 两个顺序表取并集,即新的顺序表要进行去重 void UnionList(SeqList La, SeqList Lb, SeqList *Lc)
  • 遍历输出顺序表的所有元素 void PrintList(SeqList L)
#include <stdio.h>
#define MAXSIZE 100		//线性表的最大长度
typedef int DataType;

typedef struct Node {
    DataType data[MAXSIZE];
    int length;
} SeqList;

//初始化,将所有元素置为0,顺序表的实际长度为0
void InitList(SeqList *L) {
    int i;
    for (i = 0; i < MAXSIZE; i++) {
        L->data[i] = 0;
    }
    L->length = 0;
}

//顺序表的判空
int ListEmpty(SeqList L) {
    return L.length == 0;
}

//按位查找,i表示位序,从1开始
int GetElement(SeqList L, int i) {
    if (i < 1 || i > L.length) {	//不符合边界条件返回0
        return 0;
    }
    return L.data[i - 1];
}

//按位插入
int InsertList(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1 || L->length == MAXSIZE) {	//不符合边界条件或是顺序表满了返回0
        return 0;
    }
    int j;
    for (j = L->length; i <= j; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e;
    L->length++;
    return 1;
}

//按位删除
int DeleteList(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length) {
        return 0;
    }
    int j;
    *e = L->data[i - 1];
    for (j = i; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    L->length--;
    return 1;

}

//按值查找返回位置,找不到返回-1
int LocateElement(SeqList L, int e) {
    int i;
    for (i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;		//这里的i表示下标从0开始,返回位序要+1
        }
    }
    return -1;
}

//遍历输出顺序表的所有元素
void PrintList(SeqList L) {
    int i;
    for (i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

//合并两个非递减的顺序表,新的顺序表保持非递减(归并排序)
void MerGeList(SeqList La, SeqList Lb, SeqList *Lc) {
    if (La.length+Lb.length > MAXSIZE) {
        return;
    }
    //先初始化Lc顺序表
    Lc->length = La.length + Lb.length;
    int a = 0, b = 0, c=0;
    while(a<La.length && b<Lb.length) {
        if (La.data[a]<=Lb.data[b]) {
            Lc->data[c++] = La.data[a++];
        } else {
            Lc->data[c++] = Lb.data[b++];
        }
    }
    while(a<La.length) {
        Lc->data[c++] = La.data[a++];
    }
    while(b<Lb.length) {
        Lc->data[c++] = Lb.data[b++];
    }
}

//两个顺序表取并集,即新的顺序表要进行去重
void UnionList(SeqList La, SeqList Lb, SeqList *Lc) {
    //1先把La的元素插入Lc中并判断Lc中是否已经存在该元素
    //2再吧Lb的元素插入Lc中并判断Lc中是否已经存在该元素
    int i;
    for (int i = 0; i < La.length; ++i) {
        DataType e = La.data[i];
        if(LocateElement(*Lc, e)==-1) {     //等于-1说明这个元素不存在可以插入
            InsertList(Lc, Lc->length+1, e);
        }
    }
    for (int i = 0; i < Lb.length; ++i) {
        DataType e = Lb.data[i];
        if(LocateElement(*Lc, e)==-1) {
            InsertList(Lc, Lc->length+1, e);
        }
    }

}


void main() {
    SeqList L;
    int i, n;
    InitList(&L);
    printf("顺序表是否为空:%d\n",ListEmpty(L));

    for (i = 0; i < 10; i++) {
        InsertList(&L, i + 1, i);
    }
    printf("顺序表是否为空:%d\n", ListEmpty(L));
    printf("在第一个位置插入-1,是否成功:%d\n", InsertList(&L, 1, -1));
    printf("删除第一个位置的元素,是否成功:%d\n", DeleteList(&L, 1, &n));
    printf("第5个位置的元素是:%d\n", GetElement(L, 5));
    printf("9是顺序表中的第%d个元素\n", LocateElement(L, 9));
    printf("遍历顺序表:");
    PrintList(L);
    //合并两个非递减的顺序表
    SeqList Lc;
    MerGeList(L, L, &Lc);
    PrintList(Lc);
    //两个顺序表取并集
    SeqList La, Lb;
    UnionList(L, L, &Lc);
    PrintList(Lc);
    printf("%d", Lc.length);
}

点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注