緒論-線性表課件

1、 計算機是一門研究用計算機進行信息表示和處理的科學。而與計算機信息表示和處理直接相關(guān)的便是處理信息的程序的效率。 隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當復(fù)雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課程所要研究的問題。第一章 緒論第一章 緒論例1-1 圖書館的書目檢索系統(tǒng)自動化問題。 1.1 什么是數(shù)據(jù)結(jié)構(gòu) “線性結(jié)構(gòu)”例1-2 計算機和人對奕的問題。 “樹形結(jié)構(gòu)”例1-3 多叉路口交通燈的管理問題。 “圖狀結(jié)構(gòu)”第一章 緒論 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機

2、的操作對象以及它們之間的關(guān)系和操作等等的學科。1.1 什么是數(shù)據(jù)結(jié)構(gòu)第一章 緒論數(shù)據(jù)（Data）1.2 基本概念和術(shù)語 ：是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素（Data Element） ：是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)項（Data Item） ：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。數(shù)據(jù)元素可以是數(shù)據(jù)項的集合。數(shù)據(jù)對象（Data Object） ：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)（Data Structure） ：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。第一章 緒論1

3、.2 基本概念和術(shù)語數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)第一章 緒論數(shù)據(jù)類型（Data Type）1.2 基本概念和術(shù)語 ：和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，是一個值的集合和定義在這個值集上的一組操作的總稱。抽象數(shù)據(jù)類型（Abstract Data Type） ：是指一個數(shù)學模型以及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學抽象特性。第一章 緒論1.2 基本概念和術(shù)語和數(shù)據(jù)結(jié)構(gòu)的形式定義相對應(yīng)，抽象數(shù)據(jù)類型可用以下三元組表示： (D，S，P)其中：D是數(shù)據(jù)元素的有限集，S是D上的關(guān)系集，P是對D的基本操作。第一章 緒論1.4 算法和算法分析算法的概念：

4、是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。 第一章 緒論1.4 算法和算法分析算法的特性：有窮性確定性可行性零個或多個輸入一個或多個輸出 第一章 緒論1.4 算法和算法分析算法設(shè)計的要求：評價一個好的算法有以下幾個標準:正確性：算法應(yīng)滿足具體問題的需求。可讀性：算法應(yīng)該好讀。以有利于閱讀者對程序的理解。健狀性：算法應(yīng)具有容錯處理。當輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。第二章 線性表2.1 線性表的類型定

5、義常常將非空的線性表(n0)記作： (a1，a2，an) 這里的數(shù)據(jù)元素ai只是一個抽象的符號，其具體含義在不同的情況下可以不同。第二章 線性表2.1 線性表的類型定義例1、 26個英文字母組成的字母表 （A，B，C、Z）例2、 某校從1978年到1983年各種型號的計算機擁有量的變化情況。 （6，17，28，50，92，188）例3、 一副撲克牌的點數(shù)。 （2，3，4，J，Q，K，A）第二章 線性表線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中：存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素；存在唯一的一個被稱做“最后一個”的數(shù)據(jù)元素；除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；除最后一個之外，集

6、合中的每個數(shù)據(jù)元素均只有一個后繼。 第二章 線性表2.1 線性表的類型定義抽象數(shù)據(jù)類型線性表的定義例2-1 假設(shè)利用兩個線性表LA和LB分別表示兩個集合 A 和B（即：線性表中的數(shù)據(jù)元素即為集合中的元素）， 現(xiàn)要求 A B 并將結(jié)果存放于集合A 中。算法 2.1例2-2 已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排 列，現(xiàn)要求 將LA和LB歸并為一個新的線性表LC，且 LC中的數(shù)據(jù)元素仍按值非遞減有序排列。算法 2.2第二章 線性表2.2 線性表的順序表示和實現(xiàn)線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。而以這種方式存儲的線性表稱為順序表。第二章 線性表2.2

7、線性表的順序表示和實現(xiàn)假設(shè)線性表的每個元素需占用l 個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i +1個數(shù)據(jù)元素的存儲位置LOC( a i+1)和第i 個數(shù)據(jù)元素的存儲位置LOC(a i )之間滿足下列關(guān)系： LOC(a i+1)=LOC(a i)+l線性表的第i個數(shù)據(jù)元素ai的存儲位置為： LOC(a i)=LOC(a1)+(i -1)*l第二章 線性表2.2 線性表的順序表示和實現(xiàn) 線性表的動態(tài)分配順序存儲結(jié)構(gòu)#define LIST_INIT_SIZE 100 /線性表存儲空間的初始分配量#define LISTINCREMENT 10 /線性表存儲空

8、間的分配增量typedef struct ElemType * elem; /存儲空間基址 int length; /當前長度 int listsize; /當前分配的存儲容量 / (以 sizeof ( ElemType) 為單位) SqList;第二章 線性表2.2 線性表的順序表示和實現(xiàn)元素1元素2.元素i.L.elemi-1 elem lengthlistsize01i-1第二章 線性表2.3 線性表的鏈式表示和實現(xiàn)特點：用一組任意的存儲單元(可以是連續(xù)的,也可以是不連續(xù)的)存放線性表的數(shù)據(jù)元素。數(shù)據(jù)域指針域結(jié)點第二章 線性表2.3 線性表的鏈式表示和實現(xiàn)例：線性表（ZHAO,QIAN

9、,SUN,LI,ZHOU,WU,ZHENG,WANG） 的鏈式存儲結(jié)構(gòu)如下所示：第二章 線性表2.3 線性表的鏈式表示和實現(xiàn)第二章 線性表2.2 線性表的鏈式表示和實現(xiàn) 線性表的單鏈表存儲結(jié)構(gòu)typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;第二章 線性表2.2 線性表的鏈式表示和實現(xiàn)a1a2ana3L.不帶頭結(jié)點的線性鏈表第二章 線性表2.2 線性表的鏈式表示和實現(xiàn)a1a2ana3L.帶頭結(jié)點的線性鏈表第二章 線性表2.2 線性表的鏈式表示和實現(xiàn)單鏈表的基本操作：單鏈表的創(chuàng)建頭插法尾插法第二章 線性表2.2 線性表的鏈式表示和實現(xiàn)單鏈表的基本操作：插入bappbaxs第二章 線性表2.2 線性表的鏈式表示和實現(xiàn)單鏈表的基本操作：刪除ai-1aiai+1pq第二章 線性表2.2 線性表的鏈式表示和實現(xiàn)單鏈表的基本操作：查找合并第二章 線性表2.3.2 循環(huán)鏈表：首尾相接的鏈表將最后一個結(jié)點