c題庫期末復(fù)習(xí)ppt課件(已修改)
2025-01-24 09:42 本頁面
【正文】 BUPT 期末復(fù)習(xí) BUPT 1 第一章 緒論 ? 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語 – 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)等基本概念 – 數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系 – 數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)及四種常用的存儲表示方法 – 抽象數(shù)據(jù)類型的概念及其與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 BUPT 2 ? 算法的描述和分析 – 算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度的概念 – 算法描述和算法分析的方法 BUPT 3 第二章 線性表 ? 線性表的邏輯結(jié)構(gòu) – 線性表的邏輯結(jié)構(gòu)特征 – 線性表上定義的基本運(yùn)算，并能利用基本運(yùn)算構(gòu)造出較復(fù)雜的運(yùn)算 BUPT 4 ? 線性表的順序存儲結(jié)構(gòu) – 順序表的存儲方式及它如何映射線性表中元素之間的邏輯關(guān)系 – 順序表的存儲結(jié)構(gòu)定義 – 線性表基本運(yùn)算在順序表上的實(shí)現(xiàn)方法及其時(shí)間性能分析 – 利用順序表設(shè)計(jì)算法解決應(yīng)用問題 BUPT 5 ? 設(shè)順序表 va中的數(shù)據(jù)元素遞增有序。試寫一算法，將 x插入到順序表的適當(dāng)位置上，以保持該表的有序性。 ? 解題思路：在遞增有序的順序表中插入一個(gè)元素 x，首先應(yīng)查找待插入元素的位置。因順序表元素遞增有序，采用折半查找法比順序查找效率要高。查到插入位置后，從此位置直到線性表尾依次向后移動(dòng)一個(gè)元素位置，之后將元素 x插入即可。假設(shè)順序表 va存放在數(shù)組 A[]中（假設(shè)下標(biāo)從 1開始）。 void Insert（ ElemType A[]， int size, ElemType x）。 {low=1； high=num； //假設(shè)下標(biāo)從 1開始 while（ low=high） ∥ 對分查找元素 x的插入位置。 {mid=（ low+high） /2； if（ A[mid]==x） {low=mid+1； break； } else if（ A[mid]x） high=mid1 ； else low=mid+1 ； } for（ i=num； i=low； i） A[i+1]=A[i]； ∥ 元素后移。 A[i+1]=x； ∥ 將元素 x插入。 }算法結(jié)束 BUPT 6 ? 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) – 鏈表的存儲方式及它如何映射線性表中元素之間的邏輯關(guān)系 – 鏈表中頭指針和頭節(jié)點(diǎn)的使用 – 單鏈表、雙鏈表、循環(huán)鏈表在鏈接方式上的區(qū)別 – 各種鏈表的存儲結(jié)構(gòu)定義 – 線性表基本運(yùn)算在鏈表上的實(shí)現(xiàn)方法及其時(shí)間性能分析 – 循環(huán)鏈表上尾指針取代頭指針的作用 – 利用鏈表設(shè)計(jì)算法解決簡單的應(yīng)用問題 BUPT 7 ? 已知線性表中的元素以值遞增有序排列，并以單鏈表（帶頭結(jié)點(diǎn)）作為存儲結(jié)構(gòu)，試寫一算法刪除表中所有值大于mink且小于 maxk的元素。 ? 解題思路：首先找到最后一個(gè)元素值小于等于 mink的結(jié)點(diǎn)位置（ q）；再往后依次刪除結(jié)點(diǎn)直到第一個(gè)值大于等于maxk結(jié)點(diǎn)為止。 void delete(sqlist *la,int mink,int mark) { sqlist *p,*q,。 q=la。 p=lanext。 while (p amp。amp。 pdata=mink) { q=p。 p=pnext。 } while (p amp。amp。 pdatamaxk) { u=p。 p=pnext。 free(p)。 } qnext=p。 } BUPT 8 ? 寫出單鏈表（帶頭結(jié)點(diǎn)）就地逆置算法。 void reverse(linklist *h) { linklist p,q。 p=hnext。 hnext=NULL。 while(p!=null) { q=p。 //q
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1