必胜高考网_全国高考备考和志愿填报信息平台

必勝高考網(wǎng) > 計算機類 > 計算機等級 > 資訊 >

全國計算機等級考試四級復(fù)習(xí)綱要:數(shù)據(jù)結(jié)構(gòu)

時間: 家輝2 資訊

  數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。通常,一個數(shù)據(jù)對象中的數(shù)據(jù)元素不是孤立的,而是彼此之間存在著一定的聯(lián)系,這種聯(lián)系就是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)對象中數(shù)據(jù)元素之間的聯(lián)系需要在對數(shù)據(jù)進行存儲和加工中反映出來,因此,數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容:數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計算機中的存儲方式、以及在這些數(shù)據(jù)上定義的運算的集合。

  (1)數(shù)據(jù)的邏輯結(jié)構(gòu)

  數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系,它與數(shù)據(jù)的存儲無關(guān),是獨立于計算機的。

  數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類,線性結(jié)構(gòu)的邏輯特征是:有且僅有一個開始結(jié)點和一個終端結(jié)點,并且所有的結(jié)點都最多有一個直接前驅(qū)和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是:一個結(jié)點可能有多個直接前驅(qū)和直接后繼。樹、圖等都是非線性結(jié)構(gòu)。

  2.算法

  (1)算法及其特征

  簡單地說,一個算法就是一種解題方法,更嚴格地說,算法是由若干條指令組成的有窮序列,它必須具有以下特征:

  ①有窮性 一個算法必須在執(zhí)行有窮步后結(jié)束。

 ?、诖_定性 算法的每一步必須是確切地定義的,無二義性。

 ?、劭尚行?算法中的所有待實現(xiàn)的運算必須在原則上能夠由人使用筆和紙在做有窮次運算后完成。

  ④輸入 一個算法具有0個或多個輸入的外界量,它們是算法開始前對算法最初給出的量。

 ?、葺敵?一個算法至少產(chǎn)生一個輸出,它們是與輸入有某種關(guān)系的量。

  算法的含義與程序十分相似,但二者又有區(qū)別。一個程序不一定滿足有窮性,操作系統(tǒng)就是如此,只要整個系統(tǒng)不被破壞,操作系統(tǒng)就永遠不會停止,所以操作系統(tǒng)程序不是一個算法。另外,程序中的指令必須是機器可以執(zhí)行的,而算法中的指令則無此限制。但是,一個算法如果用機器可執(zhí)行的語言書寫,則它就是一個程序。

  對一個算法的描述可以采用自然語言、數(shù)學(xué)語言、約定的符號語言、以及圖解等方式。

  (2)算法的分析

  求解同一個問題可以有多種不同的算法,評價一個算法的優(yōu)劣除了正確性和簡明性外,主要考慮兩點:一是執(zhí)行算法所耗費的時間,二是執(zhí)行算法所耗費的存儲空間,特別是輔助存儲空間的耗費。就這兩者而言,前者顯得比后者更為重要,在數(shù)據(jù)結(jié)構(gòu)中往往更注重對算法執(zhí)行時間的分析。

  一個算法所耗費的時間是該算法中每條語句的執(zhí)行時間之和,而每條語句的執(zhí)行時間是該語句執(zhí)行次數(shù)(頻度)與該語句一次執(zhí)行所需時間的乘積。如果假定每條語句一次執(zhí)行所需的時間均為單位時間,則一個算法的時間耗費就是該算法中所有語句的頻度之和。

  二、線性表

  (1)線性表及其基本操作

  線性表是n≥0個元素的一個有限序列:(a 1 ,a 2 ,a 3 ,…,a n- 1 ,a n ,)表中元素的個數(shù)n稱為表的長度,長度n=0的表稱為空表。表元素又稱為結(jié)點,線性表的一個重要特性是可以按照諸元素在表中的位置確定它們在表中的先后次序。若n≥1,則a 1 ,為第一個元素,a n 為最后一個元素。元素a i-1 先于a i ,我們稱a i-1 為a i 的前驅(qū);a i 在a i-1 之后,a 1 為a i-1 的后繼。除第一個元素外,每個元素都有一個且僅有一個直接前驅(qū);除最后一個元素外,每個元素都有一個且僅有一個直接后繼,下面所列的是其中一些常用的運算。

 ?、俨檎疫\算

  查找線性表的第i(0≤i≤n-1)個表元;

  在線性表中查找具有給定鍵值的表元;

 ?、诓迦脒\算

  把新表元插在線性表的第i(0≤i≤n)個位置上;

  把新表元插在具有給定鍵值的表元的前面或后面;

 ?、蹌h除運算

  刪除線性表的第i(0≤i≤n-1)個表元;

  刪除線性表中具有給定鍵值的表元;

  ④其他運算

  統(tǒng)計線性表元的個數(shù);

  輸出線性表各表元的值;

  復(fù)制線性表;

  線性表分析;

  線性表合并;

  線性表排序;

  按某種規(guī)則整理線性表。

  (2)線性表的存儲

  有多種存儲方式能將線性表存儲在計算機內(nèi),其中最常用的是順序存儲和鏈接存儲。

 ?、倬€性表的順序存儲

  線性表的順序存儲是最簡單的存儲方式。程序通常用一個足夠大的數(shù)組,從數(shù)組的第一個元素開始,將線性表的結(jié)點依次存儲在數(shù)組中。即線性表的第i個結(jié)點存儲在數(shù)組的第i(0≤i≤n-1)個元素中,用數(shù)組元素的順序存儲來體現(xiàn)線性表中結(jié)點的先后次序關(guān)系。用數(shù)組存儲線性表的最大優(yōu)點是能直接訪問線性表中的任一結(jié)點。

  用數(shù)組存儲線性表的缺點主要有兩個:一是程序中的數(shù)組通常大小是固定的,可能會與線性表的結(jié)點可以任意增加和減少的要求相矛盾;二是執(zhí)行線性表的結(jié)點插、刪操作時要移動存于數(shù)組中的其他元素,使插和刪操作不夠簡便。

 ?、诰€性表的鏈接存儲

  線性表鏈接存儲是用鏈表存儲線性表,最簡單的用單鏈表。如從鏈表的第一個表元開始,將線性表的結(jié)點依次存儲在鏈表的各表元中。即線性表的第i個結(jié)點存儲在鏈表的第i(0≤i≤n-1)個表元中。鏈表的每個表元除要存儲線性結(jié)點的信息外,還要有一個成分用來存儲其后繼結(jié)點的指針。單鏈表就是通過鏈接指針來體現(xiàn)線性表中結(jié)點的先后次序關(guān)系。每個鏈表還要有一個指向鏈表的第一個表元,鏈表的最末一個表元的后繼指針值為空。用鏈表存儲線性表的優(yōu)點是線性表的每個表元的后繼指針就能完成插或刪的操作,不需移動任何表元。

  其缺點也主要有兩條:一是每個表元增加了一個后繼指針成分,要花費更多的存儲空間;二是不便隨機地直接訪問線性表的任一結(jié)點。

  (3)線性表上的查找

  線性表上的查找運算是指在線性表中找某個鏈值的結(jié)點。根據(jù)線性表的存儲形式和線性表本身的性質(zhì)差異,有多種查找算法,如:順序查找、二分法查找、分塊查找、散列查找等。

56710 主站蜘蛛池模板: 今日热点_实时热点_奇闻异事_趣闻趣事_灵异事件 - 奇闻事件 | 雨燕360体育免费直播_雨燕360免费NBA直播_NBA篮球高清直播无插件-雨燕360体育直播 | 精密模具-双色注塑模具加工-深圳铭洋宇通 | 仓储货架_南京货架_钢制托盘_仓储笼_隔离网_环球零件盒_诺力液压车_货架-南京一品仓储设备制造公司 | 不锈钢电动球阀_气动高压闸阀_旋塞疏水调节阀_全立阀门-来自温州工业阀门巨头企业 | 塑料异型材_PVC异型材_封边条生产厂家_PC灯罩_防撞扶手_医院扶手价格_东莞市怡美塑胶制品有限公司 | 山东齐鲁漆业有限公司【官网】-工业漆专业生产厂家 | 派克防爆伺服电机品牌|国产防爆伺服电机|高低温伺服电机|杭州摩森机电科技有限公司 | 技德应用| 玻璃钢罐_玻璃钢储罐_盐酸罐厂家-河北华盛节能设备有限公司 | 噪声治理公司-噪音治理专业隔音降噪公司 | ?水马注水围挡_塑料注水围挡_防撞桶-常州瑞轩水马注水围挡有限公司 | 彩信群发_群发彩信软件_视频短信营销平台-达信通| 撕碎机_轮胎破碎机_粉碎机_回收生产线厂家_东莞华达机械有限公司 | 北京开业庆典策划-年会活动策划公司-舞龙舞狮团大鼓表演-北京盛乾龙狮鼓乐礼仪庆典策划公司 | 物联网卡_物联网卡购买平台_移动物联网卡办理_移动联通电信流量卡通信模组采购平台? | 精密光学实验平台-红外粉末压片机模具-天津博君 | 东风体检车厂家_公共卫生体检车_医院体检车_移动体检车-锦沅科贸 | 翅片管散热器价格_钢制暖气片报价_钢制板式散热器厂家「河北冀春暖气片有限公司」 | 刑事律师_深圳著名刑事辩护律师_王平聚【清华博士|刑法教授】 | 知名电动蝶阀,电动球阀,气动蝶阀,气动球阀生产厂家|价格透明-【固菲阀门官网】 | 蔬菜清洗机_环速洗菜机_异物去除清洗机_蔬菜清洗机_商用洗菜机 - 环速科技有限公司 | 明渠式紫外线杀菌器-紫外线消毒器厂家-定州市优威环保 | 微信聊天记录恢复_手机短信删除怎么恢复_通讯录恢复软件下载-快易数据恢复 | 电子海图系统-电梯检验系统-智慧供热系统开发-商品房预售资金监管系统 | 节流截止放空阀-不锈钢阀门-气动|电动截止阀-鸿华阀门有限公司 | Win10系统下载_32位/64位系统/专业版/纯净版下载 | 一体化预制泵站-一体化提升泵站-一体化泵站厂家-山东康威环保 | 免费分销系统 — 分销商城系统_分销小程序开发 -【微商来】 | 聚合氯化铝-碱式氯化铝-聚合硫酸铁-聚氯化铝铁生产厂家多少钱一吨-聚丙烯酰胺价格_河南浩博净水材料有限公司 | 数码听觉统合训练系统-儿童感觉-早期言语评估与训练系统-北京鑫泰盛世科技发展有限公司 | 数控专用机床,专用机床,自动线,组合机床,动力头,自动化加工生产线,江苏海鑫机床有限公司 | 砍排机-锯骨机-冻肉切丁机-熟肉切片机-预制菜生产线一站式服务厂商 - 广州市祥九瑞盈机械设备有限公司 | 红酒招商加盟-葡萄酒加盟-进口红酒代理-青岛枞木酒业有限公司 | 气动绞车,山东气动绞车,气动绞车厂家-烟台博海石油机械有限公司 气动隔膜泵厂家-温州永嘉定远泵阀有限公司 | 胀套-锁紧盘-风电锁紧盘-蛇形联轴器「厂家」-瑞安市宝德隆机械配件有限公司 | 不锈钢螺丝 - 六角螺丝厂家 - 不锈钢紧固件 - 万千紧固件--紧固件一站式采购 | 济南玻璃安装_济南玻璃门_济南感应门_济南玻璃隔断_济南玻璃门维修_济南镜片安装_济南肯德基门_济南高隔间-济南凯轩鹏宇玻璃有限公司 | 海外仓系统|国际货代系统|退货换标系统|WMS仓储系统|海豚云 | 石油/泥浆/不锈钢防腐/砂泵/抽砂泵/砂砾泵/吸砂泵/压滤机泵 - 专业石油环保专用泵厂家 | 真丝围巾|真丝丝巾|羊绒围巾|围巾品牌|浙江越缇围巾厂家定制 |