第一篇：實驗四 單鏈表及其應(yīng)用(參考程序)

實驗四 單鏈表的建立

一、實驗?zāi)康?/p>

1.掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表的定義及C語言實現(xiàn)。2.掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)——單鏈表中的各種基本操作。

二、實驗內(nèi)容

1.建立一個帶頭結(jié)點的單鏈表，結(jié)點的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)分別按尾插入法和頭插法來建立相應(yīng)單鏈表。【知識要點】

為了便于實現(xiàn)各種運(yùn)算，通常在單鏈表的第一個結(jié)點前增設(shè)一個附加結(jié)點，稱為頭結(jié)點，它的結(jié)構(gòu)與表結(jié)點相同，其數(shù)據(jù)域可不存儲信息，也可存儲表長等附加信息，具體如下圖。

【實驗提示】

單鏈表的結(jié)點結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個指針域。用C語言描述結(jié)點結(jié)構(gòu)如下：

typedef int datatype;

/* 線性表中存放整型元素 */ typedef struct LNode

/ * 結(jié)點類型定義 * /

{

datatype data;

/ * 數(shù)據(jù)域 * /

struct node *next;

/ * 指針域 * / }Linklist；

/* Linklist為單鏈表類型*/

注意結(jié)點的建立方法及構(gòu)造新結(jié)點時指針的變化。構(gòu)造一個結(jié)點需用到C語言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個結(jié)點的地址：

p=(strcut LNode *)malloc(sizeof(Linklist));該語句的功能是申請分配一個類型為Linklist的結(jié)點的地址空間，并將首地址存入指針變量p中(或p=new(struct LNode);即生成新結(jié)點)。當(dāng)結(jié)點不需要時可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點存儲空間，這時p為空值（NULL）。【程序提示】

#include typedef struct LNode{

//補(bǔ)充實現(xiàn)表節(jié)點類型的定義； } Linklist;

Linklist * creatlist(){ int x;Linklist *head, *p;// head為單鏈表的頭指針，p指向新建的結(jié)點

//補(bǔ)充實現(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 typedef struct LNode{ int data;struct LNode *next;} Linklist;

Linklist * creatlist(){ int x;

Linklist *head, *p,*r;/* head為頭指針 */

head=new(struct LNode);

head->data=0;

/* 表頭結(jié)點數(shù)據(jù)域賦值 */

r=head;

/* 尾指針的初值為頭結(jié)點head */

printf(“請隨機(jī)輸入互不相同的正整數(shù)以0作為結(jié)束符:n”);

scanf(“%d”, &x);

/* 讀入第一個結(jié)點的值 */

while(x!=0)

/* 輸入數(shù)據(jù)，以0為結(jié)束符 */ { p=new(struct LNode);/* 生成新結(jié)點 */

p->data=x;

/* 給新結(jié)點的數(shù)據(jù)域賦值 */

r->next=p;

/* 新結(jié)點插入到表尾*rear之后 */

r=p;

/* 將尾指針rear指向新的尾結(jié)點 */

head->data++;

/* 鏈表長度計數(shù) */

scanf(“%d”, &x);

/* 輸入下一個結(jié)點的數(shù)據(jù) */

}

r->next=NULL;

/* 將鏈表最后一個結(jié)點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 typedef struct LNode{ int data;struct LNode *next;} Linklist;

Linklist * creatlist(){ int x;

Linklist *head, *p;/* head為頭指針 */

head=new(struct LNode);

head->data=0;

/* 表頭結(jié)點數(shù)據(jù)域賦值 */

head->next=NULL;

printf(“n請隨機(jī)輸入一組正整數(shù)以0結(jié)束輸入:n”);

scanf(“%d”,&x);

/* 輸入第一個結(jié)點數(shù)據(jù)值 */

while(x!=0)

/* 輸入數(shù)據(jù)，以0為結(jié)束符 */

{ p=new(struct LNode);/* 生成新結(jié)點 */

p->data=x;/* 給新結(jié)點的數(shù)據(jù)域賦值 */

p->next=head->next;

/* 將新結(jié)點插入表頭結(jié)點head之后 */

head->next=p;

head->data++;

/* 鏈表長度計數(shù) */

scanf(“%d”,&x);

/* 輸入下一個結(jié)點的值 */

}

return(head);/* 函數(shù)返回鏈表頭指針head */ }

void output(Linklist *HeadL){

} void main(void){

Linklist *List;List=creatlist();output(List);}

方法二 void main(void){

} 2.在第一題的基礎(chǔ)上，增加單鏈表的查找，插入，刪除子程序。#include #include“stdlib.h”

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é)點數(shù)據(jù)域賦值 */

head->next=NULL;

cout<<“n請隨機(jī)輸入一組正整數(shù)以0結(jié)束輸入:n”;

cin>>x;/* 輸入第一個結(jié)點數(shù)據(jù)值 */

while(x!=0)

/* 輸入數(shù)據(jù)，以0為結(jié)束符 */

{ p=new(struct LNode);/* 生成新結(jié)點 */

p->data=x;/* 給新結(jié)點的數(shù)據(jù)域賦值 */

p->next=head->next;

/* 將新結(jié)點插入表頭結(jié)點head之后 */

head->next=p;

head->data++;

/* 鏈表長度計數(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 */ /* 輸入下一個結(jié)點的值 */

P=P->next;

}

cout<<“n”;} } Linklist *no_search(Linklist *head, int i){

Linklist *p;int j;

p=head->next;

j=1;

/* 從首結(jié)點開始掃描 */

while((p!=NULL)&&(j

{ p=p->next;

/* 掃描下一個結(jié)點 */

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é)點 */

s->data=x;

/* 將x值賦給s→data */

/* 統(tǒng)計已掃描結(jié)點的個數(shù) */

s->next=p->next;/* 新結(jié)點s后繼指向原p結(jié)點后繼 */

p->next=s;

/* p結(jié)點的后繼指向新結(jié)點s */

return(head);

/* 返回帶頭結(jié)點的單鏈表頭指針*/ } Linklist *key_delete(Linklist *head, int x){

Linklist *p, *q;

/* p是被刪除結(jié)點，q是p的前驅(qū)結(jié)點 */

p=head;

while((p!=NULL)&&(p->data!=x))

{

q=p;

p=p->next;

}

if(p!=NULL)

{

q->next=p->next;

/* 修改p前驅(qū)結(jié)點q指針域 */

/* 釋放結(jié)點空間 */

/* 若該結(jié)點存在，則刪除之 */

free(p);

return(head);

}

/* 函數(shù)返回鏈表頭指針*/

else

{

cout<<“要刪的結(jié)點不存在，請重輸數(shù)據(jù)!n”;

return(NULL);

} }

void main(void){

Linklist *List,*chazhao;List=creatlist();output(List);chazhao=no_search(List,2);//查找第二個節(jié)點，并輸出數(shù)據(jù)域信息 cout<<“n查找第二個節(jié)點，數(shù)據(jù)域信息為：n”;cout<data;List=data_insert(List,chazhao,50);//在第二個節(jié)點后插入數(shù)據(jù)為50的節(jié)點 cout<<“n在第二個節(jié)點后插入數(shù)據(jù)為50的節(jié)點：n”;

output(List);List=key_delete(List,50);//刪除數(shù)據(jù)為50的節(jié)點 cout<<“n刪除數(shù)據(jù)為50的節(jié)點：n”;

output(List);}

第二篇：單鏈表實驗報告

《數(shù)據(jù)結(jié)構(gòu)》實驗報告二

分校：

學(xué)號：

日期：

班級：

姓名：

程序名： L2311.CPP

一、上機(jī)實驗的問題和要求：

單鏈表的查找、插入與刪除。設(shè)計算法，實現(xiàn)線性結(jié)構(gòu)上的單鏈表的產(chǎn)生以及元素的查找、插入與刪除。具體實現(xiàn)要求：

1.從鍵盤輸入20個整數(shù)，產(chǎn)生帶表頭的單鏈表，并輸入結(jié)點值。

2.從鍵盤輸入1個整數(shù)，在單鏈表中查找該結(jié)點。若找到，則顯示“找到了”；否則，則顯示“找不到”。

3.從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i，另一個表示欲插入的數(shù)值x，將x插入在對應(yīng)位置上，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。4.從鍵盤輸入1個整數(shù)，表示欲刪除結(jié)點的位置，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。5.將單鏈表中值重復(fù)的結(jié)點刪除，使所得的結(jié)果表中個結(jié)點值均不相同，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。

6.刪除其中所有數(shù)據(jù)值為偶數(shù)的結(jié)點，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。

7.把單鏈表變成帶表頭結(jié)點的循環(huán)鏈表，輸出循環(huán)單鏈表所有結(jié)點值，觀察輸出結(jié)果。8.（★）將單鏈表分解成兩個單鏈表A和B，使A鏈表中含有原鏈表中序號為奇數(shù)的元素，而B鏈表中含有原鏈表中序號為偶數(shù)的元素，且保持原來的相對順序，分別輸出單鏈表A和單鏈表B的所有結(jié)點值，觀察輸出結(jié)果。

二、程序設(shè)計的基本思想，原理和算法描述：

（包括程序的結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，輸入/輸出設(shè)計，符號名說明等）

三、源程序及注釋：

四、運(yùn)行輸出結(jié)果：

五、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：

六、對算法的程序的討論、分析，改進(jìn)設(shè)想，其它經(jīng)驗教訓(xùn)：

七、對實驗方式、組織、設(shè)備、題目的意見和建議：

第三篇：第三章 單文檔應(yīng)用程序

第三章 單文檔應(yīng)用程序

在本學(xué)習(xí)情境中主要學(xué)習(xí)：（1）單文檔應(yīng)用框架（2）文檔與視圖

3.1 MFC消息處理

3.1.1事件驅(qū)動程序設(shè)計

事件驅(qū)動程序設(shè)計是一種全新的程序設(shè)計方法，它不是由事件的順序來控制，而是由事件的發(fā)生來控制，而這種事件的發(fā)生是隨機(jī)的、不確定的，并沒有預(yù)定的順序，這樣就允許程序的的用戶用各種合理的順序來安排程序的流程。對于需要用戶交互的應(yīng)用程序來說，事件驅(qū)動的程序設(shè)計有著過程驅(qū)動方法無法替代的優(yōu)點。它是一種面向用戶的程序設(shè)計方法，它在程序設(shè)計過程中除了完成所需功能之外，更多的考慮了用戶可能的各種輸入，并針對性的設(shè)計相應(yīng)的處理程序。它是一種“被動”式程序設(shè)計方法，程序開始運(yùn)行時，處于等待用戶輸入事件狀態(tài)，然后取得事件并作出相應(yīng)反應(yīng)，處理完畢又返回并處于等待事件狀態(tài)。它的框圖如圖1所示:

圖1事件驅(qū)動程序模型

3.1.2 MFC的消息處理

在DOS應(yīng)用程序下，可以通過getchar()、getch()等函數(shù)直接等待鍵盤輸入，并直接向屏幕輸出。而在Windows下，由于允許多個任務(wù)同時運(yùn)行，應(yīng)用程序的輸入輸出是由Windows來統(tǒng)一管理的。

Windows操作系統(tǒng)包括三個內(nèi)核基本元件：GDI, KERNEL ,USER。其中GDI(圖形設(shè)備接口)負(fù)責(zé)在屏幕上繪制像素、打印硬拷貝輸出，繪制用戶界面包括窗口、菜單、對話框等。系統(tǒng)內(nèi)核KERNEL支持與操作系統(tǒng)密切相關(guān)的功能：如進(jìn)程加載，文本切換、文件I/O，以及內(nèi)存管理、線程管理等。USER為所有的用戶界面對象提供支持，它用于接收和管理所有輸入消息、系統(tǒng)消息并把它們發(fā)給相應(yīng)的窗口的消息隊列。消息隊列是一個系統(tǒng)定義的內(nèi)存塊，用于臨時存儲消息；或是把消息直接發(fā)給窗口過程。每個窗口維護(hù)自己的消息隊列，并從中取出消息，利用窗口函數(shù)進(jìn)行處理。框圖2如下：

圖2 消息驅(qū)動模型

從消息的發(fā)送途徑上看，消息分兩種：隊列消息和非隊列消息。隊列消息送到系統(tǒng)消息隊列，然后到線程消息隊列；非隊列消息直接送給目的窗口過程。

Windows維護(hù)一個系統(tǒng)消息隊列（System message queue），每個GUI線程有一個線程消息隊列（Thread message queue）。

鼠標(biāo)、鍵盤事件由鼠標(biāo)或鍵盤驅(qū)動程序轉(zhuǎn)換成輸入消息并把消息放進(jìn)系統(tǒng)消息隊列，例如WM_MOUSEMOVE、WM_LBUTTONUP、WM_KEYDOWN、WM_CHAR等等。Windows每次從系統(tǒng)消息隊列移走一個消息，確定它是送給哪個窗口的和這個窗口是由哪個線程創(chuàng)建的，然后，把它放進(jìn)窗口創(chuàng)建線程的線程消息隊列。線程消息隊列接收送給該線程所創(chuàng)建窗口的消息。線程從消息隊列取出消息，通過Windows把它送給適當(dāng)?shù)拇翱谶^程來處理。

除了鍵盤、鼠標(biāo)消息以外，隊列消息還有WM_PAINT、WM_TIMER和WM_QUIT。這些隊列消息以外的絕大多數(shù)消息是非隊列消息。

通過消息映射,我們可以把消息和它的消息處理函數(shù)聯(lián)系起來。VC++為我們提供了Class Wizard 來為用戶添加一個消息映射關(guān)系,而用戶只需編寫該消息發(fā)生響應(yīng)的函數(shù)即可。

從View菜單中選擇“ClassWizard”命令，便可調(diào)出如圖3所示的ClassWizard對話框，它一共分為五個選項卡，依次分別是消息映射、成員變量、自動化、ActiveX事件和類信息。最常用的是消息映射和成員變量兩個選項卡，如果程序中使用了ActiveX控件，那么還需要使用ActiveX事件選項卡來添加事件處理函數(shù)，類信息選項卡可用來了解各個類的文件名、基類和資源等信息，自動化選項卡只有在編寫OLE自動化服務(wù)器時才用得著。下面我們就來看看消息映射和成員變量兩個選項卡的特點和用途。

消息映射選項卡主要用途是為選中的類添加消息處理函數(shù)。其中，Projects組合框用于選擇Workspace中的一個工程，Class name組合框用于選擇工程中的一個類。Objects IDs中列出了所選擇的類的名稱及屬于它的一系列ID，對于CXXXView類來說，列出的ID基本上都是菜單命令，對于一個對話框類來說，列出的ID多數(shù)對應(yīng)著對話框模板中的控件。

從Objects IDs選擇不同的類名或ID后，右邊的Messages列表框中的內(nèi)容也會跟著改變，選中類名時，Messages列表框中會顯示出所有該類能處理的標(biāo)準(zhǔn)Windows消息以及該類可以重載的成員函數(shù)，選中一個ID時，Messages列表框中會顯示出這個ID對應(yīng)的對象（菜單選項或控件）所能引發(fā)的命令消息和通知消息。在Messages列表框中選擇一條消息（或一個可以重載的成員函數(shù)）后，如果該消息還沒有相應(yīng)的消息處理函數(shù)（或還未重載該成員函數(shù)），那么ClassWizard對話框右上角的Add Function按鈕就會變?yōu)橛行В崾疚覀兛梢蕴砑右粋€消息處理函數(shù)（或重載該成員函數(shù)），按下Add Function按鈕后，ClassWizard就會在所選的類中添加一個處理函數(shù)（為一個ID添加處理函數(shù)時，還會彈出一個對話框，要求輸入函數(shù)名），并在Member funtions列表框中顯示出剛添加的函數(shù)，在這個列表框中雙擊該函數(shù)名后，ClassWizard對話框?qū)⒆詣雨P(guān)閉，文本編輯器會定位在函數(shù)的實現(xiàn)代碼處，這些代碼及它在類定義中的聲明都是由ClassWizard自動生成的。

圖 3Class wizard 對話框

Member functions列表框并沒有列出類的所有成員函數(shù)，而只是列出了消息處理函數(shù)和重載的成員函數(shù)，其中每個函數(shù)的左邊都有一個小圖標(biāo)，如果小圖標(biāo)為“W”字樣，表示該函數(shù)是一個消息處理函數(shù)，除了Add function按鈕外，消息映射選項卡中還有三個按鈕，其中Delete Function用來刪除一個消息處理函數(shù)或重載的成員函數(shù)，但是此按鈕只能刪除函數(shù)在類定義中的聲明，函數(shù)的實現(xiàn)代碼還需要手工來刪除；Edit Code按鈕的用途相當(dāng)于在Member functions中雙擊一個成員函數(shù)；Add Class按鈕則可用于向工程中添加一個新的類。3.1.3 文檔與視圖

先利用Appwizard 來新建一個單文檔工程。在SDI框架程序中，主要包含四個類：

主框架類：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派生。用戶對話框類：CAboutDlg負(fù)責(zé)用戶對話框的設(shè)置，從MFC類的CDialog類派生。

文檔是存儲的對象.文檔類負(fù)責(zé)數(shù)據(jù)的維護(hù)，包括數(shù)據(jù)的讀取、存儲和修改，并將更改的數(shù)據(jù)通知相關(guān)視圖，另外它還負(fù)責(zé)將數(shù)據(jù)存儲到文件及從文件中讀取數(shù)據(jù)。

文檔是一種數(shù)據(jù)源，數(shù)據(jù)源有很多種，最常見的是磁盤文件，但它不必是一個磁盤文件，文檔的數(shù)據(jù)源也可以來自串行口、網(wǎng)絡(luò)或攝像機(jī)輸入信號等。文檔對象負(fù)責(zé)來自所有數(shù)據(jù)源的數(shù)據(jù)的管理。

視圖類的作用是與用戶交互。視圖對象負(fù)責(zé)對保存在文擋對象中的數(shù)據(jù)以某種方式進(jìn)行顯示，并接受用戶的輸入，將這些輸入交文擋類進(jìn)行處理。

視圖是數(shù)據(jù)的用戶窗口，為用戶提供了文檔的可視的數(shù)據(jù)顯示，它把文檔的部分或全部內(nèi)容在窗口中顯示出來。視圖還給用戶提供了一個與文檔中的數(shù)據(jù)交互的界面，它把用戶的輸入轉(zhuǎn)化為對文檔中數(shù)據(jù)的操作。每個文檔都會有一個或多個視圖顯示，一個文檔可以有多個不同的視圖。比如，在Excel電子表格中，我們可以將數(shù)據(jù)以表格方式顯示，也可以將數(shù)據(jù)以圖表方式顯示。一個視圖既可以輸出到窗口中，也可以輸出到打印機(jī)上。

圖 文檔與視圖關(guān)系

3.1.4 鼠標(biāo)消息舉例

我們先通過一個例子來說明如何用class wizard 來實現(xiàn)捕獲鼠標(biāo)消息,進(jìn)行消息映射和定義消息處理函數(shù).利用class wizard來設(shè)置消息選項。選擇ClassName中的CXXXView，選擇其中相對應(yīng)的WM_LBUTTONDOWN，雙擊選中的消息，單擊Edit Code 按紐，如圖4所示，并增加相關(guān)代碼，如圖5所示。

圖4 增加鼠標(biāo)消息映射

圖5 增加代碼

圖6 運(yùn)行結(jié)果

3.1.4鍵盤消息舉例

鍵盤的輸入是從掃描碼開始的,windows鍵盤驅(qū)動程序?qū)⑦@些掃描碼轉(zhuǎn)換成為與硬件無關(guān)的形式,即虛擬鍵碼.WM_CHAR:此消息在鍵被按下時產(chǎn)生,通常用于處理非打印鍵中的按鍵消息.圖7 在工程中增加相關(guān)變量

圖8 增加變量Text

圖9 初始化變量為空

圖10 增加鍵盤的消息影射

圖11 編寫Onchar處理函數(shù)

圖12 輸出接收到的字符

圖13 運(yùn)行結(jié)果 為了能夠?qū)崿F(xiàn)輸入字符的換行功能，在CXXXDoc類中增加一個用來計算行數(shù)的成員變量m_Line,如圖14所示，并初始化變量m_Line，如圖15所示。

圖 增加成員變量

圖15 初始化成員變量

為了保存字符串行的數(shù)據(jù)，定義一個字符串列表變量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ù)輸出出來，增加一個DrawText函數(shù)，如圖17所示和圖18所示。

圖17 在CXXXDoc類中增加成員函數(shù)

圖18 增加DrawText函數(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 }

第四篇：北郵數(shù)據(jù)結(jié)構(gòu)實驗報告 單鏈表

北京郵電大學(xué) 數(shù)據(jù)結(jié)構(gòu)試驗報告

實驗名稱： 實驗一

線性表 學(xué)生姓名：

班

級：

班內(nèi)序號：

學(xué)

號：

日

期： 2014年1月3日

實驗?zāi)康?/p>

? 熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法 ? 學(xué)習(xí)指針、模板類、異常處理的使用 ? 掌握線性表的操作的實現(xiàn)方法 ? 學(xué)習(xí)使用線性表解決實際問題的能力 實驗內(nèi)容

2.1題目1 根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)線性表，并完成線性表的基本功能。

線性表存儲結(jié)構(gòu)（五選一）：

1、帶頭結(jié)點的單鏈表

2、不帶頭結(jié)點的單鏈表

3、循環(huán)鏈表

4、雙鏈表

5、靜態(tài)鏈表

線性表的基本功能：

1、構(gòu)造：使用頭插法、尾插法兩種方法

2、插入：要求建立的鏈表按照關(guān)鍵字從小到大有序

3、刪除

4、查找

5、獲取鏈表長度

6、銷毀

7、其他：可自行定義

編寫測試main()函數(shù)測試線性表的正確性。程序分析

3.1 存儲結(jié)構(gòu) 單鏈表的存儲結(jié)構(gòu)：

3.2 關(guān)鍵算法分析

一、關(guān)鍵算法 1.頭插法

自然語言描述：a.在堆中建立新結(jié)點

b.將a[i]寫入到新結(jié)點的數(shù)據(jù)域

c.修改新結(jié)點的指針域

d.修改頭結(jié)點的指針域,將新結(jié)點加入鏈表中 代碼描述： template LinkList::LinkList(T a[], int n)//頭插法建立 {

front = new Node;front->next = NULL;for(int i=n-1;i>=0;i--){ Node* s = new Node;s->data = a[i];

}

} s->next = front->next;front->next = s;時間復(fù)雜度：O(n)

2.尾插法

自然語言描述：a.在堆中建立新結(jié)點

b.將a[i]寫入到新結(jié)點的數(shù)據(jù)域

c.將新結(jié)點加入到鏈表中

d.修改修改尾指針 代碼描述: template LinkList::LinkList(T a[], int n)//尾插法建立 {

front = new Node;front->next=NULL;Node * r = front;for(int i=0;i * s = new Node;

}

} s->data = a[i];s->next = r->next;r->next= s;r=s;時間復(fù)雜度：O(n)

3.析構(gòu)函數(shù)

自然語言描述：a.新建立一個指針，指向頭結(jié)點

b.移動a中建立的指針

c.逐個釋放指針

代碼描述: template LinkList::~LinkList()//析構(gòu)函數(shù)，銷毀鏈表 {

Node * p = front;while(p){ front = p;p = p->next;

} } delete front;4.按位查找函數(shù)

自然語言描述: a.初始化工作指針p和計數(shù)器j，p指向第一個結(jié)點，j=1

b.循環(huán)以下操作，直到p為空或者j等于1

b1：p指向下一個結(jié)點

b2：j加1

c.若p為空，說明第i個元素不存在，拋出異常

d.否則，說明p指向的元素就是所查找的元素，返回元素地址

代碼描述: template Node* LinkList::Get(int i)//按位查找 {

Node * p = front;int j=0;while(p){

if(j

} else break;p = p->next;j++;

} if(!p)throw“查找位置非法”;else

return p;} 時間復(fù)雜度：O(n)

5.按值查找函數(shù)

自然語言描述：a.初始化工作指針p和計數(shù)器j，p指向第一個結(jié)點，j=1

b.循環(huán)以下操作，找到這個元素或者p指向最后一個結(jié)點

b1.判斷p指向的結(jié)點是不是要查找的值，如果是，返回j;

b2.否則p指向下一個結(jié)點,并且j的值加一

c.如果找到最后一個結(jié)點還沒有找到要查找的元素，返回查找失敗信息

代碼描述: template int LinkList::Locate(T x)//按值查找 {

Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else { p = p->next;

j++;} } 時間復(fù)雜度：O(n)6.插入函數(shù)

自然語言描述： a.在堆中建立新結(jié)點

b.將要插入的結(jié)點的數(shù)據(jù)寫入到新結(jié)點的數(shù)據(jù)域

c.修改新結(jié)點的指針域

d.修改前一個指針的指針域，使其指向新插入的結(jié)點的位置

代碼描述: template void LinkList::Insert(int i,T x)//插入函數(shù) {

Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;} 時間復(fù)雜度：O(n)7.按位刪除函數(shù)

自然語言描述：a.從第一個結(jié)點開始，查找要刪除的位數(shù)i前一個位置i-1的結(jié)點

b.設(shè)q指向第i個元素

c.將q元素從鏈表中刪除

d.保存q元素的數(shù)據(jù)

e.釋放q元素 代碼描述: template T LinkList::Delete(int i)//刪除函數(shù) { Node *p = Get(i-1);Node *q = p->next;

T x=q->data;

} p->next = q->next;delete q;return x;

8.遍歷打印函數(shù)

自然語言描述: a.判斷該鏈表是否為空鏈表，如果是，報錯

b.如果不是空鏈表，新建立一個temp指針

c.將temp指針指向頭結(jié)點

d.打印temp指針的data域

e.逐個往后移動temp指針，直到temp指針的指向的指針的next域為空

代碼描述: template void LinkList::PrintList()//打印鏈表 {

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;9.獲取鏈表長度函數(shù)

自然語言描述： a.判斷該鏈表是否為空鏈表，如果是，輸出長度0

b.如果不是空鏈表，新建立一個temp指針，初始化整形數(shù)n為0

c.將temp指針指向頭結(jié)點

d.判斷temp指針指向的結(jié)點的next域是否為空，如果不是，n加一，否則return n

e.使temp指針逐個后移，重復(fù)d操作，直到temp指針指向的結(jié)點的next域為0，返回n 代碼描述: template int LinkList::GetLength()//分析鏈表長度 {

} Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;4 程序運(yùn)行結(jié)果

4.1主函數(shù)流程圖

4.2程序運(yùn)行框圖

實驗心得

1.調(diào)試時出現(xiàn)的問題及解決的方法

在編寫按值查找函數(shù)時，由于沒有處理好指針類型的原因，導(dǎo)致指針無法正常返回，屢屢報錯。最后意識到c++沒有指針強(qiáng)制類型的轉(zhuǎn)換機(jī)制，經(jīng)過細(xì)致檢查后才改正錯誤使得程序正常運(yùn)行。2.心得體會

了解了單鏈表的基本的操作函數(shù)實現(xiàn)，對鏈?zhǔn)酱鎯Y(jié)構(gòu)有了較好的認(rèn)識 3.下一步的改進(jìn)

可以增加完善報錯機(jī)制，增強(qiáng)程序的健壯性

完整源代碼

#include using namespace std;

template struct Node {

};

template class LinkList { public:

};

//template //LinkList::LinkList(T a[], int n)//頭插法建立 LinkList(){ front = new Node;front->next = NULL;}//無參構(gòu)造函數(shù) LinkList(T a[],int n);//構(gòu)造函數(shù) void Insert(int i,T x);//插入函數(shù) T Delete(int i);//刪除函數(shù)

Node* Get(int i);//查找第幾個的元素，返回的是該元素的地址 int Locate(T x);//定位某元素 int GetLength();//分析鏈表長度 ~LinkList();//析構(gòu)函數(shù) void PrintList();//打印鏈表 Node * front;T data;Node * next;private: //{ // // // // // // // // // //}

template LinkList::LinkList(T a[], int n)//尾插法建立 {

}

template LinkList::~LinkList()//析構(gòu)函數(shù)，銷毀鏈表 {

}

template void LinkList::PrintList()//打印鏈表 { Node * p = front;while(p){

} front = p;p = p->next;delete front;front = new Node;front->next=NULL;Node * r = front;for(int i=0;i

} Node * s = new Node;s->data = a[i];s->next = r->next;r->next= s;r=s;front = new Node;front->next = NULL;for(int i=n-1;i>=0;i--){

} Node* s = new Node;s->data = a[i];s->next = front->next;front->next = s;

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;

template Node* LinkList::Get(int i)//按位查找 {

}

template int LinkList::Locate(T x)//按值查找 {

} Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else

{ } p = p->next;

j++;Node * p = front;int j=0;while(p){

} if(!p)throw“查找位置非法”;else

return p;if(j

} else break;p = p->next;j++;

template void LinkList::Insert(int i,T x)//插入函數(shù) {

}

template T LinkList::Delete(int i)//刪除函數(shù) {

}

template int LinkList::GetLength()//分析鏈表長度 {

}

void main(){ Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;Node *p = Get(i-1);Node *q = p->next;p->next = q->next;delete q;return x;Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;

T x=q->data;

} int n;cout<<“將要輸入的鏈表長度為：”;cin>>n;int *b=new int[n];cout<<“輸入鏈表中的元素：”;for(int k=0;k>b[k];LinkList a(b,n);a.PrintList();cout<<“鏈表的長度:”<>i;cout<<“被刪除掉的元素是：”<>j;cout<<“要將其插入在哪個位置：”;cin>>i;a.Insert(i,j);cout<<“插入后得到的鏈表是：”;a.PrintList();cout<<“要查找第幾個元素：”;cin>>i;cout<<“要查找的元素為：”<data<>j;cout<<“輸入的元素位置在：”<

第五篇：求解Josephus問題實驗總結(jié)(用C語言循環(huán)單鏈表實現(xiàn))

求解Josephus問題實驗總結(jié)

1實驗題目: josephus問題可描述如下：

設(shè)有n個人圍成一個環(huán)，現(xiàn)從第s個人開始報數(shù)，數(shù)到第m的人出列，然后從出列的下一個人從新開始報數(shù)，數(shù)到第m的人又出列，如此重復(fù)，直至所有人均出列為止。求這些人出列的順序。

2實驗?zāi)康模?/p>

熟練掌握線性表的順序?qū)崿F(xiàn)和鏈?zhǔn)綄崿F(xiàn)的基本操作。

3實驗方法：

通過運(yùn)用已學(xué)的向量和循環(huán)單鏈表編寫程序，并在電腦上運(yùn)行，實現(xiàn)josephus問題的求解。4實驗過程與結(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試驗體會與收獲：

（1）寫程序是要隨時注意縮進(jìn)，使得程序?qū)哟吻逦阌趯ふ义e誤，同時也讓別人看的更加方便。（2）構(gòu)造循環(huán)單鏈表，要以單鏈表為單元指針指向把最后個單元與第一個即可（3）建立好循環(huán)單鏈表后，通過三個指針（p,q,tmp）的指示，來確定報數(shù)，出列人的位置，得以完成。具體過程如下：p指向head頭指針,通過s次循環(huán)將p指向報數(shù)的起始位置s，用q記錄p的位置，再經(jīng)過m次循環(huán)另p指向出列者的位置，將其數(shù)值保存在一維數(shù)組中，并將其從鏈表中刪除，p指向下一次起始位置，結(jié)束時返回數(shù)組A[j]。（4）刪除節(jié)點時，注意要釋放節(jié)點。

（5）構(gòu)造函數(shù)時，一定要明確函數(shù)的類型，即返回行還是不返回型，以免出現(xiàn)不必要的錯誤。