（详解）数据结构线性表的创建——前插法、后插法

大家好，欢迎来到IT知识分享网。

目录

引言

一、结点的定义

二、前插法（头插法）创建单链表

1.步骤：

2.算法描述：

3.时间复杂度：

三、后插法（尾插法）创建单链表

1.步骤：

2.算法描述：

3.时间复杂度：

引言

        前插法与后插法属于链表的创建方法。

        链表的创建与顺序表不同，链表是一种动态结构。整个可用存储空间可以为多个 链表共同享用，每个链表不需要像顺序表那样提前分配好占用空间，而是由系统按照需求即使生成。

        即从空表的初始化后，依次建立各元素结点，并逐个插入链表。

一、结点的定义

        在创建链表之前，需要自定义结点类型。

typedef struct { char data; struct node* next; }LinkList;

二、前插法（头插法）创建单链表

        前插法（头插法）是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

1.步骤：

1. 创建一个只有头结点的空链表。
2. 根据带创建链表包括的元素个数n，循环n次执行以下操作：

• 生成一个新结点*p；
• 输入元素值赋给新结点*p的数据域；
• 将新结点*p插入到头结点之后。

2.算法描述：

 void CreateList_H(LinkList $L, int n) { //逆位序输入n个元素的值，建立代表头结点的单链表L L = new LNode; L->next = NULL; //先建立一个带头结点的空链表 for (i = 0; i < n; i++) { p = new LNode; //生成新结点*P cin >> p->data; //输入元素值赋给新结点*p的数据域 p->next = L->next; L->next = p; //将新结点*p插入到头结点之后 } }

3.时间复杂度：

        前插法的时间复杂度为O(n)。

三、后插法（尾插法）创建单链表

        后插法是通过将新结点逐个插入链表的尾部来创建链表。与前插法一致，每次申请一个新结点，读入相应的数据元素值。除此之外，必须增加一个尾指针，使其始终指向当前链表的尾结点。

1.步骤：

1. 创建一个只有头结点的空链表。
2. 尾指针r初始化，指向头节点。
3. 根据创建链表包括的元素个数n，循环n次执行以下操作：

• 生成一个新结点*p；
• 输入元素值赋给新结点*p的数据域；
• 将新结点*p插入尾结点*r之后；
• 尾指针r指向新的尾结点*p。

2.算法描述：

void CreateList_R(LinkList $L, int n) { //正位序输入n个元素的值，建立代表头结点的单链表L L = new LNode; L->next = NULL; r = L; for (i = 0; i < n; i++) { p = new LNode; //生成新结点*P cin >> p->data; //输入元素值赋给新结点*p的数据域 p->next = NULL; r->next = p; //将新结点*p插入到尾结点*r之后 r = p; //r指向新的尾结点*p } }

3.时间复杂度：

        后插法的时间复杂度为O(n)。