文档介绍：第21章数据结构
前面的章节已经对C语言的基本语法机作了介绍,但要写出好的程序,解决实际问题,还要了解一些数据组织方面的内容,即数据结构的相关知识,常见的数据结构包括链表、栈、队列、树、图和线性表等,本章主要从链表、栈和队列角度入手,介绍数据结构的一些基本知识。
链表
数组对应着一个连续存储的内存块,将同类型的元素一个个地排列起来,是组织数据的很好的手段,声明数组时需要告诉编译器数组的大小(即元素的个数),以便开辟足够大小的内存,但解决实际问题时,元素的个数常常是不确定的,此时该如何声明数组呢?如果指定的数组太小而实际数据太多,无法满足要求,可如果指定的数组太大而实际却用不了那么多,又会造成内存浪费。
在这种背景下,有人提出用链表来存储数据,像用线串珠子一样,元素不一定需要连续的内存空间,只要在需要存储数据时,再申请存储空间(动态申请内存空间或栈分配)即可,并采用指针将数据一个一个链接起来,称为链表,如所示:
链表的结构
链表元素常称为链表结点,每一个结点是一个结构体,包含两个域:数据域和指针域。数据域保存数据,指针域连接该结点到下一个结点。结点类型可以相同,也可不同,当结点类型相同时,称为同质链表,否则,称为异质链表,在实际应用中,常用的是同质链表。
每一个结点占用一块存储单元,结点的增减都十分容易,当要在链表中增加一个结点时,可动态地为该结点分配一个存储单元;当要在链表中删除一个结点时,也可释放该结点的存储单元。
就所示的链表来说,如果将该链表比作一串珠子,头结点HEAD就是绳头,找珠子就要从头结点开始,头结点指向的结点A是链表的第1个数据结点,也就是第1颗珠子,A中不仅有数据域,还包含指向下一结点B的指针,依此类推,顺藤摸瓜,即可遍历整个链表。
头结点的数据域可以不包含任何信息,也可以存储诸如元素个数等附加信息,或者干脆用一个指针代替头结点,如果链表为空,头结点的指针域为空。
创建链表并遍历输出
链表的建立一般是指先建立一个空链表,而后一个个地将元素插在队尾,来看如下的示例:
链表的插入
顾名思义,插入即是往链表中加入一个新结点,使链表变长。受链表插入位置的影响,将一个元素插入链表有以下几种情况:
链表结点的删除
删除几乎可以看成是结点插入的逆操作,将到换一个顺序即可:
如果删除的是第1个数据结点,即从到,则应使head指针指向E1,同时释放掉Einsert申请的动态内存。
如果删除的是中间结点,即从到,则只需让E2->next指向Einsert->next,同时,释放掉Einsert占据的动态内存。
如果删除的尾结点,即从到,只需让E1->next为NULL,同时释放掉Einsert占据的动态内存。
链表的逆置
所谓链表的逆置,是指“头变尾,尾变头”,将原来的“ABCD……”变成“……DCBA”,先从单链表模型来看,如:
链表的销毁
在链表使用完毕后,需将其销毁,回收所分配的内存。由于是整体销毁,实现起来比结点的删除简单,可以采取如下策略:每次删除第1个结点后面的结点,最后再删除头结点,这样即可实现整个链表的销毁。
仅仅删除第1个结点并不意味着整个链表被删除掉了,链表是一个结点一个结点建立起来的,所以,销毁它也必须一个结点一个结点地删除才行。
编写链表销毁的函数如下:
void freeAll(STU* head)
{
STU* p=NULL,*q=NULL;
p=head;
while(p->next!=NULL)
{
q=p->next;
p->next=q->next; /*删除结点*/
free(q); /*释放内存*/
}
free(head); /*释放第1个结点所占内存*/
}
综合实例
前面对链表常用的操作进行了介绍,根据这些机理可以编写其他操作的代码,此处不再赘述,为了对链表的使用有个整体的认识,我们利用前面编写的函数形成一个完整的源程序,以检验效果:
循环链表
和前面介绍的单链表一样,循环链表是一种链式的存储结构,不同的是,循环链表的最后一个结点的指针是指向该循环链表第1个结点的,也就是说,头尾相加构成一个环形结构。循环链表和单链表的操作基本一致,有两点需要特别注意:
(1)新建循环链表时,必须使最后一个结点的指针指向第1个结点,而不是像单链表一样对其赋值为NULL。
(2)在判断是否达到链表尾部时,是判断该结点指针域是否指向第1个结点,而不是像单链表一样判断其是否为NULL。