第一篇：實(shí)驗(yàn)四 單鏈表及其應(yīng)用(參考程序)
實(shí)驗(yàn)四 單鏈表的建立
一、實(shí)驗(yàn)?zāi)康?/p>
1.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。2.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表中的各種基本操作。
二、實(shí)驗(yàn)內(nèi)容
1.建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)分別按尾插入法和頭插法來(lái)建立相應(yīng)單鏈表。【知識(shí)要點(diǎn)】
為了便于實(shí)現(xiàn)各種運(yùn)算，通常在單鏈表的第一個(gè)結(jié)點(diǎn)前增設(shè)一個(gè)附加結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，它的結(jié)構(gòu)與表結(jié)點(diǎn)相同，其數(shù)據(jù)域可不存儲(chǔ)信息，也可存儲(chǔ)表長(zhǎng)等附加信息，具體如下圖。
【實(shí)驗(yàn)提示】
單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：
typedef int datatype;
/* 線性表中存放整型元素 */ typedef struct LNode
/ * 結(jié)點(diǎn)類型定義 * /
{
datatype data;
/ * 數(shù)據(jù)域 * /
struct node *next;
/ * 指針域 * / }Linklist；
/* Linklist為單鏈表類型*/
注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：
p=(strcut LNode *)malloc(sizeof(Linklist));該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為L(zhǎng)inklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p中(或p=new(struct LNode);即生成新結(jié)點(diǎn))。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）?！境绦蛱崾尽?/p>
#include
//補(bǔ)充實(shí)現(xiàn)表節(jié)點(diǎn)類型的定義； } Linklist;
Linklist * creatlist(){ int x;Linklist *head, *p;// head為單鏈表的頭指針，p指向新建的結(jié)點(diǎn)
//補(bǔ)充實(shí)現(xiàn)單鏈表的建立；
return(head);
// 函數(shù)返回鏈表頭指針head }
void output(Linklist *HeadL){ if(HeadL->next==NULL)printf(“空鏈表!n”);else { printf(“鏈表為：n”);Linklist *P;P=HeadL->next;while(P!=NULL){
printf(“%d->”,P->data);P=P->next;} printf(“n”);}
}
void main(void){ Linklist *List;List=creatlist();output(List);} 【參考程序】
1、尾插法
#include
Linklist * creatlist(){ int x;
Linklist *head, *p,*r;/* head為頭指針 */
head=new(struct LNode);
head->data=0;
/* 表頭結(jié)點(diǎn)數(shù)據(jù)域賦值 */
r=head;
/* 尾指針的初值為頭結(jié)點(diǎn)head */
printf(“請(qǐng)隨機(jī)輸入互不相同的正整數(shù)以0作為結(jié)束符:n”);
scanf(“%d”, &x);
/* 讀入第一個(gè)結(jié)點(diǎn)的值 */
while(x!=0)
/* 輸入數(shù)據(jù)，以0為結(jié)束符 */ { p=new(struct LNode);/* 生成新結(jié)點(diǎn) */
p->data=x;
/* 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值 */
r->next=p;
/* 新結(jié)點(diǎn)插入到表尾*rear之后 */
r=p;
/* 將尾指針rear指向新的尾結(jié)點(diǎn) */
head->data++;
/* 鏈表長(zhǎng)度計(jì)數(shù) */
scanf(“%d”, &x);
/* 輸入下一個(gè)結(jié)點(diǎn)的數(shù)據(jù) */
}
r->next=NULL;
/* 將鏈表最后一個(gè)結(jié)點(diǎn)rear指針域置空 */
return(head);/* 函數(shù)返回鏈表頭指針head */ }
void output(Linklist *HeadL){
if(HeadL->next==NULL)printf(“空鏈表!n”);else {
printf(“鏈表為：n”);
Linklist *P;
P=HeadL->next;
while(P!=NULL)
{
printf(“%d->”,P->data);
P=P->next;
}
printf(“n”);}
} void main(void){
Linklist *List;List=creatlist();output(List);}
2、頭插法
#include
Linklist * creatlist(){ int x;
Linklist *head, *p;/* head為頭指針 */
head=new(struct LNode);
head->data=0;
/* 表頭結(jié)點(diǎn)數(shù)據(jù)域賦值 */
head->next=NULL;
printf(“n請(qǐng)隨機(jī)輸入一組正整數(shù)以0結(jié)束輸入:n”);
scanf(“%d”,&x);
/* 輸入第一個(gè)結(jié)點(diǎn)數(shù)據(jù)值 */
while(x!=0)
/* 輸入數(shù)據(jù)，以0為結(jié)束符 */
{ p=new(struct LNode);/* 生成新結(jié)點(diǎn) */
p->data=x;/* 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值 */
p->next=head->next;
/* 將新結(jié)點(diǎn)插入表頭結(jié)點(diǎn)head之后 */
head->next=p;
head->data++;
/* 鏈表長(zhǎng)度計(jì)數(shù) */
scanf(“%d”,&x);
/* 輸入下一個(gè)結(jié)點(diǎn)的值 */
}
return(head);/* 函數(shù)返回鏈表頭指針head */ }
void output(Linklist *HeadL){
} void main(void){
Linklist *List;List=creatlist();output(List);}
方法二 void main(void){
} 2.在第一題的基礎(chǔ)上，增加單鏈表的查找，插入，刪除子程序。#include
typedef struct LNode{ int data;struct LNode *next;Linklist *head,*p;head=creatlist();printf(“output the list:n”);p=head->next;while(p){ } printf(“%d ”,p->data);p=p->next;} Linklist;
Linklist * creatlist(){ int x;
Linklist *head, *p;
/* head為頭指針 */
head=new(struct LNode);
head->data=0;
/* 表頭結(jié)點(diǎn)數(shù)據(jù)域賦值 */
head->next=NULL;
cout<<“n請(qǐng)隨機(jī)輸入一組正整數(shù)以0結(jié)束輸入:n”;
cin>>x;/* 輸入第一個(gè)結(jié)點(diǎn)數(shù)據(jù)值 */
while(x!=0)
/* 輸入數(shù)據(jù)，以0為結(jié)束符 */
{ p=new(struct LNode);/* 生成新結(jié)點(diǎn) */
p->data=x;/* 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值 */
p->next=head->next;
/* 將新結(jié)點(diǎn)插入表頭結(jié)點(diǎn)head之后 */
head->next=p;
head->data++;
/* 鏈表長(zhǎng)度計(jì)數(shù) */
cin>>x;
}
return(head);} void output(Linklist *HeadL){
if(HeadL->next==NULL)cout<<“空鏈表!n”;else {
cout<<“鏈表為：n”;
Linklist *P;
P=HeadL->next;
while(P!=NULL)
{
cout<
data<<“->”;/* 函數(shù)返回鏈表頭指針head */ /* 輸入下一個(gè)結(jié)點(diǎn)的值 */
P=P->next;
}
cout<<“n”;} } Linklist *no_search(Linklist *head, int i){
Linklist *p;int j;
p=head->next;
j=1;
/* 從首結(jié)點(diǎn)開始掃描 */
while((p!=NULL)&&(j { p=p->next; /* 掃描下一個(gè)結(jié)點(diǎn) */ j++; } if(i==j)return(p); else return(NULL); /* 若找不到，則返回空指針 */ } Linklist *data_insert(Linklist *head, Linklist *p, int x){ Linklist *s; s =new(struct LNode);/* 建立新結(jié)點(diǎn) */ s->data=x; /* 將x值賦給s→data */ /* 統(tǒng)計(jì)已掃描結(jié)點(diǎn)的個(gè)數(shù) */ s->next=p->next;/* 新結(jié)點(diǎn)s后繼指向原p結(jié)點(diǎn)后繼 */ p->next=s; /* p結(jié)點(diǎn)的后繼指向新結(jié)點(diǎn)s */ return(head); /* 返回帶頭結(jié)點(diǎn)的單鏈表頭指針*/ } Linklist *key_delete(Linklist *head, int x){ Linklist *p, *q; /* p是被刪除結(jié)點(diǎn)，q是p的前驅(qū)結(jié)點(diǎn) */ p=head; while((p!=NULL)&&(p->data!=x)) { q=p; p=p->next; } if(p!=NULL) { q->next=p->next; /* 修改p前驅(qū)結(jié)點(diǎn)q指針域 */ /* 釋放結(jié)點(diǎn)空間 */ /* 若該結(jié)點(diǎn)存在，則刪除之 */ free(p); return(head); } /* 函數(shù)返回鏈表頭指針*/ else { cout<<“要?jiǎng)h的結(jié)點(diǎn)不存在，請(qǐng)重輸數(shù)據(jù)!n”; return(NULL); } } void main(void){ Linklist *List,*chazhao;List=creatlist();output(List);chazhao=no_search(List,2);//查找第二個(gè)節(jié)點(diǎn)，并輸出數(shù)據(jù)域信息 cout<<“n查找第二個(gè)節(jié)點(diǎn)，數(shù)據(jù)域信息為：n”;cout< output(List);List=key_delete(List,50);//刪除數(shù)據(jù)為50的節(jié)點(diǎn) cout<<“n刪除數(shù)據(jù)為50的節(jié)點(diǎn)：n”; output(List);} 《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告二 分校： 學(xué)號(hào)： 日期： 班級(jí)： 姓名： 程序名： L2311.CPP 一、上機(jī)實(shí)驗(yàn)的問題和要求： 單鏈表的查找、插入與刪除。設(shè)計(jì)算法，實(shí)現(xiàn)線性結(jié)構(gòu)上的單鏈表的產(chǎn)生以及元素的查找、插入與刪除。具體實(shí)現(xiàn)要求： 1.從鍵盤輸入20個(gè)整數(shù)，產(chǎn)生帶表頭的單鏈表，并輸入結(jié)點(diǎn)值。 2.從鍵盤輸入1個(gè)整數(shù)，在單鏈表中查找該結(jié)點(diǎn)。若找到，則顯示“找到了”；否則，則顯示“找不到”。 3.從鍵盤輸入2個(gè)整數(shù)，一個(gè)表示欲插入的位置i，另一個(gè)表示欲插入的數(shù)值x，將x插入在對(duì)應(yīng)位置上，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。4.從鍵盤輸入1個(gè)整數(shù)，表示欲刪除結(jié)點(diǎn)的位置，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。5.將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中個(gè)結(jié)點(diǎn)值均不相同，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。 6.刪除其中所有數(shù)據(jù)值為偶數(shù)的結(jié)點(diǎn)，輸出單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。 7.把單鏈表變成帶表頭結(jié)點(diǎn)的循環(huán)鏈表，輸出循環(huán)單鏈表所有結(jié)點(diǎn)值，觀察輸出結(jié)果。8.（★）將單鏈表分解成兩個(gè)單鏈表A和B，使A鏈表中含有原鏈表中序號(hào)為奇數(shù)的元素，而B鏈表中含有原鏈表中序號(hào)為偶數(shù)的元素，且保持原來(lái)的相對(duì)順序，分別輸出單鏈表A和單鏈表B的所有結(jié)點(diǎn)值，觀察輸出結(jié)果。 二、程序設(shè)計(jì)的基本思想，原理和算法描述： （包括程序的結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，輸入/輸出設(shè)計(jì)，符號(hào)名說(shuō)明等） 三、源程序及注釋： 四、運(yùn)行輸出結(jié)果： 五、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施： 六、對(duì)算法的程序的討論、分析，改進(jìn)設(shè)想，其它經(jīng)驗(yàn)教訓(xùn)： 七、對(duì)實(shí)驗(yàn)方式、組織、設(shè)備、題目的意見和建議： 第三章 單文檔應(yīng)用程序 在本學(xué)習(xí)情境中主要學(xué)習(xí)：（1）單文檔應(yīng)用框架（2）文檔與視圖 3.1 MFC消息處理 3.1.1事件驅(qū)動(dòng)程序設(shè)計(jì) 事件驅(qū)動(dòng)程序設(shè)計(jì)是一種全新的程序設(shè)計(jì)方法，它不是由事件的順序來(lái)控制，而是由事件的發(fā)生來(lái)控制，而這種事件的發(fā)生是隨機(jī)的、不確定的，并沒有預(yù)定的順序，這樣就允許程序的的用戶用各種合理的順序來(lái)安排程序的流程。對(duì)于需要用戶交互的應(yīng)用程序來(lái)說(shuō)，事件驅(qū)動(dòng)的程序設(shè)計(jì)有著過程驅(qū)動(dòng)方法無(wú)法替代的優(yōu)點(diǎn)。它是一種面向用戶的程序設(shè)計(jì)方法，它在程序設(shè)計(jì)過程中除了完成所需功能之外，更多的考慮了用戶可能的各種輸入，并針對(duì)性的設(shè)計(jì)相應(yīng)的處理程序。它是一種“被動(dòng)”式程序設(shè)計(jì)方法，程序開始運(yùn)行時(shí)，處于等待用戶輸入事件狀態(tài)，然后取得事件并作出相應(yīng)反應(yīng)，處理完畢又返回并處于等待事件狀態(tài)。它的框圖如圖1所示: 圖1事件驅(qū)動(dòng)程序模型 3.1.2 MFC的消息處理 在DOS應(yīng)用程序下，可以通過getchar()、getch()等函數(shù)直接等待鍵盤輸入，并直接向屏幕輸出。而在Windows下，由于允許多個(gè)任務(wù)同時(shí)運(yùn)行，應(yīng)用程序的輸入輸出是由Windows來(lái)統(tǒng)一管理的。 Windows操作系統(tǒng)包括三個(gè)內(nèi)核基本元件：GDI, KERNEL ,USER。其中GDI(圖形設(shè)備接口)負(fù)責(zé)在屏幕上繪制像素、打印硬拷貝輸出，繪制用戶界面包括窗口、菜單、對(duì)話框等。系統(tǒng)內(nèi)核KERNEL支持與操作系統(tǒng)密切相關(guān)的功能：如進(jìn)程加載，文本切換、文件I/O，以及內(nèi)存管理、線程管理等。USER為所有的用戶界面對(duì)象提供支持，它用于接收和管理所有輸入消息、系統(tǒng)消息并把它們發(fā)給相應(yīng)的窗口的消息隊(duì)列。消息隊(duì)列是一個(gè)系統(tǒng)定義的內(nèi)存塊，用于臨時(shí)存儲(chǔ)消息；或是把消息直接發(fā)給窗口過程。每個(gè)窗口維護(hù)自己的消息隊(duì)列，并從中取出消息，利用窗口函數(shù)進(jìn)行處理。框圖2如下： 圖2 消息驅(qū)動(dòng)模型 從消息的發(fā)送途徑上看，消息分兩種：隊(duì)列消息和非隊(duì)列消息。隊(duì)列消息送到系統(tǒng)消息隊(duì)列，然后到線程消息隊(duì)列；非隊(duì)列消息直接送給目的窗口過程。 Windows維護(hù)一個(gè)系統(tǒng)消息隊(duì)列（System message queue），每個(gè)GUI線程有一個(gè)線程消息隊(duì)列（Thread message queue）。 鼠標(biāo)、鍵盤事件由鼠標(biāo)或鍵盤驅(qū)動(dòng)程序轉(zhuǎn)換成輸入消息并把消息放進(jìn)系統(tǒng)消息隊(duì)列，例如WM_MOUSEMOVE、WM_LBUTTONUP、WM_KEYDOWN、WM_CHAR等等。Windows每次從系統(tǒng)消息隊(duì)列移走一個(gè)消息，確定它是送給哪個(gè)窗口的和這個(gè)窗口是由哪個(gè)線程創(chuàng)建的，然后，把它放進(jìn)窗口創(chuàng)建線程的線程消息隊(duì)列。線程消息隊(duì)列接收送給該線程所創(chuàng)建窗口的消息。線程從消息隊(duì)列取出消息，通過Windows把它送給適當(dāng)?shù)拇翱谶^程來(lái)處理。 除了鍵盤、鼠標(biāo)消息以外，隊(duì)列消息還有WM_PAINT、WM_TIMER和WM_QUIT。這些隊(duì)列消息以外的絕大多數(shù)消息是非隊(duì)列消息。 通過消息映射,我們可以把消息和它的消息處理函數(shù)聯(lián)系起來(lái)。VC++為我們提供了Class Wizard 來(lái)為用戶添加一個(gè)消息映射關(guān)系,而用戶只需編寫該消息發(fā)生響應(yīng)的函數(shù)即可。 從View菜單中選擇“ClassWizard”命令，便可調(diào)出如圖3所示的ClassWizard對(duì)話框，它一共分為五個(gè)選項(xiàng)卡，依次分別是消息映射、成員變量、自動(dòng)化、ActiveX事件和類信息。最常用的是消息映射和成員變量?jī)蓚€(gè)選項(xiàng)卡，如果程序中使用了ActiveX控件，那么還需要使用ActiveX事件選項(xiàng)卡來(lái)添加事件處理函數(shù)，類信息選項(xiàng)卡可用來(lái)了解各個(gè)類的文件名、基類和資源等信息，自動(dòng)化選項(xiàng)卡只有在編寫OLE自動(dòng)化服務(wù)器時(shí)才用得著。下面我們就來(lái)看看消息映射和成員變量?jī)蓚€(gè)選項(xiàng)卡的特點(diǎn)和用途。 消息映射選項(xiàng)卡主要用途是為選中的類添加消息處理函數(shù)。其中，Projects組合框用于選擇Workspace中的一個(gè)工程，Class name組合框用于選擇工程中的一個(gè)類。Objects IDs中列出了所選擇的類的名稱及屬于它的一系列ID，對(duì)于CXXXView類來(lái)說(shuō)，列出的ID基本上都是菜單命令，對(duì)于一個(gè)對(duì)話框類來(lái)說(shuō)，列出的ID多數(shù)對(duì)應(yīng)著對(duì)話框模板中的控件。 從Objects IDs選擇不同的類名或ID后，右邊的Messages列表框中的內(nèi)容也會(huì)跟著改變，選中類名時(shí)，Messages列表框中會(huì)顯示出所有該類能處理的標(biāo)準(zhǔn)Windows消息以及該類可以重載的成員函數(shù)，選中一個(gè)ID時(shí)，Messages列表框中會(huì)顯示出這個(gè)ID對(duì)應(yīng)的對(duì)象（菜單選項(xiàng)或控件）所能引發(fā)的命令消息和通知消息。在Messages列表框中選擇一條消息（或一個(gè)可以重載的成員函數(shù)）后，如果該消息還沒有相應(yīng)的消息處理函數(shù)（或還未重載該成員函數(shù)），那么ClassWizard對(duì)話框右上角的Add Function按鈕就會(huì)變?yōu)橛行?，提示我們可以添加一個(gè)消息處理函數(shù)（或重載該成員函數(shù)），按下Add Function按鈕后，ClassWizard就會(huì)在所選的類中添加一個(gè)處理函數(shù)（為一個(gè)ID添加處理函數(shù)時(shí)，還會(huì)彈出一個(gè)對(duì)話框，要求輸入函數(shù)名），并在Member funtions列表框中顯示出剛添加的函數(shù)，在這個(gè)列表框中雙擊該函數(shù)名后，ClassWizard對(duì)話框?qū)⒆詣?dòng)關(guān)閉，文本編輯器會(huì)定位在函數(shù)的實(shí)現(xiàn)代碼處，這些代碼及它在類定義中的聲明都是由ClassWizard自動(dòng)生成的。 圖 3Class wizard 對(duì)話框 Member functions列表框并沒有列出類的所有成員函數(shù)，而只是列出了消息處理函數(shù)和重載的成員函數(shù)，其中每個(gè)函數(shù)的左邊都有一個(gè)小圖標(biāo)，如果小圖標(biāo)為“W”字樣，表示該函數(shù)是一個(gè)消息處理函數(shù)，除了Add function按鈕外，消息映射選項(xiàng)卡中還有三個(gè)按鈕，其中Delete Function用來(lái)刪除一個(gè)消息處理函數(shù)或重載的成員函數(shù)，但是此按鈕只能刪除函數(shù)在類定義中的聲明，函數(shù)的實(shí)現(xiàn)代碼還需要手工來(lái)刪除；Edit Code按鈕的用途相當(dāng)于在Member functions中雙擊一個(gè)成員函數(shù)；Add Class按鈕則可用于向工程中添加一個(gè)新的類。3.1.3 文檔與視圖 先利用Appwizard 來(lái)新建一個(gè)單文檔工程。在SDI框架程序中，主要包含四個(gè)類： 主框架類：CMainFrame用于管理主程序窗口，從MFC 類的CFrameWnd派生。 應(yīng)用類：CXXXApp負(fù)責(zé)初始化及程序結(jié)束前的整理工作，從MFC 類的CWinApp派生。 文檔類：CXXXDoc負(fù)責(zé)存放程序數(shù)據(jù)和在磁盤上讀寫數(shù)據(jù)，從MFC 類的CDocment派生。 視圖類：CXXXView負(fù)責(zé)數(shù)據(jù)的顯示及處理用戶的輸入，從MFC類的CView派生。用戶對(duì)話框類：CAboutDlg負(fù)責(zé)用戶對(duì)話框的設(shè)置，從MFC類的CDialog類派生。 文檔是存儲(chǔ)的對(duì)象.文檔類負(fù)責(zé)數(shù)據(jù)的維護(hù)，包括數(shù)據(jù)的讀取、存儲(chǔ)和修改，并將更改的數(shù)據(jù)通知相關(guān)視圖，另外它還負(fù)責(zé)將數(shù)據(jù)存儲(chǔ)到文件及從文件中讀取數(shù)據(jù)。 文檔是一種數(shù)據(jù)源，數(shù)據(jù)源有很多種，最常見的是磁盤文件，但它不必是一個(gè)磁盤文件，文檔的數(shù)據(jù)源也可以來(lái)自串行口、網(wǎng)絡(luò)或攝像機(jī)輸入信號(hào)等。文檔對(duì)象負(fù)責(zé)來(lái)自所有數(shù)據(jù)源的數(shù)據(jù)的管理。 視圖類的作用是與用戶交互。視圖對(duì)象負(fù)責(zé)對(duì)保存在文擋對(duì)象中的數(shù)據(jù)以某種方式進(jìn)行顯示，并接受用戶的輸入，將這些輸入交文擋類進(jìn)行處理。 視圖是數(shù)據(jù)的用戶窗口，為用戶提供了文檔的可視的數(shù)據(jù)顯示，它把文檔的部分或全部?jī)?nèi)容在窗口中顯示出來(lái)。視圖還給用戶提供了一個(gè)與文檔中的數(shù)據(jù)交互的界面，它把用戶的輸入轉(zhuǎn)化為對(duì)文檔中數(shù)據(jù)的操作。每個(gè)文檔都會(huì)有一個(gè)或多個(gè)視圖顯示，一個(gè)文檔可以有多個(gè)不同的視圖。比如，在Excel電子表格中，我們可以將數(shù)據(jù)以表格方式顯示，也可以將數(shù)據(jù)以圖表方式顯示。一個(gè)視圖既可以輸出到窗口中，也可以輸出到打印機(jī)上。 圖 文檔與視圖關(guān)系 3.1.4 鼠標(biāo)消息舉例 我們先通過一個(gè)例子來(lái)說(shuō)明如何用class wizard 來(lái)實(shí)現(xiàn)捕獲鼠標(biāo)消息,進(jìn)行消息映射和定義消息處理函數(shù).利用class wizard來(lái)設(shè)置消息選項(xiàng)。選擇ClassName中的CXXXView，選擇其中相對(duì)應(yīng)的WM_LBUTTONDOWN，雙擊選中的消息，單擊Edit Code 按紐，如圖4所示，并增加相關(guān)代碼，如圖5所示。 圖4 增加鼠標(biāo)消息映射 圖5 增加代碼 圖6 運(yùn)行結(jié)果 3.1.4鍵盤消息舉例 鍵盤的輸入是從掃描碼開始的,windows鍵盤驅(qū)動(dòng)程序?qū)⑦@些掃描碼轉(zhuǎn)換成為與硬件無(wú)關(guān)的形式,即虛擬鍵碼.WM_CHAR:此消息在鍵被按下時(shí)產(chǎn)生,通常用于處理非打印鍵中的按鍵消息.圖7 在工程中增加相關(guān)變量 圖8 增加變量Text 圖9 初始化變量為空 圖10 增加鍵盤的消息影射 圖11 編寫Onchar處理函數(shù) 圖12 輸出接收到的字符 圖13 運(yùn)行結(jié)果 為了能夠?qū)崿F(xiàn)輸入字符的換行功能，在CXXXDoc類中增加一個(gè)用來(lái)計(jì)算行數(shù)的成員變量m_Line,如圖14所示，并初始化變量m_Line，如圖15所示。 圖 增加成員變量 圖15 初始化成員變量 為了保存字符串行的數(shù)據(jù)，定義一個(gè)字符串列表變量m_strList，如圖16所示。 圖16 定義字符串列表變量 修改CXXXView類中的OnChar函數(shù)，如下所示。 void CSDIView::OnChar(UINT nChar, UINT nRepCnt, UINT nFlags){ // TODO: Add your message handler code here and/or call default CSDIDoc *pDoc=GetDocument();ASSERT_VALID(pDoc); } if(nChar==VK_RETURN){ pDoc->m_Line++;pDoc->m_strList.AddTail(pDoc->Text);pDoc->Text.Empty(); Invalidate();} else { pDoc->Text+=nChar; CClientDC dc(this); TEXTMETRIC tm; dc.GetTextMetrics(&tm); int nLineHeight=tm.tmHeight+tm.tmExternalLeading; dc.TextOut(0,pDoc->m_Line*nLineHeight,pDoc->Text);} CView::OnChar(nChar, nRepCnt, nFlags);為了保證能夠?qū)XXXDoc類中m_strList的數(shù)據(jù)輸出出來(lái)，增加一個(gè)DrawText函數(shù)，如圖17所示和圖18所示。 圖17 在CXXXDoc類中增加成員函數(shù) 圖18 增加DrawText函數(shù) 實(shí)現(xiàn)CXXXDoc類中的DrawText函數(shù)，如下所示。void CSDIDoc::DrawText(CDC *pDC){ TEXTMETRIC tm; CString str;int line=0; pDC->GetTextMetrics(&tm); int nLineHeight=tm.tmHeight+tm.tmExternalLeading; POSITION pos=m_strList.GetHeadPosition();for(;pos!=NULL;m_strList.GetNext(pos)){ str=m_strList.GetAt(pos); pDC->TextOut(0,line*nLineHeight,str); line++;} } 修改CXXXView類中的OnDraw函數(shù)，如下所示。 void CSDIView::OnDraw(CDC* pDC){ CSDIDoc* pDoc = GetDocument();ASSERT_VALID(pDoc); pDoc->DrawText(pDC); // TODO: add draw code for native data here } 北京郵電大學(xué) 數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告 實(shí)驗(yàn)名稱： 實(shí)驗(yàn)一 線性表 學(xué)生姓名： 班 級(jí)： 班內(nèi)序號(hào)： 學(xué) 號(hào)： 日 期： 2014年1月3日 實(shí)驗(yàn)?zāi)康?/p> ? 熟悉C++語(yǔ)言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法 ? 學(xué)習(xí)指針、模板類、異常處理的使用 ? 掌握線性表的操作的實(shí)現(xiàn)方法 ? 學(xué)習(xí)使用線性表解決實(shí)際問題的能力 實(shí)驗(yàn)內(nèi)容 2.1題目1 根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表，并完成線性表的基本功能。 線性表存儲(chǔ)結(jié)構(gòu)（五選一）： 1、帶頭結(jié)點(diǎn)的單鏈表 2、不帶頭結(jié)點(diǎn)的單鏈表 3、循環(huán)鏈表 4、雙鏈表 5、靜態(tài)鏈表 線性表的基本功能： 1、構(gòu)造：使用頭插法、尾插法兩種方法 2、插入：要求建立的鏈表按照關(guān)鍵字從小到大有序 3、刪除 4、查找 5、獲取鏈表長(zhǎng)度 6、銷毀 7、其他：可自行定義 編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性。程序分析 3.1 存儲(chǔ)結(jié)構(gòu) 單鏈表的存儲(chǔ)結(jié)構(gòu)： 3.2 關(guān)鍵算法分析 一、關(guān)鍵算法 1.頭插法 自然語(yǔ)言描述：a.在堆中建立新結(jié)點(diǎn) b.將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域 c.修改新結(jié)點(diǎn)的指針域 d.修改頭結(jié)點(diǎn)的指針域,將新結(jié)點(diǎn)加入鏈表中 代碼描述： template front = new Node } } s->next = front->next;front->next = s;時(shí)間復(fù)雜度：O(n) 2.尾插法 自然語(yǔ)言描述：a.在堆中建立新結(jié)點(diǎn) b.將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域 c.將新結(jié)點(diǎn)加入到鏈表中 d.修改修改尾指針 代碼描述: template front = new Node } } s->data = a[i];s->next = r->next;r->next= s;r=s;時(shí)間復(fù)雜度：O(n) 3.析構(gòu)函數(shù) 自然語(yǔ)言描述：a.新建立一個(gè)指針，指向頭結(jié)點(diǎn) b.移動(dòng)a中建立的指針 c.逐個(gè)釋放指針 代碼描述: template Node } } delete front;4.按位查找函數(shù) 自然語(yǔ)言描述: a.初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1 b.循環(huán)以下操作，直到p為空或者j等于1 b1：p指向下一個(gè)結(jié)點(diǎn) b2：j加1 c.若p為空，說(shuō)明第i個(gè)元素不存在，拋出異常 d.否則，說(shuō)明p指向的元素就是所查找的元素，返回元素地址 代碼描述: template Node if(j } else break;p = p->next;j++; } if(!p)throw“查找位置非法”;else return p;} 時(shí)間復(fù)雜度：O(n) 5.按值查找函數(shù) 自然語(yǔ)言描述：a.初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1 b.循環(huán)以下操作，找到這個(gè)元素或者p指向最后一個(gè)結(jié)點(diǎn) b1.判斷p指向的結(jié)點(diǎn)是不是要查找的值，如果是，返回j; b2.否則p指向下一個(gè)結(jié)點(diǎn),并且j的值加一 c.如果找到最后一個(gè)結(jié)點(diǎn)還沒有找到要查找的元素，返回查找失敗信息 代碼描述: template Node } return-1;if(p->data == x)return j;else { p = p->next; j++;} } 時(shí)間復(fù)雜度：O(n)6.插入函數(shù) 自然語(yǔ)言描述： a.在堆中建立新結(jié)點(diǎn) b.將要插入的結(jié)點(diǎn)的數(shù)據(jù)寫入到新結(jié)點(diǎn)的數(shù)據(jù)域 c.修改新結(jié)點(diǎn)的指針域 d.修改前一個(gè)指針的指針域，使其指向新插入的結(jié)點(diǎn)的位置 代碼描述: template Node } else throw“插入位置非法”;Node 自然語(yǔ)言描述：a.從第一個(gè)結(jié)點(diǎn)開始，查找要?jiǎng)h除的位數(shù)i前一個(gè)位置i-1的結(jié)點(diǎn) b.設(shè)q指向第i個(gè)元素 c.將q元素從鏈表中刪除 d.保存q元素的數(shù)據(jù) e.釋放q元素 代碼描述: template T x=q->data; } p->next = q->next;delete q;return x; 8.遍歷打印函數(shù) 自然語(yǔ)言描述: a.判斷該鏈表是否為空鏈表，如果是，報(bào)錯(cuò) b.如果不是空鏈表，新建立一個(gè)temp指針 c.將temp指針指向頭結(jié)點(diǎn) d.打印temp指針的data域 e.逐個(gè)往后移動(dòng)temp指針，直到temp指針的指向的指針的next域?yàn)榭?/p> 代碼描述: template } Node } cout< 自然語(yǔ)言描述： a.判斷該鏈表是否為空鏈表，如果是，輸出長(zhǎng)度0 b.如果不是空鏈表，新建立一個(gè)temp指針，初始化整形數(shù)n為0 c.將temp指針指向頭結(jié)點(diǎn) d.判斷temp指針指向的結(jié)點(diǎn)的next域是否為空，如果不是，n加一，否則return n e.使temp指針逐個(gè)后移，重復(fù)d操作，直到temp指針指向的結(jié)點(diǎn)的next域?yàn)?，返回n 代碼描述: template } Node } return i-1;p = p->next;i++;4 程序運(yùn)行結(jié)果 4.1主函數(shù)流程圖 4.2程序運(yùn)行框圖 實(shí)驗(yàn)心得 1.調(diào)試時(shí)出現(xiàn)的問題及解決的方法 在編寫按值查找函數(shù)時(shí)，由于沒有處理好指針類型的原因，導(dǎo)致指針無(wú)法正常返回，屢屢報(bào)錯(cuò)。最后意識(shí)到c++沒有指針強(qiáng)制類型的轉(zhuǎn)換機(jī)制，經(jīng)過細(xì)致檢查后才改正錯(cuò)誤使得程序正常運(yùn)行。2.心得體會(huì) 了解了單鏈表的基本的操作函數(shù)實(shí)現(xiàn)，對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有了較好的認(rèn)識(shí) 3.下一步的改進(jìn) 可以增加完善報(bào)錯(cuò)機(jī)制，增強(qiáng)程序的健壯性 完整源代碼 #include template }; template }; //template Node template } template } template } front = p;p = p->next;delete front;front = new Node } Node } Node } Node } cout< template } template } Node } return-1;if(p->data == x)return j;else { } p = p->next; j++;Node } if(!p)throw“查找位置非法”;else return p;if(j } else break;p = p->next;j++; template } template } template } void main(){ Node } return i-1;p = p->next;i++;Node } else throw“插入位置非法”;Node T x=q->data; } int n;cout<<“將要輸入的鏈表長(zhǎng)度為：”;cin>>n;int *b=new int[n];cout<<“輸入鏈表中的元素：”;for(int k=0;k 求解Josephus問題實(shí)驗(yàn)總結(jié) 1實(shí)驗(yàn)題目: josephus問題可描述如下： 設(shè)有n個(gè)人圍成一個(gè)環(huán)，現(xiàn)從第s個(gè)人開始報(bào)數(shù)，數(shù)到第m的人出列，然后從出列的下一個(gè)人從新開始報(bào)數(shù)，數(shù)到第m的人又出列，如此重復(fù)，直至所有人均出列為止。求這些人出列的順序。 2實(shí)驗(yàn)?zāi)康模?/p> 熟練掌握線性表的順序?qū)崿F(xiàn)和鏈?zhǔn)綄?shí)現(xiàn)的基本操作。 3實(shí)驗(yàn)方法： 通過運(yùn)用已學(xué)的向量和循環(huán)單鏈表編寫程序，并在電腦上運(yùn)行，實(shí)現(xiàn)josephus問題的求解。4實(shí)驗(yàn)過程與結(jié)果： （1）輸入n值為6，s值為3，m值為2，輸入A[i]的值為1 2 3 4 5 6 輸出結(jié) 果為：4 6 2 5 3 1 截圖如下： （2） 1、輸入n值為-1, s值為3，m值為2，顯示：ERROR。截圖如下： 2、輸入n值為6, s值為0，m值為3，顯示：ERROR。截圖如下： 3、輸入n值為6, s值為3，m值為0，顯示：ERROR。截圖如下 ： 5試驗(yàn)體會(huì)與收獲： （1）寫程序是要隨時(shí)注意縮進(jìn)，使得程序?qū)哟吻逦阌趯ふ义e(cuò)誤，同時(shí)也讓別人看的更加方便。（2）構(gòu)造循環(huán)單鏈表，要以單鏈表為單元指針指向把最后個(gè)單元與第一個(gè)即可（3）建立好循環(huán)單鏈表后，通過三個(gè)指針（p,q,tmp）的指示，來(lái)確定報(bào)數(shù)，出列人的位置，得以完成。具體過程如下：p指向head頭指針,通過s次循環(huán)將p指向報(bào)數(shù)的起始位置s，用q記錄p的位置，再經(jīng)過m次循環(huán)另p指向出列者的位置，將其數(shù)值保存在一維數(shù)組中，并將其從鏈表中刪除，p指向下一次起始位置，結(jié)束時(shí)返回?cái)?shù)組A[j]。（4）刪除節(jié)點(diǎn)時(shí)，注意要釋放節(jié)點(diǎn)。 （5）構(gòu)造函數(shù)時(shí)，一定要明確函數(shù)的類型，即返回行還是不返回型，以免出現(xiàn)不必要的錯(cuò)誤。第二篇：?jiǎn)捂湵韺?shí)驗(yàn)報(bào)告
第三篇：第三章 單文檔應(yīng)用程序
第四篇：北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 單鏈表
第五篇：求解Josephus問題實(shí)驗(yàn)總結(jié)(用C語(yǔ)言循環(huán)單鏈表實(shí)現(xiàn))
點(diǎn)擊咨詢 