数据结构之链表
C++中常见的数据结构-CSDN博客
目录
一、链表的定义
二、链表的创建
三、链表的遍历
四、链表的插入
五、链表的删除
六、总结
链表是计算机科学中常见的一种数据结构,c/c++语言中也有着丰富的链表操作函数库。本文将从链表的定义、创建、遍历、插入、删除等多个方面进行详细讲解,带你从入门到精通。
一、链表的定义
链表是一种动态数据结构,由节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。链表分为单向链表、双向链表和循环链表等多种类型。使用链表可以灵活地插入、删除元素,不需要预先分配固定大小的内存空间。
二、链表的创建
在c/c++中,可以使用结构体来定义一个节点,并用指针来表示节点之间的关系,从而实现链表。下面是一个单向链表的创建示例代码:
#include <stdio.h> #include <stdlib.h> struct node{int data; //数据域struct node *next;//指针域 }; int main() {struct node *head,*p,*q;int n,i;printf("请输入节点个数n:");scanf("%d",&n);head = NULL;for (i=1; i <=n;i++){p =(struct node *)malloc(sizeof(struct node));if (p== NULL){printf("内存分配失败!");exit(1);}printf("请输入第%d个节点的值:",i);scanf("%d",&p->data);p->next = NULL;if (head == NULL){head =p;}else {q->next =p;}q =p;}printf("链表各节点的值为:");p = head;while (p!= NULL){printf("%d",p->data);p =p->next;}return 0; }
三、链表的遍历
链表遍历是指按照一定的顺序依次访问链表中的每一个节点。下面是一个单向链表的遍历示例代码:
cstruct node *p; p = head; while (p!= NULL) {//访问节点pp =p->next; }
四、链表的插入
链表插入是指在链表中任意位置插入一个新节点。下面是一个单向链表的插入示例代码:
void insert(struct node *head, int i, int x) {struct node *p,*q,*new_node;new_node =(struct node *)malloc(sizeof(struct node));if (new_node == NULL){printf("内存分配失败!");exit(1);}new_node->data =x;p = head;for (int j =1; j <=i;j++){q =p;p =p->next;}new_node->next =p;q->next = new_node; }
五、链表的删除
链表删除是指在链表中删除一个节点。下面是一个单向链表的删除示例代码:
void delete(struct node *head, int i) {struct node *p,*q;p = head;for (int j =1; j <=i;j++){q =p;p =p->next;}q->next =p->next;free(p); }
六、总结
本文从链表的定义、创建、遍历、插入、删除等多个方面进行了详细讲解,希望能够帮助大家更好地理解和掌握c/c++语言中的链表操作。在实际应用中,需要根据具体情况选择合适的链表类型和操作方式,才能发挥链表的优势。