在这一部分(数据结构(Chapter Two -01)—线性表及顺序表-CSDN博客)里面,我们知道线性表包括顺序表和链表结构。前面写了顺序表的基本操作,那这部分就写一写线性表叭!
链表特点:不需要使用地址连续的存储单元,即不要求逻辑上相邻的元素在物理地址上也相邻。
优点:插入和删除不需要移动元素(顺序表的缺点是需要移动)
缺点:不可以随机存取。需要额外的存放地址的指针域,浪费空间。
我们可以发现顺序表和链表的缺点和优点似乎恰好相反。来一个单链表结点的结构:
我们可以看到指针域是存放下一个结点的地址的,每一个结点(除第一个)的读取都需要靠前一个结点读取,这就导致了缺点(不能随机读取)。
头指针:可用于标识一个单链表,如单链表L,头指针为NULL时表示一个空表。
头结点:为了操作上面的方便,通常会为单链表附加一个头结点。头结点数据域可以不设置任何信息,也可以记录表长等信息。
头结点和头指针的区别:不管带不带头结点,头指针都始终指向链表的第一个结点,而头结点是带头结点的链表中的第一个结点,结点内通常不存储信息。
举个栗子,下图为带了头结点的单链表:
引入头结点两个优点:
1、由于第一个数据结点的位置被存放头结点的指针域中,因此在链表的第一个位置上的操作和在表的其他位置上的操作一致,无需特殊处理。
2、无论链表是否为空,其头指针都指向头结点的非空指针(空表中头结点的指针域为空,但是可以存在)。
注意了:空表可以存在头结点(不存在的时候就是NULL),但是空表长度为0,因此线性表长度是不包括头结点的。
由以上我们可以写出单链表的结点描述,代码如下:
typedef struct LNode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode* next; //指针域
}LNode,*LinkList;
//头插法构建单链表
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
LNode *s;
int x;
L = (LinkList) malloc(sizeof(LNode));//创建头结点,L指向的那片区域是头结点
L->next = NULL; //初始为空链表
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode));//创建新结点
s->data=x;
s->next=L->next;
L->next=s; //将新结点插入表中,L为头指针
scanf("%d",&x);
}
return L;
}
//尾插法构建单链表
LinkList List_TailInsert(LinkList &L){//正向建立单链表
int x;
L = (LinkList)malloc(sizeof(LNode));
LNode *s,*r =L; //r表示尾指针
scanf("%d",&x); //输入结点的值
while(x!=9999){ //输入9999表示结束
s=(LNode*)malloc(sizeof(LNode));
s->data =x;
r->next =s;
r=s; //r指向新的表尾结点
scanf("%d",&x);
}
r->next = NULL; //尾结点指针设置为空
return L;
}
其中头插法和尾插法的区别:插入的位置不同,头插法每一次都是在头结点的下一个插入,尾插法就是每一次插入的是链表的末端。
原文地址:https://blog.csdn.net/weixin_45987528/article/details/135783281
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_63273.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!