所有的限制,幾乎都是從自己的內心開始的。
(2012.11.13)資料結構(本)課程教學研討(文字)
王春鳳:各位老師,下午好,歡迎參加本次教研活動。
本次教研活動的內容:
1.對各章重點進行分析
2.交流教學方法
3.對課程資源需求徵求意見
各章重點內容分析
第1章緒論
本章主要討論以下幾個問題:
1.資料結構研究的主要問題
資料結構課程研究資料的邏輯結構、儲存結構及其操作。
2.什麼是資料結構
資料結構:(資料元素間的關係稱為結構),相互間存在一種或多種特定關係的資料元素的集合稱為資料結構。
邏輯結構:元素間的邏輯關係,與計算機無關。
儲存結構:是邏輯結構在計算機中的表示(包括資料元素和關係的表示),同一種邏輯結構可以對應不同的物理結構。
3.四種基本資料結構
集合、線形、樹形、圖
4.演算法的時間複雜度
演算法:解決特定問題的方法
時間複雜度
第2章線性表
1.線性表的定義和邏輯結構
2.線性表的順序儲存結構(順序表)和相關操作
插入、刪除操作、時間複雜度分析
3.線性表的鏈式儲存結構(鍊錶)和相關操作
建鍊錶(頭插法、尾插法)
遍歷鍊錶:關鍵操作p=p->next;
刪除鍊錶:關鍵操作p1- >next =p2->next;
插入結點:關鍵操作s->next=p->next;
p->next=s;
4.迴圈鍊錶的特點
5.單向鍊錶的應用
第3章棧和佇列
1.棧和佇列的定義和操作特點(操作受限的線性表)
2.順序儲存的棧和佇列的操作(同陣列的操作)
3.鏈式儲存的棧和佇列的操作(同煉表的操作)
4.迴圈佇列的概念
5.棧在遞迴程式設計技術中的應用
6.簡單問題的遞迴程式設計
第4章串
1.串的定義和儲存方法
2.串的各種運算的定義
3.c字串的特點
第5章陣列和廣義表
1.特殊矩陣進行壓縮儲存的下標變換公式
2.對稱矩陣、三角矩陣
3.稀疏矩陣的三元組表示方法
4.廣義表的結構特點
第6章樹和二叉樹
1.二叉樹的定義、性質
葉結點數等於雙分支結點數加1
二叉樹第i層上至多有2i-1個結點
深度為h的二叉樹至多有2h-1個結點
2.完全二叉樹的定義
3.滿二叉樹的定義
4.二叉樹中順序編號為i的結點左孩子結點為2i,右孩子結點為2i+1
5.二叉樹中編號為i的結點雙親結點為li/2
6.二叉樹的順序儲存結構
結點編號相應於
陣列的下標,由二叉樹的性質計算各結點之間的關係
7.二叉樹的鏈結儲存結構
8.n個結點有2n個指標域.有(n-1)個指向結點,有n+1個為空域
9.二叉樹的遍歷
10.按一定次序訪問樹中結點一次且僅一次
11.前序、中序、後序由根結點的訪問順序決定前、中、後序遍歷的三個子問題為:根、左子樹、右子樹規定先左後右
12.通過遍歷序列構建二叉樹中序、後序前序、中序
13.後序、前序不能確定二叉樹
14.二叉樹遍歷的遞迴演算法
15.二叉樹遍歷的非遞迴演算法
16.二叉樹的相關操作
17.樹的帶權路徑長度
18.哈夫曼樹(最優二叉樹)的定義
19.構造huffman樹的演算法
20哈夫曼樹的性質不唯
一、高度不唯一,除葉結點外均為雙分支結點字首碼哈夫曼編碼哈夫曼編碼用於資料壓縮第7章
1.圖的儲存結構
2.圖的遍歷:
圖的廣度優先遍歷的規則和步驟
3.圖的最小生成樹生成樹帶權圖連通圖一定存在生成樹,且不一定唯一樹權:
最小生成樹所有的限制,幾乎都是從自己的內心開始的。
第8章1.查詢表、關鍵字;主關鍵字
2.線性表的查詢:
順序查詢:從表的某一端開始逐次進行比較折半查詢:針對有序的順序表,設量low、high,令mid=( low+high)/2
3.折半查詢對應的判定樹:
樹中結點相應於查詢表中的記錄,結點值相應於記錄在查詢表中的位置
4.利用折半查詢的判定樹,求成功查詢到某一元素、查不到某一元素的比較次數、等概率條件下平均查詢長度
5.分塊查詢的資料結構查詢表分塊(塊間有序)
索引表(塊內最大關鍵字值、塊起始位址)
6.二叉排序樹二叉排序樹定義二叉排序樹的建立二叉排序樹的查詢二叉排序樹的插入
7.雜湊函式第9章
1.插入排序:
直接插入:
第i趟插入是指前i-1個已有序,第i個元素逐次與前i-1個元素比較找到插入位置。插入得到i個有序序列折半插入:
採用折半查詢法找到插入位置,加快了查詢速度
2.交換排序:
氣泡排序:
快速排序:
3.選擇排序:
簡單選擇排序:
逐次從n個元素、n-1個元素...,查詢最小元素的位置,並逐一排序到位。
堆排序:
大根堆、小根堆堆與特殊完全二叉樹的對應篩選:輸出堆頂元素(存入到最後乙個元
元素的位置),以最後乙個元素替換,並自頂向下重新調整為堆建初始堆:從最後乙個非葉子結點開始直到第乙個結點,從下到上逐次篩選
4.歸併排序:
歸併:把兩個有序序列合成乙個有序序列(逐次比較)
一趟歸併演算法對待排序列逐次施行(1,1)歸併、(2,2)歸併,...最終完成排序課程教學要求和教學建議教學要求
1.了解本課程的學習目的、課程性質和重點掌握的內容
2.理解資料結構、演算法的基本概念
3.掌握典型資料結構和相關操作,能利用c語言實現相關操作和解決簡單應用問題
4.掌握常用的典型非數值演算法的基本原理、演算法步驟,能結合相應的儲存結構並利用c語言實現相關演算法
5.了解相關資料結構、演算法的實際應用案例教學建議
1.教學中要堅持重應用、重實踐的原則
2.教學內容要遵循少而精的原則
3.講解中要深入淺出、重點突出
資料結構課程要點
1 緒論 演算法的概念 幾種常見的資料結構型別 線 樹 圖等 程式的時間複雜度和空間複雜度 2 線性表 線性表的定義 線性表的順序和鏈式儲存結構 兩種儲存結構上操作的時間效能分析 3 棧 佇列 棧和佇列操作的特點 棧和佇列的幾個基本操作 4 串 串的定義及相關概念 5 陣列 求二維資料按行 列儲存時...
資料結構課程總結
1 知識點概述 1 資料結構和演算法 本章作為全書的導引,全面介紹了相關概念,如資料 資料元素 資料型別以及資料結構的定義。其中,資料結構包括邏輯結構 儲存結構和運算集合。邏輯結構分為四類 集合型 線性 樹形和圖形結構 資料元素的儲存結構分為 順序儲存 鏈結儲存 索引儲存和雜湊儲存四類 最後介紹演算...
資料結構課程設計
指導書山東建築大學 電腦科學與技術學院 二 六年十二月 課程設計基本情況 課程名稱 資料結構課程設計 相關課程 c語言程式設計 visual c 程式設計 資料結構 適合專業 電腦科學與技術 網路工程 軟體工程 設計週數 2周 學分 2學分 開課學期 第4學期 開課單位 電腦科學與技術學院 一 課程...