数据结构之线性表
1.线性表的定义
线性表是一种线性结构。在一个线性表中数据元素的类型是相同的,或者说线性表是由同一类型的数据元素构成的线性结构。
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。
n表示表长,当n=0时称该线性表为空表。
2.线性表的存储方式
线性表的存储方式有顺序存储和链式存储两种
1.顺序存储:
在内存中用连续的一块存储空间顺序存放线性表中的各数据元素。
优点:内存中的地址空间是线性的,物理位置关系上的实现数据元素之间的逻辑相邻关系简单自然。
缺点:当不确定存储多少数据时,内存开辟了之后,多了造成浪费,少了不够用,其次,数据中的元素增删查改时间复杂度过高。
2.链式存储:
在内存中以链表的形式存储,内存中的地址不连续。
优点:可以根据需要来申请内存空间,方便灵活。
缺点:物理位置关系上不能反映数据元素之间的逻辑。为指针开辟一个空间,会有多余的内存损耗。
3.顺序表的存储
顺序表的存储方式有两种:
1.静态顺序表
2.动态顺序表
今天我们来详细了解静态顺序表的相关操作
顺序表的静态存储就是在存放数据时,已经给定了存储空间的大小。
其结构体的声明为:
typedef struct {datatype data[MAXSIZE];//MAXSIZE为元素的最大存储个数 int last;//last起到一个指针的作用,始终指向线性表中的最后一个元素,当表空时,last==-1 }SeqList; //定义一个顺序表 SeqList L;
其中表长=L.last+1,线性表中的数据元素a1~an分别存放在L.data[0]-L.data[L.last]中。
4.顺序表的基本操作实现
我们学会了顺序表的基本语法,我们现在可以对线性表进行简单的操作。
以下为顺序表的静态存储的相关操作:
4.1顺序表的初始化
//顺序表的初始化 Seqlist* init_SeqList(Seqlist* L) {Seqlist* L; L = malloc(sizeof(Seqlist)); L->last = -1; return L; }
4.2顺序表的插入
//顺序表的插入 int insert_SeqList(Seqlist* L,int i, datatype x) {if (L->last == MAXSIZE - 1) {printf("表满\n"); return (-1); } if (i<1 || i>L->last + 2) {printf("插入位置错误\n"); return 0; } int j = 0; for (int j = L->last; j > i; j--) {L->data[j + 1] = L->data[j]; } L->data[j] = x; L->last++; return (1); }
4.3顺序表的删除
//顺序表的删除 void Deleate_SeqList (Seqlist* L, int i) {int j; if (i<1||i>L->last +1) {printf("不存在第i个元素\n"); } for (j = i + 1; j < L->last; j++) {L->data[j - 1] = L->data[j]; } L->last--; }
4.4顺序表的按值查找
//顺序表的查找 void Find_SeqList(Seqlist* L, datatype x) {int i = 0; int flag = 0; for (i = 0; i < L->last; ++i) {if (L->data[i] == x) {flag = 1; printf("查找的元素在第%d个位置上\n", i); break; } } if (flag == 0) {printf("查找的该元素不存在\n"); } }
4.5顺序表中值的修改
//顺序表中值的修改 void Change_SeqList(Seqlist* L,int i,datatype x) {if (i<1 || i>L->last + 1) {printf("修改位置错误\n"); } for (int j = 0; j < i; j++) {L->data[j] = x; } }
以上就是对顺序表静态存储中的增删查改的相关操作了,下文继续创作动态存储下顺序表的相关操作,谢谢大家支持!