顺序创建链表--尾插法

• 问题引入
• 问题分析
• 链表整体结构
• 元素入链
• 元素出链
• 代码实现

问题引入

在数据结构中，线性表示一种很重要的线性结构，线性表可分为多种类型，常见的如：顺序表，链表等。

问题分析

想要搞明白“链表”，首先你要明白两个问题：

1. 什么是线性表
   一个线性表(Linear list),是 n个数据元素的有限序列。
2. 链表的特点是什么

1：与顺序表相比不可随机存取，只能按顺序查找进行操作
2：链表也即采用链式存储结构，用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的也可以是不连续的），存储单元就是我们所说的“结点”，每个结点都可以记录下一结点的地址，因此系统分配存储空间时，存储单元可以不连续，但是仍然需要找到结点位置在哪里。
3：链式结构中，每个结点包含两个域：数据域，指针域，数据域用于存储数据，指针域用于记录下一存储单元结点的地址，其中指针域存储的信息称为“指针”或“链”，线性表采用链式结构存储数据，“链表”也因此得名。
4：表中元素个数叫表长，元素个数可以有对个，也可以为0个，某个元素的上一个元素叫直接前驱元素，下一个元素叫直接后继元素。

链表整体结构

链式结构主要是蒋一个一个存储信息的结点通过结点前驱记录结点的地址信息并连接在一起，形成一种链式结构，其本质上又是一个线性表，指针域记录的值称为“链”，因此称为“链表”。
🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀🚀
对于链表而言，我们每次插入数据时必须要指定一个指针记录当前链表的元素末位置，开头位置我们通过头结点记录，这样我们才能清楚的知道当前线性表的长度以及位置。

元素入链

👩👩👩例如：要在 链表中插入新结点：结点P。
🎅🎅🎅分析：首先需要分配一个“新结点的存储空间”，其次将数据输入结点p的数据域中，然后将节点q和节点p进行连接。

🧡🧡🧡

1. 先让节点p的指针域指向下一节点位置(p->next = q->next)
2. 再让节点q的指针域指向节点p
   通过上述两步操作，就完成了数据插入。

元素出链

👩👩👩
例如： 在链队列中删除数据为22节点
如果明白了元素入链表的过程，那么元素的出链表与入链表是相似的，我们也是通过设置一个辅助结点用于指向要删除的元素位置，之后在进行删除。

1. p指向待删除节点（p=q->next）
2. 然后 p的前驱节点的 指针域 保存 p的指针域(q->next = p->next)，链表断裂
3. 利用库函数 delete(q) ，释放空间，表长减1

代码实现

// 导入头文件
#include
#include
using namespace std;// 创建结点结构
typedef struct Lnode{int data; //数据域struct Lnode *next;  // 指针域}Lnode,*Linklist;// 顺序创建链表
void createList(Linklist &head)
{Linklist p,q; // 辅助变量// 为头节点head 分配存储空间head = (Linklist)malloc(sizeof(Lnode));// 头节点置为空head->next =NULL;q = head ; // q指向 headp =(Linklist)malloc(sizeof(Lnode));// 为节点p分配存储空间cin>>p->data; // 输入节点数据，循环创建pwhile(p->data != -10) {p->next = q->next;q->next = p;q=p;p =(Linklist)malloc(sizeof(Lnode));cin >> p->data;}}// 输出链表元素
void printList(Linklist list){Linklist p; // 辅助变量p = list->next;while(p!=NULL){cout << p->data << " ";p = p->next;}cout << endl;
}int main(){Linklist lst; // 定义链表cout<< "创建链表lst，请输入元素，以-10结束："<< endl;createList(lst);cout << endl;cout << "输出lst验证："<< endl;printList(lst);cout<< endl;
}