线性表之顺序表(C语言实现)

2024-07-17 10:02| 来源: 网络整理| 查看: 265

线性表之顺序表顺序表定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表当中的数据元素。从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接的存储的也就是第i+1个元素。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同

其顺序存储结构如下

数组下表顺序表内存地址0a1LOC(A)1a2LOC(A)+sizeof(ElemType)2a3LOC(A)+2*sizeof(ElemType)3a4LOC(A)+3*sizeof(ElemType)…┊┊MaxSize-1┊LOC(A)+(MaxSize-1)*sizeof(ElemType)

假设线性表L存储的起始位置是LOC(A),sizeof(ElemType)是每个数据元素所占存储空间的大小，ElemType表示的是数据的类型,如果存的是整形,就是int。(注意线性表中的位序是从1开始的,数组中元素的下表是0)

顺序表类型描述如下

#define MaxSize 50 typedef struct List { ElemType data[MaxSize]; int length = 0; }SqList;

当然一位数组可以是静态分配的,也可以选择用动态分配

#define MaxSize 50 type struct List { ElemType *data; int length = 0; }SqList;

C语言初始动态分配如下

L.data = (ElemType*)malooc(sizeof(ElemType)*MaxSize)

顺序表上的基本操作如下,上代码

插入操作 bool ListInsert(SqList; &L, int i, ElemType e) { //本函数实现在第i个位置插入元素e if(i < 1 || i > L.length + 1) //判断i是否越界 return false; if(L.length >= MaxSize) //存储空间已满,不能插入 return false; for(int j = L.length; j >= i; j--) // 将第i个元素及后面的元素往后移,为元素e腾地方 L.data[j] = L.data[j-1]; L.data[i-1] = e; L.length++; return true; } 删除操作 bool ListDelete(SqList; &L, int i, ElemType &e) { //本函数实现删除第i个元素,并将被删除的元素用引用变量e返回 if(i < 1 || i > L.length) //判断i是否越界 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; } 查找操作 int LocateElem(SqList; &L, ElemType e) { //本函数实现查找元素e在表中的位序,查找失败返回0 for(int i = 0; i < L.length; i++) if(L.data[i] == e) return i+1; return e; } 总代码 #include #define MaxSize 100 typedef struct List { int data[MaxSize]; int length = 0; }SqList; bool ListInsert(SqList &L, int i, int e) { //本函数实现在第i个位置插入元素e if(i < 1 || i > L.length + 1) //判断i是否越界 return false; if(L.length >= MaxSize) //存储空间已满,不能插入 return false; for(int j = L.length; j >= i; j--) // 将第i个元素及后面的元素往后移,为元素e腾地方 L.data[j] = L.data[j-1]; L.data[i-1] = e; L.length++; return true; }; bool ListDelete(SqList &L, int i, int &e) { //本函数实现删除第i个元素,并将被删除的元素用引用变量e返回 if(i < 1 || i > L.length) //判断i是否越界 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; } int LocateElem(SqList &L, int e) { //本函数实现查找元素e在表中的位序,查找失败返回0 for(int i = 0; i < L.length; i++) if(L.data[i] == e) return i+1; return 0; } int main() { int a; SqList L; ListInsert(L, 1, 10); ListInsert(L, 2, 20); ListInsert(L, 3, 15); ListInsert(L, 4, 18); printf("15在顺序表的位序是: %d\n", LocateElem(L, 15)); ListDelete(L, 3, a); printf("删除了顺序表第3个元素, 值为: %d\n", a); if(LocateElem(L, 15) == 0) printf("顺序表中不存在15这个值\n"); else printf("15在顺序表的位序是: %d\n", LocateElem(L, 15)); return 0; } 输出: 15在顺序表的位序是: 3 删除了顺序表第3个元素, 值为: 15 顺序表中不存在15这个值

单链表

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章