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

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

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

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

4、next) p = p-next; / 找到最后一個對象 p-next = obj; / 把obj掛在最后一個對象后面 obj-next = NULL; / 現(xiàn)在obj作為最后一個對象(3) 對象從哪來？C/C+學(xué)習(xí)指南 邵發(fā) 鏈表中的對象，一般都動態(tài)創(chuàng)建的。（注意：動態(tài)創(chuàng)建的對象的生命期，自malloc之時生效，到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個成功；-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ā) 注意：在遍歷有頭鏈表時，不包含頭節(jié)點本身/ 遍歷void show_all()Student* p = m_head.next; while(p)printf(ID: %d, name: %sn, p-id, p-name);p = p-next; / 下一個對象小結(jié)C/C+學(xué)習(xí)指南 邵發(fā) 1. 比較了有頭節(jié)點和無頭節(jié)點(無頭節(jié)點：當(dāng)對象個數(shù)為0時，不太好表示）2. 有頭節(jié)點的構(gòu)造方法，動態(tài)創(chuàng)建對象，并加入到鏈表中。習(xí)題C/C+學(xué)習(xí)指南 邵發(fā)