数据结构之线性表（1）

2024-06-10 09:44

文章标签 线性表数据结构

本文主要是介绍数据结构之线性表（1），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构之线性表

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;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  Deleate_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[i] = x;}
}