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

必勝高考網(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 主站蜘蛛池模板: 南京试剂|化学试剂|分析试剂|实验试剂|cas号查询-专业60年试剂销售企业 | 合肥通道闸-安徽车牌识别-人脸识别系统厂家-安徽熵控智能技术有限公司 | 量子管通环-自清洗过滤器-全自动反冲洗过滤器-北京罗伦过滤技术集团有限公司 | 新能源汽车电池软连接,铜铝复合膜柔性连接,电力母排-容发智能科技(无锡)有限公司 | 合肥抖音SEO网站优化-网站建设-网络推广营销公司-百度爱采购-安徽企匠科技 | 点焊机-缝焊机-闪光对焊机-电阻焊设备生产厂家-上海骏腾发智能设备有限公司 | 颚式破碎机,圆锥破碎机,制砂机-新乡市德诚机电制造有限公司 | 中药超微粉碎机(中药细胞级微粉碎)-百科 | 包塑软管|金属软管|包塑金属软管-闵彬管业 | 气象监测系统_气象传感器_微型气象仪_气象环境监测仪-山东风途物联网 | 蜘蛛车-登高车-高空作业平台-高空作业车-曲臂剪叉式升降机租赁-重庆海克斯公司 | 飞象网 - 通信人每天必上的网站| 一体化污水处理设备-一体化净水设备-「山东梦之洁水处理」 | 造价工程师网,考试时间查询,报名入口信息-网站首页 | SRRC认证_电磁兼容_EMC测试整改_FCC认证_SDOC认证-深圳市环测威检测技术有限公司 | 云阳人才网_云阳招聘网_云阳人才市场_云阳人事人才网_云阳人家招聘网_云阳最新招聘信息 | 电梯乘运质量测试仪_电梯安全评估测试仪-武汉懿之刻 | 锂电池砂磨机|石墨烯砂磨机|碳纳米管砂磨机-常州市奥能达机械设备有限公司 | 长沙一级消防工程公司_智能化弱电_机电安装_亮化工程专业施工承包_湖南公共安全工程有限公司 | 欧洲MV日韩MV国产_人妻无码一区二区三区免费_少妇被 到高潮喷出白浆av_精品少妇自慰到喷水AV网站 | 奥运星-汽车性能网评-提供个性化汽车资讯 | 万家财经_财经新闻_在线财经资讯网| 门禁卡_智能IC卡_滴胶卡制作_硅胶腕带-卡立方rfid定制厂家 | 全自动固相萃取仪_高通量真空平行浓缩仪-勤业永为 | 耐酸碱泵-自吸耐酸碱泵型号「品牌厂家」立式耐酸碱泵价格-昆山国宝过滤机有限公司首页 | 3d可视化建模_三维展示_产品3d互动数字营销_三维动画制作_3D虚拟商城 【商迪3D】三维展示服务商 广东健伦体育发展有限公司-体育工程配套及销售运动器材的体育用品服务商 | 识禅_对禅的了解,从这里开始| 五轴加工中心_数控加工中心_铝型材加工中心-罗威斯 | 煤矿人员精确定位系统_矿用无线通信系统_煤矿广播系统 | 鄂泉泵业官网|(杭州、上海、全国畅销)大流量防汛排涝泵-LW立式排污泵 | 胶原检测试剂盒,弹性蛋白检测试剂盒,类克ELISA试剂盒,阿达木单抗ELISA试剂盒-北京群晓科苑生物技术有限公司 | vr安全体验馆|交通安全|工地安全|禁毒|消防|安全教育体验馆|安全体验教室-贝森德(深圳)科技 | 厦门ISO认证|厦门ISO9001认证|厦门ISO14001认证|厦门ISO45001认证-艾索咨询专注ISO认证行业 | 广州冷却塔维修厂家_冷却塔修理_凉水塔风机电机填料抢修-广东康明节能空调有限公司 | 药品/药物稳定性试验考察箱-埃里森仪器设备(上海)有限公司 | 选矿设备,选矿生产线,选矿工艺,选矿技术-昆明昆重矿山机械 | 安驭邦官网-双向万能直角铣头,加工中心侧铣头,角度头[厂家直销] 闸阀_截止阀_止回阀「生产厂家」-上海卡比阀门有限公司 | 合肥展厅设计-安徽展台设计-合肥展览公司-安徽奥美展览工程有限公司 | 超声波气象站_防爆气象站_空气质量监测站_负氧离子检测仪-风途物联网 | 户外环保不锈钢垃圾桶_标识标牌制作_园林公园椅厂家_花箱定制-北京汇众环艺 | SMC-SMC电磁阀-日本SMC气缸-SMC气动元件展示网 |