数据结构 - 线性表

微风

2022 年 09 月 17 日

755 次浏览

暂无评论

4320字数

线性表的定义

线性表是属于数据结构三要素中的逻辑结构

线性表基本操作

顺序表的定义

顺序表的实现 - 静态分配

顺序表初始化 - 静态分配

顺序表的实现 - 动态分配

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10 // 顺序表最大默认长度
typedef struct {
  int* data; // 指示动态分配数组的指针
  int MaxSize; // 顺序表的最大容量
  int length; // 顺序表的当前长度
}SeqList;

// 初始化数组
void InitList(SeqList &L) {
  // 使用malloc 函数申请一片连续的存储空间
  L.data = (int*)malloc(InitSize * sizeof(int));
  L.length = 0;
  L.MaxSize = InitSize;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L,int len) {
  int* p = L.data;
  L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
  for (int i = 0;i < L.length;i++) {
    L.data[i] = p[i];// 将数据赋值到新区域
  }
  L.MaxSize = L.MaxSize + len; // 顺序表最大长度增加len
  free(p);// 释放原来的内存空间
}

int main() {
  SeqList L; // 声明顺序表
  InitList(L); // 初始化顺序表
  // 往顺序表中插入几个元素
  IncreaseSize(L, 5);
  return 0;
}

顺序表的特点

随机访问，即可以在O（1）时间内找到第i个元素
存储密度高，每个节点只存储数据元素
拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
插入、删除操作不方便，需要移动大量元素

知识回顾与重要考点

顺序表的基本操作 - 插入

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10
typedef struct {
  int data[MaxSize]; // 用静态的数组存放数据元素
  int length;
}SqList;

// 初始化
void InitList(SqList &L) {
  for (int i = 0;i < MaxSize;i++) {
    L.data[i] = 0;
  }
  L.length = 0;
}

// 插入元素
void ListInsert(SqList &L,int i,int e) {
  for (int j = L.length;j >= i;j--) { // 将第i个元素之后的元素后移
    L.data[j] = L.data[j - 1];
  }
  L.data[i - 1] = e; // 在位置i处存放e
  L.length++;// 长度+1
}

int main() {
  SqList L;
  InitList(L);
  L.data[0] = 1;
  L.data[1] = 2;
  L.data[2] = 4;
  L.data[3] = 5;
  L.data[4] = 6;
  L.length = 5;
  ListInsert(L, 3, 3);
  for (int i = 0;i < L.length;i++) {
    printf("%d ", L.data[i]);
  }
  return 0;
}

对插入操作进行改写

// 插入元素升级版
bool ListInsert(SqList &L,int i,int e) {
  if (i < 1 || i > L.length+1) {
    return false;
  }
  if (L.length >= MaxSize) {
    return false;
  }
  for (int j = L.length;j >= i;j--) {
    L.data[j] = L.data[j - 1];
  }
  L.data[i - 1] = e;
  L.length++;
  return true;
}

int main() {
  SqList L;
  InitList(L);
  L.data[0] = 1;
  L.data[1] = 2;
  L.data[2] = 4;
  L.data[3] = 5;
  L.data[4] = 6;
  L.length = 5;
  bool b = ListInsert(L, 9, 3);
  if (b) {
    printf("插入元素成功！");
  }
  else {
    printf("插入元素失败！");
  }
  return 0;
}

顺序表的基本操作 - 删除

#include <stdio.h>
#include <stdlib.h>


#define MaxSize 10
typedef struct {
  int data[MaxSize]; // 用静态的数组存放数据元素
  int length;
}SqList;

// 初始化
void InitList(SqList& L) {
  for (int i = 0;i < MaxSize;i++) {
    L.data[i] = 0;
  }
  L.length = 0;
}

// 删除顺序表中元素
bool ListDelete(SqList &L,int i,int &e) {

  if (i < 1 || i > L.length) {
    return false;
  }
  e = L.data[i - 1];
  for (int j = i;j < L.length;j++) {
    L.data[j - 1] = L.data[j];
  }
  L.length--;
  return true;
}


int main() {
  SqList L;
  InitList(L);
  L.data[0] = 1;
  L.data[1] = 2;
  L.data[2] = 4;
  L.data[3] = 5;
  L.data[4] = 6;
  L.length = 5;

  // 实现元素的删除操作
  int e = -1;
  bool b = ListDelete(L,3,e);
  if (b)
    printf("删除成功！删除元素为%d", e); // 4
  else
    printf("删除失败,参数不符合规则！");
  return 0;
}