尾插法建立单链表的原理
时间: 2023-08-15 08:37:04 浏览: 69
尾插法是一种常用的单链表建立方法,其原理是从链表的尾部开始插入新节点,最终形成一个完整的单链表。
具体实现过程如下:
1. 定义一个链表头指针和一个尾指针,初始时它们都指向NULL。
2. 依次读入数据,创建一个新节点,并将新节点的数据域赋值为当前读入的数据。
3. 将新节点的指针域赋值为NULL。
4. 如果链表为空,则将头指针和尾指针都指向新节点。
5. 如果链表不为空,则将尾指针的指针域指向新节点,并将尾指针指向新节点。
6. 重复步骤2-5,直到所有数据都被读入并创建成新节点。
7. 最终得到的链表就是一个按照读入顺序建立的单链表。
尾插法的优点是可以保证插入新节点的时间复杂度为O(1),而不会像头插法一样需要遍历整个链表来定位插入位置,从而提高了链表的建立效率。
相关问题
尾插法建立单链表 c
尾插法是一种常用的方法来建立单链表。在尾插法建立单链表时,我们首先创建一个头节点,并将其指针指向NULL。然后,依次读入元素并插入链表的尾部,直到读到结束符号为止。具体步骤如下所示:
1. 创建头节点,并将其指针指向NULL。
2. 创建一个指针p,使其指向头节点。
3. 读入第一个元素,创建一个新节点s,并将元素赋值给s的data域。
4. 将p的指针指向新节点s,并将p指向s。
5. 重复步骤3和步骤4,直到读到结束符号为止。
6. 将p的指针指向NULL,表示链表的结尾。
下面是尾插法建立单链表的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
LinkList Create() {
LinkList L, p, s;
ElemType e;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
p = L;
scanf("%d", &e);
while (e != -1) {
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
p->next = s;
p = p->next;
scanf("%d", &e);
}
p->next = NULL;
return L;
}
void print(LinkList L) {
LinkList p;
p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
LinkList L = Create();
print(L);
return 0;
}
```
头插法尾插法建立单链表
单链表是一种常见的数据结构,它由若干个结点组成,每个结点包含一个数据域和一个指向下一个结点的指针域。单链表的建立有两种方法:头插法和尾插法。
头插法建立单链表的过程是:首先创建一个头结点,然后依次读入数据,每读入一个数据就创建一个新结点,并将新结点插入到头结点之后,最后返回头结点的指针即可。
尾插法建立单链表的过程是:首先创建一个头结点,然后依次读入数据,每读入一个数据就创建一个新结点,并将新结点插入到链表的尾部,最后返回头结点的指针即可。
头插法和尾插法的区别在于插入新结点的位置不同,头插法是插入到头结点之后,而尾插法是插入到链表的尾部。头插法和尾插法都可以建立单链表,但是它们的时间复杂度不同,头插法的时间复杂度为O(n),而尾插法的时间复杂度为O(1)。
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)