數據結構線性表PPT.ppt

(107頁)

'數據結構線性表PPT.ppt'
第2章 線性表 2.1 線性表的基本概念 2.2 線性表的順序存儲2.3 線性表的鏈式存儲2.4 線性表的應用 本章小結 2.5 有序表 2.1 線性表的基本概念 2.1.1 線性表的定義2.1.2 線性表的運算2.1.1 線性表的定義 線性表是具有相同特性的數據元素的一個有限序列。該序列中所含元素的個數叫做線性表的長度,用n表示,n≥0。 當n=0時,表示線性表是一個空表,即表中不包含任何元素。設序列中第i(i表示位序)個元素為ai(1≤i≤n)。 線性表的一般表示為: (a1,a2,…ai,ai+1,…,an) 其中a1為第一個元素,又稱做表頭元素,a2為第二個元素,an為最后一個元素,又稱做表尾元素。 例如,在線性表 (1,4,3,2,8,10)中,1為表頭元素,10為表尾元素。2.1.2 線性表的運算 線性表的基本運算如下: (1) 初始化線性表InitList(&L):構造一個空的線性表L。 (2) 銷毀線性表DestroyList(&L):釋放線性表L占用的內存空間。 (3) 判線性表是否為空表ListEmpty(L):若L為空表,則返回真,否則返回假。 (4) 求線性表的長度ListLength(L):返回L中元素個數。 (5) 輸出線性表DispList(L):當線性表L不為空時,順序顯示L中各結點的值域。 (6) 求線性表L中指定位置的某個數據元素GetElem(L,i,&e):用e返回L中第 i(1≤i≤ListLength(L))個元素的值。 (7) 定位查找LocateElem(L,e):返回L中第1個值域與e相等的位序。若這樣的元素不存在,則返回值為0。 (8) 插入數據元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)個元素之前插入新的元素e,L的長度增1。 (9) 刪除數據元素ListDelete(&L,i,&e):刪除L的第i(1≤i≤ListLength(L))個元素,并用e返回其值,L的長度減1。 例2.1 假設有兩個集合 A 和 B 分別用兩個線性表 LA 和 LB 表示,即線性表中的數據元素即為集合中的成員。編寫一個算法求一個新的集合C=A∪B,即將兩個集合的并集放在線性表LC中。 解:本算法思想是:先初始化線性表LC,將LA的所有元素復制到LC中,然后掃描線性表LB,若LB的當前元素不在線性表LA中,則將其插入到LC中。算法如下:void unionList(List LA,List LB,List &LC) { int lena,lenc,i; ElemType e; InitList(LC); for (i=1;i<=ListLength(LA);i++) /*將LA的所有元素插入到Lc中*/ { GetElem(LA,i,e); ListInsert(LC,i,e); } lena=ListLength(LA); /*求線性表的長度*/ lenB=ListLength(LB); for (i=1;i<=lenb;i++) { GetElem(LB,i,e); /*取LB中第i個數據元素賦給e*/ if (!LocateElem(LA,e)) ListInsert(LC,++lenc,e); /*LA中不存在和e相同者,則插入到LC中*/ }} 由于LocateElem(LA,e)運算的時間復雜度為O(ListLength(LA)),所以本算法的時間復雜度為: O(ListLength(LA)*ListLength(LB))。2.2 線性表的順序存儲2.2.1 線性表的順序存儲—順序表2.2.2 順序表基本運算的實現2.2.1 線性表的順序存儲—順序表 線性表的順序存儲結構就是:把線性表中的所有元素按照其邏輯順序依次存儲到從計算機存儲器中指定存儲位置開始的一塊連續的存儲空間中。 這樣,線性表中第一個元素的存儲位置就是指定的存儲位置,第i+1個元素(1≤i≤n-1)的存儲位置緊接在第i個元素的存儲位置的后面?! 【€性表 ? 邏輯結構  順序表 ? 存儲結構  假定線性表的元素類型為ElemType,則每個元素所占用存儲空間大小(即字節數)為sizeof(ElemType),整個線性表所占用存儲空間的大小為:   n*sizeof(ElemType) 其中,n表示線性表的長度。順序表示意圖 在定義一個線性表的順序存儲類型時,需要定義一個數組來存儲線線表中的所有元素和定義一個整型變量來存儲線性表的長度。 假定數組用data[MaxSize]表示,長度整型變量用length表示,并采用結構體類型表示,則元素類型為通用類型標識符ElemType的線性表的順序存儲類型可描述如下: typedef struct { ElemType data[MaxSize]; int length; } SqList; /*順序表類型*/ 其中,data成員存放元素,length成員存放線性表的實際長度。 說明:由于C/C++中數組的下標從0開始,線性表的第i個元素ai存放順序表的第i-1位置上。為了清楚,將ai在邏輯序列中的位置稱為邏輯位序,在順序表中的位置稱為物理位序。2.2.2 順序表基本運算的實現 一旦采用順序表存儲結構,我們就可以用C/C++語言實現線性表的各種基本運算。為了方便,假設ElemType為char類型,使用如下自定義類型語句: typedef char ElemType;1. 建立順序表  其方法是將給定的含有n個元素的數組的每個元素依次放入到順序表中,并將n賦給順序表的長度成員。算法如下:  void CreateList(SqList *&L,ElemType a[],int n)   /*建立順序表*/  {   int i; L=(SqList *)malloc(sizeof(SqList));   for (i=0;idata[i]=a[i];   L->length=n;  }2. 順序表基本運算算法(1) 初始化線性表InitList(L) 該運算的結果是構造一個空的線性表L。實際上只需將length成員設置為0即可。 void InitList(SqList *&L) //引用型指針 { L=(SqList *)malloc(siz。省略部分。是不確定的,但由于提供隨機查找行中的數據,所以每行的數據采用順序存儲結構,這里用長度為MaxCol的數組存儲每行的數據。因此,該單鏈表中數據結點類型定義如下: #define MaxCol 10 /*最大列數*/ typedef struct Node1 /*定義數據結點類型*/ { ElemType data[MaxCol]; struct Node1 *next; /*指向后繼數據結點*/ } DList; 另外,需要指定每個表的行數和列數,為此將單鏈表的頭結點類型定義如下: typedef struct Node2 /*定義頭結點類型*/ { int Row,Col; /*行數和列數*/ DList *next; /*指向第一個數據結點*/ } HList; 采用尾插法建表方法創建單鏈表,用戶先輸入表的行數和列數,然后輸入各行的數據,為了簡便,假設表中數據為int型,因此定義: typedef int ElemType; 對應的建表算法如下:void create(HList *&h){ int i,j; DList *r,*s; h=(HList *)malloc(sizeof(HList));h->next=NULL; printf("表的行數,列數:"); scanf("%d%d",&h->Row,&h->Col); for (i=0;iRow;i++) { printf(" 第%d行:",i+1); s=(DList *)malloc(sizeof(DList)); for (j=0;jCol;j++) scanf("%d",&s->data[j]); if (h->next==NULL) h->next=s; else r->next=s; r=s; /*r始終指向最后一個數據結點*/ } r->next=NULL; } 采用尾插法建表對應的輸出表的算法如下:void display(HList *h){ int j; DList *p=h->next; while (p!=NULL) { for (j=0;jCol;j++) printf("%4d",p->data[j]); printf("\n"); p=p->next; }} 為了實現兩個表h1和h2的簡單自然連接,先要輸入兩個表連接的列序號f1和f2,然后掃描單鏈表h1,對于h1的每個結點,從頭至尾掃描單鏈表h2,若自然連接條件成立,即h1的當前結點*p和h2的當前結點*q滿足: p->data[f1-1]==q->data[f2-1]則在新建單鏈表h中添加一個新結點。 新建的單鏈表h也是采用尾插法建表方法創建的。 實現兩個表h1和h2的簡單自然連接并生成結果h的算法如下:void link(HList *h1,HList *h2,HList *&h){ int f1,f2,i;DList *p=h1->next,*q,*s,*r; printf("連接字段是:第1個表位序,第2個表位序:"); scanf("%d%d",&f1,&f2); h=(HList *)malloc(sizeof(HList)); h->Row=0; h->Col=h1->Col+h2->Col; h->next=NULL; while (p!=NULL) { q=h2->next; while (q!=NULL) { if (p->data[f1-1]==q->data[f2-1]) /*對應字段值相等*/ { s=(DList *)malloc(sizeof(DList)); /*創建一個數據結點*/ for (i=0;iCol;i++) /*復制表1的當前行*/ s->data[i]=p->data[i]; for (i=0;iCol;i++) s->data[h1->Col+i]=q->data[i];/*復制表2的當前行*/ if (h->next==NULL) h->next=s; else r->next=s; r=s; /*r始終指向最后數據結點*/ h->Row++; /*表行數增1*/ } q=q->next; /*表2下移一個記錄*/ } p=p->next; /*表1下移一個記錄*/ } r->next=NULL;/*表尾結點next域置空*/ } 尾插法建表2.5 有序表 所謂有序表,是指這樣的線性表,其中所有元素以遞增或遞減方式排列,并規定有序表中不存在元素值相同的元素。在這里仍以順序表進行存儲。 其中只有ListInsert()基本運算與前面的順序表對應的運算有所差異,其余都是相同的。有序表的ListInsert()運算對應的算法如下: int ListInsert(SqList &L,ElemType e) { int i=0,j; while (i<L.length && L.data[i]i;j--) /*將data[i]及后面元素后移一個位置*/ L.data[j]=L.data[j-1]; L.data[i]=e; L.length++; /*順序表長度增1*/ return 1; } 注意:這里用的不是順序表指針,直接就是順序表本章小結本章的基本學習要點如下: (1) 理解線性表的邏輯結構特性。 (2) 深入掌握線性表的兩種存儲方法,即順序表和鏈表。體會這兩種存儲結構之間的差異。 (3) 重點掌握順序表和鏈表上各種基本運算的實現。 (4) 綜合運用線性表這種數據結構解決一些復雜的實際問題。
關 鍵 詞:
數據 ppt 線性 結構
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:數據結構線性表PPT.ppt
鏈接地址: http://www.476824.live/p-51461487.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 湖北十一选五任选基本走势图 11选5下期推算方法 看十一运夺金选号技巧 沪深在线配资 福建东方6十1历史开奖码 北京11选5遗漏统计 0304棋牌老版本 快乐10分开奖数据 广西十一选五开奖结果双色球开奖结果 2007上证指数