第一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二 求解約瑟夫問題

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二

求解約瑟夫問題

問題描述：使用代表頭節(jié)點(diǎn)的循環(huán)單鏈表解決此問題。設(shè)有n個(gè)人圍坐在一張圓桌周圍，現(xiàn)從某個(gè)人開始從1報(bào)數(shù)，數(shù)到m的人離開。接著從出列的下一個(gè)人開始重新從1開始報(bào)數(shù)，數(shù)到m的人又出列，如此下去直到所有的人都出列為止。求出他們的出列序列。

問題分析：例如，當(dāng)n=8,m=4時(shí)，若從第一個(gè)人開始報(bào)數(shù)（設(shè)從1開始編號(hào)），則得到的序列是：4，8，5，2，1，3，7，6。算法：

void Josephus(int n, int m,int s)

{ //生成表頭節(jié)點(diǎn)，空單循環(huán)鏈表

LNode * HL = new LNode;

HL-> next = HL;

int i;//生成含有 n 個(gè)節(jié)點(diǎn)的、節(jié)點(diǎn)值依次為1，2……，n的帶表頭節(jié)點(diǎn)的循環(huán)單鏈表

For(i = n;i>=1;i--)

{ LNode * newptr = new LNode;

Newptr-> data = i;

newptr-> next = HL-> next;

HL-> next = newptr;}

//從表頭開始順序查找出第s個(gè)節(jié)點(diǎn)，對(duì)應(yīng)第一個(gè)開始報(bào)數(shù)的人 LNode * ap = HL, *cp = HL->next;for(i= 1;i

ap = cp;

cp = cp->next;if(cp = = HL){ ap = HL;cp = HL->next;} } //依次使n-1個(gè)人出列 for(i=1;i

//順序查找出待出列的人，即為循環(huán)結(jié)束后cp所指向的節(jié)點(diǎn)

for(int j=1;jnext;if(cp ==HL){ ap = HL;cp = HL->next;} } //輸出cp節(jié)點(diǎn)的值，即出列的人

cout << cp->data <<”

“;//從單鏈表中刪除cp節(jié)點(diǎn)

ap-> next = cp-> next;delete cp;//使cp指向被刪除節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)

cp = ap-> next;//若cp指向了表頭節(jié)點(diǎn)，則后移ap和cp指針 if(cp = = HL){ ap = HL;cp = HL-> next;} }

//使最后一人出列

count << HL->next-> data << end1;

//刪除表頭節(jié)點(diǎn)和表頭附加節(jié)點(diǎn)

delete HL->next;

delete HL;}

補(bǔ)充操作系統(tǒng)練習(xí)：

1、有一個(gè)虛擬存儲(chǔ)系統(tǒng), 每個(gè)進(jìn)程在內(nèi)存占有3頁數(shù)據(jù)區(qū)、1頁程序區(qū).剛開始時(shí)數(shù)據(jù)區(qū)為空.有以下訪頁序列: 1、5、4、1、2、3、2、1、5、4、2、4、6、5、1

試給出下列情形下的缺頁次數(shù):

(1)系統(tǒng)采用先進(jìn)先出(FIFO)淘汰算法.(2)系統(tǒng)采用最近最少使用(LRU)淘汰算法.(3)若采用優(yōu)化(OPT)淘汰算法呢?

2、設(shè)系統(tǒng)中有三類資源A、B和C，又設(shè)系統(tǒng)中有5個(gè)進(jìn)程P1，P2，P3，P4和P5.在T0時(shí)刻系統(tǒng)狀態(tài)如下：

最大需求量

已分配資源量

剩余資源量

A

B

C

A

B

C

A

B

C

P1 8

P2 4

P3 10 1

P4 3

P5 5(1)系統(tǒng)是否處于安全狀態(tài)？如是，則給出進(jìn)程安全序列.(2)如果進(jìn)程P5申請(qǐng)1個(gè)資源類A、1個(gè)資源類B和1個(gè)資源類C，能否實(shí)施分配？為什么？

3、在一個(gè)兩道的批處理操作系統(tǒng)中，有6個(gè)作業(yè)進(jìn)入系統(tǒng)，它們的進(jìn)入時(shí)刻、估計(jì)運(yùn)行時(shí)間和優(yōu)先級(jí)如下表所示.作業(yè)號(hào)

進(jìn)入時(shí)刻

估計(jì)運(yùn)行時(shí)間

優(yōu)先級(jí)

JOB1

8：00

90分鐘

JOB2

8：10

30分鐘

JOB3

8：30

20分鐘

JOB4

8：50

15分鐘

JOB5

9：20

10分鐘

JOB6

9：40

5分鐘系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法，作業(yè)一旦被調(diào)度運(yùn)行就不再退出.但當(dāng)有新的作業(yè)投入運(yùn)行時(shí)，可以按照優(yōu)先級(jí)進(jìn)行進(jìn)程調(diào)度.（1）試給出各個(gè)作業(yè)的運(yùn)行時(shí)間序列.（例如：JOB1：8：00-8：30，9：10-9：20，…）

（2）試計(jì)算出作業(yè)的平均周轉(zhuǎn)時(shí)間.

第二篇：數(shù)據(jù)結(jié)構(gòu)報(bào)告--約瑟夫環(huán)范文

實(shí)習(xí)報(bào)告

題目:約瑟夫環(huán)

班級(jí)：08052712學(xué)號(hào): 08052211姓名: 葛俊峰

一、需求分析

1.本演示程序中，編號(hào)為1，2，?，n的n個(gè)人按順時(shí)針方向圍坐一圈，每個(gè)人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，如此下去，直到所有人全部出列為止。

2.演示程序以用戶和計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入相應(yīng)數(shù)據(jù)（即總?cè)藬?shù)，m的值，每個(gè)人所持的密碼），運(yùn)算結(jié)果顯示在其后。

3.程序執(zhí)行的命令包括：

（1）構(gòu)造鏈表；（2）輸入數(shù)據(jù)；（3）執(zhí)行報(bào)數(shù)，儲(chǔ)存出列人的序號(hào)，刪除出列人的信息以及把出列人的密碼賦給m；（4）結(jié)束。

4.測試數(shù)據(jù)：

m的初始值為20；n＝7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4，首先m值為6，則這正確的出列順序?yàn)?，1，4，7，2，3，5。

二、概要設(shè)計(jì)

為了實(shí)現(xiàn)上述操作，應(yīng)以單向循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)。為此，需要1個(gè)抽象數(shù)據(jù)類型：線性表。

1.線性表的抽象數(shù)據(jù)類型為：

ADT List{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,?，n,n≥0}

數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2,3,?,n}

基本操作：

InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空的線性表L。

}ADT List

2.本程序包括三個(gè)模塊:

1）主程序模塊：

void main（）{

初始化；

輸入數(shù)據(jù)；

函數(shù)調(diào)用；

}

2）構(gòu)造鏈表并輸入每個(gè)人信息的模塊-----實(shí)現(xiàn)線性表的抽象數(shù)據(jù)類型；

3）運(yùn)行模塊-----模擬約瑟夫環(huán)依次出列；

各模塊之間調(diào)用關(guān)系如下：

主程序模塊

↓

構(gòu)造鏈表并輸入每個(gè)人信息的模塊

↓

運(yùn)行模塊

三、詳細(xì)設(shè)計(jì)

1.結(jié)點(diǎn)類型和指針類型

typedef struct Node{

int num;

int password;

struct Node *next;

}LNode,*LinkList;//結(jié)點(diǎn)類型,指針類型

Status MakeNode（LinkList &p，Elem Type e）

{

//分配由p指向的數(shù)據(jù)元素為e、后繼為“空”的特點(diǎn)，并返回TRUE，//若分配失敗，則返回FALSE

P=(LinkType)malloc（sizeof（NodeType））；

If（！p）return FALSE；

p->data=e；p->next=null；return TRUE；

}

viod Free Node（Link Type &p）

{

//釋放p所指結(jié)點(diǎn)

}

2.主函數(shù)和其他函數(shù)

int main()

{

//主函數(shù)

LinkList L = NULL;

LinkList s ,r;

int n,i,j,m;//初始化

printf(“請(qǐng)輸入人數(shù)nn”);

scanf(“%d”,&n);

printf(“請(qǐng)輸入mn”);

scanf(“%d”,&m);

printf(“請(qǐng)依次輸入每個(gè)人的密碼n”);//輸入數(shù)據(jù)

CreatList(L,s,r,n);//創(chuàng)建鏈表run(L,n,m);//模擬約瑟夫環(huán)并輸出

return 0;

}//main

void CreatList(LinkList &L,LinkList &s,LinkList &r,int n)

{

//創(chuàng)建鏈表

int i=1;

s=(LNode*)malloc(sizeof(LNode));//分配空間

scanf(“%d”,&s->password);//輸入密碼

s->num = i;//序號(hào)為i

if(L==NULL)

L=s;

else

r->next=s;

r=s;//為下次連接做準(zhǔn)備

for(i=2;i<=n;i++)

{

s=(LNode*)malloc(sizeof(LNode));//分配空間

scanf(“%d”,&s->password);

s->num = i;

r->next=s;//連接到下個(gè)結(jié)點(diǎn)

r=s;//為下次連接做準(zhǔn)備

}

r->next = L;//閉合L = r;

} // void CreatList

void run(LinkList &L,int n,int m)

{

//模擬約瑟夫環(huán)并輸出

LinkList s,r;

int i,j;

for(i = 0;i < n;i ++)

{

for(j = 1;j < m;j ++)

L = L->next;//報(bào)數(shù)

s = L->next;

r = s->next;

printf(“%dn”,s->num);//輸出序號(hào)

m = s->password;

L->next = r;

free(s);//刪除結(jié)點(diǎn)

}

}//run

3.函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu):

main

↓↓

CreatListrun

↓↓

Make NodeFree Node

四、調(diào)試分析

1.剛開始由于使用頭結(jié)點(diǎn),使得程序不符合要求。

2.在寫程序時(shí)忽略了一些變量參數(shù)的標(biāo)識(shí)“&”,使調(diào)試程序費(fèi)時(shí)不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識(shí)。

3.本程序模塊劃分比較簡單且容易看懂，但頭指針賦空不太合理。

4.本實(shí)習(xí)作業(yè)采用數(shù)據(jù)抽象的設(shè)計(jì)方法，將程序劃分為3個(gè)層次，使得設(shè)計(jì)時(shí)思路清晰，實(shí)現(xiàn)調(diào)試順利

五、用戶手冊

1.本程序運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為約瑟夫環(huán).exe。

2． 進(jìn)入演示程序后出現(xiàn)提示信息：

“請(qǐng)輸入人數(shù)n”

輸入后，出現(xiàn)提示信息：

“請(qǐng)輸入m”

輸入后，出現(xiàn)提示信息：

“請(qǐng)依次輸入每個(gè)人的密碼”

輸入后，顯示相應(yīng)的結(jié)果。

第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 背包問題的求解

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

背包問題的求解

摘要 組合優(yōu)化問題的求解方法研究已經(jīng)成為了當(dāng)前眾多科學(xué)關(guān)注的焦點(diǎn)，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價(jià)值，同時(shí)也在于它們能在現(xiàn)實(shí)生活中廣泛的應(yīng)用。背包問題是一個(gè)典型的組合優(yōu)化問題，本課程設(shè)計(jì)用遞歸算法求解背包問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。關(guān)鍵詞 背包問題；

遞歸算法；

1問題描述

1.1問題描述

背包問題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價(jià)值之和最大。

1.2基本思想

（1）分別輸入n件物品的重量和價(jià)值。（2）采用遞歸尋找物品的方案。

（3）輸出最佳的裝填方案，包括選中的是哪幾種物品，總價(jià)值為多少。

2問題分析

背包問題的求解是一個(gè)很經(jīng)典的案例。對(duì)于它的分析與研究已經(jīng)到達(dá)了一定的深度，解決這個(gè)問題有很多很多的辦法。其中遞歸方法是比較簡化程序，也比較難理解的一個(gè)。

設(shè)n件物品的重量分別為w0,w1,?,wn-1,物品的價(jià)值分別為v0,v1,?,vn-1。采用遞歸尋找物品的選擇方案。設(shè)前面已經(jīng)有了多種選擇方案，并保留了其中最大的選擇方案于數(shù)組option[],設(shè)方案的的總價(jià)值存于變量maxv,當(dāng)前正在考察新方案其物品選擇情況保存于數(shù)組cop[]，嘉定當(dāng)前方案已經(jīng)考慮了前i-1件物品，現(xiàn)在正在考慮第i件物品；當(dāng)前方案已經(jīng)包含的物品的質(zhì)量之和為tw;至此，若其余物品都選擇可能的話，本方案能達(dá)到的總價(jià)值的期望值設(shè)為tv，算法引入tv是當(dāng)一旦當(dāng)前方案的總價(jià)值的期望值也小于前面方案的總價(jià)值maxv時(shí)，急需考察當(dāng)前方案變成無意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個(gè)方案。因?yàn)楫?dāng)方案的總價(jià)值不比maxv大時(shí)，該方案不會(huì)不會(huì)再被考察。這同時(shí)保證函數(shù)后找到的方案一定會(huì)比前面的方案更好。2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 對(duì)于第i件物品的選擇有兩種可能：

（1）物品i被選擇，這種可能性僅當(dāng)包含它不會(huì)超過方案總重量的限制時(shí)才是可行的。選中后，繼續(xù)遞歸去考慮其余物品的選擇；

（2）物品i不被選擇，這種可能性僅當(dāng)不包物品i也有可能會(huì)找大價(jià)值更大的方案的情況。

就此，通過不斷地對(duì)從第一件開始的物品到第n件物品進(jìn)行選擇或是不選擇，從而從各個(gè)方案的比較中選擇出最優(yōu)方案。

采用option[]和cop[]兩個(gè)數(shù)組，來輔助完成遞歸尋找物品的選擇方案。數(shù)組option[]起到一個(gè)“旗幟”作用，用來區(qū)別于未被選擇的物品，從而達(dá)到輸出被選擇的函數(shù)。而cop[]則像是一個(gè)中間變量，它在遞歸過程中不斷地發(fā)生變化，將有效的最終數(shù)據(jù)傳輸給數(shù)組option[]，起到一個(gè)橋梁作用。

3數(shù)據(jù)結(jié)構(gòu)描述

背包問題結(jié)構(gòu)體：

struct{

int weight;

int value;

}a[N];4算法設(shè)計(jì)

4.1程序流程圖

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

圖4-1 程序流程圖

4.2算法設(shè)計(jì)

根據(jù)問題分析中的思想寫出遞歸算法如下：

find（物品當(dāng)前選擇已達(dá)到的重量和tw,本方案可能達(dá)到的總價(jià)值為tv）｛

/*考慮物品i包含在當(dāng)前方案中的可能性*/ if（包含物品i是可接受的）｛

將物品i包含在當(dāng)前方案中；

if(i

以當(dāng)前方案作為臨時(shí)最佳方案保存；

恢復(fù)物品i不包含狀態(tài)；

｝ 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

/*考慮物品i不包含在當(dāng)前方案中的可能性*/ if（不包含物品i僅是可考慮的）

if(i

以當(dāng)前方案作為臨時(shí)最佳方案保存；

｝

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

/*物品i包含在當(dāng)前方案的可能性*/ { cop[i]=1;if(imaxv)

/*物品i不包含在當(dāng)前方案的可能性*/ if(i

opion[k]=cop[k];maxv=tv-a[i].value;} } 5詳細(xì)程序清單

詳細(xì)程序清單見附錄。

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

背包問題求解界面如圖6-1所示。

圖6-1 背包問題求解界面

程序調(diào)試成功。

在課程設(shè)計(jì)代碼調(diào)試過程中也出了不少差錯(cuò)，比如頭文件很容易忽略，同學(xué)指出才發(fā)現(xiàn)；一些符號(hào)像“；”也很容易丟掉或是中英文格式不正確；甚至像0和 O這種小錯(cuò)誤有時(shí)也會(huì)發(fā)生，在經(jīng)過調(diào)試和完善程序的過程中，這些錯(cuò)誤已經(jīng)全部改正。在此過程中我們學(xué)到了不少調(diào)試的技巧，極大得豐富了編程的知識(shí)，這些在程序的優(yōu)化方面幫助很大。

7心得體會(huì)

通過此次課程設(shè)計(jì)的實(shí)踐，感觸較深。不僅使我們加深了對(duì)書本知識(shí)的理解，而且鍛煉了我們編寫程序、調(diào)試程序的能力。同時(shí)，此次課程設(shè)計(jì)也充分彌補(bǔ)了課堂教學(xué)中知識(shí)的缺陷。這次課程設(shè)計(jì)由于時(shí)間有限，對(duì)有些地方考慮的還不夠周到。

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

在本課題中，我們研究了如何用遞歸算法求解組合優(yōu)化問題中的背包問題，背包問題是一個(gè)典型的組合優(yōu)化問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。所以我們試著用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)以及遞歸法來解決普通的背包問題。背包問題的遞歸思想確實(shí)有點(diǎn)難以理解，為了理解這個(gè)思想，我們確實(shí)花了很長時(shí)間，不過很高興最后經(jīng)過我們的討論掌握了這個(gè)思想。

參考文獻(xiàn)

[1] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn).北京：清華大學(xué)出版社，2002:100-132 [2] 張乃笑.數(shù)據(jù)結(jié)構(gòu)與算法.北京：電子工業(yè)出版，2000:3-5 [3] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京： 清華大學(xué)出版社，2002:100-132 [4] 李春葆.數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析（修訂版）.北京：清華大學(xué)出版，2000:45-66

Knapsack problem solving

Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

附錄：詳細(xì)程序清單

#include #define N 100 int limitw，/*限制的總重量*/ totv，/*全部物品的總價(jià)*/ maxv;

/*可實(shí)現(xiàn)最大總價(jià)值*/ int opion[N]，cop[N];

struct{

int weight;

int value;

}a[N];int n;

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

{ cop[i]=1;if(i

/*方案的選擇*/ /*當(dāng)前方案的選擇*/ /*背包問題結(jié)構(gòu)體*/

/*物品種數(shù)*/ /*物品i包含在當(dāng)前方案的可能性*/ 7

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

if(tv-a[i].value>maxv)

/*物品i不包含在當(dāng)前方案的可能性*/ if(i

第%d種物品（重量，價(jià)值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的總重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k

printf(“最佳裝填方案是：n”);for(k=0;k

第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二報(bào)告

——簡單計(jì)算器

姓名：王稀賓 班 級(jí)：06111106 學(xué)號(hào)：1120111699 一實(shí)驗(yàn)?zāi)康?/p>

按照四則運(yùn)算加、減、乘、除、冪（^）和括號(hào)的優(yōu)先關(guān)系和慣例，編寫計(jì)算器程序。

二實(shí)驗(yàn)內(nèi)容

要求：

從鍵盤輸入一個(gè)完整的表達(dá)式，以回車作為表達(dá)式輸入結(jié)束的標(biāo)志。輸入表達(dá)式中的數(shù)值均為大于等于零的整數(shù)。中間的計(jì)算過程如果出現(xiàn)小數(shù)也只取整。

三程序設(shè)計(jì)

程序模塊：

1輸入模塊，輸入多項(xiàng)式；

2計(jì)算模塊，根據(jù)輸入內(nèi)容，判斷分析，計(jì)算出結(jié)果； 3輸出模塊，輸出計(jì)算結(jié)果。

定義結(jié)構(gòu)創(chuàng)建結(jié)點(diǎn)： typedef struct { double data[50];int top;}OPND_Stack;//運(yùn)算符結(jié)構(gòu)體 typedef struct { char data[50];int top;}OPTR_Stack;主函數(shù)部分： void main(){ char a[80];int m;char b[80];printf(“============簡易計(jì)算器============n”);printf(“[四則運(yùn)算.如:-1+(2+3)*9/(-2)-6].n請(qǐng)輸入一個(gè)表達(dá)式:n”);while(1){

gets(a);

strcpy(b,a);

while(1)

{

int p;

m=strlen(a);

p=Can(a,m);

if(p==0)break;

printf(“輸入錯(cuò)誤.請(qǐng)從新輸入表達(dá)式:n”);

gets(a);

strcpy(b,a);

}

printf(“=*=*=*=*=*=*表達(dá)式結(jié)果=*=*=*=*=*=*n”);

printf(“該表達(dá)式的結(jié)果為:n%s=%-10.3lfn”,b,EvaluateExpression(a));

printf(“=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n”);

printf(“繼續(xù)使用[四則運(yùn)算.如:-1+(2+3)*9/(-2)-6].<關(guān)閉退出>.n請(qǐng)?jiān)佥斎?一個(gè)表達(dá)式:n”);} }

四程序調(diào)試分析

1在四則混合運(yùn)算中，運(yùn)算符號(hào)的優(yōu)先級(jí)比較難判斷。2心得體會(huì): 我對(duì)編程是有很濃厚興趣的。在編程的過程中，我深深地體會(huì)到力不從心—有些知識(shí)沒能深入地理解和掌握以及VC++的許多功能沒能探索和了解使我編程時(shí)有好多的思想運(yùn)用不上(如設(shè)計(jì)一個(gè)美觀的操作界面)。另外，我也感受到了數(shù)據(jù)結(jié)構(gòu)的重要性，有了結(jié)構(gòu)才能將好的思想付諸實(shí)踐。同時(shí)經(jīng)過查詢資料了解到棧由多種運(yùn)用方法，其中包括棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，棧是計(jì)算表達(dá)式的經(jīng)典應(yīng)用。數(shù)據(jù)結(jié)構(gòu)中的許多結(jié)構(gòu)都是很經(jīng)典思想，只有把編程語言和數(shù)據(jù)結(jié)構(gòu)都熟練掌握的情況下，才能做出一些很好的作品。在編程過程中，雖然有時(shí)候是很發(fā)悶的，尤其是程序無錯(cuò)但結(jié)果不對(duì)，但是在完成一個(gè)完整的程序時(shí)所帶來的喜悅是其它事情所不能替代的。我很喜歡編程，即使我的知識(shí)和能力有限，但我相信經(jīng)過努力，一切皆有可能。

五用戶使用說明

按要求正確輸入表達(dá)式即可得到結(jié)果。

六程序運(yùn)行結(jié)果 附程序清單

#include #include #include //算符優(yōu)先級(jí)表 char First[7][7]= { //'+','-','*','/','(',')','^' /*'+'*/ '>','>','<','<','<','>','<', /*'-'*/ '>','>','<','<','<','>','<', /*'*'*/ '>','>','>','>','<','>','<', /*'/'*/ '>','>','>','>','<','>','<', /*'('*/ '>','>','>','>','>','>',' >', /*')'*/ '<','<','<','<','< ','>','<', /*'^'*/ '>','>','>','>','<','> ','<' };//運(yùn)算符數(shù)組

char OP[7]={'+','-','*','/','(',')','#'};//數(shù)據(jù)結(jié)構(gòu)體 typedef struct { double data[50];int top;}OPND_Stack;//運(yùn)算符結(jié)構(gòu)體 typedef struct

{ char data[50];int top;}OPTR_Stack;//初始化運(yùn)算符棧函數(shù)

void InitStack_R(OPTR_Stack *a){ a->top=-1;} //初始化數(shù)據(jù)站函數(shù)

void InitStack_D(OPND_Stack *a){ a->top=-1;} //運(yùn)算符進(jìn)棧函數(shù)

void Push_R(OPTR_Stack *a,char b){ a->top++;a->data[a->top]=b;} //數(shù)據(jù)進(jìn)棧函數(shù)

void Push_D(OPND_Stack *a,double b){ a->top++;a->data[a->top]=b;} //取運(yùn)算符棧頂符函數(shù)

void GetTop_R(OPTR_Stack *a,char *b){ *b=a->data[a->top];} //取數(shù)據(jù)棧頂數(shù)函數(shù)

void GetTop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];} //判斷數(shù)據(jù)是否為運(yùn)算符函數(shù) int In(char a,char *s){ for(int i=0;i<7;i++)

if(a==s[i])

return 1;return 0;} //算符優(yōu)先級(jí)判斷函數(shù)

char Precede(char a,char b){ int m,n;for(int i=0;i<7;i++){

if(a==OP[i])

m=i;

if(b==OP[i])

n=i;} return First[m][n];} //刪除運(yùn)算符棧頂元素，并取新棧的棧頂元素 void Pop_R(OPTR_Stack *a,char *b){ a->top--;*b=a->data[a->top];} //取數(shù)據(jù)站的棧頂元素，并從棧中刪除此元素 void Pop_D(OPND_Stack *a,double *b){ *b=a->data[a->top];a->top--;} //算符優(yōu)先算法求值核心函數(shù)

double EvaluateExpression(char *s){ OPND_Stack OPND;OPTR_Stack OPTR;char ch,theta;double x,a,b;int k=0;strcat(s,“#”);InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);GetTop_R(&OPTR,&ch);while(s[k]!='#'||ch!='#'){

if(In(s[k],OP)==0)

{

x=Getdouble(s,&k);

Push_D(&OPND,x);

}

else

{

switch(Precede(ch,s[k]))

{

case'<':Push_R(&OPTR,s[k]);

k++;

break;

case'=':Pop_R(&OPTR,&ch);

k++;

break;

case'>':GetTop_R(&OPTR,&theta);Pop_R(&OPTR,&ch);

Pop_D(&OPND,&b);Pop_D(&OPND,&a);

Push_D(&OPND,Operate(a,theta,b));

break;

}

}

GetTop_R(&OPTR,&ch);} GetTop_D(&OPND,&x);return x;InitStack_R(&OPTR);Push_R(&OPTR,'#');InitStack_D(&OPND);} //判斷表達(dá)式是否輸入正確.int Can(char a[],int n){ int p=0,s=0,t=0;for(int i=0;i

if(a[i]=='('||a[i]==')')

p++;

if((a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/')&&((a[i+1]<'0'&&a[i+1]!='(')||a[i+1]>'9'))

s++;

if(a[i]=='/'&&a[i+1]=='0')

s++;

if((a[i]=='('&&(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'))||(a[i]==')'&&a[i+1]=='('))

s++;

if(a[i]==')'&&a[i+1]!='