四 单链表(1)
尘随风落
金融类国企IT民工
概述
单链表是链式存储的线性表,单链表为线性表中的每一个数据单元开辟一块空间,每块空间在物理位置上并不连续,每块空间中都有一个指针域用来存储下一块空间的位置,这样每一块空间在逻辑上便有了联系(逻辑上线性相连,每一块空间里都有下一个空间的地址)。
如下图所示:
整理一下:
头结点(head)的相关问题
每一个单链表都有一个头指针,头指针始终指向单链表的第一个空间,若有头结点则指向头结点,没有头结点指向第一个结点。
通常情况下,单链表都有一个头结点,这个结点并不存储数据(数据域实际可以使用,但通常不使用),但其指针域指向第一个结点所在的位置。
使用头结点之后,链表非空与空的两种情况下,无须进行特殊情况处理,因为头指针必定不为空。
在不实使用头结点的情况下,链表为空表时,头指针L为NULL。
单链表结点结构体的定义
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
data是数据域,用来存储数据的。
next是指针域,用来存放下一个空间的地址,next是一个结构体指针类型的变量,只能存放LNode类型结构体的地址。
LinkList是结构体LNode类型的指针。
每一个结点占用一块空间,每一块空间物理上不连续,每一个结点使用next指针域指向下一结点的位置。
图片:
单链表的创建
1.头插法建立单链表
LinkList CreatList1(LinkList &L){
LNode *s;int x;
L = (LinkList)malloc(sizeof(LNode));
L -> next = NULL;
scanf("%d",&x);
while(x != 9999){
s = (Node*)malloc(sizeof(Node));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d",&x);
}
return L;
}
第一步,s->next = L->next; 将头结点之后的东西转接到新结点后面。
第二步, L->next = s; 将新结点接到头结点后面,成为第一个结点。
*** 第二步的时候头结点的指针域改变,指向a2的链会断开。
2.尾插法建立单链表
LinkList CreatList2(LinkList &L){
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s,*r = L;
scanf("%d",&x);
while(x != 9999){
s = (Node*)malloc(sizeof(Node));
s->data = x;
r->next = s;
r = s;
scanf("%d",&x);
}
r -> next = NULL;
return L;
}
第一步,s = (Node*)malloc(sizeof(Node));s->data = x;开辟一个新的节点;
第二步,r->next = s;将新的结点接到最后一个结点后面。其中 指针 R 始终指向单链表的最后一个结点,每次插入一个新的结点,新结点的地址S最后要赋值给R,所以R每次都指向最后一个结点。
3.建立单链表的时间复杂度
- 两种建表方式的时间复杂度都为 O(n) 。
编辑于 2017-08-02 11:44