第一篇：《Linux協(xié)議棧源碼分析》讀書報(bào)告
讀 書 報(bào) 告
題目 《Linux協(xié)議棧源碼分析》
一、介紹......................................................................................................................................1.1、中斷模型......................................................................................................................-21.1.2、硬中斷...............................................................................................................-2
二、中斷處理..............................................................................................................................2.1、中斷線..........................................................................................................................-32.1.2、特性...................................................................................................................-32.2.1、硬中斷的開關(guān)...................................................................................................-42.3、軟中斷處理..................................................................................................................-52.3.2、注冊軟中斷處理函數(shù).......................................................................................-52.4、軟中斷處理和硬中斷處理區(qū)別..................................................................................-6
三、中斷處理中數(shù)據(jù)結(jié)構(gòu)...........................................................................................................3.1、中斷描述符..................................................................................................................-63.3、中斷控制器描述符(PIC、APIC)................................................................................3.4、中斷服務(wù)例程(ISR)...................................................................................................四、總結(jié)..................................................................................................................................../ 13
二、中斷處理
2.1、中斷線
每個能夠產(chǎn)生中斷的設(shè)備或者模塊都會在內(nèi)核中注冊一個中斷服務(wù)例程(ISR)，當(dāng)產(chǎn)生中斷時，中斷處理程序會被執(zhí)行，在中斷處理程序中，首先會保存中斷向量號和上下文，之后執(zhí)行中斷線對應(yīng)的中斷服務(wù)例程。對于CPU來說，中斷線是非常寶貴的資源，而由于計(jì)算機(jī)的發(fā)展，外部設(shè)備數(shù)量和種類越來越多，導(dǎo)致了中斷線資源不足的情況，linux為了應(yīng)對這種情況，實(shí)現(xiàn)了兩種中斷線分配方式，分別是：共享中斷線，中斷線動態(tài)分配。2.1.1、中斷線分配方式（1）共享中斷線
多個設(shè)備共用一條中斷線，當(dāng)此條中斷線發(fā)生中斷時，因?yàn)椴豢赡茴A(yù)先知道哪個特定的設(shè)備產(chǎn)生了中斷，因此，這條中斷線上的每個中斷服務(wù)例程都會被執(zhí)行，以驗(yàn)證是哪個設(shè)備產(chǎn)生的中斷(一般的，設(shè)備產(chǎn)生中斷時，會標(biāo)記自己的狀態(tài)寄存器，中斷服務(wù)例程通過檢查每個設(shè)備的狀態(tài)寄存器來查找產(chǎn)生中斷的設(shè)備)，因此共享中斷線的分配方式是比較常見的。（2）中斷線動態(tài)分配
一條中斷線在可能使用的時刻才與一個設(shè)備驅(qū)動程序關(guān)聯(lián)起來，這樣一來，即使幾個硬件設(shè)備并不共享中斷線，同一個中斷向量也可以由這幾個設(shè)備在不同時刻運(yùn)行。2.1.2、特性
(1)中斷處理程序正在運(yùn)行時，CPU會通知中斷控制器屏蔽產(chǎn)生此中斷的中斷線。此中斷線發(fā)出的信號被暫時忽略，當(dāng)中斷處理程序結(jié)束時恢復(fù)此中斷線。(2)在中斷服務(wù)例程的設(shè)計(jì)中，原則上是立即處理緊急的操作，將非緊急的操作延后處理(交給軟中斷進(jìn)行處理)。
(3)中斷處理程序是運(yùn)行在中斷上下文，但是其是代表進(jìn)程運(yùn)行的，因此它所代表的進(jìn)行必須處于TASK_RUNNING狀態(tài)，否則可能出現(xiàn)僵死情況，因此在中斷處理程序中不能執(zhí)行任何阻塞過程。
/ 13
action=(struct irqaction*)Kmalloc(sizeof(struct irqaction),GFR_ATOMIC);……
此handler就是剛才介紹的handle_IRQ_event 函數(shù)中要處理的handler。action->handler=handler;action->flags=irqflags;action->maks-0;action->name=devname;action->next=NULL;action->dev_id=dev_id;retval=setup_irq(irq,action);return retval;}
2.3、軟中斷處理
2.3.1、軟中斷的開關(guān)
禁止下半部，如softirq、tasklet和workqueue等： local_bh_disable();local_bh_enable();需要注意的是，禁止下半部時仍然可以被硬中斷搶占。軟中斷由softirq_action結(jié)構(gòu)體表示： struct softirq_action { void(*action)(struct softirq_action *);/* 軟中斷的處理函數(shù) */ };2.3.2、注冊軟中斷處理函數(shù) /** * @nr: 軟中斷的索引號 * @action: 軟中斷的處理函數(shù)
*/void open_softirq(int nr, void(*action)(struct softirq_action *)){ softirq_vec[nr].action = action;} 例如：
open_softirq(NET_TX_SOFTIRQ, net_tx_action);open_softirq(NET_RX_SOFTIRQ, net_rx_action);
/ 13
函數(shù)，而在do_IRQ()函數(shù)中，會根據(jù)中斷向量號，從中斷描述符數(shù)組中獲取對應(yīng)的中斷描述符，如下圖： 整個中斷描述符結(jié)構(gòu)如下： struct irq_desc {
struct irq_data irq_data;/* irq的統(tǒng)計(jì)信息，在proc中可查到 */ unsigned int __percpu *kstat_irqs;/* 回調(diào)函數(shù)，當(dāng)此中斷產(chǎn)生中斷時，會調(diào)用handle_irq，在handle_irq中進(jìn)行遍歷irqaction鏈表
* handle_simple_irq 用于簡單處理；
* handle_level_irq 用于電平觸發(fā)中斷的流控處理；
* handle_edge_irq 用于邊沿觸發(fā)中斷的流控處理；
* handle_fasteoi_irq 用于需要響應(yīng)eoi的中斷控制器；
* handle_percpu_irq 用于只在單一cpu響應(yīng)的中斷；
* handle_nested_irq 用于處理使用線程的嵌套中斷； */irq_flow_handler_t handle_irq;#ifdef CONFIG_IRQ_PREFLOW_FASTEOI irq_preflow_handler_t preflow_handler;#endif
/* 中斷服務(wù)例程鏈表 */ struct irqaction *action;
/* IRQ action list *//* 狀態(tài) */ unsigned int status_use_accessors;/* 函數(shù)調(diào)用中使用，另一個名稱為istate */ unsigned int
core_internal_state__do_not_mess_with_it;/* 嵌套深度，中斷線被激活顯示0，如果為正數(shù)，表示被禁止次數(shù) */ unsigned int
depth;
/* nested irq disables */ unsigned int
wake_depth;
/* nested wake enables */ /* 此中斷線上發(fā)生的中斷次數(shù) */ unsigned int
irq_count;
/* For detecting broken IRQs */ /* 上次發(fā)生未處理中斷時的jiffies值 */ unsigned long
last_unhandled;
/* Aging timer for unhandled count */ /* 中斷線上無法處理的中斷次數(shù)，如果當(dāng)?shù)?00000次中斷發(fā)生時，有超過99900次是意外中斷，系統(tǒng)會禁止這條中斷線 */ unsigned int
irqs_unhandled;atomic_t
threads_handled;
/ 13
core_internal_state__do_not_mes_with_it成員是用于記錄此中斷線狀態(tài)的，中斷線狀態(tài)有如下幾種形式：
IRQS_AUTODETECT
/* 該IRQ線用來進(jìn)行硬件設(shè)備探測 */ IRQS_SPURIOUS_DISABLED // 該IRQ線被禁止，是由于產(chǎn)生了欺騙性中斷
IRQS_POLL_INPROGRESS
/* 該IRQ進(jìn)行輪詢檢查是否發(fā)生中斷 */ IRQS_ONESHOT
/* 此IRQ沒有在主處理函數(shù)中進(jìn)行unmasked處理 */ IRQS_REPLAY
/* IRQ線已被禁止，但前一個出現(xiàn)的中斷還沒有被應(yīng)答 */ IRQS_WAITING
/* 進(jìn)行硬件設(shè)備探測時，會將所有沒有掛載中斷服務(wù)程序的IRQ線狀態(tài)設(shè)置為IRQS_WAITING，如果該IRQ上有中斷產(chǎn)生，就清除這個狀態(tài)，可以推斷哪些引腳產(chǎn)生過中斷 */ IRQS_PENDING /* IRQ已經(jīng)被應(yīng)答(掛起)，但是內(nèi)核還沒有進(jìn)行處理 */ IRQS_SUSPENDED
/* 此IRQ被延遲 */
3.2、中斷描述符表和中斷描述符數(shù)組
在中斷系統(tǒng)中有兩個名字很相像的結(jié)構(gòu)，就是中斷描述符表和中斷描述符數(shù)組。這里我們先說說中斷描述符表。一個系統(tǒng)中的中斷和異常加起來一共是256個，它們以向量的形式保存在中斷描述符表中，每一個向量是8字節(jié)(整個表大小就是8 x 256=2048字節(jié))，其主要保存著權(quán)限位和向量對應(yīng)的中斷或異常處理程序的入口地址。而一般的，linux會將中斷描述符表中的0~31用于非屏蔽中斷和異常，其他的中斷用于32~255之間。CPU把中斷描述符表的向量類型分為三種類型：任務(wù)門、中斷門、陷阱門。CPU為了防止惡意程序訪問中斷，限制了中斷門的權(quán)限，而在某些時候，用戶程序又必須使用中斷，所以Linux把中斷描述符的中斷向量類型改為了5種：中斷門，系統(tǒng)門，系統(tǒng)中斷門，陷阱門，任務(wù)門。這個中斷描述符表的基地址保存在idtr寄存器中。（1）中斷門
用戶程序不能訪問的CPU中斷門(權(quán)限字段為0)，所有的中斷處理程序都是這個，被限定在內(nèi)核態(tài)執(zhí)行。會清除IF標(biāo)志，屏蔽可屏蔽中斷。
/ 13
信號，將IRQ1的中斷向量號發(fā)到數(shù)據(jù)總線上，此時CPU會通過數(shù)據(jù)總線讀取IRQ1的中斷向量號。
最后，如果中斷控制器需要EOI(End of Interrupt)信號，CPU則會發(fā)送，否則中斷控制器自動將INT拉低，并清除IRQ1對應(yīng)的中斷請求寄存器位。
在linux內(nèi)核中，用struct irq_chip結(jié)構(gòu)體描述一個可編程中斷控制器，它的整個結(jié)構(gòu)和調(diào)度器中的調(diào)度類類似，里面定義了中斷控制器的一些操作，如下： struct irq_chip { /* 中斷控制器的名字 */ const char
*name;/* 控制器初始化函數(shù) */ unsigned int
(*irq_startup)(struct irq_data *data);/* 控制器關(guān)閉函數(shù) */ void
(*irq_shutdown)(struct irq_data *data);/* 使能irq操作，通常是直接調(diào)用irq_unmask()，通過data參數(shù)指明irq */ void
(*irq_enable)(struct irq_data *data);/* 禁止irq操作，通常是直接調(diào)用irq_mask，嚴(yán)格意義上，他倆其實(shí)代表不同的意義，disable表示中斷控制器根本就不響應(yīng)該irq，而mask時，中斷控制器可能響應(yīng)該irq，只是不通知CPU */ void
(*irq_disable)(struct irq_data *data);/* 用于CPU對該irq的回應(yīng)，通常表示cpu希望要清除該irq的pending狀態(tài)，準(zhǔn)備接受下一個irq請求 */ void(*irq_ack)(struct irq_data *data);/* 屏蔽irq操作，通過data參數(shù)表明指定irq */ void
(*irq_mask)(struct irq_data *data);/* 相當(dāng)于irq_mask()+ irq_ack()*/ void
(*irq_mask_ack)(struct irq_data *data);/* 取消屏蔽指定irq操作 */ void
(*irq_unmask)(struct irq_data *data);/* 某些中斷控制器需要在cpu處理完該irq后發(fā)出eoi信號 */ void
(*irq_eoi)(struct irq_data *data);/* 用于設(shè)置該irq和cpu之間的親和力，就是通知中斷控制器，該irq發(fā)生時，那些cpu有權(quán)響應(yīng)該irq */ int(*irq_set_affinity)(struct irq_data *data, const struct cpumask *dest, bool force);
1/ 13
void __percpu
*percpu_dev_id;
/* 鏈表中下一個中斷服務(wù)例程 */
struct irqaction
*next;
/* 進(jìn)行中斷處理的內(nèi)核線程執(zhí)行函數(shù) */
irq_handler_t
thread_fn;
/* 一個內(nèi)核線程，用于執(zhí)行中斷處理 */
struct task_struct
*thread;
/* IRQ線，IRQ號 */
unsigned int
irq;
unsigned int
flags;
unsigned long
thread_flags;
unsigned long
thread_mask;
const char
*name;
/* 指向/proc/irq/n目錄的描述符 */
struct proc_dir_entry
*dir;} ____cacheline_internodealigned_in_smp;
四、總結(jié)
在CPU里，中斷和異常都會放入到一個中斷描述符表中，都需要特定的處理程序進(jìn)行處理，并且它們都是異步事件，內(nèi)核完全不知道何時會有一個異常或者中斷發(fā)生。當(dāng)異?；蛘咧袛喟l(fā)生時，進(jìn)程都會陷入內(nèi)核，在內(nèi)核中執(zhí)行相應(yīng)的處理。異常一般都是由CPU內(nèi)部或者進(jìn)程產(chǎn)生，而中斷一般都是由外部設(shè)備產(chǎn)生。異常處理過程實(shí)際上和系統(tǒng)調(diào)用沒什么區(qū)別(實(shí)際上系統(tǒng)調(diào)用是通過一個0x80異常陷入內(nèi)核當(dāng)中)，而中斷的處理過程和情況就相對來說比較復(fù)雜。
一個中斷處理分為硬中斷和軟中斷兩個部分，在中斷處理的過程中系統(tǒng)是禁止調(diào)度和搶占的，而異常處理過程中是允許的。一個中斷處理程序可以搶占其他的中斷處理程序，也可以搶占異常處理程序，相反的，異常處理程序卻不能夠搶占中斷處理程序。
3-/ 13
第二篇：java-Floodlight源碼分析IOFMessageListener
package net.floodlightcontroller.core;
import org.openflow.protocol.OFMessage;
import org.openflow.protocol.OFType;
/**
*
*
* @author
*/
public interface IOFMessageListener extends IListener
/** messages
* @param sw the OpenFlow switch that sent this message
* @param msg the message
* @param* information between listeners
* @return the command to continue or stop the execution
*/
public Command receive(IOFSwitch sw, OFMessage msg, FloodlightContext cntx);
}
IOFMessageListener接口繼承了IListener接口，協(xié)議類型為
receive方法的返回值使用了IListener中的枚舉類型，且receive方法沒有方法體，在OFMessageFilterManager中可以看到它的實(shí)現(xiàn)。
第三篇：軟件源碼移交保密協(xié)議
系統(tǒng)源碼授權(quán)使用保密協(xié)議
╳╳系統(tǒng)
源碼授權(quán)使用保密協(xié)議
甲方:珠海市聯(lián)進(jìn)高技術(shù)有限公司乙方:
簽訂地點(diǎn)：
一、協(xié)議背景 ╳╳系統(tǒng)是珠海市聯(lián)進(jìn)高技術(shù)有限公司(以下簡稱甲方)為╳╳(以下簡稱乙方)承建的。茲雙方確認(rèn)甲方擁有╳╳系統(tǒng)全部源代碼的版權(quán)，為了便于乙方更好的進(jìn)行系統(tǒng)維護(hù)工作，并考慮到今后的業(yè)務(wù)需求變更后，對業(yè)務(wù)系統(tǒng)可能提出的修改要求，甲方把與業(yè)務(wù)系統(tǒng)相關(guān)的源代碼授權(quán)乙方使用，同時雙方達(dá)成以下協(xié)議。協(xié)議條款標(biāo)的內(nèi)容：
甲方提供給乙方的源代碼，是現(xiàn)行╳╳系統(tǒng)的應(yīng)用程序部分。甲方保證所提供的部分源代碼與系統(tǒng)當(dāng)前正在運(yùn)行的前臺程序是同一版本，利用所提供的源代碼及相關(guān)資源可以直接編譯生成當(dāng)前系統(tǒng)的應(yīng)用程序部分。
二、用途限定
甲方授權(quán)乙方使用源代碼的方式僅限于對現(xiàn)行系統(tǒng)的程序改進(jìn)之用途;乙方有義務(wù)對源代碼進(jìn)行保密，在任何情況下，未經(jīng)甲方同意，乙方不得將此源代碼提供給任何第三方。乙方并應(yīng)限制有關(guān)源代碼的具體使用范圍，使之僅限于現(xiàn)行系統(tǒng)的維護(hù)/升級等系統(tǒng)開發(fā)用途，僅為直接開發(fā)人員所了解和使用，不應(yīng)在同行業(yè)其他項(xiàng)目使用，不得用于其他用途。
三、知識產(chǎn)權(quán)歸屬 甲方擁有╳╳系統(tǒng)全部源代碼的版權(quán)。
乙方可以對源代碼進(jìn)行改變，由此衍生的有關(guān)程序及源代碼的知識產(chǎn)權(quán)由雙方共同擁有。未經(jīng)甲方許可，乙方不得將修改后的源代碼提供給任何第三方。甲方原則上沒有義務(wù)向乙方提供對源代碼及其相關(guān)資訊的技術(shù)支持和培訓(xùn)，但雙方另有協(xié)議除外。
對于由乙方使用修改后程序所引起的故障和損失，根據(jù)是初始程序內(nèi)BUG引起的還是由于乙方的不當(dāng)修改造成，分清責(zé)任，并視責(zé)任情況承擔(dān)各自的責(zé)任。對于假若不修改程序就不會出現(xiàn)的故障，甲方不承擔(dān)責(zé)任。在乙方使用有關(guān)源代
系統(tǒng)源碼授權(quán)使用保密協(xié)議
碼的過程中，確需甲方技術(shù)支持的，可以通過協(xié)商解決。
四、生效條件與協(xié)議終止
有關(guān)協(xié)議一旦簽署，立即生效;并將長期有效，除非以下條件之一成立：
4.1、雙方另有協(xié)議，并一致同意廢止此協(xié)議；
4.2、乙方不再使用現(xiàn)行系統(tǒng)；
4.3、乙方主動提出終止此協(xié)議；
4.4、由于乙方過錯導(dǎo)致系統(tǒng)源代碼泄密，甲方有權(quán)解除此協(xié)議。
協(xié)議終止時，乙方有責(zé)任向甲方提交或立即銷毀所持有、保管或控制的包含所有該源代碼信息的所有文檔，軟件及相關(guān)資料(不含由接收方開發(fā)的后續(xù)版本所屬的文檔，軟件及相關(guān)資料)，并向甲方提供書面確認(rèn)，作為法律上認(rèn)可的憑據(jù)。
五、違約責(zé)任
乙方如果違反本協(xié)議第二條及第四條條款，在未經(jīng)甲方許可的情況下，將甲方授權(quán)其使用的源代碼或修改后的衍生源代碼提供給任何第三方，均應(yīng)承擔(dān)對甲方的賠償責(zé)任，方式為向甲方支付違約金人民幣20萬元（大寫：貳拾萬元整）。
六、爭議解決條款
本合同一式兩份，甲乙雙方各執(zhí)一份，具有同等法律效力。
在履行本協(xié)議中出現(xiàn)任何爭議，雙方均應(yīng)首先協(xié)商解決，協(xié)商沒有結(jié)果的。甲方有權(quán)向乙方所在地司法機(jī)關(guān)提起上訴。
甲方（蓋章）：╳╳乙方（蓋章）：╳╳╳╳╳╳
代表人（簽字）：代表人（簽字）：電話：╳╳╳╳
2011年 3月 15 日
電話：╳╳╳╳ 2011年 3月 15 日
第四篇：軟件自組網(wǎng)協(xié)議棧
軟件自組網(wǎng)流程：
設(shè)備啟動之后，由主機(jī)進(jìn)行掃描，由于出廠時候設(shè)備id相同均為00 00 00 00，不同的只有設(shè)備編號，主機(jī)會向00 00 00 00 ID發(fā)送查詢包。此時只有1臺設(shè)備同主機(jī)建立連接（該設(shè)備自動選定）。設(shè)備會向主機(jī)報(bào)告設(shè)備類型，主機(jī)會根據(jù)設(shè)備類型給該節(jié)點(diǎn)分配ID，設(shè)備受到新ID后，會將本ID寫入flash。依次類推，可以對每一個接入設(shè)備分配不同ID。同時主機(jī)將在rom中保持一個對應(yīng)設(shè)備列表：
設(shè)備ID--設(shè)備類型--設(shè)備命名。
設(shè)備列表作用為，主機(jī)斷電之后不需要重新進(jìn)行自組網(wǎng)。
此時設(shè)備命名為空。
設(shè)備命名流程：
自組網(wǎng)完成后，手機(jī)端軟件進(jìn)行查詢，會發(fā)現(xiàn)未命名開關(guān)1-1（表示開關(guān)1的第一位），未命名開關(guān)1-2（表示開關(guān)1的第二位），未命名開關(guān)2-1（表示開關(guān)2的第一位）等，未命名插座1-1（插座1的第一位），未命名插座1-2（插座1的第二位）?？蛻艨梢詫Ω鱾€開關(guān)/插座進(jìn)行重新命名。比如：客戶家里開關(guān)1的第一位為走廊燈，就可以在手機(jī)軟件中進(jìn)行修改，并提交主機(jī)進(jìn)行保存配置。主機(jī)在收到保存配置命令之后，主機(jī)rom中列表的設(shè)備命名項(xiàng)進(jìn)行相應(yīng)更新。如果手機(jī)軟件每次開啟之后會對設(shè)備命名、設(shè)備類型和主機(jī)進(jìn)行同步（從主機(jī)中讀取設(shè)備列表，并進(jìn)行更新）。設(shè)備可以在路由配置頁面（PC訪問），手機(jī)APP中進(jìn)行配置，兩者配置功能相同。
第五篇：數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列報(bào)告
棧和隊(duì)列上機(jī)實(shí)習(xí)
1、實(shí)驗(yàn)?zāi)康模?/p>
（1）熟練掌握棧的邏輯結(jié)構(gòu)和操作規(guī)則，能在相應(yīng)的實(shí)際問題中正確選用該結(jié)構(gòu)。（2）熟練掌握棧的2種存儲結(jié)構(gòu)實(shí)現(xiàn)方法（順序棧和鏈棧），兩種存儲結(jié)構(gòu)和基本運(yùn)算的實(shí)
現(xiàn)算法，注意?？蘸袧M的判斷條件及它們的描述方法。
（3）熟練掌握隊(duì)列的邏輯結(jié)構(gòu)和操作規(guī)范，能在相應(yīng)的實(shí)際問題中正確選用該結(jié)構(gòu)。（4）掌握循環(huán)隊(duì)列與鏈隊(duì)列兩種存儲結(jié)構(gòu)的實(shí)現(xiàn)，熟練掌握各種隊(duì)列基本運(yùn)算的實(shí)現(xiàn)。
2、實(shí)驗(yàn)要求：
（1）順序棧的插入、刪除，棧頂數(shù)據(jù)元素的讀取。（2）鏈棧的插入、刪除，棧頂數(shù)據(jù)元素的讀取。（3）循環(huán)隊(duì)列的插入、刪除。（4）鏈隊(duì)列的插入、刪除。
3、實(shí)驗(yàn)內(nèi)容: ① 棧
（1）抽象數(shù)據(jù)類型定義
typedef struct
{
ElemType data[MaxSize];
//棧的空間大小為MaxSize
int top;
//設(shè)置棧頂指針
}SqStack;
//棧的結(jié)構(gòu)定義
在本次實(shí)驗(yàn)中，首先建立一個空棧，進(jìn)入主程序后首先初始化棧為其分配空間，然后進(jìn)入菜單選擇界面，通過不同的數(shù)字輸入，實(shí)現(xiàn)入棧，出棧，讀取棧頂元素，顯示棧的所有元素，棧的長度，釋放棧等操作。
（2）存儲結(jié)構(gòu)定義及算法思想
在棧結(jié)構(gòu)體的定義中，typedef int Typeelem 為整型，存儲結(jié)構(gòu)（入棧）如下：
cin>>a;
s->top++;
//在入棧是首先將棧頂指針向上加1
s->data[s->top]=a;
//與數(shù)組賦值一樣，直接賦值
//其他存儲與此類似，都是直接賦值與數(shù)組的某一位
退棧函數(shù)模塊：
void Pop(SqStack * &s){
//對指針的引用
if(s->top ==-1){
cout<<“棧是空棧，不能退?！? //首先判斷是否為空棧，若為空，則退出 return;} cout<<“退棧的元素為：”< //顯示退棧元素 s->top--; //棧頂元素減1，指向?qū)嶋H棧的最上面 } 顯示棧所有元素函數(shù)模塊： void DispStack(SqStack *s){ //從棧頂?shù)綏５醉樞蝻@示所有元素 int i;cout<<“棧的元素分別為：”< //同過循環(huán)實(shí)現(xiàn)實(shí)現(xiàn)從棧頂元素到棧底元素的遍歷以輸出 } cout< 棧結(jié)構(gòu)的入棧和退棧是兩個相反的過程，先進(jìn)后出，入棧是先讓棧頂指針加1,指向未被賦值位置，然后進(jìn)行賦值，退棧是先取出退棧元素，然后棧頂元素減1，指向推展后的實(shí)際棧頂。諸如讀取棧頂元素，顯示棧的元素，讀取棧的長度，都是用過對棧頂指針實(shí)現(xiàn)相關(guān)操作。 （3）實(shí)驗(yàn)結(jié)果與分析 ② 循環(huán)隊(duì)列 （1）抽象數(shù)據(jù)類型定義 typedef struct { ElemType elem[Maxqsize]; //循環(huán)隊(duì)列的長度為MaxSize int front,rear; //設(shè)置隊(duì)列的頭指針和尾指針 }SqQueue; //循環(huán)隊(duì)列的結(jié)構(gòu)體定義 在本次實(shí)驗(yàn)中，首先建立一個空隊(duì)列，進(jìn)入主程序后首先初始化隊(duì)列為其分配空間，然后進(jìn)入菜單選擇界面，通過不同的數(shù)字輸入，實(shí)現(xiàn)入隊(duì)，出隊(duì)，顯示隊(duì)列的所有元素，隊(duì)列的長度，釋放隊(duì)列等操作。 （2）存儲結(jié)構(gòu)定義及算法思想 在隊(duì)列結(jié)構(gòu)體的定義中，typedef int Typeelem 為整型，存儲（入隊(duì)）結(jié)構(gòu)如下： q->rear=(q->rear+1)%Maxqsize; //尾指針加1 q->elem[q->rear]=a; //將入隊(duì)元素裝到新的空尾部 在此隊(duì)列的存儲結(jié)構(gòu)的實(shí)現(xiàn)：先讓隊(duì)尾指針進(jìn)1，再將新的元素加入到隊(duì)尾指針?biāo)甘镜奈恢?，因此，?duì)尾指針指示實(shí)際的隊(duì)尾位置，隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置，要想退出隊(duì)頭元素，必須先讓隊(duì)頭指針進(jìn)1，才能取出隊(duì)頭元素。 退隊(duì)函數(shù)模塊如下： void deQueue(SqQueue *&q){ //對指針的引用 if(QueueEmpty(q)) { //調(diào)用帶返回值的判斷空隊(duì)函數(shù) cout<<“隊(duì)列為空”< //判斷隊(duì)列是否為空 } q->front=(q->front+1)%Maxqsize; //隊(duì)頭指針進(jìn)1 cout<<“退隊(duì)的元素為：”< //取出隊(duì)頭元素 } 遍歷隊(duì)表函數(shù)： void displayqueue(SqQueue *q){ int m;m=q->front+1; //隊(duì)頭元素進(jìn)1，指向?qū)嶋H隊(duì)頭 if(QueueEmpty(q)) { cout<<“隊(duì)列為空”< //判斷是夠?yàn)榭贞?duì) } cout<<“所有隊(duì)列元素為：”< while(q->rear+1>m){ cout< //通過循環(huán)遍歷所有元素 m++; } cout< 循環(huán)隊(duì)列的入隊(duì)和退隊(duì)分別是在隊(duì)尾與隊(duì)頭跟別進(jìn)行操作的，通過隊(duì)頭隊(duì)尾指針的操作便可實(shí)現(xiàn)對隊(duì)列的相關(guān)操作。 （3）實(shí)驗(yàn)結(jié)果與分析 ③ 心得體會 本次上機(jī)是做棧與隊(duì)列的操作，這次實(shí)驗(yàn)，我有意的用到了對指針的引用與指針實(shí)現(xiàn)子函數(shù)功能的調(diào)用，剛開始編譯的時候也有錯誤，但是在慢慢的摸索中，也逐漸掌握了它們的用法，這次實(shí)驗(yàn)也讓我熟練了對隊(duì)列與棧存儲結(jié)構(gòu)的應(yīng)用。 附錄： 順序表源代碼: 棧： #include void InitStack(SqStack * &s) //建立一個空棧，即將棧頂指針指向-1即可 的引用 { s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;} void ClearStack(SqStack * &s) //釋放棧s占用的存儲空間 { free(s);} void StackLength(SqStack *s) { cout<<“棧的長度為：” <<(s->top +1)< int StackEmpty(SqStack *s){ return(s->top==-1);} void Push(SqStack *&s){ if(s->top==MaxSize-1) { cout<<“棧滿”< // s=(SqStack *)realloc(s,sizeof(SqStack));} int a; 指針 cout<<“請輸入入棧元素”< void Pop(SqStack * &s){ if(s->top ==-1){ cout<<“棧是空棧，不能退?！? return;} cout<<“退棧的元素為：”< void GetTop(SqStack * &s,ElemType &e){ if(s->top==-1){cout<<“空?！? void DispStack(SqStack *s) //從棧頂?shù)綏５醉樞蝻@示所有元素 { int i;cout<<“棧的元素分別為：”< cout<<“請選擇功能”< cout<<“ 入棧 1”< cout<<“ 出棧 2”< cout<<“ 讀取棧頂元素 3”< cout<<“ 顯示棧所有元素 4”< cout<<“ 棧的長度 5”< cout<<“ 釋放棧 6”< cin>>k; switch(k) { case 1: Push(s);break; case 2: Pop(s);break; case 3: GetTop(s,e);cout<<“棧頂元素為： ”< case 4: DispStack(s);break; case 5: StackLength(s);break; case 6: ClearStack(s);break; default :break; } } } 隊(duì)列： #include TypeElem elem[Maxqsize]; int front,rear;}SqQueue;void InitQueue(SqQueue *&q){ q=(SqQueue *)malloc(sizeof(SqQueue)); q->front=q->rear=0;} void ClearQueue(SqQueue *&q){ free(q);exit(0);} void QueueLength(SqQueue *q){ cout<<“隊(duì)列長度為：”<<(q->rear-q->front+Maxqsize)%Maxqsize< return(q->front==q->rear); } void enQueue(SqQueue *&q){ int a; if((q->rear+1)%Maxqsize==q->front) { cout<<“隊(duì)列已滿，無法插入”< } cout<<“請輸入插入元素”< cin>>a; q->rear=(q->rear+1)%Maxqsize; q->elem[q->rear]=a;} void deQueue(SqQueue *&q){ if(QueueEmpty(q)) { cout<<“隊(duì)列為空”< } q->front=(q->front+1)%Maxqsize; cout<<“退隊(duì)的元素為：”< } void displayqueue(SqQueue *q){ int m;m=q->front+1; if(QueueEmpty(q)) { cout<<“隊(duì)列為空”< } cout<<“所有隊(duì)列元素為：”< while(q->rear+1>m) { cout< m++; } cout< int k=0; SqQueue *q; InitQueue(q); if(QueueEmpty(q))cout<<“隊(duì)列為空”< while(1){ cout<<“請選擇功能”< cout<<“ 入隊(duì) cout<<” 出隊(duì) cout<<“ 隊(duì)列長度 cout<<” 顯示隊(duì)列元素 cout<<“ 釋放棧 cin>>k; switch(k) { case 1: enQueue(q);break; case 2: deQueue(q);break; case 3: QueueLength(q);break; case 4: displayqueue(q);break; case 5: ClearQueue(q);break; default :break; } } } 1”< 2“< 4“<
點(diǎn)擊咨詢 