再上一篇:8.5 new与delete
上一篇:8.6 引用和其它类型的指针
主页
下一篇:8.8 类型定义
再下一篇:第九章 类和对象
文章列表

8.7 简单链表及其应用

《VC++程序设计基础》,讲述C++语言的语法和标准库,以及Visual C++ 函数库和MFC类库的使用,并附相关代码示例。

8.7.1 链表概述

在本节中,简单地介绍利用结构体和指针来实现链表处理的方法。所谓链表是指将若干个同类型的结构体类型数据(每一个结构体类型的数据称为一个结点)按一定的原则连接起来。每一个结点应包含二部分数据:一是描述某一实体所需要的实际数据。如描述一个人的通讯录,包括的数据可以是:姓名,工作单位,单位的电话号码,住宅的的电话号码和邮编等。二是结构类型的指针,它指向下一个结点。将结点连接起来的的原则是:前一个结点通过指针指向下一个结点,如图8.11所示。

head

张 三 李 四 王 五

89 100 89

0

图 8.11 链表结构示意图

图8.11给出的简单链表中,每一个结点包含的数据有二个:姓名和成绩。每一个结点的指针域用来存放下一个结点的地址。head 称为链首指针,或简称为头指针。它指向链表中的第一个结点。每一个结点可以是用运算符new分配的动态内存空间,各个结点在内存中可以是不连续的。若要查找链表中的某一个结点(如姓名为“李 四”的结点),必须从head所指向的第一个结点开始,逐个结点查找。首先看第一个结点上的姓名是否为“李 四”;若是,则已找到。若不是,则通过第一个结点中的指针域,找到下一个结点(第二个结点),看其姓名是否为“李 四”。若不是,再通过这一结点的指针域,找到下一个结点,依此类推,直到找到满足条件的结点,或找到链表上的最后一个结点为止。

描述上述结点的数据结构为:

struct node {

char name[20];

int score;

node *next;

};

其中next为指向这种结构体类型的指针,它存放指向下一个结点的地址。通常,程序设计者并不要具体知道下一个结点的地址值,而只要将用new为下一个结点分配的动态内存空间的起始地址存放在next中。

8.7.2 建立链表

对链表进行的基本操作包括:建立链表,把一个结点插入链表,从链表中查找到某一个结点,删除链表中的某一个结点,输出链表中的所有结点数据等。我们结合例子来说明这些操作的实现方法。为了把注意力集中在链表的操作上,设每一个结点上只包含一个整数。

例8.31 链表的基本操作。

本例所做工作包括:建立一条无序链表;输出该链表上各结点的数据;删除链表上的某一个结点;再输出链表上的数据;释放无序链表各结点占用的内存空间;建立一条排序链表(升序排序);输出链表上的数据;最后释放链表上各结点占用的内存空间。

链表上结点的数据结构为:

struct node {

int data;

node *next;

};

1、建立一条无序链表

建立无序链表的函数如下:

node *Create( )

{

node *p1, *p2, *head;

int a;

head = 0; //A

cout<<"产生一条无序链表,请输入数据,以-1结束:";

cin >> a;

while ( a != -1 ) {

p1 = new node; //B

p1->data = a; //C

if ( head == 0 ) {

head = p1 ; p2 = p1 ; //D

}

else {

p2->next = p1; p2 = p1; //E

}

cin >> a;

}

p2->next = 0; //F

return (head);

}

A行,首先将链表首指针head置为0,表示当前为空链表。当输入的整数为-1 时,表示建立链表的过程结束。建立一条无序链表的过程可分为:第一步是输入一个整数,建立一个新结点;第二步将这个结点插入链表尾。重复这二步,直到输入的整数为-1时为止。B行和C行完成建立一个新结点的工作,并使p1指这个新结点。把一个新结点插入链表尾时,有二种情况:一种情况是,当前为空链表,即head的值为0。这时,应使head和p2指向这个新结点,D行完成这一工作。插入过程如图8.12所示。第二种情况是,把新结点插入链表尾。因p2总是指向链表尾结点,只要先使p2所指向结点的next指针指向要插入的结点,再使p2指向链表尾结点,E行完成此工作。注意,E行中的二个语句的顺序不可交换。插入过程如图8.13所示。

Head head

0 200

200

p1 p1 p2

(a)插入之前 (b)插入之后

图8.12 插入链首结点

...... ......

p2 500 p2 500

p1 1000 p1

1000

(a)插入之前 (b)插入之后

图8.13 链尾增加一个结点

当输入数据为-1时,结束while()循环,执行F行,将p2所指向的链表尾结点的next赋为0。注意,链表上最后一个结点的next赋为0,是必不可少的,它表示链表的结束。

2、输出链表上各个结点的值

这是一个历遍链表上的各个结点问题。实现这一功能的函数如下:void Print(const node *head)

{

const node *p;

p = head ;

cout <<"链表上各结点的数据为:\n";

while ( p != NULL ) {

cout <data << '\t'; //A

p= p->next; //B

}

cout <<"\n";

}

首先使指针变量p指向链表首结点。A行输出p所指向结点上的数据。然后,使p指向下一个结点(B行)。重复执行A、B二行,直到链表尾为止。

3、删除链表上具有指定值的一个结点

删除链表上某一个结点的动作为:首先是找到要删除的结点,其次是删除已找到的结点。实现这功能的函数如下:

node *Delete_one_node(node *head,int num)

{

node *p1,*p2;

if ( head == NULL ) { //A

cout <<"链表为空,无结点可删!\n";

return ( NULL );

}

if ( head->data == num ){

p1=head; //B

head = head->next; //C

delete p1; //D

cout <<"删除了一个结点!\n";

}

else {

p2=p1 = head;

while (p2->data != num && p2->next != NULL ) { //G

p1 = p2 ; //E

p2 = p2->next; //F

}

if ( p2->data == num ) {

p1->next = p2->next; //H

delete p2; //I

cout <<"删除了一个结点!\n";

}

else cout <

}

return ( head );

}

设置二个指针p1和p2。查找时有三种情况:一是链表为空链表,这时无结点可删,A行完成这一功能。二是要删除的结点是链表的首结点。方法是,先使p1指向第一个结点(B行),使head指向第二个结点(C行),然后删除p1所指向的结点(D行)。三是要删的结点不是链表首结点,使p1指向前一个结点(E行),使p2指向后一个结点(F行),并判断p2所指向的结点是否为要查找的结点。G 行的循环语句完成链表上的查找工作。循环的结束条件有二个:一是 p2所指向的结点已是要找的结点;二是p2已指向链表上的最后一个结点,且该结点不是要找的结点。后者表明链表上没有要删的结点,J行指明这种情况。第一种结束G行的循环条件是要删除p2所指向的结点,首先要从链表上取下p2所指向的结点,H行完成这一功能,然后删除p2所指向的结点(I行)。

4、释放链表的结点空间

完成释放链表的结点空间的函数如下:

void deletechain(node *h)

{

node *p1;

while(h){ //A

p1=h; //B

h=h->next; //C

delete p1; //D

}

}

函数的参数h指向链表首指针。释放链表可归结为依次从链表上取下一个结点,释放该结点占用的空间,直到链表上无结点可取为止。B行和C行完成从链表取下一个结点,并使p1指向要删的结点,h指向下一个结点(作为新的链表),然后删除p1所指向的结点(D行)。重复这一过程(A行),直到链表上没有结点为止。

5、把一个结点插入链表

把一个结点插入链表时,仍保持链表上各个结点的升序关系。插入函数如下:node *Insert( node *head,node *p)

{

node *p1 , *p2;

if (head == 0 ) {

head = p; //A

p->next = 0; //B

return (head);

}

if ( head->data >= p->data ) { //C

p->next=head; //D

head=p; //E

return(head);

}

p2=p1 = head;

while ( p2->next && p2->data < p->data ) { //F

p1 = p2 ;

p2 = p2->next;

}

if ( p2->data < p->data ) {

p2->next = p; //G

p->next =0; //H

}

else {

p->next = p2; //I

p1->next = p; //J

}

return (head);

}

函数的第一个参数head指向链表的第一个结点,第二个参数p指向要插入的结点。第一种特殊情况是head的值为0,表明是空链表,使head指向这结点(A行),并使链表尾指针置为0(B行)。第二种特殊情况是,p所指向的结点插入链表首部(满足C行条件)。这时将head所指向的链表接在p所指向的结点之后(D行),并使head指向新的链表首部(E行)。第三种情况要从链表上找到插入位置,然后把新结点插入。F行的循环语句实现查找过程,这完全类同于删除一结点中的查找过程,不重复说明了。查找结束后分二种情况:首先是,当p2->data < p->data时,p2已指向链表上的最后一个结点,应将p所指向的结点插入链表尾。G行和H行完成这一功能。另一种情况是将p所指向的结点插入p1和p2所指向的结点之间。I行和J行完成这一功能。

6、建立一条有序链表

建立一条有序链表的函数如下:

node *Create_sort(void)

{

node *p1,*head =0; //A

int a;

cout<<"产生一条排序链表,请输入数据,以-1结束:";

cin >> a;

while ( a != -1 ) {

p1 = new node ; //B

p1->data = a; //C

head = Insert ( head , p1); //D

cin >> a;

}

return (head);

}

建立一条有序链表的过程可分为二步:首先建立一个新结点,B行和C行完成建立新结点。其次,将新结点插入链表中,D行完成这一功能。A行将head置初值为0是必要的,表明开始时链表为空。

完成链表处理的完整的程序如下:

#include

struct node {

int data;

node *next;

};

node *Create(void ) //产生一条无序链表

{

node *p1, *p2 ,*head;

int a;

head = 0;

cout<<"产生一条无序链表,请输入数据,以-1结束:";

cin >> a;

while ( a != -1 ) {

p1 = new node;

p1->data = a;

if ( head == 0 ) { //插入链表的首部

head = p1 ; p2 = p1 ;

}

else { //插入链表尾

p2->next = p1; p2 = p1;

}

cin >> a;

}

p2->next = 0;

return (head);

}

void Print(const node *head) //输出链表上各结点的数据

{

const node *p;

p = head ;

cout <<"链表上各结点的数据为:\n";

while ( p != 0 ) {

cout <data << '\t';

p= p->next;

}

cout <<"\n";

}

node *Delete_one_node(node *head,int num) //删除一个结点{

node *p1,*p2;

if ( head == 0 ) {

cout <<"链表为空,无结点可删!\n";

return ( 0 );

}

if ( head->data == num ){ //删除链表首结点

p1=head;

head = head->next;

delete p1;

cout <<"删除了一个结点!\n";

}

else {

p1 = head;

p2 = head->next;

while ( p2->data != num && p2->next!= 0 ){ //找到要删的结点

p1 = p2 ;

p2 = p2->next;

}

if ( p2->data == num ) { //删除已找到的结点

p1->next = p2->next;

delete p2;

cout <<"删除了一个结点!\n";

}

else cout <

}

return ( head );

}

node *Insert( node *head,node *p) //将一个结点插入链表中

{

node *p1 , *p2;

if (head == 0 ) { //空链表,插入链表首部

head = p;

p->next = 0;

return (head);

}

if ( head->data >= p->data ) { //非空链表,插入链表首部

p->next=head;

head=p;

return(head);

}

p2=p1 = head;

while ( p2->next && p2->data < p->data ) { //找到要插入位置

p1 = p2 ;

p2 = p2->next;

}

if ( p2->data < p->data ) { //插入链表尾

p2->next = p;

p->next =0;

}

else { //插入p1和p2所指向的结点之间

p->next = p2;

p1->next = p;

}

return (head);

}

node *Create_sort(void) //产生一条有序链表

{

node *p1,*head =0;

int a;

cout<<"产生一条排序链表,请输入数据,以-1结束:";

cin >> a;

while ( a != -1 ) {

p1 = new node ; //产生一个新结点

p1->data = a;

head = Insert ( head , p1); //将新结点插入链表中

cin >> a;

}

return (head);

}

void deletechain(node *h) //释放链表上各结点占用的内存空间{

node *p1;

while(h){

p1=h;

h=h->next;

delete p1;

}

}

void main(void )

{

node *head ;

int num;

head = Create(); //产生一条无序链表

Print(head); //输出链表上的各结点值

cout <<"输入要删除结点上的整数:\n";

cin >> num;

head = Delete_one_node(head, num); //删除链表上具有指定值的结点

Print(head); //输出链表上的各结点值

deletechain(head); //释放链表上各结点占用的内存空间

head = Create_sort(); //产生一条有序链表

Print(head); //输出链表上的各结点值

deletechain(head); //释放链表上各结点占用的内存空间}

最后,要说明的是:对于初学者来说, 要掌握指针变量的正确使用必须通过多编程多上机实践才行。使用指针变量来处理数据时, 可以提高计算速度, 使得程序的通用性更好。但用得不好, 在程序执行期间可能会产生一些意想不到的错误。