我在论坛上看到有网友说,在C++学习过程中认为链表部分不是太好理解,在这我想写写我学习链表的一些体会。希望能对这些朋友有所帮助!如果大家有什么好的方法,也不妨拿出来让我们分享!
首先,要明白C++引入链表概念是为了什么,也就是说链表的作用是什么?其次,要弄清链表的本质;最后是链表的使用方法。那我先举个例子,如果建立一个有关学生的分数管理系统需要建立一个结构,如下:
- struct Student
- {
- char Name[20];
- long id;
- float score;
- }
如果要是学生的人数确定,只要声明一个这个结构的数组就OK了。可是如果人数是不确定的,那就需要用到链表了。链表之所以能解决这个问题,这就涉及到了链 表的本质问题——使用动态内存分配技术。其实现在的数据库系统的内部实现正是在动态分配技术基础上实现的。要把结构变成链表,只需在结构成员中加入一个自 身的指针成员(一会有解释)。到这里有一个问题是需要注意的:结构成员不能是自身结构的变量,但指针可以。为什么需要加入一个自身结构的指针,请看图。毕竟图形是非常直观的。
我们清晰的看到,每个结构成员在内存中的地址是不连续的,“链表”这个名字起的非常形象,就是把结构成员像链子一样,一环扣一环的串起来,以便于查询、删除和插入。能担此重任的只有指针!看下图:
一目了然,在结构中引入自身的结构指针成员,是为了存储下一个结构成员的地址。使它们串起来! 现在我们来看一个完整的例子(遍历链表也称查询链表),有一个概念要说一下——结点,在这个结构中,每个Student结构变量称为结点。
- #include <iostream.h>
-
- struct Student
- {
- long lId;
- float fScore;
- Student* pNext;
- };
-
- Student* pHead;
-
- Student* Create()
- {
- Student* pStart;
- Student* pEnd;
- pStart = new Student;
-
- cin >> pStart->lId >> pStart->fScore;
-
- pHead = NULL;
-
- pEnd = pStart;
- while(pStart->lId != 0)
- {
-
- if (pHead ==NULL)
- pHead = pStart;
- else
- pEnd->pNext = pStart;
- pEnd = pStart;
- pStart = new Student;
- cin >> pStart->lId >> pStart->fScore;
- }
-
- pEnd->pNext = NULL;
-
- delelte pStart;
- return (pHead);
- }
-
- void Print (Student* head)
- {
- cout << " List of the items\n";
- while (head)
- {
- cout << head->lId << "," << head -> fScore;
-
- pHead = pHead->pNext;
- }
- }
-
- void main()
- {
-
- Print(Create());
- }
删除链表结点
链表删除操作要保证不破坏链表的链接关系,这也是难点之所在——一个结点删除后,它的前一个结点的指针成员应指向它的后一结点,这就不会因为删除操作而使链接中断。关系如下图:
删除链首结点:
删除非链首结点:
下面的函数实现了链表结点的删除
- void Delete(Student* head, long number)
- {
- Student* p;
- if (!head)
- {
- cout << "This is the last node \n";
- return;
- if (pHead->lId == number)
- {
- p=head;
- head = pHead->pNext;
- delete p;
- cout << "the head of list have been deleted\n";
- return;
- }
-
-
-
-
-
-
- for (Student* pGuard = head; pGuard->pNext; pGuard = pGuard->pNext)
- {
-
- if (pGuard->pNext->lId == number)
- {
-
- p = pGuard->pNext;
-
- pGuard->pNext = p->pNext;
- delete p;
- cout << "have been deleted!\n";
- return;
- }
- }
- cout << "not found\n";
- }
/*在找到待删除结点时,pGuard指向待删除结点的前一个结点是重要的。否则,待删除结点的前一结点地址丢失,其pNext成员无法与待删除结点的后一结点链接。在数据结构中,通常称pGuard指针为“哨兵”。*/
在main() 主函数中的调用如下:
pHead = Create(); //这一步不可丢下,这是为了使pHead指向表头
Delete(pHead, fScore); //把number改成相应的成绩数
插入链表结点
同样,插入操作也不能破坏链接关系。应将插入结点的pNext成员指向它的后一个结点,然后将前一个结点的pNext成员指向新插入的结点,这样就得了新的链表。如图:
我们假设创建链表时,结点是按lId值由小到大排列的。
- void insert (Student* head, Student* stud)
- {
-
- if (head ==NULL)
- head = stud;
- stud.pNext = NULL;
- return;
- }
-
- if (head->lId > stud->lId)
- {
- stud.pNext = head;
- head = stud;
- return;
- }
-
-
- Student* pGuard = head;
- while (pGuard->pNext && pGuard->pNext->lId > stud->lId)
-
- pGuard = pGuard->pNext;
-
- stud->pNext = pGuard->pNext;
-
- pGuard->pNext = stud;
- }
到此为止,链表的控制已经叙述完毕。总之,其中的精髓之处是如何按排删除或插入结点的操作顺序。用一句白话说就是在操作之前想好下一步,给自己留一条后路 ——当你意识到下一步没办法走的时候,肯定是上一步没有作好准备工作。这只是我个人的一些感受,也不知合适与否,反正书上是不会这么写的!
如需转载请与作者联系
作者姓名: 快果(linchao14)
邮件地址: linchao14@xinhuanet.com
(快果(linchao14)) |