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

必勝高考網(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 主站蜘蛛池模板: 高精度-恒温冷水机-螺杆式冰水机-蒸发冷冷水机-北京蓝海神骏科技有限公司 | 安徽华耐泵阀有限公司-官方网站 安德建奇火花机-阿奇夏米尔慢走丝|高维|发那科-北京杰森柏汇 | 拖链电缆_柔性电缆_伺服电缆_坦克链电缆-深圳市顺电工业电缆有限公司 | 一级建造师培训_一建培训机构_中建云筑建造师培训网校 | 技德应用| 珠海白蚁防治_珠海灭鼠_珠海杀虫灭鼠_珠海灭蟑螂_珠海酒店消杀_珠海工厂杀虫灭鼠_立净虫控防治服务有限公司 | 贵州自考_贵州自学考试网| 代理记账_免费注册公司_营业执照代办_资质代办-【乐财汇】 | 气动调节阀,电动调节阀,自力式压力调节阀,切断阀「厂家」-浙江利沃夫自控阀门 | 顺景erp系统_erp软件_erp软件系统_企业erp管理系统-广东顺景软件科技有限公司 | 在线浊度仪_悬浮物污泥浓度计_超声波泥位计_污泥界面仪_泥水界面仪-无锡蓝拓仪表科技有限公司 | 电动葫芦|防爆钢丝绳电动葫芦|手拉葫芦-保定大力起重葫芦有限公司 | 检验科改造施工_DSA手术室净化_导管室装修_成都特殊科室建设厂家_医疗净化工程公司_四川华锐 | 冷却塔风机厂家_静音冷却塔风机_冷却塔电机维修更换维修-广东特菱节能空调设备有限公司 | 苗木价格-苗木批发-沭阳苗木基地-沭阳花木-长之鸿园林苗木场 | ★济南领跃标识制作公司★济南标识制作,标牌制作,山东标识制作,济南标牌厂 | 国产离子色谱仪,红外分光测油仪,自动烟尘烟气测试仪-青岛埃仑通用科技有限公司 | 食药成分检测_调料配方还原_洗涤剂化学成分分析_饲料_百检信息科技有限公司 | 郑州大巴车出租|中巴车租赁|旅游大巴租车|包车|郑州旅游大巴车租赁有限公司 | 防水套管厂家-柔性防水套管-不锈钢|刚性防水套管-天翔管道 | 精密模具制造,注塑加工,吹塑和吹瓶加工,EPS泡沫包装生产 - 济南兴田塑胶有限公司 | 天津市能谱科技有限公司-专业的红外光谱仪_红外测油仪_紫外测油仪_红外制样附件_傅里叶红外光谱技术生产服务厂商 | 无锡网站建设-做网站-建网站-网页设计制作-阿凡达建站公司 | 缓蚀除垢剂_循环水阻垢剂_反渗透锅炉阻垢剂_有机硫化物-郑州威大水处理材料有限公司 | 电表箱-浙江迈峰电力设备有限公司-电表箱专业制造商 | 美的商用净水器_美的直饮机_一级代理经销商_Midea租赁价格-厂家反渗透滤芯-直饮水批发品牌售后 | 拉力机-拉力试验机-万能试验机-电子拉力机-拉伸试验机-剥离强度试验机-苏州皖仪实验仪器有限公司 | 贝壳粉涂料-内墙腻子-外墙腻子-山东巨野七彩贝壳漆业中心 | 浴室柜-浴室镜厂家-YINAISI · 意大利设计师品牌 | 咿耐斯 |-浙江台州市丰源卫浴有限公司 | 耙式干燥机_真空耙式干燥机厂家-无锡鹏茂化工装备有限公司 | 电动液压篮球架_圆管地埋式篮球架_移动平箱篮球架-强森体育 | 反渗透水处理设备|工业零排放|水厂设备|软化水设备|海南净水设备--海南水处理设备厂家 | 深圳公司注册-工商注册公司-千百顺代理记账公司 | 工业胀紧套_万向节联轴器_链条-规格齐全-型号选购-非标订做-厂家批发价格-上海乙谛精密机械有限公司 | 奶茶加盟,奶茶加盟店连锁品牌-甜啦啦官网 | 选宝石船-陆地水上开采「精选」色选机械设备-青州冠诚重工机械有限公司 | 运动木地板_体育木地板_篮球馆木地板_舞台木地板-实木运动地板厂家 | 纳米二氧化硅,白炭黑,阴离子乳化剂-臻丽拾科技| 喷涂流水线,涂装流水线,喷漆流水线-山东天意设备科技有限公司 | 煤矿支护网片_矿用勾花菱形网_缝管式_管缝式锚杆-邯郸市永年区志涛工矿配件有限公司 | 东莞市海宝机械有限公司-不锈钢分选机-硅胶橡胶-生活垃圾-涡电流-静电-金属-矿石分选机 |