課件l13-02有頭鏈表的構(gòu)造

1、C/C+學(xué)習(xí)指南 第13.2講：有頭鏈表的構(gòu)造作者：邵發(fā) 官網(wǎng)： 答疑： kbase/引例C/C+學(xué)習(xí)指南 邵發(fā) 一個(gè)鏈表，當(dāng)有N個(gè)對象串起來是，使用第一個(gè)對象來指代整個(gè)鏈表?？梢韵蜴湵碇刑砑訉ο?，也可以刪除對象?？紤]：如果向鏈表中刪除了所有對象，這個(gè)鏈表該怎么表示？(或者說，鏈表中有0個(gè)對象）有這個(gè)問題引出了兩種形式的表示方法:有頭鏈表、無頭鏈表有頭鏈表與無頭鏈表C/C+學(xué)習(xí)指南 邵發(fā) 無頭鏈表：所有的節(jié)點(diǎn)都包含了有效數(shù)據(jù)。(上節(jié)課演示的鏈表就是無頭鏈表）有頭鏈表：用一個(gè)固定的頭節(jié)點(diǎn)來指代整個(gè)鏈表，所有的對象掛在這個(gè)頭節(jié)點(diǎn)下面，而頭節(jié)點(diǎn)本身不包含有效數(shù)據(jù)。有頭鏈表C/C+學(xué)習(xí)指南 邵發(fā) 有頭

2、鏈表：使用固定的鏈表頭。（很容易表示對象個(gè)數(shù)為0的情形）有頭鏈表C/C+學(xué)習(xí)指南 邵發(fā) 使用固定的頭節(jié)點(diǎn)，是為了簡化鏈表操作。本篇介紹這種有頭鏈表的使用。無頭鏈表的缺點(diǎn)：沒有固定的頭節(jié)點(diǎn)，所有的節(jié)點(diǎn)都是數(shù)據(jù)節(jié)點(diǎn)。因此，當(dāng)鏈表對象個(gè)數(shù)為0時(shí)，不好表示 。(1) 定義一個(gè)有頭鏈表C/C+學(xué)習(xí)指南 邵發(fā) 只需要定義一個(gè)對象作為其節(jié)點(diǎn)，將成員next初始化為NULL。Student m_head = 0, head, NULL;或?qū)懽鱏tudent m_head = 0;當(dāng)有對象加入時(shí)，直接加在它的后面就可以。當(dāng)它的next為NULL時(shí)，表示該鏈表一個(gè)對象也沒有。(也就是說，頭節(jié)點(diǎn)自身只用于掛接，本身

3、是不算作長度的）(2) 添加一個(gè)對象C/C+學(xué)習(xí)指南 邵發(fā) void add(Student* obj) obj-next = m_head.next; m_head.next = obj-next;鏈表中的對象，一般都動(dòng)態(tài)創(chuàng)建的。比如，當(dāng)用戶需要添加一個(gè)對象時(shí)，從控制臺輸入信息，然后創(chuàng)建一個(gè)對象，插入到鏈表中。(2) 添加一個(gè)對象C/C+學(xué)習(xí)指南 邵發(fā) 比如，原鏈表中有4個(gè)對象A,B,C,D，調(diào)用add函數(shù)，添加一個(gè)對象X(2) 添加一個(gè)對象C/C+學(xué)習(xí)指南 邵發(fā) 也可以把對象附加到末尾void add(Student* obj) Student* p = &m_head; while(p-

4、next) p = p-next; / 找到最后一個(gè)對象 p-next = obj; / 把obj掛在最后一個(gè)對象后面 obj-next = NULL; / 現(xiàn)在obj作為最后一個(gè)對象(3) 對象從哪來？C/C+學(xué)習(xí)指南 邵發(fā) 鏈表中的對象，一般都動(dòng)態(tài)創(chuàng)建的。（注意：動(dòng)態(tài)創(chuàng)建的對象的生命期，自malloc之時(shí)生效，到free之后失效）Student* obj = (Student*)malloc (sizeof(Student);obj-id = 12;strcpy(obj-name, X);add(obj);(3) 對象從哪來？C/C+學(xué)習(xí)指南 邵發(fā) 對象的數(shù)據(jù)可以讓用戶來輸入/ 用戶輸入數(shù)

5、據(jù)/ 返回值：0個(gè)成功；-1表示用戶輸入有誤int user_input(Student* obj)printf(學(xué)號: );scanf(%d, &obj-id);printf(姓名: );scanf(%s, obj-name);return 0;(4) 有頭鏈表的遍歷C/C+學(xué)習(xí)指南 邵發(fā) 注意：在遍歷有頭鏈表時(shí)，不包含頭節(jié)點(diǎn)本身/ 遍歷void show_all()Student* p = m_head.next; while(p)printf(ID: %d, name: %sn, p-id, p-name);p = p-next; / 下一個(gè)對象小結(jié)C/C+學(xué)習(xí)指南 邵發(fā) 1. 比較了有頭節(jié)點(diǎn)和無頭節(jié)點(diǎn)(無頭節(jié)點(diǎn)：當(dāng)對象個(gè)數(shù)為0時(shí)，不太好表示）2. 有頭節(jié)點(diǎn)的構(gòu)造方法，動(dòng)態(tài)創(chuàng)建對象，并加入到鏈表中。習(xí)題C/C+學(xué)習(xí)指南 邵發(fā)