c++链表（一）
分享内容
- 链表的概念
- 建立链表
- 链表的基本操作
虚拟内存空间
操作系统为每个正在运行的进程分配独立的虚拟内存空间。这种机制的优点包括:
隔离性:一个进程无法直接访问另一个进程的内存空间,从而提高了系统的安全性和稳定性。
简化编程模型:每个进程都感觉自己拥有整个计算机的内存资源。
链表的概念
数组的概念
· 在内存中,数组是一块连续的区域。
· 数组大小固定,不利于扩展(当数组定义的空间不够时要重新定义数组)。
链表
新的数据结构一链表:
●链表(linked list)是一种线性数据结构。
● 链表是由多个独立的“节点”组成的,节点之间通过“指针”连接。整体构成一个链表!
● 每个节点都包含两项数据:节点的“数据”和指向下一节点的“指针”。
● 链表的首个节点被称为“头节点”,最后一个节点被称为“尾节点”。
● 尾节点指向的是“空”。
这种链表也称为单向链表,因为节点只能访问后续节点。
链表的内存特点
链表的概念-练习
1)链表的节点由几部分组成()?A
A、两部分,一部分存放节点值,另一部分存放指针
B、只有一部分,存放节点值
C、只有一部分,存放指针
D、两部分,一部分存放节点值,另一部分存放节点所占内存
插入节点
插入节点:在链表中插入节点非常容易。
例如,在节点1、2之间插入“节点4”。分两步完成:
①“节点4”指向“节点2”
②“节点1”指向“节点4”
删除节点
删除节点:在链表中删除节点也非常方便
例如,删除下面链表中的“节点4”。只需要1步:把“节点1”的指针指向“节点2”
【注意】尽管在删除操作完成后“节点4”仍然指向“节点2”,但实际上遍历此链表已经
无法访问到“节点4”,这意味着“节点4”已经不再属于该链表了。
查找节点
**查找节点:**在链表中查找节点的效率较低。
例如,在下面链表中访问(查找)数据部分=7的节点。需要从头节点出发,逐个向后遍历,直至找到目标节点。
同样,访问第i个节点,也只能从头节点出发,逐个找下一个并记数,没有办法像数组一
样直接用下标访问。
链表(总结)
① 链表(Linked List)是一种线性数据结构,其中每个节点存储一个数据和一个指向
下一个节点的指针。
②链表的优点
● 插入和删除操作无需移动其他元素,时间复杂度为O(1)。
● 链表不需要预先分配固定大小的内存空间,链表的大小可以根据需要动态扩展或缩减。
③ 链表的缺点
● 访问任意节点需要从头节点开始遍历,时间复杂度为O(n)。
● 链表节点除了包含值,还需额外保存一个指针。因此在相同数据量下,链表比数组占用更多的内存空间。
链表的概念-练习
2)以下关于链表的描述,哪一项是错误的?D
A、链表是一种线性数据结构,其中每个节点存储一个数据元素和一个指向下一个节
点的指针。
B、链表的优点是插入和删除操作的时间复杂度为O(1),无需移动其他元素。
C、链表的缺点是访问任意节点的时间复杂度为O(n),因为需要从头节点开始遍历。
D、链表必须预先分配固定大小的内存空间。
链表的典型应用
链表通常用于实现栈、队列、哈希表和图等数据结构。
· 当插入和删除操作都在链表的一端进行时,它表现的特性为先进后出,对应栈;
·当插入操作在链表的一端进行,删除操作在链表的另一端进行,它表现的特性为先进先出,对应队列。
建立链表
一般把链表节点定义为结构体
①定义节点
struct node{
int data;// 数据
node *next;// 指向下一个节点的指针
};
② 声明、初始化节点变量
【注意】a、b、c三个变量的内存地址不一定连续
node a = {1, NULL} ;
node b = {2, NULL} ;
node c = {3, NULL} ;
· 在大括号里为节点的每个成员指定初始值
· NULL表示指针为空(指向空地址)
③构建节点之间的链接关系
a.next = &b;
b.next = &c;
&:取地址运算符
(注意】结构体变量访问成员时用.符号
得到一个有三个节点的链表:
通常将头节点当作链表的代称,比如以上链表可记作链表a。
验证一下,节点是否真的链接成功?
从头节点开始遍历:
node *head = &a;
while (head != NULL) {//循环终止条件
cout << head->data << " ";
head = head->next;
}
cout << endl;
【注意】结构体指针变量访问成员时用->符号
插入节点
插入节点分:插入成为头节点和其他情况(插入在某节点后)
①把P节点插入链表,成为新的头节点。
【思考】如果P和head都是指针,代码怎么写?
② 在节点n0后面插入一个新节点P
插入节点-练习
3)假设已有一个链表。请你创建一个新的数值为4的节点,调用insert函数,把新节点插入到节点b后面。
/*在链表的节点 n0 之后插入节点 P */
void insert (node *n0, node *P) {
P->next = n0->next;
n0->next = P;
}
第一步,创建新节点
node d = {4, NULL} ;
第二步,调用insert函数
insert (&b, &d);
4)假设一个链表,head指向头节点。哪个代码可以实现把新节点P,插入成为新的头节点?D
A, head.next = p;
B. p.next = head;
C. head= p;
D. p->next = head; head = p;
删除节点
删除节点分:删除头节点、删除中间节点、删除尾节点
①删除头节点
步骤:
node *n1 = n0->next;
if (n1 != NULL) {
node *n2 = n1->next;
n0->next =n2;
}
实现删除n0后面的节点的函数remove()
/*删除链表的节点 n0 之后的首个节点 */
void remove (node *n0) {
node *n1 = n0->next;
if (n1 != NULL) {
node *n2 = n1->next;
n0->next = n2;
}
}
时间复杂度O(1)
查找节点
第一种情况:查找链表中数值等于value的节点
/*访问链表中数值为 value 的节点,head 是头节点 */
node*access (node *head, int value) {
while ( head != NULL && head->data != value)
head = head->next;
return head;
}
找到,则返回找到的节点指针,否则返回NULL。
第二种情况:查找链表中数值等于value的节点的前导节点
/*访问链表中数值为 value 的节点的前导节点 */
node* access (node *head, int value) {
node *pre = NULL;
while ( head != NULL&& head->data != value) {
pre = head;
head = head->next;
}
return pre;
}
找到,则返回找到的节点指针,否则返回NULL。
第三种情况:查找链表中索引为index的节点
/*访问链表中索引为 index 的节点,head 是头节点 */
node* access (node *head, int index) {
for (int i = 0; i < index; i++) {
if (head == NULL)
return NULL;
head = head->next;
}
return head;
}
找到,则返回非NULL的节点指针,否则返回NULL。
时间复杂度O(n)
链表操作
创建一个链表,按顺序存储数字1~5。然后:
1、创建节点P,存储数字9。
2、在链表中寻找数字m(1≤m≤5),在数字m的节点后面插入节点P。
3、删除头节点。
4、依次输出链表中的数据。
【输入描述】输入m(1≤m≤5)。
【输出描述】链表中的数据(空格隔开)
【输入样例】3
输出样例】 2 3 9 4 5
实现链表功能
①定义节点(结构体)
②实现链表的基本函数:insert、remove、access
主程序流程
①声明、初始化节点变量,存储数字1~5
② 按顺序建立链表连接
③创建节点P,存储数字9。
④在链表中寻找数字m(1≤m≤5),在数字m的节点后面插入节点P。
⑤ 删除头节点。
⑥ 依次输出链表中的数据
创建一个链表,按顺序存储数字1~5。
1.定义节点
struct node{
int data;// 数据
node *next;// 指向下一个节点的指针
}
2.实现insert()函数:在节点n0后面插入一个新节点P
void insert (node *n0, node *P) {
P->next = n0->next;
n0->next = P;
}
实现remove()函数:删除链表的节点n0之后的首个节点
void remove (node *n0) {
node *n1 = n0->next;
if (n1 != NULL) {
node *n2 = n1->next;
n0->next = n2;
}
}
实现 access()函数:查找链表中数值等于value的节点
node*access (node *head, int value) {
while ( head != NULL && head->data != value)
head = head->next;
return head;
}
创建一个链表,按顺序存储数字1~5
1 声明、初始化节点变量
2 按顺序建立链表连接
node n1 = {1, NULL} ;
node n2 = {2, NULL} ;
node n3 = {3, NULL} ;
node n4 = {4, NULL} ;
node n5 = {5, NULL} ;
n1.next =&n2;
n2.next =&n3;
n3.next = &n4;
n4.next = &n5;
完整代码
#include<iostream>
using namespace std;
struct node{
int data;// 数据
node *next;// 指针
/*在链表的节点 n0 之后插入节点 P*/
void insert (node *n0, node *P) {
P->next = n0->next;
n0->next = P;
}
/* 删除链表的节点 n0 之后的首个节点*/
void remove (node *n0) {
node *n1 = n0->next;
if(n1 != NULL) {// n0 -> n1 -> n2
node *n2 = n1->next;
n0->next = n2;
}
}
/*访问链表中数值为 value 的节点,head 是头节点 */
node* access (node *head, int value) {
while ( head != NULL && head->data != value)
head = head->next;
return head;
}
int main() {
// 创建节点
node n1 = {1, NULL} ;
node n2 = {2, NULL} ;
node n3 = {3, NULL} ;
node n4 = {4, NULL} ;
node n5 = {5, NULL} ;
// 建立连接 n1->n2->n3->n4->n5
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;
n4.next = &n5;
node *head= &n1;//指向头节点
int m;
cin >> m;
//1、创建结点P,存储数字9。
node P = {9,NULL} ;
//2、在链表中寻找数字m(1≤m≤5),在数字m的后面插入结点P。
node *mNode = access (head,m) ;
insert (mNode, &P) ;
// 3、删除头节点
head = head->next;
// 4、依次输出链表中的数据。
node *temp= head;// 从头节点开始
while( temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
return 0;
}
本次课程的知识点
-
链表的概念
-
链表和数组的对比
-
建立链表的步骤
-
链表的操作:插入节点、删除节点、访问节点
1、以下关于链表的描述,哪一项是错误的?D
A、链表是一种线性数据结构,其中每个节点存储一个数据元素和一个指向下一
个节点的指针。
B、链表的优点是插入和删除操作的时间复杂度为O(1),无需移动其他元素。
C、链表的缺点是访问任意节点的时间复杂度为O(n),因为需要从头节点开始
遍历。
D、链表必须预先分配固定大小的内存空间。
字母链表
创建一个链表,按顺序存储字母A’~‘E’。从第一个节点依次输出链表中的
数据。
【输入】无
【输出】ABCDE
#include<iostream>
using namespace std;
struct node{
char data;// 数据
node *next;// 指针
}
int main(){
// 创建节点
node n1 = {'A', NULL} ;
node n2 = {'B', NULL} ;
node n3 = {'C', NULL} ;
node n4 = {'D', NULL} ;
node n5 = {'E', NULL} ;
// 建立连接 n1->n2->n3->n4->n5
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;
n4.next = &n5;
node *head= &n1;// 指向头节点
while ( head != NULL) {
cout << head->data;
head = head->next;
}
cout << endl;
return 0;
}
更多推荐
4
0- 0
已为社区贡献18条内容
所有评论(0)