C语言实现 顺序表结构体、建空表、求表长，插入元素...

C语言实现 顺序表结构体、建空表、求表长，插入元素... 顺序表结构体

• 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(0)

• 最坏的情况：在表头插入，即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 
#include 

#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;
}