⭐⭐⭐⭐⭐⭐
🎊专栏【数据结构】
🍔喜欢的诗句：更喜岷山千里雪 三军过后尽开颜。
🎆音乐分享【勋章】
大一同学小吉，欢迎并且感谢大家指出我的问题🥰
⭐⭐⭐⭐⭐⭐
目录
⭐定义：
⭐ 理解：
⭐存储方式 ：
⭐顺序存储的优缺点：
优点：
缺点：
⭐链式存储的优缺点：
优点：
缺点：
⭐基本操作
✨顺序存储
🍔存储结构
🎈添加数字建立表
🎈输出线性表里面的数
🎈插入数字
🎈删除数字
🎈取出数字
🎈置空
😎完整代码1
🚌小细节：什么时候使用引用，什么时候不使用引用
😎完整代码2
✨链式存储
🍔存储结构
⭐易错：首元结点VS头节点VS头指针
⭐链表增加头结点的好处
🎈便于首元结点的处理
🎈便于空表和非空表的统一处理
🎈初始化
🎈尾插法建立单链表
🎈头插法建立单链表
🎈插入
🎈删除
🎈取出元素
🎈输出链表
😎完整代码1
😎完整代码2
⭐定义：
线性表（List）:零个或多个数据元素的有限序列
⭐ 理解：
线性表，顾名思义，就是具有像线一样性质的表，元素之间是有顺序的，若元素存在多个，那么第一个元素没有前驱元素，最后一个元素没有后继元素，其他元素既有前驱元素又有后继元素
⭐存储方式 ：
线性存储
链式存储
⭐顺序存储的优缺点：
优点：
1.表中数据元素可以根据序号 随机存取
2. 存储密度大，存储密度为1（存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比）
缺点：
1.做插入、删除操作时，要移动大量元素，因此对很长的线性表操作效率低，插入和删除操作不方便；
2.要预先分配存储空间，预先估计过大，会导致存储空间浪费，估计过小，会造成数据溢出。
⭐链式存储的优缺点：
优点：
1.做插入、删除操作时，不用移动大量元素，相比线性存储方式方便；
2.不用预先分配存储空间。
缺点：
1.表中数据元素不可随机存取
2.存储密度小，存储密度小于1
⭐基本操作
✨顺序存储
🍔存储结构
#define maxsize 100
typedef struct{
ElemType *elem;//由于这里不知道线性表的具体长度，所以这里就用了指针
//可以是elem[maxsize]
int length;
}SqList;
其中ElemType可以改为其他的数据类型 ，比如
typedef int ElemType
length表示当前线性表中数据元素的个数，注意数组里面的下标是从0开始的，那么
a1->elem[0]; //注意，用数组表示
a2->elem[1];
a3->elem[2] ;
an->elem[length-1];
🎈初始化
🚕分配空间，建立空表，使空表长度为0
使用引用初始化
int InitList(SqList &L)
{
L.elem=new ElemType[maxsize];
if(!L.elem) return -1; //内存分配失败
L.length=0; //空表长度为0
return 1;
}
使用指针初始化
int InitList(SqList* L)
{
L->elem = new int[100];
if (!L->elem) exit(overflow);
L->length = 0;
return OK;
}
🎈添加数字建立表
🚕向空表里面添加数字，从而建立线性表
使用引用
void InputList(SqList& L, int num)
{
L.elem[k++] = num;
L.length++;
}
使用指针
void InputList(SqList* L, int num)
{
L->elem[k++] = num;
L->length++;
}
🎈输出线性表里面的数
🚕输出线性表里面的数
使用引用
void OutputList(SqList& L)
{
for (int i = 1; i length; i++)
{
cout = place; i--)
{
L->elem[i + 1] = L->elem[i];
}
L->elem[place] = num;
}
🎈删除数字
🚕与插入数字类似，删除数字采用的是向前覆盖数字
使用引用
void ListDelete(SqList& L, int place)
{
for (int i = place; i elem[i - 1] = L->elem[i];
}
L->length--;
}
🎈取出数字
🚕就是给出这个数字的位置，就是想当于给出了这个数字在数组里面的位置，然后直接根据这个位置取值
int GetElem(SqList L, int i, int& e)//int *e
{
if ((i L.length)) return -1;
e = L.elem[i]; //*e=L.elem[i];
return 1;
}
int GetElem(SqList *L, int i, int& e)
{
if ((i L->length)) return -1;
e = L->elem[i];
return 1;
}
🎈置空
🚕直接L.length=0就可以了
（如果要返回线性表的长度，直接L.length即可）
😎完整代码1
#include
using namespace std;
#define OK 1
#define overflow -1
int k=1;
typedef struct{
int *elem;
int length;
}SqList;
int InitList(SqList &L)
{
L.elem=new int[100];
if(!L.elem) exit(overflow);
L.length=0;
return OK;
}
//3
void InputList(SqList &L,int n)
{
L.elem[k++]=n;
L.length++;
}
//4
void OutputList(SqList &L)
{
for(int i=1;i 
