线性表是最基本最常用的数据结构，常用的存储方式有两种：顺序存储和链式存储。
顺序表的实现如下：
1、seqlist.h 文件
/*
* 线性表的顺序存储结构（顺序表）
*/
#ifndef SEQLIST_H__
#define SEQLIST_H__
// 宏定义
#define DATASIZE 1024
// 顺序表元素类型定义
typedef int datatype;
/*
* 顺序表结构
* 使用定长数组来存储数据元素
*/
typedef struct node_st {
datatype data[DATASIZE];
int last; // 用来保存当前存放最后一个元素的位置
}seqlist;
/*
* 初始化，创建顺序表
* 返回结构体类型的指针
*/
seqlist *seqlist_create();
/*
* 初始化，创建顺序表
* 传入一个二级指针的方式
*/
void seqlist_init(seqlist **);
/*
* 销毁顺序表
* 释放顺序表所占内存
*/
void seqlist_destroy(seqlist *);
/*
* 判断顺序表是否为空
*/
int seqlist_is_empty(seqlist *);
/*
* 顺序表置空
*/
void seqlist_set_empty(seqlist *);
/*
* 获取顺序表中元素的个数
*/
int seqlist_length(seqlist *);
/*
* 从顺序表中查找数据
*/
int seqlist_find(seqlist *, datatype *);
/*
* 往顺序表中插入数据
*/
int seqlist_insert(seqlist *, int, datatype *);
/*
* 从顺序表中删除数据
*/
int seqlist_delete(seqlist *, int);
/*
* 遍历顺序表
*/
void seqlist_display(seqlist *);
/*
* 合并两个顺序表
*/
void seqlist_union(seqlist *, seqlist *);
#endif
2、seqlish.c 文件
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"
/*
* 初始化，创建顺序表
* 返回结构体类型的指针
*/
seqlist *seqlist_create() {
seqlist *ptr;
ptr = malloc(sizeof(*ptr));
if (ptr == NULL) {
return NULL;
}
// 刚初始化的顺序表没有元素
ptr->last = -1;
return ptr;
}
/*
* 初始化，创建顺序表
* 传入一个二级指针的方式
*/
void seqlist_init(seqlist **ptr) {
*ptr = malloc(sizeof(**ptr));
if (*ptr == NULL) {
return; // 无返回值
}
// 刚初始化的顺序表没有元素
(*ptr)->last = -1;
return; // 无返回值
}
/*
* 销毁顺序表
* 释放顺序表所占内存
*/
void seqlist_destroy(seqlist *ptr) {
// 释放顺序表内存
free(ptr);
// 释放内存后指针置空
ptr = NULL;
return; // 无返回值
}
/*
* 判断顺序表是否为空
*/
int seqlist_is_empty(seqlist *ptr) {
if (ptr->last == -1) {
// 顺序表为空
return 0;
}
// 非空
return -1;
}
/*
* 顺序表置空
*/
void seqlist_set_empty(seqlist *ptr) {
ptr->last = -1;
return; // 无返回值
}
/*
* 获取顺序表中元素的个数
*/
int seqlist_length(seqlist *ptr) {
/*
* 当 last 为 -1 时，表示顺序表为空
* 当 last 为 0 时，表示顺序表中有一个元素
* 因此，顺序表中元素的个数为 last + 1
*/
return (ptr->last + 1);
}
/*
* 从顺序表中查找数据
*/
int seqlist_find(seqlist *ptr, datatype *data) {
int i; // 循环索引值
if (seqlist_is_empty(ptr) == 0) {
// 顺序表为空
return -2;
}
for (i = 0; i <= ptr->last; i++) {
if (ptr->data[i] == *data) {
// 返回元素所在位置
return i;
}
}
// 没有找到
return -1;
}
/*
* 往顺序表中插入数据
*/
int seqlist_insert(seqlist *ptr, int pos, datatype *data) {
int i; // 循环索引值
if (ptr->last == DATASIZE - 1) {
// 空间满了
return -1;
}
if (pos < 0 || pos > ptr->last + 1) {
// 插入的位置不对
return -2;
}
for (i = ptr->last; pos <= i; i--) {
// 要插入位置上的元素，及其之后的元素，依次后移一位
ptr->data[i+1] = ptr->data[i];
}
// 插入数据
ptr->data[pos] = *data;
ptr->last++;
// 成功插入
return 0;
}
/*
* 从顺序表中删除数据
*/
int seqlist_delete(seqlist *ptr, int pos) {
int i; // 循环索引值
if (pos < 0 || pos > ptr->last) {
// 删除元素的位置不对
return -1;
}
for (i = pos + 1; i <= ptr->last; i++) {
// 要删除元素的位置后的所有元素依次前移一位
ptr->data[i-1] = ptr->data[i];
}
ptr->last--;
// 删除成功
return 0;
}
/*
* 遍历顺序表
*/
void seqlist_display(seqlist *ptr) {
int i; // 循环索引值
if (seqlist_is_empty(ptr) == 0) {
// 顺序表为空
return; // 无返回值
}
for (i = 0; i <= ptr->last; i++) {
printf("%d ", ptr->data[i]);
}
printf("\n");
return; // 无返回值
}
/*
* 合并两个顺序表
* 将 list2 中的所有元素合并到 list1 中
* 合并时去除重复数据
*/
void seqlist_union(seqlist *list1, seqlist *list2) {
int i; // 循环索引值
for (i = 0; i <= list2->last; i++) {
if (seqlist_find(list1, &list2->data[i]) < 0) {
// 去重追加插入
seqlist_insert(list1, list1->last+1, &list2->data[i]);
}
}
}
3、main.c 文件
#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"
int main() {
int i; // 循环索引值
int ret; // 返回状态值
seqlist *list1 = NULL, *list2 = NULL; // 两个顺序表
// 两条测试数据
datatype data1[] = {63, 89, 95, 76, 57, 31};
datatype data2[] = {49, 76, 63, 81, 35, 24};
// 查找的数据
int search_data = 95;
/* 初始化顺序表 */
// 采用不同的方式初始化两个顺序表
list1 = seqlist_create();
if (list1 == NULL) {
fprintf(stderr, "初始化顺序表 list1 失败！\n");
exit(1);
}
seqlist_init(&list2);
if (list2 == NULL) {
fprintf(stderr, "初始化顺序表 list2 失败！\n");
exit(1);
}
/* 往顺序表中插入数据 */
for (i = 0; i < sizeof(data1)/sizeof(*data1); i++) {
// 往顺序表 list1 中插入 data1 数据
if ((ret = seqlist_insert(list1, list1->last + 1, &data1[i])) != 0) {
if (ret == -1) {
fprintf(stderr, "顺序表 list1 空间满了。\n");
} else if (ret == -2) {
fprintf(stderr, "顺序表 list1 数据插入位置有误。\n");
} else {
fprintf(stderr, "发生未知错误。\n");
}
exit(1);
}
}
for (i = 0; i < sizeof(data2)/sizeof(*data2); i++) {
// 往顺序表 list2 中插入 data2 数据
if ((ret = seqlist_insert(list2, list2->last + 1, &data2[i])) != 0) {
if (ret == -1) {
fprintf(stderr, "顺序表 list2 空间满了。\n");
} else if (ret == -2) {
fprintf(stderr, "顺序表 list2 数据插入的位置有误。\n");
} else {
fprintf(stderr, "发生未知错误。\n");
}
exit(1);
}
}
/* 遍历顺序表 */
printf("顺序表 list1 中的元素：");
seqlist_display(list1);
printf("顺序表 list2 中的元素：");
seqlist_display(list2);
/* 顺序表置空 */
//seqlist_set_empty(list1);
/* 从顺序表中查找数据 */
ret = seqlist_find(list1, &search_data);
if (ret == -2) {
printf("顺序表 list1 为空。\n");
} else if (ret == -1) {
printf("在顺序表 list1 中没有找到 %d\n", search_data);
} else {
printf("%d 在顺序表 list1 中的索引值：%d\n", search_data, ret);
}
/* 从顺序表中删除数据 */
if ((ret = seqlist_delete(list1, 2)) != 0) {
if (ret == -1) {
fprintf(stderr, "从顺序表 list1 中删除元素的位置有误。\n");
} else {
fprintf(stderr, "发生未知错误。\n");
}
exit(1);
}
/* 合并两个顺序表 */
seqlist_union(list1, list2);
/* 获取顺序表中元素的个数 */
printf("顺序表 list1 中元素的个数：%d\n", seqlist_length(list1));
printf("顺序表 list2 中元素的个数：%d\n", seqlist_length(list2));
/* 遍历顺序表 */
printf("顺序表 list1 中的元素：");
seqlist_display(list1);
printf("顺序表 list2 中的元素：");
seqlist_display(list2);
/* 销毁顺序表 */
seqlist_destroy(list1);
seqlist_destroy(list2);
}
4、Makefile 文件
OBJS=main.o seqlist.o
CC=gcc
CFLAGS+=-c -Wall -g
seqlist:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $^ $(CFLAGS) -o $@
clean:
$(RM) *.o seqlist -r
执行效果：
gcc main.c -c -Wall -g -o main.o
gcc seqlist.c -c -Wall -g -o seqlist.o
gcc main.o seqlist.o -o seqlist
root@RicenOS:~# ./seqlist
顺序表 list1 中的元素：63 89 95 76 57 31
顺序表 list2 中的元素：49 76 63 81 35 24
95 在顺序表 list1 中的索引值：2
顺序表 list1 中元素的个数：9
顺序表 list2 中元素的个数：6
顺序表 list1 中的元素：63 89 76 57 31 49 81 35 24
顺序表 list2 中的元素：49 76 63 81 35 24
Copyright © 2005-2023 by www.ricensoftwares.com.cn All Rights Reserved.
