我们至少可以通过两种结构存储数据。
数组:数组是一个固定长度的存储相同数据类型的数据结构,数组中的元素被存储在一段连续的内存空间中。
优点:存取速度快。
缺点:需要一个连续的很大的内存;
插入和删除元素效率很低。
链表:链表是一种物理存储结构上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
优点:插入和删除元素效率高;
不需要一个连续很大的内存。
缺点:查找某位置元素效率低。
二.链式存储结构——链表链表是一种常见的采用动态存储分配方式的数据结构。在链表中,每一个元素包含两个部分:数据部分(数据域)和指针部分(指针域)。数据部分用来存放元素所包含的数据,指针部分用来指向下一个元素。最后一个元素的指针指向NULL,表指向的地址为空。
链表结构示意图1、链表相关专有名词
首节点:存放第一个有效数据的节点。
尾节点:存放最后一个有效数据的节点。
头结点:头结点是首节点前的节点,头结点并不存放数据;
头结点的数据类型和首节点的数据类型一模一样;
头结点的设置是为了方便链表的使用。
头指针:存放头结点地址的指针变量。
2、确定一个链表需要一个参数
头指针 (可以通过头指针推算出链表其他所有的参数)
3、链表的分类
- 单链表
- 双向链表
- 循环链表
- 非循环链表
<1>单链表
在链表中,每个结点只有一个指针,所有的结点都是单线联系,除末尾结点指针为外,每个结点都指向下一个结点,一环扣一环形成一条线性链,称此链表为单向链表或简称为单链表。
单链表结构示意图
<2>双向链表
双向链表中的每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。所以,在这里一个节点包括了三部分,前驱、数据、后驱。
双向链表示意图
<3>循环链表
循环链表是一种头尾相接的链表。表中的最后一个结点的指针域指向头结点,整个链表形成环状结构。循环链表来源于单链表,所以结构与单链表相似。
<4> 非循环链表
三、链表的初始化、插入、删除、创建以及查询1、链表的初始化(以单链表为例)
单链表的初始化就是创建一个头结点,头结点的数据域可以不使用,头结点的指针域为空,表示空单链表。
linkList InitList() { linkList head; head=(Node*)malloc(sizeof(Node)); head->next=NULL; return head; }
2、链表的插入
链表的插入 *** 作可以在链表头指针位置进行插入,也可以在链表中某个结点的位置进行插入,或者在链表的最后面添加结点。虽然有三种插入 *** 作,但是 *** 作的思想是一样的。
单链表插入 *** 作
void Insert(linkList head,int i) { Node *p=head,*s; int j=0; while(jnext; j++; } if(p) { s=(Node*)malloc(sizeof(Node)); //定义s指向新分配的空间 scanf("%s",s->name); scanf("%d",&s->number); s->next=p->next; //新结点指向原来的第i个结点 p->next=s; //新结点成为新链表的第i个结点 } }
在该程序中,首先从链表的头结点开始,找到第i-1个结点的地址p。如果该结点存在,则可以在第i-1个结点后插入第i个结点。为插入的新结点分配内,然后向新结点输入数据。插入时,首先将新结点的指针s指向原来的第i个结点(s->next=p->next),然后将第i-1个结点指向新结点(p->next=s),这样就完成了插入结点的 *** 作。
3.链表的删除
Delete函数中有两个参数,其中head表示链表的头指针,pos表示要删除结点在链表中的位置。定义整型变量j来控制循环的次数,然后定义指针变量p表示该结点之前的结点。接着利用循环找到要删掉结点之前的结点p,如果该结点存在并且待删除结点存在,则将指针变量q指向待删除结点(q=p->next),再连接要删除结点两边的结点(p->next=q->next),并使用free函数将q指向的内存空间进行释放。
单链表删除 *** 作
void Delete(linkList head,int pos) { Node *p=head,*q; int j=0; while(jnext; j++; } if(p==NULL || p->next==NULL) //第pos个结点不存在 printf("the pos is ERROR!"); else { q=p->next; //q指向第pos个结点 p->next=q->next; //连接删除结点两边的结点 free(q); //释放要删除结点的内存空间 } }
<4>链表的创建
创建链表前需要先创建结构体作为节点和头指针:
typedef struct Node //typedef方法函数可以对于struct Node进行重命名 { char name[20]; int number; struct Node *next; }LNode,*linkList; //定义一个结构体指针方便后续的 *** 作
<5>链表的查询
Search函数有两个参数,其中head表示链表的头指针,name表示要查找的值。定义指针变量p,使其从首元结点开始到链表结束。如果某结点的成员和给定不等,则继续查找下一个结点(p=p->next)。如果查找成功,则返回结点的地址值;若查找失败,则打印提示信息,并返回NULL。
Node *Search(linkList head,char name[]) //在单链表head中找到值为name的结点 { Node *p=head->next; while(p) { if(strcmp(p->name,name)!=0) p=p->next; else break; //查找成功 } if(p==NULL) printf("没有找到值为%s的结点!",name); return p; }
这里对单链表的插入等 *** 作都是以创建一个链表表示班级,其中结点表示学生。
四、小结链表的 *** 作很多以上仅为部分简单 *** 作,其他内容可通过查找资料等进行学习。希望大家共同学习进步,不足之处望指出。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)