C++实现单向链表操作:插入、删除与创建

4星 · 超过85%的资源 需积分: 4 4 下载量 161 浏览量 更新于2024-10-21 收藏 16KB TXT 举报
"这篇文章主要介绍了如何使用C++实现单向链表的各种操作,包括链表的创建、元素的插入和删除。" 在计算机科学中,链表是一种基础的数据结构,它由一系列节点(也称为元素)组成,每个节点包含数据以及指向下一个节点的引用。在单向链表中,每个节点只有一个指向下一个节点的指针,而没有指向前一个节点的指针,这与双向链表不同。链表相比于数组,提供了更灵活的内存管理,但访问效率较低,因为无法通过索引直接访问。 本文提供的代码展示了如何用C++实现单向链表的基本功能。首先,定义了一个名为`NODE`的结构体,用于存储链表节点,包含两个成员:`data`用于存储数据,`next`是一个指向下一个节点的指针。 接着,定义了三个创建链表的函数: 1. `creat1(lklist&L)`:这是采用引用传递的方式创建链表,通过不断读取用户输入的整数(直到输入值大于等于100时停止),创建新节点并将其插入到链表中,直到链表长度达到100。 2. `creat1_(lklistL)`:这个函数也是创建链表,但它返回了创建后的链表头指针。其内部逻辑与`creat1()`相同,但采用了值传递的方式。 3. `creat1__(lklist*L)`:这个函数同样接收链表头指针的引用,创建链表的过程与前两者一致,但在创建过程中,直接对传入的引用进行操作,更新链表头。 此外,虽然在给定的代码片段中未展示,但通常链表操作还包括插入和删除元素的功能。插入元素可能是在链表的特定位置(如头部、尾部或中间),而删除元素则需要找到目标节点并调整前后节点的链接关系。这些功能可以通过遍历链表来实现。 例如,插入元素的函数`insert(lklist&L, int pos, datatype value)`可以在链表的指定位置插入一个新节点,删除元素的函数`deleteNode(lklist&L, int value)`可以删除具有特定值的节点。 在实际应用中,链表常用于实现各种数据结构,如栈、队列和哈希表,以及在算法中解决各种问题,如排序和搜索。链表的动态特性使其在处理数据变化或需要高效插入和删除操作的场景中非常有用。

LinkList InitRing(int n, LinkList R) //尾插入法建立单循环链表函数 { ListNode *p, *q; int I; R=q=(LinkNode *)malloc(sizeof(LinkNode)); for(i=1;i<n;i++){ p=(LinkNode *)malloc(sizeof(LinkNode)); q->data=i; q->next=p; q=p; } p->data=n; p->next=R; R=p; return R; } LinkList DeleteDeath(int n, int k, LinkList R) //生者与死者的选择 { int i, j; ListNode *p, *q; p=R; for(i=1; i<n/2; i++){ //删除一半结点 for(j=1; j<k-1; j++) //沿链前进k-1步 p=p->next; q=p->next; p->next=q->next; printf(“%4d”, q->data); free(q); } R=p; return R; } void OutRing(int n, LinkList R){ //输出所有生者 int i; LinkNode *p; p=R; for(i=1;i<=n/2; i++, p=p->next){ printf(“%4d”, p->data) } } 有了上述算法分析和设计之后,实现就比较简单了。首先要定义一个链表结构类型,然后编写一个主函数调用上面已定义好的函数即可。主函数的源程序如下: #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node * next; }ListNode; typedef ListNode * LinkList; void main(){ LinkList R; int n,k; LinkList InitRing(int n, LinkList R); LinkList DeleteDeath(int n, int k, LinkList R); void OutRing(int n, LinkList R); printf(“总人数n. 报数上限k=”); scanf(“%d%d”,&n, &k); R=InitRing(n, R); R=DeleteDeath(n, k, R); OutRing(n, R); } 5 运行结果 编译运行上述程序,提示:总人数n. 报数上限k= 输入30和9后并“回车”可得出如下结果: 9 18 27 6 16 26 7 19 30 12 24 8 22 5 23 21 25 28 29 1 2 3 4 10 11 13 14 15 17 20

2023-06-02 上传