第8講 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法

《第8講 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、1程序設(shè)計語言C/C++第8講基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院2013年9月2教學(xué)目標(biāo)理解數(shù)組和鏈表結(jié)構(gòu)的特點(diǎn)和主要用途；掌握數(shù)組和鏈表結(jié)構(gòu)的基本操作；熟練使用數(shù)組和鏈表結(jié)構(gòu)解決實(shí)際問題。3本講內(nèi)容1數(shù)組基本操作2鏈表結(jié)構(gòu)及其基本操作3查找和排序算法4幾個常用算法4本講內(nèi)容1數(shù)組基本操作2鏈表結(jié)構(gòu)及其基本操作3查找和排序算法4幾個常用算法1數(shù)組基本操作1.1求數(shù)組的長度算法描述：①使用sizeof運(yùn)算符求得數(shù)組占用內(nèi)存大?。虎谑褂胹izeof運(yùn)算符求得每個數(shù)組元素占用內(nèi)存大??；③用數(shù)組的

2、內(nèi)存大小/數(shù)組元素的內(nèi)存大小。1數(shù)組基本操作1.2在數(shù)組中順序查找一個指定值開始流程圖：輸入待查找的值m（假定數(shù)組名為a，數(shù)組長下標(biāo)變量i置為0度為len）Ni

3、023214532447890232145324787890232145324789090無效了1數(shù)組基本操作1.5動態(tài)數(shù)組動態(tài)數(shù)組是指在程序執(zhí)行過程中數(shù)組長度可以動態(tài)變化的數(shù)組。?結(jié)合new和delete運(yùn)算符，用指針實(shí)現(xiàn)。?一般設(shè)置一個初始長度的數(shù)組；?數(shù)組中增加或減少一個元素一般用函數(shù)實(shí)現(xiàn)。10本講內(nèi)容1數(shù)組基本操作2鏈表結(jié)構(gòu)及其基本操作3查找和排序算法4幾個常用算法112鏈表結(jié)構(gòu)及其基本操作2.1什么是鏈表?鏈表是一種物理上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)的邏輯順序通過鏈表中的指針鏈接次序

4、實(shí)現(xiàn)。122鏈表結(jié)構(gòu)及其基本操作2.1什么是鏈表?鏈表中的元素稱為結(jié)點(diǎn)。每一個結(jié)點(diǎn)都包含兩類數(shù)據(jù)：一類數(shù)據(jù)稱為結(jié)點(diǎn)的值域；另一類數(shù)據(jù)稱為鏈域，它是與結(jié)點(diǎn)同類型的指針。結(jié)點(diǎn)類型定義structnode{intdata;node*next;};node*p1,*p2;132鏈表結(jié)構(gòu)及其基本操作2.1什么是鏈表?結(jié)點(diǎn)數(shù)據(jù)的訪問形式設(shè)指針p指向某結(jié)點(diǎn)，可用p訪問該結(jié)點(diǎn)數(shù)據(jù)域：（*p).data或p->data指針域：（*p).next或p->next142鏈表結(jié)構(gòu)及其基本操作2.2創(chuàng)建一條無序鏈表（1）

5、置頭指針head=0;（2）輸入一個數(shù)據(jù)，如果該數(shù)據(jù)有效，則轉(zhuǎn)步驟（3），否則轉(zhuǎn)步驟（5）；（3）申請分配一個結(jié)點(diǎn)空間，并把該空間的地址存入指針變量p中，然后把輸入的數(shù)據(jù)存入該結(jié)點(diǎn)；（4）若當(dāng)前鏈表為空，即head為0，則直接把p賦給head，否則接入鏈表末尾。轉(zhuǎn)步驟（2）；（5）如果head不為0，則置尾結(jié)點(diǎn)的指針域?yàn)?；（6）返回頭指針head的值，程序結(jié)束。152鏈表結(jié)構(gòu)及其基本操作2.2遍歷輸出鏈表各節(jié)點(diǎn)值voidPrint(constnode*head){constnode*p;p=h

6、ead;while(p!=0){cout<data<<'t';p=p->next;}cout<

7、echain(node*head){node*p1;while(head){p1=head;head=head->next;deletep1;}}182鏈表結(jié)構(gòu)及其基本操作2.2把一個節(jié)點(diǎn)插入升序鏈表node*Insert(node*head,node*p){node*p1,*p2;if(head==0){head=p;p->next=0;returnhead;}if(head->data>=p->data){p->next=head;head=p;returnhead;}p2=p1=head;

8、while(p2->next&&p2->datadata){p1=p2;p2=p2->next;}if(p2->datadata){p2->next=p;p->next=0;}else{p->next=p2;p1->next=p;}returnhead;}192鏈表結(jié)構(gòu)及其基本操作2.2建立一條有序鏈表node*Create_sort(void){node*p1,*head=NULL;inta;cout<<“產(chǎn)生一條有序鏈表，輸入數(shù)據(jù)，以-1結(jié)束：";cin>>a;while