文档文本内容
本节内容
单链表
建立
王道考研/CSKAOYAN.COM知识总览
如果给你很多个数据元素(ElemType),要把它们存到一个单链表里
边,咋 neng 呢?
本节探讨带头
Step 1:初始化一个单链表
结点的情况
Step 2:每次娶一个数据元素,插入到表尾/表头
王道考研/CSKAOYAN.COM尾插法建立单链表
L 头 NULL
王道考研/CSKAOYAN.COM尾插法建立单链表
尾插法建立单链表:
初始化单链表
设置变量 length 记录链表长度
While 循环 {
每次取一个数据元素 e;
ListInsert (L, length+1, e) 插到尾部;
length++;
}
每次都从头开始之后遍历,
时间复杂度为 O(n2)
L 头 10 16 27 NULL
设置一个
length=3
表尾指针 r
王道考研/CSKAOYAN.COM尾插法建立单链表
后插操作
L 头 10 16 27 NU40LL
设置一个
表尾指针 r
王道考研/CSKAOYAN.COM尾插法建立单链表
LinkList List_TailInsert(LinkList &L){ //正向建立单链表
int x; //设ElemType为整型
L=(LinkList)malloc(sizeof(LNode)); //建立头结点 初始化空表
LNode *s,*r=L; //r为表尾指针
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode *)malloc(sizeof(LNode)); O(n)
时间复杂度:
s->data=x; 在r结点之后插入元素 x
r->next=s;
r=s; //r指向新的表尾结点 永远保持 r 指向
最后一个结点
scanf("%d",&x);
}
r->next=NULL; //尾结点指针置空
return L;
}
如果不带头结点呢?
x 输入: 10 输入: 16 输入: 27 输入: 9999
L 头 10 16 27 NULL
r s
王道考研/CSKAOYAN.COM头插法建立单链表
对头结点的
后插操作
L 头 10 16 27 NULL
4101
头插法建立单链表:
初始化单链表
While 循环 {
每次取一个数据元素 e;
InsertNextNode (L, e);
}
王道考研/CSKAOYAN.COM头插法建立单链表
养成好习惯,只要是
初始化单链表,都先
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表
把头指针指向 NULL
LNode *s; 如果去掉这
int x; 一句呢?
L=(LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode)); //创建新结点
s->data=x;
s->next=L->next;
L->next=s; //将新结点插入表中,L为头指针
scanf("%d",&x);
} 重要应用!!!
return L; 链表的逆置
}
如果不带头结点呢?
x 输入: 10 输入: 16 输入: 27 输入: 9999
一定要动手鸭
L 头 27 16 10 NULL
王道考研/CSKAOYAN.COM知识回顾与重要考点
头插法、尾插法:核心就是初始化操作、指定结点的后插操作
注意设置一个指向
表尾结点的指针
头插法的重要应用:链表的逆置
动手试一试:给你一个 LinkList L,
如何逆置?
L 头 27 16 10 NULL
王道考研/CSKAOYAN.COM