链表的基本操作

1、定义链表结点类型

链表的基本操作

单向链表的主要操作包括:建立链表、向链表中插入和删除结点、遍历链表等。下面通过一个简单实例简要介绍单向链表的基本操作。

【例1】使用链表存放多个商品的资料,每个商品包括:商品编号和商品价格。

1、定义链表结点类型

程序中如果要使用链表,首先要定义描述链表结点的结构体类型,下面给出本例中结点的结构体定义：

struct product

{

int id;//商品编号

double price;//商品价格

struct product *next;//指针域

};

typedef struct product NODE；//为结点起别名

2.建立链表

建立链表是指在程序运行过程中,从无到有地建立起链表的过程。即逐个为结点分配内空间,输入结点数据,并建立起结点之间的前后链接关系。

下面给出建立链表的函数 create的定义,链表中结点的排列是按照数据输入的先后顺序，即后输入的数据排在链表的末尾,链表的头指针以函数返回值形式得到

函数的源代码如下：

NODE *create()

{

NODE *head, *tail,*p; //head-头指针，tail-尾指针

int id;

double price;

head=NULL; //头指针置为NULL,表示链表是空表

printf("输入编号和价格(编号为0表示结束):");

scanf("% d% If", &id, &price);

while(id>0)

{

p=(NODE *)malloc( sizeof(NODE))；//分配一个结点的内存空间

//下面为结点成员赋值

p->id=id;

p->price=price;

p->next=NULL;

//下面if语句把新结点连接到链表的最后面

if(head==NULL)

{

head=p;//当链表为空时,新结点是第1个结点

}

else

{

tail->next=p;//链表不为空时,把新结点连接在原尾结点后面

}

tail=p; //tail指向新的尾结点

printf("输入编号和价格(编号为0表示结束):");

scanf("%d%lf",&id,&price);

}

return head;//返回值是链表的头指针

}

创建链表函数 create的说明:

(1)函数中定义了3个结点类型指针变量:head是链表的头指针;tail在链表建立过程中始终指向链表的末尾一个结点,增加的新结点直接链接到tail结点的后面即可;p指向链表创建过程中新增加的结点。

(2)函数的第6行把头指针head赋值为NULL,表示链表是空链表,即没有任何结点。

(3)创建链表时,每结点都要单独分配内存空间。函数第11行进行内存分配,循环每进行一次,就创建一个新结点。

(4)链表中第一个结点的创建与其他结点是不同的,直接让头指针head指向它即可(第19行),而其他结点需要链接到tail指针的后面(第23行)。

(5)循环中每次创建一个新结点并链接到链表尾部后，tail指向的结点就不再是尾结点，需要让tail指向新的尾结点(第25行)

(6)函数 create创建的链表返回给调用它的主调用函数时,只需要将头指针head作为函数的返回即可（第29行）。

(7)在main函数调用 create函数建立一个链表可以使用如下语句

NODE *head；//在main函数中定义头指针变量

head=create();//调用 create函数创建链表,并把链表的头指针赋值给head。

3.遍历链表

链表的遍历操作是指从链表的第1个结点开始,依次对链表中每一个结点进行一次访问，直到链表的结束为止。遍历链表使用循环结构实现,首先使指针p指向第1个结点,通过p对结点进行访问,访问完成后,使指针p指向下一结点。如此不断循环,直到链表结束(p为NULL)为止。

遍历操作中对结点的访问是一个通用概念,对结点的访问可以是:输出结点的数据域、修改结点数据域、对结点计数、对结点数据进行判断等。下面给出对链表进行输出和计数两种操作的函数。

输出链表所有结点的函数display的源代码如下：

void display( NODE *h)

{

NODE *p;

p=h;//p指向第1个结点

printf("-----------------------\n");

whilel(p!=NULL)//结束条件是p为NULL

{

printf("%10d, %10. 2f\n",p->id, p->price);

p=p->next;//使p指向下一个结点

}

printf("-----------------------\n");

}

输出链表函数 display几个关键地方:

(1)函数的参数h表示要输出的链表的头指针。

(2)指针p指向第1个结点,见代码第4行。

(3)判断链表是否结束的条件是p!=NULL,如果条件不成立,表示链表已经遍历完成。

(4)代码中第9行作用是使指针p指向它目前指向结点的下一个结点,该语句保证了循环是依次访问链表的所有结点,并能够到达链表末尾。

例如,main函数中已经建立一个头指针为head的链表,可以使用如下语句输出所有结点

display(head);//输出头指针head指向的链表

统计一个链表中结点的个数也是一种遍历操作,下面定义的函数 count的功能中统计个链表中共有多少个结点,函数的返回值是结点的个数。

int count( NODE *h)

{

NODE *p;

int n=0;

while(p!=NULL)

{

n++;

p=p->next;

}

return n;

}

main函数中使用如下语句可以得到头指针head指向的链表中结点个数:

int num=count(head);