顺序表是简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空值，插入、删除时需要移动大量元素。
顺序存储：
把逻辑上相邻的元素存储在物理 位置上也相邻的存储单元中，元素之间的关 系由存储单元的邻接关系来体现。
静态
#include "stdio.h"
#include "stdlib.h"
struct List {
//实现顺序表的底层数组,假设存的都是整数
int arr[10];
//表示底层数组的容量
int length;
};
//起个名字
typedef struct List *SeqList;
void InitList(SeqList L){
//容量设为10
L->length = 10;
}
int main(){
struct List L;
InitList(&L);
for(int i = 0; i < L.length; i++){
printf("data[%d]=%d ", i, L.arr[i]);
}
return 0;
}或者
#include "stdio.h"
#include "stdlib.h"
typedef struct {
//实现顺序表的底层数组
int arr[10];
//表示底层数组的容量
int length;
}SeqList;
//起个名字
//typedef struct List *SeqList;
void InitList(SeqList &L){
//容量设为10
L.length = 10;
}
int main(){
SeqList L;
InitList(L);
for(int i = 0; i < L.length; i++){
printf("data[%d]=%d ", i, L.arr[i]);
}
return 0;
}动态申请
#include "stdio.h"
#include "stdlib.h"
typedef struct {
//指向顺序表的底层数组
int *arr;
//数组的容量
int length;
}SeqList;
bool InitList(SeqList &L){
L.length = 10;
// 10:指定要分配内存的元素数量
// sizeof(int):以字节为单位返回int数据类型的大小
// (int *):进行类型强制转换，显式地将malloc返回的void *指针转换为int *指针类型
L.arr = (int *) malloc(L.length * sizeof (int));
if(L.arr == NULL){
return false;
}
return true;
}
int main(){
SeqList L;
if(InitList(L)){
printf("succeed!\n");
for(int i = 0; i < L.length; i++){
printf("data[%d]=%d ", i, L.arr[i]);
}
} else{
printf("fail\n");
}
return 0;
}
我这里并未对值进行初始化，这些从内存中拿到的自然很奇怪。
进行插入操作
#include "stdio.h"
#include "stdlib.h"
#define max_size 16
typedef struct {
//指向顺序表的底层数组
int *arr;
//数组的容量
int length;
int size;
}SeqList;
void DisplayList(SeqList &L){
for(int i = 0; i < L.length; i++){
printf("data[%d]=%d ", i, L.arr[i]);
}
printf("\n");
}
bool InitList(SeqList &L){
L.length = 10;
L.size = max_size;
// 这里我们设置链表的最大容量，并用这个数值去申请空间
L.arr = (int *) malloc(L.size * sizeof (int));
if(L.arr == NULL){
return false;
}
for(int i = 0; i < L.length; i++){
L.arr[i] = i;
}
return true;
}
bool InsertList(SeqList &L, int pos, int value) {
// 检查插入的位置是否合理
if (pos >= L.length || pos < 1) {
return false;
}
// 这里我们从尾端取数，依次后移
for (int i = L.length - 1; i >= pos; i--) {
L.arr[i + 1] = L.arr[i];
}
// 更改插入的位置的数
L.arr[pos] = value;
L.length++;
return true;
}
int main(){
SeqList L;
if(InitList(L)){
printf("succeed!\n");
DisplayList(L);
} else{
printf("fail\n");
}
printf("初始化完毕:\n");
InsertList(L, 5, 888);
DisplayList(L);
return 0;
}
删除操作和销毁操作
#include "cstdio"
#include "cstdlib"
#define max_size 128
typedef struct {
//指向顺序表的底层数组
int *arr;
//数组的容量
int length;
int size;
} SeqList;
void DisplayList(SeqList &L) {
for (int i = 0; i < L.length; i++) {
printf("data[%d]=%d ", i, L.arr[i]);
}
printf("\n");
}
bool InitList(SeqList &L) {
L.length = 10;
// 10:指定要分配内存的元素数量
// sizeof(int):以字节为单位返回int数据类型的大小
// (int *):进行类型强制转换，显式地将malloc返回的void *指针转换为int *指针类型
L.arr = (int *) malloc(L.length * sizeof(int));
L.size = max_size;
//这里可能内存发生分配失败
if (L.arr == NULL) {
return false;
}
for (int i = 0; i < L.length; i++) {
L.arr[i] = i;
}
return true;
}
bool DeleteList(SeqList &L, int pos) {
// 同样检查
if (pos < 0 || pos >= L.length) {
return false;
}
// 往前移动
for (int i = pos; i < L.length; i++) {
L.arr[i - 1] = L.arr[i];
}
// 删除了肯定要减
L.length--;
return true;
}
void DestroyList(SeqList &L) {
if (L.arr) {
delete[]L.arr;
}
L.length = 0;
L.size = 0;
}
int main() {
SeqList L;
if (InitList(L)) {
printf("初始化完毕:\n");
DisplayList(L);
} else {
printf("fail\n");
}
printf("删除一个元素:\n");
DeleteList(L, 3);
DisplayList(L);
DestroyList(L);
printf("销毁\n");
DisplayList(L);
return 0;
}
