基于C程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)離散型混合研究

鄧定勝

摘要：作為一個(gè)擁有離散結(jié)構(gòu)的數(shù)字電子計(jì)算機(jī)，它的操作對(duì)象只有離散和離散化了的數(shù)量關(guān)系，所以不光是計(jì)算機(jī)科學(xué)，還有與它和它的應(yīng)用緊密相連的現(xiàn)代科學(xué)研究領(lǐng)域都面臨著同一個(gè)難題，那就是在建立與離散結(jié)構(gòu)對(duì)應(yīng)的數(shù)學(xué)模型同時(shí)，怎樣離散已經(jīng)利用連續(xù)數(shù)量關(guān)系而建成的數(shù)字模型，并利用計(jì)算機(jī)來(lái)進(jìn)行處理。事實(shí)上離散數(shù)學(xué)大致可以被認(rèn)為是抽象化了的計(jì)算機(jī)問(wèn)題，數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)中都能夠體現(xiàn)出離散性。計(jì)算機(jī)里能夠表現(xiàn)離散性的問(wèn)題有很多，因此計(jì)算機(jī)科學(xué)在研究離散數(shù)學(xué)時(shí)有多種選擇，這些表現(xiàn)大致都能夠被認(rèn)為是計(jì)算機(jī)中的二進(jìn)制。本文主要從其算法、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)與數(shù)字電子、計(jì)算機(jī)中的離散型問(wèn)題以及實(shí)驗(yàn)仿真五個(gè)方面出發(fā)，對(duì)計(jì)算機(jī)的算法設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)離散進(jìn)行了一定的研究和分析。希望可以對(duì)有關(guān)方面的改善和促進(jìn)起到一定的借鑒作用和指導(dǎo)意義。

關(guān)鍵詞：C程序設(shè)計(jì);數(shù)據(jù)結(jié)構(gòu);離散型;算法

中圖分類(lèi)號(hào)：TP311 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）14-0210-03

Abstract： As a digital computer with discrete structure， its operating object only has discrete and discrete quantitative relationship， so not only computer science， but also modern scientific research fields closely linked with its application are facing the same problem， that is， how to discretize the continuous number while establishing the mathematical model corresponding to the discrete structure The digital model built by the relationship is processed by computer. In fact， discrete mathematics can be roughly regarded as abstract computer problems， which can be reflected in data structure and algorithm design. There are many problems in computer that can express discreteness， so computer science has many choices in the study of discrete mathematics， which can be roughly considered as binary in computer. In this paper， the algorithm design and data structure discretization of computer are studied and analyzed from five aspects： algorithm， data structure， discrete mathematics and digital electronics， discrete problems in computer and experimental simulation. I hope it can play a certain role in reference and guiding significance for the improvement and promotion of relevant parties.

Key words： C Programming; Data Structure; Discrete Type; Algorithms

互聯(lián)網(wǎng)行業(yè)的發(fā)展日新月異，引起了人們的高度重視，尤其是其中最為重要的計(jì)算機(jī)行業(yè)。理論上最應(yīng)該受到重視的就是數(shù)據(jù)結(jié)構(gòu)與程序算法，可大多數(shù)人本末倒置，對(duì)程序結(jié)果更為重視。

本文就如何體現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的離散性提出了方法，具體地說(shuō)明了怎樣解決抽象化了的計(jì)算機(jī)問(wèn)題，以達(dá)到把連續(xù)性到離散性的思維方法傳輸給讀者的目的。

作為一種科學(xué)知識(shí)，計(jì)算機(jī)算法與結(jié)構(gòu)是計(jì)算機(jī)科學(xué)中必不可少的，它是模擬實(shí)驗(yàn)和進(jìn)行計(jì)算機(jī)科學(xué)計(jì)算的主要工具，能夠促進(jìn)未來(lái)計(jì)算機(jī)科學(xué)的發(fā)展。最近幾年，計(jì)算機(jī)科學(xué)發(fā)展迅速，獲得了非常多的成就。基礎(chǔ)科學(xué)給計(jì)算機(jī)科學(xué)提供了應(yīng)有的理論支持，把計(jì)算機(jī)科學(xué)應(yīng)用在現(xiàn)實(shí)生活之中，并結(jié)合基礎(chǔ)科學(xué)構(gòu)成了其發(fā)展的基礎(chǔ)性理論[1]。數(shù)學(xué)知識(shí)是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)，在解決存在于應(yīng)用過(guò)程中的各種各樣的問(wèn)題時(shí)，需要把計(jì)算機(jī)問(wèn)題抽象化，從而把它當(dāng)作數(shù)學(xué)問(wèn)題。

1 算法

本節(jié)在表述計(jì)算機(jī)離散性問(wèn)題時(shí)通常利用算法。本節(jié)就算法的基本概念給出了概述，同時(shí)利用雙算法設(shè)計(jì)的方式來(lái)表現(xiàn)離散性。本節(jié)在表述算法時(shí)都利用了c語(yǔ)言。

1.1算法的基本概念

算法就是準(zhǔn)確又具體地去描述解題方案，是能夠把問(wèn)題解決的一連串的明確指令，而且算法作為一種策略機(jī)制，在描述與解決問(wèn)題時(shí)能夠利用系統(tǒng)的方法。意思就是，可以在短時(shí)間內(nèi)得到一定規(guī)范的輸入所對(duì)應(yīng)要求的輸出。

算法應(yīng)用在流程型的程序中時(shí)沒(méi)有什么特別高的要求，可是在人機(jī)交互、圖形圖像識(shí)別、人工智能、虛擬現(xiàn)實(shí)、社會(huì)工程學(xué)、大數(shù)據(jù)分析、音視頻識(shí)別、現(xiàn)實(shí)增強(qiáng)、云計(jì)算、大型網(wǎng)絡(luò)拓?fù)涞阮I(lǐng)域中應(yīng)用時(shí)，對(duì)算法的要求就比較高了。

在日常生活中就能發(fā)現(xiàn)一些比較好的算法設(shè)計(jì)，例如手機(jī)中各種各樣的美圖軟件。軟件怎樣把人臉識(shí)別出來(lái)？怎樣確定眼睛、嘴巴和鼻子在人臉上的位置？怎樣在人臉上進(jìn)行一定的不失真的美化？

在世界第二次大戰(zhàn)進(jìn)行時(shí)，以人工智能之父、計(jì)算機(jī)科學(xué)之父阿蘭·圖靈為領(lǐng)頭人的小組幫助盟軍把能夠破譯德國(guó)密碼系統(tǒng)Enigma的機(jī)器設(shè)計(jì)了出來(lái)。當(dāng)中對(duì)機(jī)器的設(shè)計(jì)過(guò)程可以被認(rèn)為是算法的設(shè)計(jì)過(guò)程。事實(shí)上可以說(shuō)是圖靈設(shè)計(jì)小組做出了一個(gè)能夠把德國(guó)納粹密碼系統(tǒng)在短時(shí)間內(nèi)解密出來(lái)的算法，同時(shí)為之相應(yīng)的設(shè)計(jì)出了機(jī)器。

由此可知，程序的根本就是算法。不管是普通的高等院校還是在世界上都處于前沿的科技企業(yè)，在進(jìn)行關(guān)于計(jì)算機(jī)或者程序的科學(xué)性研究時(shí)，都必然會(huì)涉及算法的研究。算法的設(shè)計(jì)是所有的系統(tǒng)中最基礎(chǔ)、最關(guān)鍵的首要步驟。

1.2算法體現(xiàn)的離散性

在進(jìn)行算法的設(shè)計(jì)時(shí)，通常能夠體現(xiàn)離散性[2]，離散性作為一種不連續(xù)的特性在計(jì)算機(jī)科學(xué)中可以經(jīng)常見(jiàn)到。

1.2.1算法設(shè)計(jì)常用的方法

算法設(shè)計(jì)有許多方法與有關(guān)文獻(xiàn)。這里介紹了兩種最簡(jiǎn)單的方法：遞推法和遞歸法，而且在后面做出了相關(guān)舉例。

（1）遞推法

遞推算法在序列計(jì)算機(jī)中是比較常見(jiàn)的，它的特點(diǎn)是化難為易，化繁為簡(jiǎn)。因?yàn)橛?jì)算機(jī)是一種機(jī)器，它的運(yùn)行速度非常快，而且不會(huì)疲憊，所以在計(jì)算序列各項(xiàng)時(shí)，有一定的規(guī)律可循，一般要想知道序列中指定的項(xiàng)，需要利用計(jì)算機(jī)前面的一些項(xiàng)來(lái)求得。其原理是把龐大又復(fù)雜的計(jì)算過(guò)程分割成多次重復(fù)的簡(jiǎn)單又容易的過(guò)程[3]。

（2）遞歸法

遞歸就是程序?qū)⒆陨淼木幊碳记杉右赃\(yùn)用的過(guò)程。表現(xiàn)為一個(gè)過(guò)程或者函數(shù)在它的說(shuō)明和定義中涉及自身的調(diào)用，它一般是將一個(gè)比較龐大復(fù)雜的問(wèn)題一點(diǎn)點(diǎn)轉(zhuǎn)化成一個(gè)大概等同于原問(wèn)題的比較小型且簡(jiǎn)單的問(wèn)題，并求解。在將一個(gè)有著多次重復(fù)計(jì)算的解題過(guò)程簡(jiǎn)化時(shí)，需要運(yùn)用遞歸法，而且僅僅需要很少的程序量就能夠解決，使程序的代碼量降低了很多。遞歸的能力表現(xiàn)在定義對(duì)象的無(wú)限集合時(shí)用的是有限的語(yǔ)句。通常遞歸的三要素是有邊界條件、遞歸前進(jìn)段以及遞歸返回段。如果邊界條件不滿足，那么遞歸前進(jìn)，反之，遞歸返回。

1.2.2兩種方法的離散性體現(xiàn)

遞推法中，計(jì)算機(jī)在進(jìn)行一個(gè)比較復(fù)雜的運(yùn)算時(shí)，用的方法比較傻。例如算法1，通過(guò)一個(gè)求最大值的算法來(lái)解釋。

算法1：求最大值

int max（int *array，int size）

{int mval=*array;

int i;

for（i=1;i

if（array[i]>mval）

mval=array[i];

return（mval）;

}

由此可見(jiàn)，不管有多少數(shù)字，只要還沒(méi)有得出最終結(jié)果，計(jì)算機(jī)就會(huì)一直按部就班地用已知的最大的數(shù)去比較數(shù)組中的下一個(gè)數(shù)。相比來(lái)說(shuō)，人類(lèi)就不會(huì)用這種死板的方式去比較數(shù)字的大小，在數(shù)字特別多的情況下時(shí)，人們就會(huì)先把數(shù)字的位數(shù)最高的挑出來(lái)，如果有多個(gè)位數(shù)最高的數(shù)字，再讓它們?nèi)ケ容^。人類(lèi)比較習(xí)慣應(yīng)用連續(xù)性的思維模式，所以由人而產(chǎn)生的初等數(shù)學(xué)都是建立在連續(xù)的基礎(chǔ)之上，從而也出現(xiàn)了幾何的概念。可是計(jì)算機(jī)作為硬邦邦的機(jī)器，不具備人類(lèi)思維靈活的特點(diǎn)，也就很難有這種連續(xù)的思維。要想讓計(jì)算機(jī)模擬人類(lèi)的連續(xù)性思維，必須為之設(shè)計(jì)出更為復(fù)雜多變的算法。人類(lèi)之所以能夠擁有這種連續(xù)性的思維，是因?yàn)樽鳛樗季S控制中心的人類(lèi)大腦這個(gè)驅(qū)動(dòng)器非常的高級(jí)，自身就能夠擁有足夠復(fù)雜的算法。目前有不少的相關(guān)研究和文獻(xiàn)能夠?yàn)槿绾卧O(shè)計(jì)出更為復(fù)雜的算法、讓計(jì)算機(jī)的運(yùn)行更為快速并能模擬出人腦的思維方式提供資料，然而這并不是本文的重點(diǎn)。

有時(shí)能夠用遞歸法來(lái)讓算法更加的簡(jiǎn)單，例如在求兩個(gè)自然數(shù)的最大公約數(shù)時(shí)，如算法2，其改用遞歸算法后如算法3。

算法2：求最大公約數(shù)

void swap（int *x，int *y）

{int tmp=*x;

*x=*y;

*y=tmp;

}

int ged（int m，int n）

{int r;

do

{if（m

swap（&m，&n）;

r=m%n;

m=n;

n=r;

}while（n！=0）

return（m）;

}

算法3：遞歸法求最大公約數(shù)

int gcd（int a，int b）

{if（a%b）

return（gcd（b，a%b）;

return（b）;

}

可以把遞歸法理解為“自己調(diào)用自己”。一種離散性的表現(xiàn)和先前的例子差不多，這里就不再重復(fù)了。這里就程序運(yùn)行所表現(xiàn)出來(lái)的離散性做出表述。計(jì)算機(jī)是在以“后進(jìn)先出”為特點(diǎn)的棧中進(jìn)行運(yùn)行程序的。在這個(gè)遞歸算法的運(yùn)行過(guò)程中，“自己”就可以滿足返回值的需要，就是參數(shù)不同而已。一直到返回出一個(gè)確定的值，再層層返回，如圖1 所示。

由此可知，在計(jì)算完成之前，計(jì)算機(jī)每用遞歸法計(jì)算一次，就伴隨著一次Push內(nèi)存，在計(jì)算完成之時(shí)，再開(kāi)始一次一次有序的Pop出，這體現(xiàn)出了計(jì)算的離散性，與人類(lèi)連續(xù)的思維模式是有區(qū)別的。

2 數(shù)據(jù)結(jié)構(gòu)

本節(jié)在表述計(jì)算機(jī)中的離散性問(wèn)題時(shí)主要利用數(shù)據(jù)結(jié)構(gòu)，就數(shù)據(jù)結(jié)構(gòu)的基本概念與其離散性的基本理解給出了概括。

2.1數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中有著舉足輕重的地位。因?yàn)閿?shù)據(jù)元素之間有著不同的特性關(guān)系，通常可以把其基本結(jié)構(gòu)分為四種：樹(shù)形結(jié)構(gòu)、集合、線性結(jié)構(gòu)、網(wǎng)狀或圖狀結(jié)構(gòu)，圖2就表示了來(lái)自于數(shù)據(jù)結(jié)構(gòu)的元素之中的離散性特征[4]。