文章教程

全国计算机等级考试二级C语言11.4链表

8/22/2020 10:24:52 PM 人评论 次浏览

11.4 链表

考点4 链表

真考链接

考点4属于重点理解、重点掌握内容。在选择题中的考核概率为60%。操作题中常常考查链表的建立、插入和删除。在操作题中的考核概率为25%。

链表是一种常见的重要的数据结构,它是动态地进行存储单元分配的一种结构。图11.1所示是一种简单的链表。

图11.1 链表示意图

从图11.1所示的链表示意图可以看出,链表中的各元素在内存中不一定是连续存放的。要找链表中某一元素,必须先找到上一个元素,根据该元素提供的下一元素的地址才能找到下一个元素。所以,如果没有头指针(head),则整个链表便无法访问。另外,这种链表的数据结构,必须利用指针变量才能实现。即一个节点中应包含一个指针变量,用它存放下一节点的地址。当然也可以不通过指针变量,用其他方式也可以构建简单链表,请参考有关数据结构的教材。

下面通过一个例子来说明如何建立和输出一个简单链表。

#include <string.h>

#include <stdio.h>

struct node

{ int data;

struct node *next;

};

typedef struct node NODETYPE;

main()

{ NODETYPE s1,s2,s3,*begin,*p;

s1.data=100;/*给变量中的data域赋值*/

s2.data=200;

s3.data=300;

begin=&s1;

s1.next=&s2; /*使s1的域next指向s2*/

s2.next=&s3;

s3.next=NULL;

p=begin;/*移动p,使之依次指向s1、s2、s3,输出它们data域中的值*/

while(p)

{ printf("% d",p->data);

p=p->next;/* p顺序后移 */

printf("\n");

main()函数中定义的变量s1、s2、s3都是结构体变量,它们都含有data和next两个成员。变量begin和p是指向NODETYPE结构体类型的指针变量,它们与结构体变量s1、s2、s3中的成员变量next类型相同。执行赋值语句后,begin中存放s1变量的地址,变量s1的成员s1.next中存放变量s2的地址……最后一个变量s3的成员s3.next置成NULL,从而把同一类型的结构体变量s1、s2、s3“链接”到一起,形成“链表”。

在此例中,链接到一起的每个节点(结构体变量s1、s2、s3)都是通过定义,由系统在内存中开辟了固定的存储单元(不一定连续)。在程序执行的过程中,不可能人为地再产生新的存储单元,也不可能人为地使已开辟的存储单元消失。从这一角度出发,可称这种链表为“静态链表”。在实际中,使用更广泛的是一种“动态链表”。

小提示

但链表最后一个节点的指针域不再存放地址时,就置成NULL值,标志着链表的结束,链表的每个节点只有一个指针域,每个指针域存放下一个节点的地址。

每一个链表都用一个“头指针”变量来指向链表的开始,称为head指针。在head指针中存放了链表第一个节点的地址。

真题精选

下列给定程序中,函数fun()的功能是:计算一个带头节点的单向链表中各节点的数据域中数值之和,结果作为函数值返回。

请在标号处填入正确的内容,使程序得出正确的结果。

注意:部分源程序给出如下。不得增行或删行,也不得更改程序的结构。

试题程序

#include <stdio.h>

#include <stdlib.h>

#define N 8

typedef struct list

{ int data;

struct list *next;

}SLIST;

SLIST *creatlist(int *);

void outlist(SLIST *);

int fun(SLIST *h)

{ SLIST *p;int s=0;

p=h->next;

while(p)

{ s+ = p->【1】;

p=p->【2】;

return s;

main()

{ SLIST *head;

int a[N] ={12,87,45,32,91,16,20,48};

head=creatlist(a);outlist(head);

printf("\nsum=% d\n",fun(【3】));

SLIST *creatlist(int a[])

{ SLIST *h,*p,*q;int i;

h = p =(SLIST *)malloc(sizeof (SLIST));

for(i=0;i<N;i++)

{ q =(SLIST *)malloc(sizeof (SLIST));

q->data=a[i];p->next=q;p=q;

p->next=NULL;

return h;

void outlist(SLIST *h)

{ SLIST * p;

p=h->next;

if(p==NULL)

printf("The list is NULL!\n");

else

{ printf("\nHead ");

do

{ printf("->% d",p->data);

p=p->next;

while(p!=NULL);

printf("->End\n");

【答案】【1】 data 【2】 next 【3】 head

【解析】本题考查:链表数据结构,节点的表示方法;掌握链表数据结构的基本思想

本题考查的是链表的数据结构,需利用指针变量才能实现,一个节点中应包含一个指针变量,用来存放下一个节点的地址。

建立单向链表的一般步骤是:建立头指针→建立第一个节点→头指针指向第一个节点→建立第二个节点→第一个节点的指针指向第二个节点→……→最后一个节点的指针指向NULL。

标号【1】:变量s用来累加各节点的数据域,因此该处应为data。

标号【2】:每次循环结束时,指针p指向下一个节点,即p=p->next;。

标号【3】:由被调用函数的形参列表可知,此处应为指针类型变量,因为要对链表的数据域求和,所以将链表的头指针传给被调用函数。

考点5 建立单向链表

真考链接

考点5难度适中,属于需重点掌握的内容。在选择题中的考核概率为10%。操作题中对此知识点的考查常在程序填空题中出现,考核概率为15%。

单向链表中,每个节点应该由两个成员组成:一个是数据成员;另一个是指向自身结构的指针类型成员。

节点的类型定义如下:

structslist

{ intdata;

structslist*next;

};

typedefstructslistSLIST;

(1)建立单向链表的主要操作步骤如下。

①读取数据。

②生成新节点。

③将数据存入节点的成员变量中。

④将新节点插入到链表中。重复上述操作直至输入结束。

(2)顺序访问链表中各节点的数据域。

(3)在单向链表中插入节点。在单向链表中插入节点,首先要确定插入的位置。当插入节点插在指针所指的节点之前,称为“前插”,当插入节点插在指针所指的节点之后,称为“后插”。

当进行“前插”操作时,需要3个工作指针(假设为s1、s2和s3)。用s1来指向新开辟的节点;用s2指向插入的位置;用s3指向s2的前趋节点(由于是单向链表,没有指针s3,就无法通过s2去指向它所指的前趋节点)。

(4)删除单向链表中的节点。为了删除单向链表中的某个节点,首先要找到待删节点的前趋节点,然后将此前趋节点的指针域去指向待删节点的后续节点,最后释放被删节点所占存储空间即可。

真题精选

【例1】以下函数creat()用来建立一个带头节点的单向链表,新产生的节点总是插在链表的末尾,节点数据域中的数值从键盘输入,以字符“?”作为输入结束标识。单向链表的头指针作为函数值返回。请填空。

试题程序

#include <stdio.h>

struct list

{ char data;

struct list *next;

};

struct list * creat()

{ struct list *h,*p,*q;

char ch;

h=______malloc(sizeof(______));

p=q=h;

ch=getchar();

while(ch!= '? ')

{ p=______malloc(sizeof(______));

p->data=ch;

q->next=p;

q=p;

ch=getchar();

p->next= ' \0';

return______;

【答案】(structlist*) structlist (structlist*) structlis th

【解析】前4个空处要求填入的内容是相同的,都是为了开辟一个链表节点的动态存储单元。由说明语句可知,节点的类型为structlist,因此在第一空处和第三空处应填指针强制类型转换(structlist*),在第二空处和第四空处应填节点的类型名structlist。函数的最后应当把所建链表的头指针作为函数值返回,而且函数的类型也是structlist*要求返回一个地址,在函数中,链表的头节点放在h中,所以在第五空处应填h。

【例2】下列给定程序中已建立了一个带头节点的单向链表,在main()函数中将多次调用fun()函数,每调用一次,输出链表尾部节点中的数据,并释放该节点,使链表缩短。

请在标号处填入正确的内容,使程序得出正确的结果。

注意:部分源程序给出如下。不得增行或删行,也不得更改程序的结构。

试题程序

#include <stdio.h>

#include <stdlib.h>

#define N 8

typedef struct list

{ int data;

struct list *next;

}SLIST;

void fun(SLIST *p)

{ SLIST *t,*s;

t=p->next;s=p;

while(t->next!= NULL)

{ s=t;

t=t->【1】;

printf("% d ",【2】);

s->next=NULL;

free(【3】);

SLIST *creatlist(int *a)

{ SLIST *h,*p,*q;int i;

h = p =(SLIST *)malloc(sizeof (SLIST));

for(i=0;i<N;i++)

{ q =(SLIST *)malloc(sizeof (SLIST));

q->data=a[i];p->next=q;p=q;

}p->next=NULL;

return h;

void outlist(SLIST *h)

{ SLIST *p;

p=h->next;

if(p==NULL)

printf("\nThe list is NULL!\n");

else

{ printf("\nHead");

do {printf("->% d",p->data);

p=p->next;}while(p!=NULL);

printf("->End\n");

main()

{ SLIST *head;

int a[N] ={11,12,15,18,19,22,25,29};

head=creatlist(a);

printf("\nOutput from head:\n");

outlist(head);

printf("\nOutput from tail:\n");

while(head->next!= NULL){

fun(head);

printf("\n\n");

printf("\nOutput from head again:\

n");

outlist(head);

【答案】【1】 next 【2】 t->data 【3】 t

【解析】本题考查:malloc函数、free函数、链表数据结构、节点的表示方法,掌握链表数据结构的基本思想;释放内存空间函数free。

标号【1】:因为是链表操作,所以要使t逐一往后移动,语句为t=t->next;。

标号【2】:输出链表节点的数据域,即t->data。

标号【3】:使用free函数将t所指向的内存空间释放。释放内存空间函数free的调用形式为:free(void*p);。

功能:释放p所指向的一块内存空间,p是一个任意类型的指针变量,它指向被释放区域的首地址。被释放区应该是由malloc或calloc函数所分配的区域。

考点6 顺序访问链表中各节点的数据域

真考链接

考点6难度偏大,属于需重点理解的内容。在选择题中的考核概率为10%。操作题对此知识点的考查常在程序修改题中出现,考核概率为15%。

所谓“访问”,可以理解为取各节点的数据域中的值进行各种运算,修改各节点的数据域中的值等一系列的操作。

输出单向链表各节点数据域中内容的算法比较简单,只需利用一个工作指针(p),从头到尾依次指向链表中的每个节点,当指针指向某个节点时,就输出该节点数据域中的内容,直到遇到链表结束标识为止。如果是空链表,就只输出提示信息并返回调用函数。

函数如下:

void printlist(NODETYPE *head)

{ NODETYPE *p;

p=head->next;    /*指向头节点后的第一个节点*/

if(p== '\0')    /*链表为空时*/

printf("Linklist is null\n");

else    /*链表不为空时*/

{ printf("head");

do

{ printf("->% d",p->data);  /*输出当前节点数据域中的值*/

p=p->next;    /*move指向下一个节点*/

}while(p! = '\0');    /*未到链表尾,继续循环下去*/

printf("->end\n");

真题精选

下列给定程序中,函数fun()的功能是:在带头节点的单向链表中,查找数据域中值为ch的节点。找到后通过函数值返回该节点在链表中所处的顺序号;若不存在值为ch的节点,函数返回0值。

请在标号处填入正确的内容,使程序得出正确的结果。

注意:部分源程序给出如下。不得增行或删行,也不得更改程序的结构。

试题程序

#include <stdio.h>

#include <stdlib.h>

#define N 8

typedef struct list

{ int data;

struct list *next;

}SLIST;

SLIST *creatlist(char *);

void outlist(SLIST *);

int fun(SLIST *h,char ch)

{ SLIST *p;int n=0;

p=h->next;

while(p!=【1】)

{ n++;

if(p->data==ch)return【2】;

else p=p->next;

return 0;

m ain()

{ SLIST *head;int k;char ch;

char a[N] ={'m', 'p', 'g', 'a', 'w', 'x', 'r', 'd'};

head=creatlist(a);

outlist(head);

printf("Enter a letter:");

scanf("% c",&ch);

k=fun(【3】);

if(k ==0) printf("\nNot found!\n");

else

printf("The sequence number is:%d\n",k);

SLIST *creatlist(char *a)

{ SLIST *h,*p,*q; int i;

h = p =(SLIST *)malloc(sizeof (SLIST));

for(i=0;i<N;i++)

{ q =(SLIST *)malloc(sizeof (SLIST));

q->data=a[i];p->next=q;p=q;

p->next=0;

return h;

void outlist(SLIST *h)

{ SLIST *p;

p=h->next;

if(p==NULL)

printf("\nThe list is NULL!\n");

else

{ printf("\nHead");

do

{ printf("->% c",

p->data);

p=p->next;

}while(p!=NULL);

printf("->End\n");

【答案】【1】 NULL 【2】 n 【3】 head,ch

【解析】本题考查:链表相关知识;while循环语句;函数返回值

标号【1】:while循环语句判断是否到达链表结尾,链表结尾节点指针域是NULL。

标号【2】:若找到指定字符,则通过return语句将该节点在链表的顺序号返回给main()函数。

标号【3】:函数调用语句,其形式是:函数名(实际参数表),因此根据函数定义语句填入head,ch。

考点7 在链表中插入和删除节点

真考链接

考点7 属于重点理解重点掌握的内容。在选择题中的考核概率为30%。操作题对此知识的考查常在编程题中出现,考核概率为20%。

1.在链表中插入节点

在单向链表中插入节点,首先要确定插入的位置。插入节点在指针p所指的节点之前称为“前插”,插入节点在指针p所指的节点之后称为“后插”。“前插”操作中各指针的指向如图11.2所示。

当进行前插操作时,需要3个工作指针:用s指向新开辟的节点,用p指向插入的位置,用q指向要插入的前趋节点。

图11.2 “前插”操作中各指针的指向

2.删除链表中的节点

为了删除单向链表中的某个节点,首先要找到待删除的节点的前趋节点(即当前要删除节点的前面一个节点),然后将此前趋节点的指针域指向待删除节点的后续节点(即当前要删除节点的下一个节点),最后释放被删除节点所占的存储空间即可。

常见问题

动态链表中,节点有何特点?

在动态链表中,每个节点元素均没有自己的名字,只能靠指针维系节点元素之间的连续关系。一旦某个元素的指针“断开”,后续元素就再也无法找寻。

真题精选

下列给定程序中已建立了一个带头节点的单向链表,请向链表中插入一个整数,使插入后的链表仍然有序。请在标号处填入正确的内容,使程序得出正确的结果。

注意:部分源程序给出如下。不得增行或删行,也不得更改程序的结构。

试题程序

#include <stdio.h>

#include <stdlib.h>

#define N 8

typedef struct list

{ int data;

struct list *next;

}SLIST;

void fun(SLIST *P,int m)

{ SLIST *t,*s;

s=(SLIST *)malloc(sizeof(SLIST));

S->data= 【1】 ;

t=p->next;

while(t!=NULL&&t->data<m)

{p=t;t= 【2】 ;}

【3】

SLIST *creatlist(int *a)

{ SLIST *h,*p,*q;int i;

h = p =(SLIST *)malloc(sizeof (SLIST));

for(i=0;i<N;i++)

{ q =(SLIST *)malloc(sizeof (SLIST));

q->data=a[i];p->next=q;p=q;

}p->next=0;

return h;

void outlist(SLIST *h)

{ SLIST *p;

p=h->next;

if(p==NULL)

printf("\nThe list is NULL!\n");else

{ printf("\nHead");

do

{ printf("->% d",p->data);

p=p->next;

}while(p!=NULL);

printf("->End\n");

main()

{ SLIST *head;

int a[N] = {11,12,15,18,19,22,25, 29},n;

head=creatlist(a);

printf("\nThe list before inpreeing:\n");

outlist(head);

printf("Intput a integer:");

scanf("% d",&n);

printf("\n The list afeer inputting:\n");

fun(head,n);

outlist(head);

【答案】【1】 m 【2】 t->next 【3】 s->next=t;p->next=s;

【解析】标号【1】:申请一个节点空间,并将形参m中的值存入新节点的数据域中

标号【2】:使用循环语句遍历链表,查找待插入的位置,指针p和t依次向后移动。

标号【3】:将新节点插入到链表中,插入时先将节点的指针域指向t,再将节点p的指针域指向s。

教程类别