赞
踩
今天学习了链表,第一次接触,感觉很不适应,写此博客梳理巩固一下。
我感觉,链表其实就是结构体+指针的运用(个人理解)。操作起来比数组简单很多。
首先创建一个结构体:
- struct node
- {
- int data;
- struct node *next;
- };
什么是结点?
结点我这里是指包含一个数据和下一个结点地址的东西。结点1(数据,结点2地址)->结点2(数据,结点3地址)->……这就是结点。
现在尝试着回忆创建一个链表:
- struct node *head;
- head = NULL;
head指向链表的最开始,因为链表还没有建立,所以head为空,也可以理解为指向一个空结点。
现在我们创建第一个结点,并用临时指针p指向这个结点:
- struct node *p;
- p = (struct node*)malloc(sizeof(struct node));
使用mollac动态申请一个空间,用来存放结点,然后使用指针p指向他。
接下来,我们来设置这个新创建结点的所包含的内容(data和地址):
- scanf("%d",&a);
- p->data=a;
- p->next=NULL;
这里应该很好理解,将输入data。
然后要创建头指针,也就是进行一个判断,是否是第一个结点,作用是方便以后从头遍历整个链表:
- if(head == NULL) head=p;
- else q->next=p;
如果这是第一个创建的结点,那么头指针指向这个结点;如果这不是第一个创建的结点,那么将上一个结点的后继指针指向当前结点。
最后,将指针q也指向当前结点,因为,一会p将会指向新创建的结点:
q=p;
完整代码:
- #include<stdio.h>
- #include<stdlib.h>
- struct node
- {
- int data;
- struct node *next;
- };
- int main(){
- struct node *head,*p,*q,*t;
- int i,n,a;
- scanf("%d",&n);
- head = NULL;//头指针初始为空
- for(i=0;i<n;i++){
- scanf("%d",&a);
- //申请一个动态空间,用来存放结点,并临时指针p指向这个结点
- p = (struct node *)malloc(sizeof(struct node));
- p->data=a;
- p->next=NULL;
- if(head==NULL) head = p;//如果这是第一个创建的结点,就指向自己。
- else q->next=p; //如果不是,让上一个结点的后继指针指向当前结点。
- q=p;//指针q指向当前结点
- }
-
- t=head;
- while(t!=NULL){
- printf("%d ",t->data);
- t=t->next;//继续下一个结点
- }
-
- return 0;
- }
-
这样就达到了和数组同样的功能。
输入:
9
2 3 5 8 9 10 18 23 32
输出:
2 3 5 8 9 10 18 23 32
现在要进行进阶:在表中插入一个数。
2->3->5->8->9->……变化为2->3->5->6->8->9->……
所以,应该从头开始遍历,和输出一样。当指针p的下一个结点的值大于6的时候,将6插入中间:
- int flag;
- scanf("%d",flag);
- t=head;
- while(t!=NULL)
- {
- if(t->next==NULL||t->next->data > flag)
- {
- p = (struct node *)malloc(sizeof(struct node));
- p->data=flag;
- p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
- t->next=p;//当前结点的后继指针指向新增结点
- break;
- }
- t=t->next;//继续下一个结点
- }
flag就是想要添加的数。下面展示完整代码:
- #include<stdio.h>
- #include<stdlib.h>
- struct node
- {
- int data;
- struct node *next;
- };
- int main(){
- struct node *head,*p,*q,*t;
- int i,n,a;
- scanf("%d",&n);
- head = NULL;//头指针初始为空
- for(i=0;i<n;i++){
- scanf("%d",&a);
- //申请一个动态空间,用来存放结点,并临时指针p指向这个结点
- p = (struct node *)malloc(sizeof(struct node));
- p->data=a;
- p->next=NULL;
- if(head==NULL) head = p;//如果这是第一个创建的结点,就指向自己。
- else q->next=p; //如果不是,让上一个结点的后继指针指向当前结点。
- q=p;//指针q指向当前结点
- }
- //想要添加的数
- int flag;
- scanf("%d",flag);
- t=head;
- while(t!=NULL)
- {
- if(t->next==NULL||t->next->data > flag)
- {
- p = (struct node *)malloc(sizeof(struct node));
- p->data=flag;
- p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
- t->next=p;//当前结点的后继指针指向新增结点
- break;
- }
- t=t->next;//继续下一个结点
- }
- //输出链表中的所有数
- t=head;
- while(t!=NULL){
- printf("%d ",t->data);
- t=t->next;//继续下一个结点
- }
-
- return 0;
- }
输入:
5
1 6 7 8 9
输出:
1 2 3 7 8 9
这就是链表的基本应用。
为什么要使用链表?
链表可以根据使用情况来申请空间,而不是像数组一样需要定义大小。并且相比较于数组,链表可以方便的添加和删除数。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。