一、静态存储
#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 -> 扩容成功
}
运行结果：
