一、数据结构的两种结构类型
1.逻辑结构
① 集合结构：一个范围内，每一个个体之间没有任何关联
② 线性结构：一对一的关系，有唯一前驱和后继
第一个元素没有前驱，最后一个元素没有后继，中间元素既有唯一前驱，也有唯一后继
③ 树形结构：一对多的关系
第一个元素没有前驱，最后一个元素没有后继，中间元素有唯一前驱，但是可以有多个后继
④ 图形结构：多对多的关系，各个元素之间可能都有关联
2.存储结构
①顺序存储
特点：元素和元素之间依次存放
实现方法：数组、malloc
优点：数据查找和修改比较方便
缺点：浪费资源空间
插入数据、删除数据效率低
②链式存储
特点:在内存中的每一个元素之间用地址进行关联
优点：节省资源空间，插入数据、删除数据效率高
缺点：数据查找和修改效率低，需要遍历全部数据
③ 索引存储
特点：每一个元素都会创建一张索引表，资源开销比较大，
优点：数据查找效率高
④Hash存储（散列存储）
二、顺序表的抽象模型：
struct seqlist
{
int buf[50]; //定义表的大小
int last; //定义表尾指针，指向表中最后一个元素
}
三、seqlist.h头文件代码
#ifndef __SEQLIST__
#define __SEQLIST__
#define N 64
typedef int data_t;
typedef struct seqlist
{
data_t buf[N]; //定义表长
int last; //定义表尾指针last，指向表中最后一个元素下标
}SeqList;
SeqList *Create_Seqlist(); //创建表
void Seqlist_Insert_Pos(SeqList *seq, int pos, data_t data); // 插入表
int Seqlist_Is_Full(SeqList *seq); //判断该表是否为满表
int Seqlist_Is_Empty(SeqList *seq);//判空
void Seqlist_Delete_Pos(SeqList *seq, int pos); //按位置删除表中元素
void Seqlist_Delete_Data(SeqList *seq, data_t data);//按值删除表中元素
data_t SeqList_Find_Pos(SeqList *seq, int pos);//查找表中元素 （按位置查找）
void Seqlist_Edit_Pos(SeqList *seq, int pos, data_t data); //修改表中元素 （按位置修改）
void Seqlist_Memset(SeqList *seq); //清空表
void Seqlist_Delete(SeqList *seq); //删除表
void Show_Seqlist(SeqList *seq); //打印表
四、seqlist.c函数实现代码
#include#include #include #include #include "seqlist.h" SeqList *Create_Seqlist() //创建表 { SeqList *seq = (SeqList *)malloc(sizeof(SeqList)); //给顺序表在堆区开辟空间 if(NULL == seq) { printf("malloc error!n"); return NULL; } memset(seq->buf, 0, sizeof(seq->buf)); //从buf地址开始，将sizeof（buf）这么大的空间全部赋值为0 seq->last = -1; //将表尾指针赋值为-1，表示该表为一张空表 return seq; //返回顺序表的首地址 } int Seqlist_Is_Full(SeqList *seq) //判断该表是否为满表 { if(seq->last == N-1) { return 1; } else { return 0; } } void Seqlist_Insert_Pos(SeqList *seq, int pos, data_t data) // 插入表 { if(pos != 0) { if((pos < 0) || (pos > seq->last+1)) //判断插入是否合法 { printf("pos error!n"); return; } } if(Seqlist_Is_Full(seq) == 1) //判满 { printf("seqlist is full!!!n"); return; } int i = 0; for(i = seq->last; i >= pos; i--) { seq->buf[i+1] = seq->buf[i]; } seq->buf[pos] = data; seq->last++; } int Seqlist_Is_Empty(SeqList *seq)//判空 { if(seq->last == -1){ return 1; } else return 0; } void Seqlist_Delete_Pos(SeqList *seq, int pos) //按位置删除表中元素 { if((pos < 0) || (pos > seq->last)) //判断插入是否合法 { printf("pos error!n"); return; } } for(int i = pos; i < seq->last; i++){ seq->buf[i] = seq->buf[i+1]; } seq->last--; return; } void Seqlist_Delete_Data(SeqList *seq, data_t data)//按值删除表中元素 { int i, k = 0; for(i = 0; i <= seq->last; i++){ if(seq->buf[i] == data){ for(int j = i; j < seq->last; j++){ seq->buf[j] = seq->buf[j+1]; } k++; seq->last--; } } if(k == 0){ printf("该值不存在！n"); } return; } data_t SeqList_Find_Pos(SeqList *seq, int pos)//查找表中元素 （按位置查找） { if((pos < 0) || (pos > seq->last)) //判断插入是否合法 { printf("pos error!n"); return; } return seq->buf[pos]; } void Seqlist_Edit_Pos(SeqList *seq, int pos, data_t data) //修改表中元素 （按位置修改） { if((pos < 0) || (pos > seq->last)) //判断插入是否合法 { printf("pos error!n"); return; } seq->buf[pos] = data; return; } void Seqlist_Memset(SeqList *seq) //清空表 { memset(seq->buf, 0, sizeof(seq->buf));//从buf地址开始，将sizeof（buf）这么大的空间全部赋值为0 seq->last = -1; return; } void Seqlist_Delete(SeqList *seq) //删除表 { free(seq); seq = NULL; return; } void Show_Seqlist(SeqList *seq) //打印表 { int i = 0; for(i = 0; i <= seq->last; i++) { printf("%d ", seq->buf[i]); } printf("n"); }
五、main.c主函数代码
#include#include "seqlist.h" int main(int argc, char *argv[]) { int n; printf("*******************************n"); printf("请选择对顺序表执行的操作n"); printf("1.创建顺序表n2.插入元素n3.查看顺序表是否满n4.查看顺序表是否空n5.修改元素n6.清空表n7.删除表n8.打印表n9.删除表中元素n10.查找表中元素n11.退出n"); printf("*******************************n"); int s = 10; SeqList *seq = Create_Seqlist(); while(s--) { Seqlist_Insert_Pos(seq, 0, s); } Show_Seqlist(seq); int pos; data_t data; while(1){ printf("请选择功能：n"); scanf("%d", &n); getchar(); switch (n) { case 1: printf("已创建顺序表n"); break; case 2: printf("请输入想要插入的位置和元素：n"); scanf("%d%d", &pos, &data); Seqlist_Insert_Pos(seq, pos, data); break; case 3: if(Seqlist_Is_Full(seq) == 1){ printf("顺序表元素已满n"); } break; case 4: if(Seqlist_Is_Empty(seq) == 1){ printf("顺序表是空表n"); } break; case 5: printf("请输入想要修改元素的位置和值：n"); scanf("%d%d", &pos, &data); Seqlist_Edit_Pos(seq, pos, data); break; case 6: Seqlist_Memset(seq); break; case 7: Seqlist_Delete(seq); break; case 8: Show_Seqlist(seq); break; case 9: printf("请输入数值或者位置删除表中元素：n"); printf("0.数值n1.位置n"); int m; scanf("%d", &m); switch (m) { case 0: printf("请输入数值：n"); scanf("%d", &data); Seqlist_Delete_Data(seq, data); break; case 1: printf("请输入位置：n"); scanf("%d", &pos); Seqlist_Delete_Pos(seq, pos); break; } break; case 10: printf("请输入元素的位置：n"); scanf("%d", &pos); data = SeqList_Find_Pos(seq, pos); printf("%dn", data); break; case 11: return 0; } } return 0; }
以上就是线性顺序表在Linux Ubuntu下的C语言实现，功能还有很多，作者只是例举了常见的一部分，欢迎大家补充，一起交流学习。
