資料結構 Data Structures Fall 2006， 95學年第一學期 Instructor : 陳宗正

Fundamentals of Data Structures in C Instructor : 陳宗正 Office: 第二教學大樓 『 6樓』 C623 Tel: (06) 2785123 ext. 2408 E-mail: tchen1@mail.cju.edu.tw Textbook: Horowitz, Shani and Anderson-Freed Fundamentals of Data Structures in C (新月圖書) Reference Sedgewick, Algorithms in C (Parts 1-4) 3rd ed. Sedgewick, Algorithms in C (Parts 5) 3rd ed. Goodrich, Data Structures and Algorithms in C++ Stephen Prata, C Primer Plus 5th ed.

Data Structures What is data structure? Objective 重要 Data Structures What is data structure? 探討一群相關資料的資料表示方法與資料運作方法 Objective 使用最有效率的方式,對一群相關資料進行處理 Programs = Data structures + Algorithms How to analyze and design? 1. 定義資料並描述該資料對欲處理物件的特性 2. 找出並描述對該資料的各種運算 3. 考慮最適當的Data Structure,使得各種運算 的效率最佳 4. 設計一個完整的Algorithm

Advantages of Studying Data Structures Solving problems by existing methods Understanding good algorithms Learning analysis and design Building complex software systems Documentation Better programming skills Knowing hardware & software Knowing an arsenal of algorithms 重要

Foundation for Other Fields Various fields in our department Communication system RF Integrated Circuits Signal Processing/Image Processing Mechatronics Integrated Engineering Computer Graphics VLSI/SOC IC Design

Foundation for Other Fields Theories shortest path problem queuing theory & spanning tree Estimation & Control theory Optimization & simulation Programming techniques pointer linked list stack, queue, heap, hash protocol, driver, firmware design

ZZZZZZZZ~~Z Question to Ask How do you start?

Start with Understanding Analysis Design

Example Problem: Solution: Read in 3 integers Find the largest and the smallest Solution: Using flowchart Using pseudocode

Structured Programming One IN one OUT flow Three basic constructs Sequence Selection Iteration

Pseudocode English-like (Chinese-like) representation of the code required for an algorithm Algorithm – Logical steps necessary to solve a problem in a computer Part English and part structured code English part – easy to read Code part – extended version of the basic algorithmic constructs

Writing a Program – System Life Cycle Requirements Analysis Top-down analysis Design Abstract data type Specification of algorithms (strategies) Detail design Not only create a system could be written in several languages, but pick the most efficient. Refinement and coding Implementation – coding in C Verification Correctness proofs Testing

C Programming Tools Visual Studio 6 Visual Studio 2005 or .NET Visual studio 6 includes C++, BASIC, JAVA and SQL VC++ 6 is needed in this class The window command or console mode is required only NO RECOMMENDED working with the GUI/MFC Visual Studio 2005 or .NET New version of Microsoft Development Suite .NET and 2005 include various of Server Protocol C compiler on Unix and Linux and gcc and Dev-C++ on Windows – not recommended/acceptable

成績計算方式 期中考與期末考(筆試)： 作業: 40% 若報告或程式二者缺一，則作業分數以0分計算 嚴禁抄襲、複製等行為，但鼓勵同學互相討論 各佔25% (close book) 作業: 40% 共四次作業，每次各佔10% 作業記分方式： (遲交以0分計算) (80%) 報告之完整性：須包含 (一) 簡介及問題描述 (二) 理論分析 (三) 演算法則 (四) 執行結果與討論 (五) 程式 (20%) 程式經壓縮後(RAR)，以學號為檔案名稱，交予班代。班代須將其彙整後，燒成光碟，當天繳交。 若報告或程式二者缺一，則作業分數以0分計算 嚴禁抄襲、複製等行為，但鼓勵同學互相討論 鼓勵同學經常向老師或助教請教問題。老師及助教各有5%的學習態度分數。若請教的問題太過淺顯易懂，或課堂上已強調多次者，學習態度分數將被倒扣。