顺序表 (数组) 详解

54 阅读 0 评论 36 点赞

我是靠谱客的博主等待马里奥，最近开发中收集的这篇文章主要介绍顺序表 (数组) 详解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

数组和链表是最基本的数据结构，栈、队列、树、图等复杂数据结构都是基于数组或链表方式存储

线性表采用顺序存储的方式存储被称为顺序表，顺序表将表中结点依次存放在计算机内存中一组地址连续的存储单元中。从顺序表定义中可看出顺序表就是数组

顺序表结构体

c语言的struct结构体类似于 java的class类
typedef struct SeqList *List;表示定义一个struct SeqList *类型的结构指针，该指针指向SeqList结构体，List是自定义类型的别名。
定义结构指针的目的：对顺序表进行操作时，直接将结构体作为函数参数传递不好，使用结构指针传递的效率更高。（所以我们将List定义为结构指针，然后就可以利用List定义线性表L，即List L；这样就可以通过L访问线性表的内容。比如下标为i的元素，可以通过L->data[i]访问。）

#define MAX_SIZE 100  //顺序表最大容量
typedef int ElemType;

//顺序表结构
struct SeqList {
	ElemType data[MAX_SIZE]; //顺序表元素
	int length; //顺序表实际长度
};
//定义一个struct SeqList *类型的结构指针，该指针指向SeqList结构体
typedef struct SeqList *List;

精简代码（上面和下面两组代码是一样的）

#define MAX_SIZE 100  //顺序表最大容量
typedef int ElemType;

//顺序表结构
typedef struct SeqList {
	ElemType data[MAX_SIZE]; //顺序表元素
	int length; //顺序表实际长度
} *List;

建空表

L是SeqList的指针，指向名为SeqList的结构体
malloc(sizeof(SeqList))是指向系统申请一块大小为sizeof(SeqList)的内存地址
(List)指的是把这个地址强制转化成SeqList *的指针

//创建一个空的顺序表
List Init() {
	List L; //定义顺序表的指针变量（L指的是SqList *的指针，指向名为SqList的结构体）
	L = (List)malloc(sizeof(SeqList)); //给顺序表开辟一块sizeof(SeqList)大小的存储空间
	L->length = 0; //设置顺序表的长度为0，表示顺序表为空
	
	return L; //返回顺序表的首地址
}

求表长

//顺序表长度
int Length(List L) {
	return L->length;
}

元素插入

顺序表的位序和元素下标是两个不同概念，位序从1开始，元素下标从0开始。位置为i的元素，它的下标为i-1
当i的值在[1，L->length+1]区间内时，都是有效的插入位置。1表示待插入元素取代第1个元素，L->length+1表示插入到最后一个元素的后面。记得，i是位序，不是下标，它的有效插入位置是(i < 1 || i > L->length + 1)，不要写成(i < 0 || i > L->length)，i为下标时才是这种写法。

//顺序表元素插入
int Insert(List L, int i, ElemType x) {
//注意：i是元素插入位置，不是下标，位置是从1开始的，下标是从0开始

	//如果顺序表满了
	if (L->length == MAX_SIZE - 1) {
		return 0; //插入失败
	}
	//判断i访问是否合法（插入的有效位置是[1,L->length+1]）
	if (i < 1 || i > L->length + 1) {
		return 0;
	}
	//将第i个元素及之后的元素后移一位
	for (int j = L->length; j >= i; j--) {
		L->data[j] = L->data[j - 1];
	}
	//将元素x插入i位置
	L->data[i - 1] = x;
	//顺序表长度加1
	L->length++;
	
	return 1;
}

最好的情况：在表尾插入，即i = L->length+1的位置插入，元素后移语句无需执行，时间复杂度为O(1)
最坏的情况：在表头插入，即i = 1的位置插入，元素后移语句将执行n次，时间复杂度为O(n)

元素删除

//顺序表元素删除
int Delete(List L, int i) {
	int j;
	//判断删除的位置是否是有效位置（删除的有效位置是[1,L->length]）
	if (i < 1 || i > L->length) {
		printf("位序%d不存在元素", i);
		return 0;
	}
	将第i个元素之后的元素前移一位
	for (j = i; j < L->length; j++) {
		L->data[j - 1] = L->data[j];
	}
	//数组长度减1
	L->length--;
	return 1;
}

元素查找

//顺序表元素查找（根据元素查找下标）
int Find(List L, ElemType x) {
	int i = 0;
	//遍历数组，直至找到目标元素
	while (i < L->length && L->data[i] != x) {
		i++;
	}
	//查找到表尾都没有该元素，则返回-1，找到了该元素，则返回元素下标
	if (i >= L->length) {
		return -1;
	} else {
		return i;
	}
}

全部代码

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

#define MAX_SIZE 100  //顺序表最大容量
typedef int ElemType;

//顺序表结构
struct SeqList {
	ElemType data[MAX_SIZE]; //顺序表元素
	int length; //顺序表实际长度
};
//定义一个struct SeqList *类型的结构指针，该指针指向SeqList结构体
typedef struct SeqList *List;


//创建一个空的顺序表
List Init() {
	List L; //定义顺序表的指针变量（L指的是SqList *的指针，指向名为SqList的结构体）
	L = (List)malloc(sizeof(SeqList)); //给顺序表开辟一块sizeof(SeqList)大小的存储空间
	L->length = 0; //设置顺序表的长度为0，表示顺序表为空
	
	return L; //返回顺序表的首地址
}

//顺序表长度
int Length(List L) {
	return L->length;
}


//顺序表元素插入
int Insert(List L, int i, ElemType x) {
//注意：i是元素插入位置，不是下标，位置是从1开始的，下标是从0开始

	//如果顺序表满了
	if (L->length == MAX_SIZE - 1) {
		return 0; //插入失败
	}
	//判断i访问是否合法（插入的有效位置是[1,L->length+1]）
	if (i < 1 || i > L->length + 1) {
		return 0;
	}
	//将第i个元素及之后的元素后移一位
	for (int j = L->length; j >= i; j--) {
		L->data[j] = L->data[j - 1];
	}
	//将元素x插入i位置
	L->data[i - 1] = x;
	//顺序表长度加1
	L->length++;
	
	return 1;
}

//顺序表元素删除
int Delete(List L, int i) {
	int j;
	//判断删除的位置是否是有效位置（删除的有效位置是[1,L->length]）
	if (i < 1 || i > L->length) {
		printf("位序%d不存在元素", i);
		return 0;
	}
	将第i个元素之后的元素前移一位
	for (j = i; j < L->length; j++) {
		L->data[j - 1] = L->data[j];
	}
	//数组长度减1
	L->length--;
	return 1;
}

//顺序表元素查找（根据元素查找下标）
int Find(List L, ElemType x) {
	int i = 0;
	//遍历数组，直至找到目标元素
	while (i < L->length && L->data[i] != x) {
		i++;
	}
	//查找到表尾都没有该元素，则返回-1，找到了该元素，则返回元素下标
	if (i >= L->length) {
		return -1;
	} else {
		return i;
	}
}


int main() {
	List L = Init();

	Insert(L, 1, 50);
	Insert(L, 2, 55);
	Insert(L, 3, 60);

	printf("%dn", Length(L));
	Delete(L, 2);
	printf("%dn", L->data[1]);
	printf("%dn", Find(L, 22));
	printf("%dn", Find(L, 60));

	return 0;
}