数据结构：顺序表的基本操作！（C语言）

一、静态存储

#include <stdio.h>
#include <stdlib.h>
 
/*[1].定义静态顺序表的最大容量*/
#define MaxSize 10
 
/*[2].自定义数据元素的数据类型*/
typedef int ElemType; 

---

1. 静态分配的定义结构体 

/*[3].静态分配的结构体定义*/
typedef struct {
	ElemType data[MaxSize];  // 静态数组存放数据元素
	int length;  // 表长 
}SqList;   // 顺序表的类型定义

---

2.初始化顺序表 

/*[4].静态分配的顺序表的初始化*/ 
void InitSqList(SqList &L) {
	L.length = 0;
} 

---

3.插入操作 

/*[5].插入操作: 在第i位置插入一个元素e */
bool ListInsert(SqList &L, int i, ElemType e) {
	//判断插入的位置是否合法
	if (i < 1 || i > L.length + 1) {   // 插入可以在1~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;
}

---

4.删除操作

/*[6].删除操作: 删除第i个位置的元素，并将删除元素返回出去*/
bool ListDelete(SqList &L, int i, ElemType &e) {
	// 与插入不同的是删除只能删的位置是 1~length 
	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;
} 

---

5.查找操作

/*[7].查找操作(按值查找): 查找第一个值等于e的元素，并返回位序*/
int LocateElem(SqList L, ElemType e) {
	int i;
	for (i=0; i<L.length; i++) {
		if (L.data[i] == e) {
			return i+1;  // 返回的是位序，不是索引号！！ 
		}
	}
	return 0; 
} 
 
/*[8].查找操作(按位查找): 查找第一个值等于e的元素，并返回位序*/
ElemType SeqListFindW(SeqList L, int i) {
	return L.data[i-1];
} 

---

6.打印顺序表元素 

bool SqListPrint(SqList L) {
	if (L.length == 0) {
		printf("the list is null！\n"); 
		return false;
	}
	
	printf("静态分配顺序表输出：");
	for (int i=0; i<L.length; i++) {
		printf("%d-->", L.data[i]);
	}
	printf("end\n");
	return true;
} 

---

7.主函数测试 

int main() {
	SqList L;
	
	/*1. 测试初始化*/ 
	InitSqList(L);
	
	/*2.测试插入操作*/ 
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 2);
	ListInsert(L, 3, 3);
	ListInsert(L, 4, 4321);
	ListInsert(L, 5, 5);
	ListInsert(L, 6, 6);
	ListInsert(L, 7, 7);
	ListInsert(L, 8, 8);
	SqListPrint(L);
	
	/*3.测试查找操作*/ 
	int num = LocateElem(L, 7);
	printf("静态分配按值查找后返回的位序是：%d\n", num);
	int num1 = SqListFindW(L, 7);
	printf("静态分配按位查找后返回的值是：%d\n", num1);
	
	/*4.测试删除操作*/ 
	ElemType e;
	ListDelete(L, 2, e); 
	SqListPrint(L);
	printf("SqList删除的元素是：%d\n", e); 
}

运行结果：

二、动态分配

#include <stdio.h>
#include <stdlib.h>
 
/*[1].动态顺序表的初始默认最大容量*/
#define InitSize 10  
 
/*[2].自定义数据元素的数据类型*/
typedef int ElemType; 

1.动态分配的结构体定义

/*[3].动态分配的结构体定义*/ 
typedef struct {
	ElemType *data; // 指示动态分配数组的指针
	int maxSize;   // 数组的最大容量 
	int length; 
}SeqList; 

---

2.动态分配的初始化

/*[4].动态分配的顺序表的初始化*/
void InitList(SeqList &L) {
	L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
	L.length = 0;
	L.maxSize = InitSize;
} 

---

3.插入操作

/*[5].插入操作(按位插入): 在第i位置插入一个元素e */
bool InsertSqList(SeqList &L, int i, ElemType 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;	
}

---

 4.删除操作

/*[6].删除操作: 删除第i个位置的元素，并将删除元素返回出去*/
bool SqListDelete(SeqList &L, int i, ElemType &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;
} 

5.查找操作

/*[7].查找操作(按值查找): 查找第一个值等于e的元素，并返回位序*/
int LocateElem(SeqList L, ElemType e) {
	int i; 
	for (int i=0; i<L.length; i++) {
		if (L.data[i] == e) {
			return i+1;
		}
	} 
	return 0;
} 
/*[8].查找操作(按位查找): 查找第一个值等于e的元素，并返回位序*/
int SqListFindW(SeqList L, int i) {
	return L.data[i-1];
} 

---

 

6.扩容操作

bool IncreaseSqList(SeqList &L, int len) {
	// 1. 生成指向原来顺序表存储空间的指针，便于后续的释放原来的内存空间 
	ElemType *p = L.data;
	// 2. 为原来的顺序表开辟一块更大的空间
	L.data = (ElemType *)malloc(sizeof(ElemType)*(L.maxsize+len));
	// 3. 转移数据
	for (int i=0; i<L.length; i++) {
		L.data[i] = p[i];
	}		
	// 4.修改顺序表的最大长度，其值 + len
	L.maxsize += len;
	// 5.释放原来的内存空间
	free(p);
	// 6.成功后返回true
	return true; 
} 

---

7.打印顺序表

bool SeqListPrint(SeqList L) {
	if (L.length == 0) {
		printf("该顺序表为空！\n"); 
		return false;
	}
	
	printf("动态分配顺序表输出：\n");
	for (int i=0; i<L.length; i++) {
		printf("%d-->", L.data[i]);
	}
	printf("end\n");
	return true; 
 
} 

---

8.主函数测试 

int main() {
	SeqList L;
	
	/*1. 测试初始化*/
	InitSqList(L);
	
	/*2.测试插入操作*/ 
	InsertSqList(L, 1, 1);
	InsertSqList(L, 2, 2);
	InsertSqList(L, 3, 3);
	InsertSqList(L, 4, 4111);
	
	/*3.测试查找操作*/
	int num = LocateElem(L, 3);
	printf("动态分配按值查找后返回的位序是：%d\n", num);
	
	int num1 = SqListFindW(L, 3);
	printf("动态分配按位查找后返回的值是：%d\n", num1);
	
	/*4.测试删除操作*/
	ElemType q;
	SqListDelete(L, 3, q);
	printf("SeqList删除的元素是：%d\n", q);
	SqListPrint(L); 
	
	/*5.测试动态分配顺序表的扩容操作*/ 
	IncreaseSqList(L, 20);
	printf("扩容后的L的maxsize为：%d\n",L.maxSize); // 30  ->  扩容成功
}

---

运行结果：