第9章 线性表 计算机软件技术 知识基础教程 .ppt

实际上，以上定义的p所指向的结点变量是通过标准函数生成的，即 p=malloc(sizeof(linklist))； 函数malloc分配一个类型为node的结点变量的空间，并将其地址放入指针变量p中。一旦所指的结点变量不再需要了，又可通过标准函数free(p)释放p所指的结点变量空间。因此，我们无法通过预先定义的标识符去访问这种动态的结点变量，而只能通过指针p来访问它。由于结点类型node是结构类型，因而?p是结构名，故可用加上“?”来取该结构的两分量(?p).data和(?p).next。这种表示形式总是要使用圆括号，显然很不精练。因此，在C语言中，对指针所指结构体的成员进行访问时，通常用运算符“→”来表示，例如取上面结构中的两个分量，可以写成p→data和p→next。它与前一种表示法的意义完全相同，它们之间的关系如图9.6所示。 图9.6 指针变量p(其值是结点地址)和结点变量?p (其值是结点内容)之关系 9.3.2 单链表的基本运算 下面我们将讨论用单链表作存储结构时，如何实现线性表的几种基本运算，为此，首先讨论如何建立单链表。 1．建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以“$”为输入结束标志。动态地建立单链表的常用方法有如下两种： 1) 头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直至读入结束标志为止。图9.7表明了在空链表head中依次插入a，b，c之后，将d插入到当前链表表头时指针的修改情况。图中的序号表明了结点插入时的操作次序。 其算法如下： linklist ?CREATLISTF( ) { char ch; /* 逐个输入字符，以“$”为结束符，返回单链表头指针 */ linklist ?head,?s; head=NULL; /* 链表开始为空 */ ch=getchar( ); /* 读入第一个结点的值 */ while (ch!=$) { s=(linklist?)malloc(sizeof(linklist)); /* 生成新结点 */ s－ data=ch; /* 将输入数据放入新结点的数据域中 */ s－ next=head; head=s; /* 将新结点插入到表头上 */ ch=getchar( ); /* 读入下一个结点的值 */ } return head; /* 返回链表头指针 */ } /* CREATLISTF */ 2) 尾插法建表 头插法建表虽简单，但生成的链表中结点的次序和输入的顺序相反。若希望两者次序一致，可利用尾插法建表。该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例如，在空链表head中插入a，b，c之后，将d插入到当前链表的表尾，其指针修改情况如图9.8所示。图中序号同样表明了操作顺序。 图9.8 新结点*s插入到单链表head的尾上 算法描述如下： linklist ?CREATLISTR() /* 尾插法建立单链表，返回表头指针 */ { char ch; linklist ?head, ?s, ?r; head=NULL; /* 链表初值为空 */ r=NULL; /* 尾指针初值为空 */ ch=getchar(); /* 读入第一个结点值 */ while (ch!=′$′) /* 以“$”为输入结束符 */ { s=(linklist?)malloc(sizeof(linklist)); /* 生成新结点?s */ s－ data=ch; if (head==NULL) head=s; /* 新结点?s插入空表 */ else r－ next=s; /* 非空表，新结点?s插入到尾结点 */ r=s; /* 尾指针r指向新的表尾 */ ch=