【郝斌】-數(shù)據(jù)結(jié)構(gòu)入門
數(shù)據(jù)結(jié)構(gòu)概述：
定義：如何把現(xiàn)實(shí)中大量而復(fù)雜的問題以特定的數(shù)據(jù)類型（個(gè)體）和特定的數(shù)據(jù)結(jié)構(gòu)（個(gè)體之間關(guān)系）保存到儲(chǔ)存器（內(nèi)存）中，并在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能（比如查找/刪除/排序）而執(zhí)行的相應(yīng)操作（又叫算法）。
常見數(shù)據(jù)結(jié)構(gòu)：
鏈表
樹
圖（任意節(jié)點(diǎn)都和其它節(jié)點(diǎn)聯(lián)系
數(shù)據(jù)結(jié)構(gòu)=個(gè)體+個(gè)體的關(guān)系
算法=對(duì)存儲(chǔ)數(shù)據(jù)的操作
算法（解題的方法和步驟
衡量算法的標(biāo)準(zhǔn)
1.時(shí)間復(fù)雜度
大概需要執(zhí)行的次數(shù)（非時(shí)間）（機(jī)器計(jì)算能力的不同
2.空間復(fù)雜度
算法執(zhí)行過程中大概所占用的最大內(nèi)存
3.難易程度（可讀性
4.健壯性（輸入非法時(shí)也能做出正確反應(yīng)
數(shù)據(jù)結(jié)構(gòu)的地位：軟件中最核心的課程
程序=數(shù)據(jù)的存儲(chǔ)+數(shù)據(jù)的操作+可以被計(jì)算機(jī)執(zhí)行的語言
預(yù)備知識(shí)：
指針
定義：
地址：
內(nèi)存單元的編號(hào)（從0開始的非負(fù)整數(shù)
范圍：0—FFFFFFFF（4G-1的內(nèi)存大小
指針：指針《==》地址
指針變量是存放內(nèi)存單元地址的變量
指針的本質(zhì)是一個(gè)操作受限的非負(fù)整數(shù)
分類：
1.基本類型的指針
2.
注意：1.指針變量只能存放內(nèi)存單元地址，而非內(nèi)容
void f(int *p)//定義了一個(gè)形參，名字叫P，類型為int*；
a[3]=*(3+a);
printf("%p\n"，a+3) 16進(jìn)制輸出，等價(jià)于輸出該對(duì)應(yīng)地址 printf("%p/n",*a+3) <==>輸出a[0]+3這個(gè)數(shù)對(duì)應(yīng)的地址
***：指針變量不論指向的變量占多少字節(jié)，本身只占四個(gè)。
結(jié)構(gòu)體:
為什么會(huì)出現(xiàn)結(jié)構(gòu)體：為了表示某些復(fù)雜的數(shù)據(jù)，而普通的基本類型變量無法滿足需求
什么是結(jié)構(gòu)體：用戶根據(jù)實(shí)際需要自行定義的復(fù)合數(shù)據(jù)類型
如何使用結(jié)構(gòu)體
struct stduent
{
}；
int main()
{
struct student st={ , , };
}
int main()
{
struct student *pst=&st;
pst->sid=99;(等價(jià)于 （*pst)。sid ，pst所指向的結(jié)構(gòu)體變量中的sid這個(gè)成員
}
注意事項(xiàng)
結(jié)構(gòu)體變量不能加減乘除，只能相互賦值；
普通結(jié)構(gòu)體變量和結(jié)構(gòu)體指針變量作為函數(shù)傳參的問題
例：
int main()
{
gst(st);
gst1(&st);
}
void g(struct studenct st)
{
……；
}
void g1(struct studenct *st)
{
……；
}
將主函數(shù)中的所有東西全部賦值到函數(shù)g中，浪費(fèi)空間和內(nèi)存，沒有使用指針g1方便
動(dòng)態(tài)內(nèi)存的分配與釋放：
動(dòng)態(tài)構(gòu)建一維數(shù)組：
int main ()
{
int len;
scanf("%d"，&len);
int *pArr=(int *)malloc(sizeof(int) *len);
//(int *):強(qiáng)制轉(zhuǎn)換 動(dòng)態(tài)數(shù)組第一個(gè)字節(jié)地址（干地址，無實(shí)際意義），以確定數(shù)組的類型（即所占地址/字節(jié)數(shù)
free(pArr);//把pArr所代表的動(dòng)態(tài)分配的內(nèi)存釋放；
}
**跨函數(shù)申請(qǐng)內(nèi)存只能通過動(dòng)態(tài)申請(qǐng)內(nèi)存實(shí)現(xiàn)（但是要記得釋放）
例：
#include <stdio.h>
int main()
{
int *p;
fun(&p);
}
int fun(int **q)
{
*q= (int *) malloc (sizeof(int));
}
模塊一：線性結(jié)構(gòu)【把所有的結(jié)點(diǎn)（類似于數(shù)組的元素）用一根直線穿起來】
連續(xù)儲(chǔ)存【數(shù)組】
1.什么叫數(shù)組：
元素類型相同，大小相等
2.數(shù)組的優(yōu)缺點(diǎn)（與鏈表相比較）：
優(yōu)：①：存取速度快（可通過下標(biāo)查找
缺：①事先必須知道數(shù)組的長(zhǎng)度
②：插入刪除元素慢
③容易受到空間的限制
④：需要大塊連續(xù)的內(nèi)存塊
樣例
#include <stdio.h>
#include <stdlib.h>//包含exit函數(shù)
#include <malloc.h>//包含malloc函數(shù)
//定義了一個(gè)數(shù)據(jù)類型，該數(shù)據(jù)類型名字叫struct Arr，該數(shù)據(jù)類型含有三個(gè)成員，分別是*pbase……，沒有定義變量
struct Arr
{
int *pBase;//存儲(chǔ)數(shù)組元素中第一個(gè)元素的地址
int len;//數(shù)組所能容納的最多元素的個(gè)數(shù)
int cnt;//當(dāng)前數(shù)組有效元素的個(gè)數(shù)
};
void init_arr(struct Arr *pArr,int length);初始化
bool append_arr(struct Arr *pArr,int val);//追加(注意數(shù)組滿了不能放入）
bool insert_arr(struct Arr *pArr,int pos;int val);//插入到第pos個(gè)數(shù) ,pos的值從1開始 表示下標(biāo)為0的
bool delete_arr(struct Arr *pArr,int pos;int val);
int get();
bool is_empty(strcut Arr *pArr);//判數(shù)組是否為空
bool is_full();//判斷數(shù)組是否滿了
void sort_arr(strcut Arr *pArr);//排序
void show_arr(strcut Arr *pArr);//輸出
void inversion_arr(strcut Arr *pArr);//倒置
find_val_arr();
deleteAll(4);
int main()
{
struct Arr arr;//粗體只是定義數(shù)據(jù)類型，此時(shí)數(shù)組內(nèi)元素為垃圾值，定義arr才是變量
int val;
init_arr(&arr,6);//
show_arr(&arr);
append(&arr,1);
if (delete_arr(&arr,1,&val))
printf("刪除成功！\n");
return 0;
}
void init_arr(struct Arr *pArr,int length)
{
pArr->pBase=(int *) malloc(sizeof(int)*length);
//判斷分配地址是否成功
if (NULL ==pAee->pBase)
{
//內(nèi)存分布失敗
exit(-1);
}
array.len=99;
}
void show_arr(strcut Arr *pArr)
{
if is_empty(pArr）//此處pArr已經(jīng)是arr地址，不可以加取地址符使得另一函數(shù)調(diào)用現(xiàn)在的*pArr的地址
printf("是空數(shù)組\n“);
else for (int i=0;i<=pArr->cnt;i++)
{
pritnf("%d ", pArr->pBase[i]);
}
printf("\n");
}
bool is_empty(strcut Arr *pArr)
{
if (pArr->cnt==0)
return 1;//true
else return 0;//false
}
bool is_full(struct Arr *pArr)
{
if (pArr->cnt==pArr->len)
return 1;//true
else return 0;//false
}
bool append_arr(struct Arr *pArr,int val)
{
if (is_full(pArr)==1)
return 0;//數(shù)組滿了false
else //不滿時(shí)追加
{
pArr->pBase[pArr->cnt]=val;
（pArr->cnt）++；
return true;
}
}
bool insert_arr(struct Arr *pArr,int pos;int val)
{
if (is->full(pArr))
return false;
if (pos<1||pos>=pArr->cnt+1)//超出容量
return false;
for (i=pArr->cnt-1;i>=pos-1;i--);
{
pArr->pBase[i]=pArr->pBase[i+1];
}
pArr->pBase[pos-1]=val;
return 1;//true
}
bool delete_arr(struct Arr *pArr,int pos;int *pVal);
{
if (is_empty(pArr))
return 0;//false
if (pos<1||pos>pArr->cnt)
return 0;//false
???//*pVal=pArr->pBase[pos-1];//刪除成功時(shí)返回被刪除的數(shù)據(jù) 以便撤回
for (i=pos;i<pArr->cnt;i++)
{
pArr->pBase[i]=pArr->pBase[i-1];
}
pArr->cnt --;
}
void inversion_arr(strcut Arr *pArr);//倒置
{
int i=0;
int j=pArr->cnt-1;
while (i<j)
{
t=pArr->pBase[j];
pArr->pBase[i]=pArr->pBase[j];
i++;
j--;
}
}
void sort_arr(st ruct Arr*pArr)(冒泡）
{
int i，j，t ;
for (i=0; i<pArr->cnt ; ++i)
{
for (j=i+1; j<pArr->cnt ; ++j)
{
if (pArr->pBase[i] > pArr->pBaso[j])
{
t = pArr->pBase[i] ;
pArr-> pBase[i]=pArr>pBase[j];
pArr->pBase[j][ = t ;
}
}
}
離散存儲(chǔ)【鏈表】
# include <stdio. h>
typedef int ZHANGSAN; //為int再重新多取一個(gè)名字，ZHANGSAN等價(jià)于int
typedef struct Student
{
int sid;
char name [100] ;
char sex;
}ST;//除ST外相當(dāng)于已有的一個(gè)數(shù)據(jù)類型（類似int
ST是為該數(shù)據(jù)類型重新取得名字
int main(void)
{
int i =10; //等價(jià)于 ZHANGSANi=10;
ZHANGSAN j=20;
printf("%d\n", j);
struct Student st ;
struct Student *ps = st ;return 0;
}
若ST換成*PST
一直到*位置都是一個(gè)數(shù)據(jù)類型 使得PST成為指針
typedef struct Student
{
int sid;
char name [100] ;
char sex;
}*PST;
int main(void)
{
struct Student st ;
PST ps=&st;
ps->sid=99;
}
若PSTU后跟上STU
typedef struct Student
{
int sid;
char name [100] ;
char sex;
}*PSTU，STU；//等價(jià)ST代表struct student,
PST代表struct Student*
int main(void)
{
STU st ;
PSTU ps=&st;
ps->sid=99;
}
離散存儲(chǔ)（鏈表）
離散：各個(gè)結(jié)點(diǎn)之間有可以被計(jì)算出的間距
定義：①n個(gè)節(jié)點(diǎn)離散分配②彼此通過指針相連③每個(gè)節(jié)點(diǎn)有且只有一個(gè)前驅(qū)和后繼節(jié)點(diǎn)，首無前驅(qū)，尾無后驅(qū)）
優(yōu)點(diǎn)：①空間沒有限制②插入刪除元素快
缺點(diǎn)：存取數(shù)據(jù)速度慢
專業(yè)術(shù)語：
有效節(jié)點(diǎn):存放有效數(shù)據(jù)的節(jié)點(diǎn)
首節(jié)點(diǎn)：第一個(gè)有效節(jié)點(diǎn)
尾節(jié)點(diǎn)：最后一個(gè)有效節(jié)點(diǎn)
頭結(jié)點(diǎn)：鏈表中在首節(jié)點(diǎn)前加一個(gè)沒有有效數(shù)據(jù)的節(jié)點(diǎn)，主要是方便對(duì)鏈表的操作，其數(shù)據(jù)類型和首節(jié)點(diǎn)一致
頭指針：指向頭節(jié)點(diǎn)的指針變量
尾指針：指向尾節(jié)點(diǎn)的指針變量
如果希望通過一個(gè)函數(shù)來對(duì)鏈表進(jìn)行處理，我們至少需要知道鏈表的哪些參數(shù)：
頭指針 ***（通過頭指針可以推算出鏈表的其他所有信息
（不是頭結(jié)點(diǎn) 是因?yàn)楸苊獠僮鲿r(shí)結(jié)點(diǎn)內(nèi)數(shù)據(jù)較多
（首節(jié)點(diǎn)非必須，可由頭節(jié)點(diǎn)退出；
長(zhǎng)度非必須，可以通過循環(huán)查找結(jié)點(diǎn)為NULL時(shí)的結(jié)點(diǎn) ++即為長(zhǎng)度）
鏈表的創(chuàng)建
#include <stdio.h>
#include <stdlib.h>?
#include <malloc.h>
typedef struct Node
{
??int data;//數(shù)據(jù)域
??struct Node *pNext;//指針域
}NODE,*PNODE;?
//NODE 等價(jià)于struct Node,PNODE 等價(jià)于struct Node*
PNODE create_list(void);
void traverse_list(PNODE pHead);//遍歷
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
void sort_list(PNODE pHead);?
bool delete_list(PNODE pHead,int pos,int *pval);
bool insert_list(PNODE pHead,int pos,int val);
int main()
{??
??int val;
??PNODE pHead = NULL;?
??//等價(jià)于struct Node * pHead = NULL;
??pHead = create_list();?//功能：創(chuàng)建一個(gè)非循環(huán)單鏈表,將該鏈表的頭結(jié)點(diǎn)地址賦值給pHead
??traverse_list (pHead) ;//遍歷
??insert_list(pHead,4,-33);//
??if (is_empty(pHead))
????printf("鏈表為空\(chéng)n");
??else printf("鏈表不空\(chéng)n");
??int?len=length_list(pHead);;
??printf("鏈表的長(zhǎng)度是%d\n",len);
??traverse_list(pHead);//遍歷
??sort_list(pHead);//排序
??traverse_list(pHead);//檢驗(yàn)遍歷是否成功
??if (delete_list(pHead,4,&val) )
????printf("刪除成功，您刪除的元素是:%d\n", val) ;
??else
????printf("刪除失敗!您刪除的元素不存在\n") ;
??return 0;
}
PNODE create_list()
{
????int len;///提示輸入鏈表的長(zhǎng)度
????int i;
????int val;//臨時(shí)存放用戶輸入節(jié)點(diǎn)的值
????//分配一個(gè)不存放有效數(shù)據(jù)的頭節(jié)點(diǎn)
????PNODE?pHead =(PNODE)malloc (sizeof(NODE));
????if (NULL==pHead)
????{
??????printf("分配失敗\n");
??????exit(-1);
????}
????PNODE pTail = pHead;
????pTail->pNext = NULL;//在用戶輸入0時(shí)清空指針域避免出現(xiàn)問題
????printf("輸入鏈表的節(jié)點(diǎn)個(gè)數(shù):len=");
????scanf("%d",&len);
????printf("\n");
????for (i=0;i<len;i++)
????{
??????printf("請(qǐng)輸入第%d個(gè)節(jié)點(diǎn)的值：",i+1);?
??????scanf("%d",&val);
??????PNODE?pNew =(PNODE)malloc (sizeof(NODE));
??????if (NULL==pNew)
??????{
????????printf("分配失敗\n");
????????exit(-1);
??????}
??????//使得pnew永遠(yuǎn)指向尾節(jié)點(diǎn)
??????pNew->data = val;
??????pTail->pNext =pNew;
??????pNew->pNext = NULL;
??????pTail = pNew;
????}
????return pHead;
}
void traverse_list(PNODE pHead)//遍歷
{
??//定義指針p，指向頭結(jié)點(diǎn)指針域（第一個(gè)有效節(jié)點(diǎn)），非空則繼續(xù)，空則輸出??
??PNODE p=pHead->pNext;
??while (p!=NULL)
??{
????printf("%d ",p->data);
????p=p->pNext;
??}
??printf("\n");
}
bool is_empty(PNODE pHead)
{
??if (pHead->pNext==NULL)
????return 1;
??else return 0;?
}
int length_list(PNODE pHead)
{
????PNODE p=pHead->pNext;
????int len=0;
????while (NULL!=p)
????{
??????len++;
??????p=p->pNext;?
????}
????return len;
}
void sort_list(PNODE pHead)
{
??int i,j,t;
??int len= length_list(pHead);
??PNODE p,q;
??for (i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)
????for (j=i+1,q=p->pNext;j<len;++j,q=q->pNext)
????{
??????if (p->data > q->data)
??????//類似于數(shù)組中的: a[i] > a[j]
??????{
????????t=p->data; //類似于數(shù)組中的t =a[i];
????????p->data = q->data;//類似數(shù)組中a[i] = a[j]???
q->data = t;
??????}?
????}??
}
bool insert_list(PNODE pHead,int pos,int val)//插入
{
????int i = 0;
????PNODE p = pHead;??
????while (NULL!=p && i<pos-1)
????{
??????p=p->pNext;
??????i++;
????}
????if (i>pos-1 || NULL==p)
??????return 0;
????PNODE pNew=(PNODE)malloc(sizeof(NODE)) ;??????
????if(NULL ==pNew)
????{
???????printf("動(dòng)態(tài)分配內(nèi)存失敗!\n");
???????exit(-1) ;
????}
????pNew->data=val;
????PNODE q=p->pNext;
????p->pNext=pNew;
????pNew->pNext=q;
????return 1;
}
bool delete_list(PNODE pHead,int pos,int *pVal)
{
????int i = 0;
????PNODE p = pHead ;??
????while (NULL!=p->pNext && i<pos-1)
????{
??????p=p->pNext;
??????i++;
????}
????if (i>pos-1 || NULL==p->pNext)
??????return 0;
????PNODE q = p->pNext ;
????*pVal =q->data;
????//刪除p節(jié)點(diǎn)后面的結(jié)點(diǎn)
????p->pNext = p->pNext->pNext ;
????free(q) ;
????q= NULL;
????return 1;
}
鏈表的分類:
單鏈表
雙鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)指針域，且最后一個(gè)節(jié)點(diǎn)指針域不指向第一個(gè)節(jié)點(diǎn)
循環(huán)鏈表：最后一個(gè)節(jié)點(diǎn)的指針域指向了第一個(gè)節(jié)點(diǎn)
非循環(huán)鏈表：
算法：
狄義的算法是與數(shù)據(jù)的存數(shù)方式密切相關(guān)
廣義的算法是與數(shù)據(jù)的存儲(chǔ)方式無關(guān)
泛型:
利用某種技術(shù)達(dá)到的效果款是:不同的存數(shù)方式，執(zhí)行的操作是一樣的
遍歷
查找
清空
銷毀
求長(zhǎng)度
排序
刪除節(jié)點(diǎn)
插入節(jié)點(diǎn)
偽算法
①：插入
錯(cuò)誤：（p->pNext= q;q->pNext = p->pNext)
//單純的檢索不到原來p后面的節(jié)點(diǎn)
正確：定義一臨時(shí)指針r來指向p后面的節(jié)點(diǎn)
(r=p->pNext;p->pNext= q;q->pNext = r;)
(q->pNext=p->pNext;p->pNext=q;)
②：刪除(p所指的后一個(gè)節(jié)點(diǎn)
錯(cuò)誤：(p->pNext= p->pNext->pNext ) //內(nèi)存未釋放 使得電腦內(nèi)存被占用
正確：定義一臨時(shí)指針r來指向p后面的節(jié)點(diǎn)
（r=p->pNext;p->pNext=r->pNext;free(r);)
③：
線性結(jié)構(gòu)的兩種常見應(yīng)用：
1.棧
定義：一種可以實(shí)現(xiàn)”先進(jìn)后出“的存儲(chǔ)結(jié)構(gòu)
分類：
靜態(tài)棧：從下往上存放0123 只能依次從上往下刪除3210
動(dòng)態(tài)棧 從下往上存放0123 可以通過最上面的元素刪除3210中任意的
算法
出棧
入棧（壓棧）
應(yīng)用
函數(shù)調(diào)用
中斷
表達(dá)式求值（2個(gè)棧做計(jì)算器
內(nèi)存分配
緩沖處理
迷宮
棧的建立：
#include <stdio.h>
#include <malloc.h>
#include <stdlib. h>
typedef struct Node
{
int data;
struct?Node *pNext ;
}NODE,*PNODE;
typedef struct Stack
{
PNODE pTop; //指向棧頂
PNODE pBottom ;//指向棧底
}STACK,*PSTACK;
void init(PSTACK ps)
{
pS->pTop(PNODE)malloc(sizoof(NODE));
if(NULL == pS->pTop)
{
printf(”動(dòng)態(tài)內(nèi)存分配失敗!\n");
exit (-1);
}
else
{
pS->pBottom= ps-> pTop;
pS->pTop->pNext = NULL;
//等價(jià)于pS->Bottom->pNext = NULL;
}
}
void push(PSTACK S,int val)
{
PNODE pNew=(PNODE)malloc(sizoof(NODE));
pNew->data = val ;
pNew->pNext =pS->pTop;
//pS->Top不能改成pS->Bottom
ps->pTop = pNew;
return ;
}
void traverse(PSTACK pS)
{
PNODE p = pS->pTop; .
while (p != pS->pBottom)
{
printf ("%d",p->data) ;
p=p->pNext;
}
printf("\n");
return;
}
//把ps所指向的棧出棧一次，并把出棧的元素存入pVal形參所指向的變量中，如果出棧失敗返回0（即棧為空），否則返回1
bool empty(PSTACK pS)
{
if (pS->pTop==pS->pBottom)
return 1;
else return 0;
}
//把ps所指向的棧出棧一次并把出棧的元素存入pval所指向的變量中，如果出棧成功返回true，否則false
bool pop(PSTACK pS，int * pVal)
{
if(empty(pS))//pS本身存放的就是S的地址
return 0;
else
{
PNODE r = pS->pTop;
*pVal=r->data;
pS->gTop = r->pNext ;
free(r) ;
r = NULL;
return 1;|
}
}
void clear(PSTACK PS）//只是刪除棧中所有數(shù)據(jù)
{
if (empty(pS))
return;
else
{
PNODE p= pS->pTop;
PNODE q = NULL;
while (p != pS->pBottom)
{
q = p->pNext;
free(p);
p=q;
}
pS->pTop = pS->pBottom;
}
}
int main(void)
{
STACK S;
init(&S);//創(chuàng)建空棧 寫S地址才能改變它的值
push(&S,1);//入棧
push(&S,2);//入棧
traverse(&S);//遍歷輸出
if (pop(&S,&val))
{
printf("出棧成功 出棧元素是%d\n",val);
}
else printf("出棧失敗\n");
clear("&S");
traverse(&S);
}
2.隊(duì)列：
定義：可以滿足先進(jìn)先出的一種存儲(chǔ)結(jié)構(gòu)
分類：鏈?zhǔn)疥?duì)列（鏈表
靜態(tài)隊(duì)列（數(shù)組
靜態(tài)隊(duì)列通常必須是循環(huán)隊(duì)列
循環(huán)隊(duì)列的講解:
1.靜態(tài)隊(duì)列為什么必須是循環(huán)隊(duì)列
溢出時(shí)回到頭
2.循環(huán)隊(duì)列需要幾個(gè)參數(shù)來確定及其含義
需要2個(gè)參數(shù)來確定
front
rear
2個(gè)參數(shù)不同場(chǎng)合有不同的含義建議初學(xué)者先記住，然后慢慢體會(huì)
1)．隊(duì)列初始化
front 和rear的值都是0
2)．隊(duì)列非空
front代表的是隊(duì)列的第一個(gè)元素
rear代表的是隊(duì)列的最后一個(gè)有效元素的下一個(gè)元素
3)﹒隊(duì)列空
front和rear的值相等，但不一定是0
3.循環(huán)隊(duì)列各個(gè)參數(shù)的含義（2已經(jīng)講完
4.循環(huán)隊(duì)列入隊(duì)偽算法講解
①將值存入r所代表的位置
②r=(r+1)%數(shù)組長(zhǎng)度
5.循環(huán)隊(duì)列出隊(duì)偽算法講解
①f=(f+1)%數(shù)組長(zhǎng)度（自己判斷是否要?jiǎng)?chuàng)建一個(gè)val來存儲(chǔ)出隊(duì)的數(shù)據(jù)）
6.如何判斷循環(huán)隊(duì)列是否為空
front=rear
7.如何判斷循環(huán)隊(duì)列是否已滿
預(yù)備知識(shí)：front和rear的值大小關(guān)系不確定，可大可小可相等
判斷方法：
常用：少用一個(gè)元素，如果fr緊挨則隊(duì)列已滿
不常用：多增加一個(gè)標(biāo)識(shí)參數(shù)，長(zhǎng)度等于數(shù)組長(zhǎng)度或者r和f重合時(shí)
if((r+1)%數(shù)組長(zhǎng)度==f) 滿;
else 不滿
3.隊(duì)列的具體應(yīng)用：所有和時(shí)間有關(guān)的操作
循環(huán)隊(duì)列程序演示
#include <stdio.h>
#include <malloc.h>
struct Queue
{
int * pBase;
int front;
int rear;
}QUEUE;
void init_queue(QUEUE *pQ);//初始化
bool full_queue (QUEUE * pQ)
{
if ( (pQ->rear + 1)% 6 == pQ->front )
return true;
else
return false;
}
bool en_queue(QUEUE *pQ,int val);//入隊(duì)
{
if ( full_queue (pQ) )
{
return false;
}
else
{
pQ->pBase [pQ->rear] = val;
pQ->rear = (pQ->rear+1)%6 ;
return true;
}
}
bool emput_queue(QUEUE *pQ)
{
if (pQ->front==pQ->rear)
return 1;
else return 0;
}
bool out_queue(QUEUE *pQ,int *pVal)
{
if (emput_queue(pQ))
return 0;
else
{
*pVal = pQ->pBase[pQ->front] ;
pQ->front = (pQ->front+1)%6;
return 1
}
}
void tarverse_queue(QUEUE *pQ)
{
int i=pQ->front;
while (i!=pQ->rear)
{
printf("%d ",pQ->Base[i]);
i=(i+1)%6;
}
}
int main(viod)
{
int val;
QUEUE Q;
init(&Q);
en_queue(&Q,1);
en_queue(&Q,2);
en_queue(&Q,3);
en_queue(&Q,4);
en_queue(&Q,5);
en_queue(&Q,6);
traverse_queue(&Q);
if (out_queue(&Q,&val))
{
printf("出隊(duì)成功，出隊(duì)元素是：%d\n“，val;
}
else printf("出隊(duì)失敗\n");
return 0;
}
3.遞歸：
定義：
一個(gè)函數(shù)直接或者間接的調(diào)用自己
直接：f套f 間接：f套g g套f
遞歸滿足三個(gè)條件:
1、遞歸必須得有一個(gè)明確的中止條件
2、該函數(shù)所處理的數(shù)據(jù)規(guī)模必須在遞減
3、這個(gè)轉(zhuǎn)化必須是可解的
循環(huán)和遞歸
遞歸:
易于理解
速度慢
存儲(chǔ)空間大
循環(huán)：
不易理解
速度快
存儲(chǔ)空間小
注意事項(xiàng)：
當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)函數(shù)之前，系統(tǒng)需要完成三件事:
1.將所有的實(shí)際參數(shù),返回地址等信息傳遞給被調(diào)函數(shù)保存
2為被調(diào)函數(shù)的局部變量(也包括形參)分配存儲(chǔ)空間
3.將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口
從被調(diào)函數(shù)返回主調(diào)函數(shù)之前，系統(tǒng)也要完成三件事:
1.保存被調(diào)函數(shù)的返回結(jié)果
2釋放被調(diào)函數(shù)所占的存儲(chǔ)空間
3.依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)
應(yīng)用：
①、高斯求和
②、階乘
③、漢諾塔
④、走迷宮
模塊二：非線性結(jié)構(gòu)
樹
專業(yè)定義
1.有且僅有一個(gè)根節(jié)點(diǎn)
2.有若干個(gè)互不相交的子樹，這些子樹本身也是一棵樹
通俗定義：
1.樹由節(jié)點(diǎn)和邊（指針域）組成
2.每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)（除根節(jié)點(diǎn)無父節(jié)點(diǎn)
樹的專業(yè)術(shù)語：
深度:
從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)稱之為深度
根節(jié)點(diǎn)是第一層
葉子節(jié)點(diǎn):
沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
非終端節(jié)點(diǎn)
實(shí)陳就是非葉子節(jié)點(diǎn)
度
子節(jié)點(diǎn)的個(gè)數(shù)稱為度
樹的分類
一般樹：任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)都不受限制
二叉樹：任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)最多兩個(gè)，且子節(jié)點(diǎn)的位置不可更改
二叉樹的分類
一般二叉樹
滿二叉樹
在不增加樹的層數(shù)的前提下，無法再增加一個(gè)節(jié)點(diǎn)的二叉樹是滿二叉樹
完全二叉樹
如果只刪除了滿二叉樹最底層最右邊的連續(xù)若干個(gè)節(jié)點(diǎn)，這樣形成的二叉樹是完全二叉樹
森林：n個(gè)互不相交的樹的集合
樹的存儲(chǔ)
二叉樹的存儲(chǔ)
連續(xù)存儲(chǔ)【完全二叉樹】
由于先中后三種樹的轉(zhuǎn)化方式都無法重新推到出樹并且不一致，只能補(bǔ)足
優(yōu)點(diǎn)：查找某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)（也包括判斷有沒有
缺點(diǎn)： 耗內(nèi)存過大
鏈?zhǔn)酱鎯?chǔ)：
一般樹的存儲(chǔ)：（無序
雙親表示法
求父節(jié)點(diǎn)方便
孩子表示法
求子節(jié)點(diǎn)方便
雙親孩子表示法
集以上兩種的特長(zhǎng)，缺點(diǎn)是編程麻煩
二叉樹表示法
把一個(gè)普通樹轉(zhuǎn)化成二叉樹來存儲(chǔ)
具體轉(zhuǎn)換方法:
設(shè)法保證任意一個(gè)節(jié)點(diǎn)的左指針域指向它的第一個(gè)孩子，右指針域指向它的兄弟
滿足此條件，就可以把一個(gè)普通樹轉(zhuǎn)化為二叉樹
森林的存儲(chǔ)
先把森林轉(zhuǎn)化為二叉樹，再存儲(chǔ)二叉樹
二叉樹的操作
遍歷
先序遍歷
先訪問根節(jié)點(diǎn)
再先序訪問左子樹
先序訪問右子樹
中序遍歷
中序遍歷左子樹
再訪問根節(jié)點(diǎn)
再中序遍歷右子樹
后序遍歷[最后訪問根節(jié)點(diǎn)]
先中序詘歷左子樹
再中序遍歷右子樹
再訪問根節(jié)點(diǎn)
已知兩種遍歷序列求原始二叉樹
通過先序和中序或者中序和后序我們可以 還原出原始的二叉樹
但是通過先序和后序是無法還原出原始的二叉樹的
先序中序求樹技巧
①先序第一個(gè)為根節(jié)點(diǎn)
②中序中的字母在先序中先出現(xiàn)的為那層的根節(jié)點(diǎn)
后序中序求樹技巧
①后序最后一個(gè)為根節(jié)點(diǎn)
②中序中的字母在后序中后出現(xiàn)的為那層的根節(jié)點(diǎn)
應(yīng)用
樹是數(shù)據(jù)庫中數(shù)據(jù)組織一種重要形式
操作系統(tǒng)子父進(jìn)程的關(guān)系本身就是一糅樹
面向?qū)ο笳Z言中類的維承關(guān)系
赫夫曼樹
二叉鏈表的創(chuàng)建(如圖
#include <stdio.h>
struct BTNode
{
int dat a;
struct BTNode * pLchild; / /p是指針 L是左 child是孩子
struct BTNode * pRchild;
}
int main(void)
{
struct BTNode * pT = CreateBTree(void) ;
//先中后序遍歷
PreTraverseBTree(pT)；
InTraverseBTree(pT);
PostTraverseBTree(pT) ;
return 0;
}
struct BTNode *CreateBTree(void)
{
struct BTNode * pA= (struct BTNode *)malloc(sizeof (struct BTNode));
struct BTNode * pB= (struct BTNode *)malloc(sizeof (struct BTNode));
struct BTNode * pC= (struct BTNode *)malloc(sizeof (struct BTNode));
struct BTNode * pD= (struct BTNode *)malloc(sizeof (struct BTNode));
struct BTNode * pE= (struct BTNode *)malloc(sizeof (struct BTNode));
pA->data = 'A'；
pB->data =‘B’；
pC->data = 'C'；
pD->data = 'D'；
pE->data = ’E’；
pA-> pLchild = pB;
pA->pRchild = pC;
pB-> pLchild = pB-> pRchild = NULL;
pC->pLchild = pD;
pC->pRchild = NULL;
pD->pLchild = NULL;
pD-> pRchild = pE;
pE->pLchild = pE->pRchild=NULL;
return pA ;
}
void PreTraverseBTree(strcut BTNode * PT)；
{
if (pT!=NULL)
{
printf("%c\n",pT->data);
if(NULL != pT-> pLchild)
PreTraverseBTree(pT->pLchild);
if(NULL != pT-> pRchild)
PreTraverseBTree(pT->pRchiid):
}
//pT->pLchild可以代表整個(gè)左子樹
/*偽算法
先訪問根節(jié)點(diǎn)
再先序訪問左子樹
再先序訪問右子樹*/
}
void InTraverseBTree(struct BTNode * pT)
if (NULL != pT)
{..
if (NULL != pT->pLchild)
InTraverseBree(pT->pLchild) ;
printf("%c\n"，pT->data);
if (NULL != pT->pRchild){
InTraverseBTree(pT->pRchild) :1/pT->pLchild可以代表整個(gè)左子樹
}
圖
{
數(shù)據(jù)庫
字段：反映事物的屬性
記錄：一個(gè)整體的事務(wù)
表：同一類事物的集合
}
