[C++知识库]线性表 —— 顺序表 (C语言)

线性表 —— 顺序表 (C语言)

• 概念

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表中的数据元素，这种表示也称做线性表的顺序储存结构或顺序映像。通常，称这种存储结构的线性表为顺序表 (Sequential List) 。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。

1. 顺序表的储存结构

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

#define MAX_SIZE 1000 //顺序表能储存的最大数值

typedef int DATA;   //抽象化int类型
typedef struct _List{
    DATA *data;
    int length;
} SeqList;

2. 顺序表的基本操作

//初始化顺序表
SeqList* initList() {
    SeqList* list = malloc(sizeof(SeqList));
  	assert(list != NULL);
    list->data = malloc(MAX_SIZE * sizeof(DATA));
    list->length = 0;  //顺序表的初始长度为0
    assert(list->data != NULL);
    return list;
}

2.1 顺序表的插入

• 头插法：

  1.将表中所有数据元素向后移一位

  2.将数据元素插入第 0 位

  3.长度 length + 1

• 图解

• 代码

void insertByHead(SeqList* list, DATA data){
    if (list->length >= MAX_SIZE){
        printf("顺序表已满无法插入数据...\n");
        return; //跳出函数
    }
    
    for (int i = list->length; i > 0; i--){
        list->data[i] = list->data[i-1];
    }
    list->data[0] = data;
    
    list->length++;
}

• 指定位置插入法：

  1.将第 index 位与它后面的所有数据元素向后移动一位

  2.将数据元素插入第 index 位

  3.长度 length + 1

• 图解

• 代码

void insertByIndex(SeqList* list, int index, DATA data){
    if ((index < 0 || index >= list->length) && list->length >= MAX_SIZE){
        printf("输入的index值错误或顺序表已满无法插入...\n");
        return; //跳出函数
    }
    
    for (int i = list->length; i > index; i--) {
	    list->data[i] = list->data[i - 1];
    }
    list->data[index] = data;
    
    list->length++;
}

• 尾插法：

  1.将数据插入第 length 位

  2.长度 length + 1

• 图解

• 代码

void insertByTail(SeqList* list, DATA data){
    if (list->length >= MAX_SIZE){
        printf("顺序表已满无法插入数据...\n");
        return; //跳出函数
    }
    list->data[list->length++] = data;
}

2.2 顺序表的查找

• 步骤

  通过数值逐个比对，若表中存在相同元素则返回较前面的元素位置。

• 代码

int find(SeqList* list, DATA data)
{
	for (int i = 0; i < list->length; i++) {
		if (list->data[i] == data) {
			return i;
		}
	}
	return -1;
}

2.3 顺序表的删除

• 通过值删除元素

  1.找到值对应的元素下标 index

  2.将第 index + 1 位与它后面的所有元素向前移动一位

  3.长度 length - 1

• 图解

• 代码

void deleteByData(SeqList* list, DATA data) {
	if (list->length == 0){
      	printf("表为空，无需进行删除...\n");
    }

	int ret = find(list, data);

	if (ret != -1) {
		for (int i = ret; i < list->length - 1; i++) {
			list->data[i] = list->data[i + 1];
		}
		
		list->length--;
	}
  	else{
    	printf("该数据不存在，无法删除...\n");
  	}
}

• 通过索引删除元素

  1.将第 index + 1 位与它后面的所有元素向前移动一位

  2.长度 length - 1

• 图解

• 代码

void deleteByIndex(SeqList* list, int index) {
	if (list->length == 0){
      	printf("表为空，无需进行删除...\n");
    }

  	if (index >= list->length){
    	printf("索引位置大于表的总长度...\n");
      	return;
  	}
  	
	for (int i = index; i < list->length - 1; i++) {
		list->data[i] = list->data[i + 1];
	}
	
	list->length--;
}