基于C程序設計與數據結構離散型混合研究

鄧定勝

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

關鍵詞：C程序設計;數據結構;離散型;算法

中圖分類號：TP311 ? ? 文獻標識碼：A

文章編號：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

互聯網行業的發展日新月異，引起了人們的高度重視，尤其是其中最為重要的計算機行業。理論上最應該受到重視的就是數據結構與程序算法，可大多數人本末倒置，對程序結果更為重視。

本文就如何體現數據結構與算法設計的離散性提出了方法，具體地說明了怎樣解決抽象化了的計算機問題，以達到把連續性到離散性的思維方法傳輸給讀者的目的。

作為一種科學知識，計算機算法與結構是計算機科學中必不可少的，它是模擬實驗和進行計算機科學計算的主要工具，能夠促進未來計算機科學的發展。最近幾年，計算機科學發展迅速，獲得了非常多的成就。基礎科學給計算機科學提供了應有的理論支持，把計算機科學應用在現實生活之中，并結合基礎科學構成了其發展的基礎性理論[1]。數學知識是計算機科學的理論基礎，在解決存在于應用過程中的各種各樣的問題時，需要把計算機問題抽象化，從而把它當作數學問題。

1 算法

本節在表述計算機離散性問題時通常利用算法。本節就算法的基本概念給出了概述，同時利用雙算法設計的方式來表現離散性。本節在表述算法時都利用了c語言。

1.1算法的基本概念

算法就是準確又具體地去描述解題方案，是能夠把問題解決的一連串的明確指令，而且算法作為一種策略機制，在描述與解決問題時能夠利用系統的方法。意思就是，可以在短時間內得到一定規范的輸入所對應要求的輸出。

算法應用在流程型的程序中時沒有什么特別高的要求，可是在人機交互、圖形圖像識別、人工智能、虛擬現實、社會工程學、大數據分析、音視頻識別、現實增強、云計算、大型網絡拓撲等領域中應用時，對算法的要求就比較高了。

在日常生活中就能發現一些比較好的算法設計，例如手機中各種各樣的美圖軟件。軟件怎樣把人臉識別出來？怎樣確定眼睛、嘴巴和鼻子在人臉上的位置？怎樣在人臉上進行一定的不失真的美化？

在世界第二次大戰進行時，以人工智能之父、計算機科學之父阿蘭·圖靈為領頭人的小組幫助盟軍把能夠破譯德國密碼系統Enigma的機器設計了出來。當中對機器的設計過程可以被認為是算法的設計過程。事實上可以說是圖靈設計小組做出了一個能夠把德國納粹密碼系統在短時間內解密出來的算法，同時為之相應的設計出了機器。

由此可知，程序的根本就是算法。不管是普通的高等院校還是在世界上都處于前沿的科技企業，在進行關于計算機或者程序的科學性研究時，都必然會涉及算法的研究。算法的設計是所有的系統中最基礎、最關鍵的首要步驟。

1.2算法體現的離散性

在進行算法的設計時，通常能夠體現離散性[2]，離散性作為一種不連續的特性在計算機科學中可以經常見到。

1.2.1算法設計常用的方法

算法設計有許多方法與有關文獻。這里介紹了兩種最簡單的方法：遞推法和遞歸法，而且在后面做出了相關舉例。

（1）遞推法

遞推算法在序列計算機中是比較常見的，它的特點是化難為易，化繁為簡。因為計算機是一種機器，它的運行速度非常快，而且不會疲憊，所以在計算序列各項時，有一定的規律可循，一般要想知道序列中指定的項，需要利用計算機前面的一些項來求得。其原理是把龐大又復雜的計算過程分割成多次重復的簡單又容易的過程[3]。

（2）遞歸法

遞歸就是程序將自身的編程技巧加以運用的過程。表現為一個過程或者函數在它的說明和定義中涉及自身的調用，它一般是將一個比較龐大復雜的問題一點點轉化成一個大概等同于原問題的比較小型且簡單的問題，并求解。在將一個有著多次重復計算的解題過程簡化時，需要運用遞歸法，而且僅僅需要很少的程序量就能夠解決，使程序的代碼量降低了很多。遞歸的能力表現在定義對象的無限集合時用的是有限的語句。通常遞歸的三要素是有邊界條件、遞歸前進段以及遞歸返回段。如果邊界條件不滿足，那么遞歸前進，反之，遞歸返回。

1.2.2兩種方法的離散性體現

遞推法中，計算機在進行一個比較復雜的運算時，用的方法比較傻。例如算法1，通過一個求最大值的算法來解釋。

算法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）;

}

由此可見，不管有多少數字，只要還沒有得出最終結果，計算機就會一直按部就班地用已知的最大的數去比較數組中的下一個數。相比來說，人類就不會用這種死板的方式去比較數字的大小，在數字特別多的情況下時，人們就會先把數字的位數最高的挑出來，如果有多個位數最高的數字，再讓它們去比較。人類比較習慣應用連續性的思維模式，所以由人而產生的初等數學都是建立在連續的基礎之上，從而也出現了幾何的概念。可是計算機作為硬邦邦的機器，不具備人類思維靈活的特點，也就很難有這種連續的思維。要想讓計算機模擬人類的連續性思維，必須為之設計出更為復雜多變的算法。人類之所以能夠擁有這種連續性的思維，是因為作為思維控制中心的人類大腦這個驅動器非常的高級，自身就能夠擁有足夠復雜的算法。目前有不少的相關研究和文獻能夠為如何設計出更為復雜的算法、讓計算機的運行更為快速并能模擬出人腦的思維方式提供資料，然而這并不是本文的重點。

有時能夠用遞歸法來讓算法更加的簡單，例如在求兩個自然數的最大公約數時，如算法2，其改用遞歸算法后如算法3。

算法2：求最大公約數

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：遞歸法求最大公約數

int gcd（int a，int b）

{if（a%b）

return（gcd（b，a%b）;

return（b）;

}

可以把遞歸法理解為“自己調用自己”。一種離散性的表現和先前的例子差不多，這里就不再重復了。這里就程序運行所表現出來的離散性做出表述。計算機是在以“后進先出”為特點的棧中進行運行程序的。在這個遞歸算法的運行過程中，“自己”就可以滿足返回值的需要，就是參數不同而已。一直到返回出一個確定的值，再層層返回，如圖1 所示。

由此可知，在計算完成之前，計算機每用遞歸法計算一次，就伴隨著一次Push內存，在計算完成之時，再開始一次一次有序的Pop出，這體現出了計算的離散性，與人類連續的思維模式是有區別的。

2 數據結構

本節在表述計算機中的離散性問題時主要利用數據結構，就數據結構的基本概念與其離散性的基本理解給出了概括。

2.1數據結構的基本概念

數據結構在計算機科學中有著舉足輕重的地位。因為數據元素之間有著不同的特性關系，通常可以把其基本結構分為四種：樹形結構、集合、線性結構、網狀或圖狀結構，圖2就表示了來自于數據結構的元素之中的離散性特征[4]。