【数据结构】线性表
线性表是n个数据元素的有限序列。
线性表是一种逻辑结构，表是元素之间一对一的相邻关系。
顺序表和链表是指存储结构。
特点
- 表中元素个数有限
- 表中元素具有逻辑上的顺序性，表中元素有其先后次序
- 表中元素都是数据元素，每个元素都是单个元素
- 每个元素占有相同大小的存储空间
顺序表
线性表的顺序存储又称为顺序表。用一组地址连续的存储单元一次存储线性表中的数据元素。逻辑上相邻的两个元素在物理位置上也相邻
一维数组空间分配
静态分配
数组的大小和空间已经固定，一旦空间站慢，再加入新的数据将会产生溢出，程序就会崩溃。
动态分配
存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用来替换原来的存储空间。
⚠️：动态分配仍然是顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。
特点
- 随机访问，通过首地址和元素序号可在时间O(1)内找到指定的元素。
- 存储密度高，每个节点只存储数据元素。
- 逻辑上相邻的元素物理上也相邻，当执行插入删除操作时，需要移动大量的元素。
基本操作的实现
插入操作
由于表中元素的物理位置是相邻的，所以当插入新元素的时候就需要对表中的元素进行整体移动。
操作描述：在顺表L的第i个位置插入新元素e。若i的输入不合法，则返回原表并显示错误提示，表示插入失败；否则，将顺序表的第i个元素及其后的所有元素向右移动一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功返回已插入的表。
//插入操作
sqlist addlist (sqlist &l,int elem,int add)//插入操作，传入表、插入的数字和第add个位置
{
if (add>l.length+1||add<1) {//判断选择插入的位置是否在表内
printf("插入位置有问题");
return l;
}
for (int i=l.length-1; i>=add-1; i--) {
//设置int型变量i来记录数组下标，初始设置i为3，当i大于等于指定位置的数组下标时，i-1.直到i小于指定位置的下标时，结束循环
//注意传入的是第几个位置，而不是数组下标
l.head[i+1]=l.head[i];//数组下标i+1存i的数值
}
l.head[add-1]=elem;//最后插入正确位置
l.length++;
return l;
}
删除操作
删除顺序表L中第i个位置的元素，若成功则返回删除后的表，并打印被删除的元素，否则返回false
//删除操作
sqlist delList(sqlist &l,int i){
if(i>l.length||i<1){
printf("erro");
exit(0);
}
int e=l.head[i-1];
printf("%d",e);
printf("
");
for(int j=i;j<l.length;j++){
l.head[j-1]=l.head[j];
}
l.length--;
return l;
}
按值查找（顺序查找）
在顺序表中查找第一个数值为e的元素，并返回其位序。
//按值查找
int locateElem(sqlist l,int e){
for(int i=0;i<l.length;i++){
if(l.head[i]==e){
int j=i+1;
printf("在第%d个位置",j);
return i+1;
}
}
return 0;
}
//插入删除操作全部可运行代码
#include <stdio.h>
#include <stdlib.h>
#define InitSize 4//初始长度
typedef struct{
int *head;//指示动态数组分配的指针
int length;
int Size;
}sqlist;
sqlist initList(){
sqlist l;
l.head=(int*)malloc(InitSize*sizeof(int));//初始化动态分配
if(!l.head){
printf("erro
");
exit(0);
}
l.length=0;
l.Size=InitSize;
return l;
}
void DispalyList(sqlist l){
for(int i=0;i<l.length;i++){
printf("%d",l.head[i]);
};
printf("
");
}
sqlist addlist (sqlist &l,int elem,int add)
{
if (add>l.length+1||add<1) {
printf("插入位置有问题");
return l;
}
for (int i=l.length-1; i>=add-1; i--) {
l.head[i+1]=l.head[i];
}
l.head[add-1]=elem;
l.length++;
return l;
}
sqlist delList(sqlist &l,int i){
if(i>l.length||i<1){
printf("erro");
exit(0);
}
int e=l.head[i-1];
printf("%d",e);
printf("
");
for(int j=i;j<l.length;j++){
l.head[j-1]=l.head[j];
}
l.length--;
return l;
}
int locateElem(sqlist l,int e){
for(int i=0;i<l.length;i++){
if(l.head[i]==e){
int j=i+1;
printf("在第%d个位置",j);
return i+1;
}
}
return 0;
}
int main()
{
sqlist l=initList();
for(int i=1;i<=InitSize;i++){
l.head[i-1]=i;
l.length++;
};
DispalyList(l);
addlist(l,0,1);
DispalyList(l);
delList(l,2);
DispalyList(l);
locateElem(l,0);
return 0;
}