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

必勝高考網(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 主站蜘蛛池模板: 十二星座查询(性格特点分析、星座运势解读) - 玄米星座网 | 断桥铝破碎机_铝合金破碎机_废铁金属破碎机-河南鑫世昌机械制造有限公司 | 绿叶|绿叶投资|健康产业_绿叶投资集团有限公司 | 亚洲工业智能制造领域专业门户网站 - 亚洲自动化与机器人网 | 找培训机构_找学习课程_励普教育 | 多功能干燥机,过滤洗涤干燥三合一设备-无锡市张华医药设备有限公司 | 拉力机-万能试验机-材料拉伸试验机-电子拉力机-拉力试验机厂家-冲击试验机-苏州皖仪实验仪器有限公司 | 「安徽双凯」自动售货机-无人售货机-成人用品-自动饮料食品零食售货机 | ISO9001认证咨询_iso9001企业认证代理机构_14001|18001|16949|50430认证-艾世欧认证网 | 布袋除尘器-单机除尘器-脉冲除尘器-泊头市兴天环保设备有限公司 布袋除尘器|除尘器设备|除尘布袋|除尘设备_诺和环保设备 | 上海小程序开发-上海小程序制作公司-上海网站建设-公众号开发运营-软件外包公司-咏熠科技 | 冷柜风机-冰柜电机-罩极电机-外转子风机-EC直流电机厂家-杭州金久电器有限公司 | 打包钢带,铁皮打包带,烤蓝打包带-高密市金和金属制品厂 | 空心明胶胶囊|植物胶囊|清真胶囊|浙江绿键胶囊有限公司欢迎您! | 金刚网,金刚网窗纱,不锈钢网,金刚网厂家- 河北萨邦丝网制品有限公司 | 好看的韩国漫画_韩漫在线免费阅读-汗汗漫画 | 耐破强度测试仪-纸箱破裂强度试验机-济南三泉中石单品站 | 多功能真空滤油机_润滑油全自动滤油机_高效真空滤油机价格-重庆润华通驰 | 广东佛电电器有限公司|防雷开关|故障电弧断路器|智能量测断路器 广东西屋电气有限公司-广东西屋电气有限公司 | 广州云仓代发-昊哥云仓专业电商仓储托管外包代发货服务 | ★塑料拖链__工程拖链__电缆拖链__钢制拖链 - 【上海闵彬】 | 玉米深加工机械,玉米加工设备,玉米加工机械等玉米深加工设备制造商-河南成立粮油机械有限公司 | 亮化工程,亮化设计,城市亮化工程,亮化资质合作,长沙亮化照明,杰奥思【官网】 | 小型UV打印机-UV平板打印机-大型uv打印机-UV打印机源头厂家 |松普集团 | 数控专用机床,专用机床,自动线,组合机床,动力头,自动化加工生产线,江苏海鑫机床有限公司 | 小程序开发公司_APP开发多少钱_软件开发定制_微信小程序制作_客户销售管理软件-济南小溪畅流网络科技有限公司 | 多功能干燥机,过滤洗涤干燥三合一设备-无锡市张华医药设备有限公司 | 山西3A认证|太原AAA信用认证|投标AAA信用证书-山西AAA企业信用评级网 | 【德信自动化】点胶机_全自动点胶机_自动点胶机厂家_塑料热压机_自动螺丝机-深圳市德信自动化设备有限公司 | 电子元器件呆滞料_元器件临期库存清仓尾料_尾料优选现货采购处理交易商城 | 细砂提取机,隔膜板框泥浆污泥压滤机,螺旋洗砂机设备,轮式洗砂机械,机制砂,圆锥颚式反击式破碎机,振动筛,滚筒筛,喂料机- 上海重睿环保设备有限公司 | 高光谱相机-近红外高光谱相机厂家-高光谱成像仪-SINESPEC 赛斯拜克 | 土壤检测仪器_行星式球磨仪_土壤团粒分析仪厂家_山东莱恩德智能科技有限公司 | 胶辊硫化罐_胶鞋硫化罐_硫化罐厂家-山东鑫泰鑫智能装备有限公司 意大利Frascold/富士豪压缩机_富士豪半封闭压缩机_富士豪活塞压缩机_富士豪螺杆压缩机 | 北京成考网-北京成人高考网| 跨境物流_美国卡派_中大件运输_尾程派送_海外仓一件代发 - 广州环至美供应链平台 | 中国产业发展研究网 - 提供行业研究报告 可行性研究报告 投资咨询 市场调研服务 | 低浓度恒温恒湿称量系统,强光光照培养箱-上海三腾仪器有限公司 | 运动木地板价格,篮球馆体育运动木地板生产厂家_欧氏地板 | 刘秘书_你身边专业的工作范文写作小秘书 | MES系统工业智能终端_生产管理看板/安灯/ESOP/静电监控_讯鹏科技 |