链表中头结点的应用.doc

链表中头结点的应用唐艳琴 张欣星 吴永芬作者简介：唐艳琴（1977），讲师，主要研究领域计算机软件。张欣星（1981），讲师，主要研究领域计算机软件。吴永芬（1979），助教，主要研究领域计算机软件。（解放军理工大学指挥自动化学院，江苏南京210007）摘要： 通过比较各种链表中带头结点与不带头结点链表的插入和删除等基本操作，说明带头结点链表的算法简单、易懂并容易实现。关键词：链表；头指针；头结点；首元结点；算法一、引言链表在线性表存储中应用非常广泛。指向链表第一个结点的指针为头指针。链表的第一个结点若不是数据结点，无内容或存储了与链表有关其他信息称为头结点；链表中第一个数据结点称为首元结点。若对线性表中多次进行插入与删除时 ,链式存储与顺序存储相比，移动元素的次数减少了,从而节省了时间 ,所以研究链表的基本操作非常重要 ,它包括建立、插入、删除、遍历等,熟练掌握它们后就容易实现其他操作。许多教材1对链表基本操作进行过算法描述,建立的是不带头结点的链表。而使用带头结点的链表可使这些算法结构更简单、思路更清晰。本文就各种链表的建立、插入、删除操作等来比较分析带头结点与不带头结点链表算法2,并给出带头结点链表的算法描述。二、单链表的插入、删除和遍历以存储学生成绩的链表为例，单链表中结点类型描述如下： typedef struct students int num;/学号float score;/成绩 struct students *next;/链域 stu,*ptr;/定义结点类型和指针类型下文中head均为头指针。为了更好地体现插入和删除算法，我们均以有序链表为例。我们知道在链表中进行插入和删除时必须知道插入和删除结点的前驱结点是哪个。而且链表总是依据头指针，然后按照链域访问每个结点的，因此在调用插入和删除函数时一旦改变了首元结点就会引起整个链表的输出结果，因此在调用时须用传引用&，即void insert(ptr &h,int num,float score)、int delete_lst(ptr &h,int num)。因此在不带头结点的有序链表中插入或删除一个结点q，使之仍然有序，这时需考虑以下几个方面：（1） 链表是否为空表；（2） 在表头进行插入或删除结点（3） 在表中或表尾插入或删除结点（4） 在调用该函数时应传递什么值而在带头结点的有序链表中插入新结点q就不必考虑这些因素。因为不管链表是否为空还是插在表头，结点q插入时就有前驱结点为头结点。而且在链表中带上头结点就起了监督作用，不管插入还是删除元素都不会改变这个头结点。算法1：在带表头结点单链表中插入元素void insert(ptr h,int num,float score)ptr pre,p,q;pre=h;p=h-next;q=newsnode();q-num=num; q-score=score;while(p!=NULL & p-datanext;q-next=p;pre-next=q;算法2：在带表头结点单链表中删除元素int delete_lst(ptr h,int num)ptr pre,p;pre=h;p=h-next;while(p!=NULL & p-data!=num)pre=p;p=pre-next;if(p=NULL)return 0; /删除不成功pre-next=p-next;free(p);return 1;算法3：单链表的遍历void output(ptr p)while(p!=NULL)printf(%d,%fn,p-num,p-score);p=p-next;对于单链表的遍历，带头结点与不带头结点的链表遍历算法都一样，只是调用时不太一样，不带头结点的链表遍历用output(head)调用，而带头结点的链表遍历用output(head-next)调用。三、循环单链表的插入、删除和遍历在不带头结点的循环单链表中插入和删除元素比单链表还复杂一些，它不仅要考虑单链表中插入/删除的四种情况，而且因为是循环链表，插入/删除在首元结点时还必须知道尾结点。而在带头结点的循环单链表中插入和删除元素就简单的多，而且因为是循环链表，我们还可以给头结点赋一个“无穷大”的结点值，起到监督作用,这样在循环中也可以减少一个测试条件(即减少判断p是否等于头结点)。算法4：在带表头结点的循环单链表中插入元素void insert(ptr h,int num,float score)ptr pre,p,q;pre=h;p=h-next;q=newsnode();q-num=num; q-score=score;while(p-datanext;q-next=p;pre-next=q;算法5：在带表头结点的循环单链表中删除元素int delete_lst(ptr h,int num)ptr pre,p;pre=h;p=h-next;while(p!=h & p-data!=num)pre=p;p=pre-next;if(p=h)return 0;/删除不成功pre-next=p-next;free(p);return 1;循环单链表遍历也与单链表遍历不一样。算法6：循环单链表的遍历void output(ptr p)while(p!=h)printf(%d,%fn,p-num,p-score);p=p-next;算法6只适合带头结点的循环单链表的遍历，用output(head-next)调用。因为在不带头结点的循环单链表中初始p就等于h，因此不能用while循环，而需先判断链表是否为空，然后改用dowhile循环来遍历整个链表。四、结论从以上几种算法的分析可以看出对链表的多数操作应明确对哪个结点以及该结点的前驱。不带头结点的链表对首元结点、中间结点分别处理等；而带头结点的链表因为有头结点，因此对首元结点、中间结点的操作相同，从而减少分支，使算法变得简单，流程清晰，对初学者更易接受。并且，对更复杂的数据结构3，如图的邻接表存储、哈希表处理冲突的链地址法等，