数据结构笔记——线性结构

• 前言
• 一、线性表的定义和特点
• • 1.线性表的定义
  • 2.线性表的逻辑关系
  • 3.线性表的类型定义
  • 3.线性表的存储结构

数据结构笔记第二章

线性表是具有相应特性数据元素的一个有限序列，由n个数据元素组成
其中数据元素的个数n定义为表的长度
当n=0时称为空表
同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系

在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而只有一个直接后继a2；
有且只有一个终端结点an，它没有直接后继，而只有一个直接前趋；
其余的内部结点都有且只有一个直接前趋和一个直接后继。

1、抽象数据类型定义

ADT List{
	数据对象： D ={ai|ai属于Elemset（i=1,2,3.......n）}
	数据关系： R={}
	基本操作：
	//此处省略，下面细讲
}ADT List

2、基本操作
InitList：构造一个空的线性表
DestoryList：摧毁已存在的线性表
ClearList：重置已存在的线性表
ListEmpty：判断线性表是否为空
ListLength：返回线性表中元素个数
GetElem：返回第i个数据元素的值
LocateElemt：返回第一个与e满足的数据元素的位序
PriorElemt：返回该元素在线性表中的前趋
NextElemt：返回该元素在线性表中的后继
ListInsert：插入新的数据元素e
ListDelete：删除第i个数据元素

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

（1）顺序存储结构：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构，顺序存储结构占用一片连续的存储空间，知道某个元素的存储位置就可以计算其他元素的存储位置
特点：地址连续、一次存放、随机存取、类型相同。
线性表长可变，数组长度不可动态定义。

define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
typedef struct{
ElemType elem[LIST_INIT_SIZE];
int length; //当前长度
}SqList；

扩充
malloc函数：开辟m字节长度的地址空间
sizeof函数：计算长度
free函数：释放指正p所指变量的存储空间
顺序表的查找：
代码实现如下

int LocateElem(SqList,ElemTyoe e){
	for(i=0;i 
顺序表的插入：
 代码如下
 
Status ListInsert_Sq(SqList &L,ElemType e){
 if(i<1||i>L.length) retrun ERROR;
 if(L.length == MAXSIZE) return ERROR;
 for(j=L.length-1;j>=i-1;j--)
 	L.elem[i-1]=L.elem[j];
 L.elem[i-1]=e;
 L.length++;
 return OK;
}
 
顺序表的删除
 代码如下
 
Status ListDelete(SqList &L,int i){
 if(i<1||i>L.length) retrun ERROR;
 for(j=i;j<=L.length-1;j++)
 	L.elem[j-1]=L.elem[j];
 L.length--;
 return OK;
}