第一章 緒論
1.1 什么是數(shù)據(jù)結(jié)構(gòu)
1.1.1 數(shù)據(jù)結(jié)構(gòu)的定義
數(shù)據(jù)：描述客觀事物的數(shù)和字符的集合
數(shù)據(jù)元素：數(shù)據(jù)的基本單位
數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集
數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系，可以看作互相之間有著特定關(guān)系的集合
1.1.2 邏輯結(jié)構(gòu)
1.邏輯結(jié)構(gòu)的表示
一?、? 圖標(biāo)表示
? ? ?采用圖表來(lái)進(jìn)行表示邏輯關(guān)系
二、? ?二元組
? ? 一種數(shù)據(jù)邏輯結(jié)構(gòu)表示方式
B=（D,? R )??
D ：數(shù)據(jù)元素的集合
R ：關(guān)系的集合
在R之中有一個(gè)關(guān)系r是序偶的集合，對(duì)于r中任意序偶<x , y>，表示 x 與 y 相鄰
x 為 y 的前驅(qū)元素? ? ? ? ? ? ?
y 為 x 的后繼元素
x沒(méi)有前驅(qū)元素為開(kāi)始元素
y沒(méi)有后繼元素為終端元素
注意：矩陣中r進(jìn)行的描述需要特別注意 設(shè)r1為行 r2為列，進(jìn)行的排列需要注意
2.邏輯結(jié)構(gòu)的類型
一、集合
二、線性結(jié)構(gòu)
? ? 線性結(jié)構(gòu)是指該結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系，開(kāi)始元素何終端元素都是唯一的，其余元素有且只有一個(gè)前驅(qū)和終端元素
三、樹(shù)形結(jié)構(gòu)
? ? 樹(shù)形結(jié)構(gòu)是指該結(jié)構(gòu)中元素存在單對(duì)多的關(guān)系，每個(gè)元素有一個(gè)或者多個(gè)后繼元素，二叉樹(shù)就是一個(gè)經(jīng)典的樹(shù)形結(jié)構(gòu)
1.1.3存儲(chǔ)結(jié)構(gòu)
?? ? 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也成為映像）也就是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)實(shí)現(xiàn)?
一、順序儲(chǔ)存結(jié)構(gòu)
? ? 采用一組連續(xù)的存儲(chǔ)單元存放所有的數(shù)據(jù)元素，即順序儲(chǔ)存結(jié)構(gòu)將數(shù)據(jù)的邏輯結(jié)構(gòu)直接映射到存儲(chǔ)結(jié)構(gòu)（特點(diǎn)：儲(chǔ)存效率高，但不便于修改數(shù)據(jù)）
二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
? ? 每個(gè)邏輯元素用一個(gè)內(nèi)存結(jié)點(diǎn)存儲(chǔ)，每個(gè)節(jié)點(diǎn)單獨(dú)分配，所有節(jié)點(diǎn)地址不一定連續(xù)，無(wú)需占用一整塊的存儲(chǔ)空間，給每個(gè)節(jié)點(diǎn)添加指針域，用于存放相鄰節(jié)點(diǎn)的存儲(chǔ)地址，也就是通過(guò)指針域?qū)⑺械墓?jié)點(diǎn)鏈接起來(lái)
三、索引存儲(chǔ)結(jié)構(gòu)? P8
四、哈希存儲(chǔ)結(jié)構(gòu)? P8?
1.1.4 數(shù)據(jù)運(yùn)算
? ? 數(shù)據(jù)運(yùn)算是指對(duì)數(shù)據(jù)實(shí)施操作，同樣的運(yùn)算在不同存儲(chǔ)結(jié)構(gòu)中，其實(shí)現(xiàn)過(guò)程不同
1.1.5 數(shù)據(jù)類型與抽象數(shù)據(jù)類型
一、數(shù)據(jù)類型
二、抽象數(shù)據(jù)類型
1.2?算法及其描述
1.2.1算法的定義
? ??對(duì)特定的問(wèn)題求解步驟的描述，是指令的有限序列，它滿足以下幾點(diǎn)
（1）有窮性
（2）確定性
（3）可行性
（4）有輸入輸出
算法與程序的區(qū)別
程序：計(jì)算機(jī)語(yǔ)言對(duì)一個(gè)算法具體實(shí)現(xiàn)? ? 算法：側(cè)重于解決問(wèn)題的方法描述
1.2.2算法設(shè)計(jì)的目標(biāo)
? ??算法設(shè)計(jì)應(yīng)該滿足以下特點(diǎn)
（1）正確性
（2）可使用性
（3）可讀性
（4）強(qiáng)壯性
（5）高效率與低存儲(chǔ)量需求
1.2.3算法的描述
? ? 詳情見(jiàn)書P16頁(yè)
1.3算法分析
1.3.1算法分析概述
分析算法占用的資源
1、cpu時(shí)間
2、內(nèi)存空間
1.3.2算法的時(shí)間性能分析
? ? 一個(gè)算法是由控制結(jié)構(gòu)（順序、分支、循環(huán)）和原操作構(gòu)成的
一、衡量算法時(shí)間性能的方法
（1）事后統(tǒng)計(jì)法
（2）事前估算法
二、算法時(shí)間復(fù)雜度的分析
（1）計(jì)算算法的頻度
void fun (int a[],int n){
int i; //1
for (i=0;i<n;i++){ //2
a[i]=2*1; //3
}
for(i=0;i<n;i++){ //4
printf("%d", a[i]); //5
}
printf("\n"); //6
}程序中1,3,5,6為原操作
原操作的執(zhí)行次數(shù)（也成為頻度），他是問(wèn)題規(guī)模n的函數(shù)，用T（n）表示
算法執(zhí)行的時(shí)間估計(jì) = 原操作所需要的時(shí)間 * T（n），所以T（n）與算法執(zhí)行的時(shí)間成正比
通過(guò)比較T（n)的大小可以得出算法執(zhí)行時(shí)間的好壞
分析程序時(shí)間復(fù)雜度
【例1-6】求兩個(gè)n階方陣的相加C=A+B的算法如下，分析其時(shí)間復(fù)雜度
#define MAX 20
void matirxadd(int n,int A[MAX][MAX],int B[MAX][MAX],int C[MAX][MAX]){
int i,j;
for(i=0;i<n;i++){ //頻度為n+1 循環(huán)次數(shù)為n
for(j=0;j<n;j++){ //頻度為n(n+1)
C[i][j]=A[i][j]+B[i][j] //頻度為n^2
}
}
}所以該程序的頻度和為? ? ? ? ? ? ? ? ???T（n）=2n^2+2n+1
(2)時(shí)間復(fù)雜度的的表示
? ? 算法中執(zhí)行實(shí)時(shí)間T（n）是問(wèn)題規(guī)模n的某個(gè)函數(shù)f（n），T(n) = Of(n)?
也就是說(shuō) T（n）<=cf(n)
三、簡(jiǎn)化算法時(shí)間復(fù)雜度分析
? ? 算法中的基本操作一般是最深層循環(huán)內(nèi)的原操作
? ? 算法執(zhí)行時(shí)間大致=原操作所需要的時(shí)間*其運(yùn)算次數(shù)
void func(int n){
int i=0, s=0;
while(s<n){
i++;
s=s+i;
}
}分析其時(shí)間復(fù)雜度
S=m(m+1)/2>=n
m(m+1)/2+k=n
此處使用韋達(dá)定理進(jìn)行運(yùn)算得到的時(shí)間復(fù)雜度為O sqrt（n）
題目練習(xí)
一、采用二元組表示的數(shù)據(jù)邏輯結(jié)構(gòu)S=<D,R>,其中D={a,b,c,......,i},R={r},r={<a,b>,<a,c>,<c,d>,?<c,f>,<f,h>,<d,e>,<f,g>,<h,i>}請(qǐng)問(wèn)r是什么類型的數(shù)據(jù)結(jié)構(gòu)？哪些節(jié)點(diǎn)是開(kāi)始節(jié)點(diǎn)？哪些節(jié)點(diǎn)是終端節(jié)點(diǎn)？
? ? ? r是樹(shù)形結(jié)構(gòu)，每個(gè)元素有一個(gè)或者多個(gè)后繼元素，其中a節(jié)點(diǎn)是開(kāi)始節(jié)點(diǎn)，b，e，i，g節(jié)點(diǎn)是終端節(jié)點(diǎn)
二、簡(jiǎn)述數(shù)據(jù)邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系
? ? 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也成為映像）也就是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)實(shí)現(xiàn)
三、有以下用C/C++語(yǔ)言描述的算法，說(shuō)明其功能:
void fun(double &y,double &x,int n){
y=x;
while(n>1){
y=y*x;
n--;
}
}? ? 由題可知，語(yǔ)句二將x的值賦給了引用的y，之后開(kāi)始循環(huán)，第一次y=y*x不難發(fā)現(xiàn)是x*x，n--，可以發(fā)現(xiàn)該代碼是在求x^n
四、分析下面程序段中循環(huán)語(yǔ)句的執(zhí)行次數(shù)
int j=0,s=0,n=100{
do{
j=j+1;
s=s+10*j;
}while(j<n && s<n) //代碼中&&表與運(yùn)算? ? 由題可知，while語(yǔ)句中（j<n && s<n)要同時(shí)滿足j<n 和 s<n的時(shí)候，循環(huán)才會(huì)繼續(xù)，?第一次執(zhí)行時(shí)j=1 s=10 第二次執(zhí)行 j=2 s=30 第三次執(zhí)行 j=3 s=60 第四次執(zhí)行j=4 s=100 ，到此不滿足while條件不繼續(xù)進(jìn)行循環(huán)，可知循環(huán)語(yǔ)句執(zhí)行了4次
五、設(shè)n為正整數(shù)，給出下列3個(gè)算法關(guān)于問(wèn)題規(guī)模n的時(shí)間復(fù)雜度
（1）算法1
void fun1(int n){
i=1,k=100;
while(i<=n){
k=k+1;
i+=2;
}
}? ? 由題可知，循環(huán)的結(jié)束是由i來(lái)決定，所以? i=1+2T(n)<=n 加上一個(gè)補(bǔ)平的K， 1+2T(n)+K=n
2T(n)=n-K-1 （n-K-1）/2=T(n)? ?可以得知算法一時(shí)間復(fù)雜度為 O(n）
(2)算法2
void fun2(int n){
int i=0,s=0;
while(s<=n){
i++;
s=s+i;
}
}? ? ?由題可知，循環(huán)的結(jié)束是由s來(lái)決定，所以可以得到以下式子 1+2+3+......+T(n)<=n,通過(guò)公式可得到 （1+T(n))T(n)/2+k=n? T(n)^2+T(n)=2n-2k 可以得出時(shí)間復(fù)雜度為O(sqrt(n))
附件1 常見(jiàn)時(shí)間復(fù)雜度對(duì)照表
第二章 線性表
2.1線性表及其邏輯結(jié)構(gòu)
2.1.1線性表的定義
? ? ?線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列，該序列中所包含的元素的個(gè)數(shù)叫線性表的長(zhǎng)度，用n表示，n>=0，當(dāng)n=0時(shí)，表示線性表為一個(gè)空表
線性表有以下特征
（1）有窮性：線性表元素個(gè)數(shù)有限
（2）一致性：一個(gè)線性表中元素性質(zhì)相同
（3）序列性：線性表中所有元素的位置是線性的
2.1.2線性表抽象類型描述
線性表有以下九個(gè)重要的基本運(yùn)算
[例 2-2]初始化線性表LC，即創(chuàng)建一個(gè)空的線性表LC，將LA的所有元素復(fù)制到LC中，然后遍歷線性表LB，將LB中不屬于LA的元素插入LC中
2.2線性表的順序儲(chǔ)存結(jié)構(gòu)
2.2.1線性表的順序儲(chǔ)存結(jié)構(gòu)----順序表
? ? ?線性表順序儲(chǔ)存結(jié)構(gòu)：把線性表中的所有元素按照順序儲(chǔ)存方法進(jìn)行存儲(chǔ)，也就是按照邏輯順序依次存儲(chǔ)到一篇連續(xù)的存儲(chǔ)空間之中，這種映射稱為直接映射?
? ? ?順序表類型的聲明
#define MaxSize 50
//設(shè)置MaxSize的大小為50
typedef struct{
ElemType data[MaxSize];
int length;
}SqList //順序表的類型? ? ?邏輯位序與物理位序相差1
2.2.2順序表基本運(yùn)算的實(shí)現(xiàn)
? ? ? 詳情見(jiàn)書P34-P42 不做細(xì)節(jié)概述
題目練習(xí)
2.2線性表的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)
2.3.1線性表的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)----鏈表
? ??線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈表，線性表的每一個(gè)元素用一個(gè)節(jié)點(diǎn)儲(chǔ)存，每個(gè)內(nèi)存節(jié)點(diǎn)不僅僅包含元素本身的信息，也包含表示每個(gè)節(jié)點(diǎn)之間邏輯關(guān)系的信息，在C/C++中用指針來(lái)表示，被稱為指針域
? ? 線性表每個(gè)元素僅有一個(gè)前驅(qū)元素和一個(gè)后繼元素，所以在每個(gè)節(jié)點(diǎn)外只設(shè)置一個(gè)指針指向后繼節(jié)點(diǎn)，構(gòu)成線性單向鏈接表，稱為單鏈表，而設(shè)置兩個(gè)指針域分別指向前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)構(gòu)成線性雙向鏈接表，稱為雙鏈表
? ? 指向頭節(jié)點(diǎn)的指針---頭指針
? ? 指向開(kāi)始節(jié)點(diǎn)/首節(jié)點(diǎn)的指針---首指針
? ? 指向尾節(jié)點(diǎn)的指針---尾指針
? ? 儲(chǔ)存密度=節(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)量/節(jié)點(diǎn)所占的存儲(chǔ)量
? ? 一般來(lái)說(shuō)存儲(chǔ)密越大，存儲(chǔ)空間利用率越高，顯然順序表的利用率為100%，而鏈表小于100%,單鏈表存儲(chǔ)密度為50%
2.3.2單鏈表
? ? 在單鏈表中節(jié)點(diǎn)類型用LinkNode來(lái)表示，它應(yīng)包含存儲(chǔ)元素的數(shù)據(jù)域，類型使用通用類型=標(biāo)識(shí)符ElemType表示，包含的指針用next表示
typedef struct LNode{
ElemType date;
struct LNode *next;
}LinkNode //單鏈表節(jié)點(diǎn)類型LinkNode
? ??重點(diǎn)：插入節(jié)點(diǎn)與刪除節(jié)點(diǎn)
? ? 循環(huán)鏈表的概念
題目練習(xí)
void fun1(LinkNode *&L1,LinkNode *&L2) {
int n=0,i;
LinkNode *p=L1;
while (p!=NULL)
{
n++;
p=p->next;
}
p=L1;
for (i=1;i<n/2;i++)
p=p->next;
L2=p->next;
p->next=NULL;
}
? ? ? 對(duì)于含有 n 個(gè)結(jié)點(diǎn)的單鏈表 L1，將 L1 拆分成兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表 L1 和 L2，其中 L1 含有原來(lái)的前 n/2 個(gè)結(jié)點(diǎn)，L2 含有余下的結(jié)點(diǎn)。
實(shí)驗(yàn)題一
//實(shí)現(xiàn)順序表的各種基本運(yùn)算的算法
#include<stdio.h>
#include<malloc.h>
//線性表的順序存儲(chǔ)結(jié)構(gòu)
#define MaxSize 50
typedef char ElemType;
char ch;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
//(1)初始化順序表
void InitList(SqList * &L)
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}
//(2)依次插入a,b,c,d,e元素
bool ListInsert(SqList * &L,int i,ElemType e)
{
int j;
if(i<1 || i>L->length+1)
return false;
i--;
for(j=L->length;j>i;j--)
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return true;
}
//(3)輸出順序表
void DisplayList(SqList * L)
{
for(int i=0;i<L->length;i++)
printf("%c",L->data[i]);
printf("\n");
}
//(4)求線性表的長(zhǎng)度
int ListLength(SqList * L)
{
return (L->length);
}
//(5)判斷順序表L是否為空
bool ListEmpty(SqList * L)
{
return (L->length==0);
}
//(6)輸出順序表L的三個(gè)元素
bool GetElem(SqList * L,int i,ElemType e)
{
if(i<1||i>L->length)
return false;
e=L->data[i-1];
ch=e;
return true;
}
//(7)查找順序表所在位置
int LocateElem(SqList * L,ElemType e)
{
int i=0;
while(i<L->length&&L->data[i]!=e)
i++;
if(i>=L->length)
return 0;
else
return i+1;
}
//(10)刪除順序表上的第三個(gè)元素
bool ListDelete(SqList * &L,int i,ElemType e)
{
int j;
if(i<1 ||i>L->length)
return false;
i--;
e=L->data[i];
for(j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return true;
}
//(12)釋放線性表
void DestroyList(SqList * &L)
{
free(L);
}
//主函數(shù)
int main()
{
SqList *L;
printf("(1)初始化順序表L.\n");
InitList(L);
printf("(2)依次插入a,b,c,d,e元素.\n");
ListInsert(L,1,'a');
ListInsert(L,2,'b');
ListInsert(L,3,'c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
printf("(3)輸出順序表L：");
DisplayList(L);
printf("(4)輸出順序表L的長(zhǎng)度：%d\n",ListLength(L));
printf("(5)判斷順序表L是否為空：%s\n",(ListEmpty(L)?"空":"非空"));
GetElem(L,3,'e');
printf("(6)輸出順序表L的第3個(gè)元素：%c\n",ch);
printf("(7)輸出元素a的位置：%d\n",LocateElem(L,'a'));
printf("(8)在第4個(gè)元素位置上插入f元素.\n");
ListInsert(L,4,'f');
printf("(9)輸出順序表L：");
DisplayList(L);
printf("(10)刪除順序表L的第3個(gè)元素.\n");
ListDelete(L,3,'e');
printf("(11)輸出順序表L：");
DisplayList(L);
printf("(12)釋放順序表L\n");
DestroyList(L);
return 0;
}第三章 棧和隊(duì)列
棧和隊(duì)列基礎(chǔ)知識(shí)
棧的基礎(chǔ)知識(shí)
棧是一種只能在一端進(jìn)行插入或刪除操作的線性表，表中允許進(jìn)行插入刪除操作的一端叫做棧頂，表的另外一端叫做棧底，棧頂?shù)奈恢檬莿?dòng)態(tài)的，當(dāng)棧中沒(méi)有元素的時(shí)候稱為空棧
棧的插入操作被稱為入?；蜻M(jìn)棧(push)，棧的刪除操作被稱為出?；蛘咄藯?pop)
棧的主要特點(diǎn)是后進(jìn)先出，所以棧也被稱為后進(jìn)先出表
采用順序儲(chǔ)存結(jié)構(gòu)的的棧被稱為順序棧，元素最大的個(gè)數(shù)不超過(guò)MaxSize，單條順序棧有以下幾個(gè)特點(diǎn)
1)棧空的條件是s->top==-1? ?當(dāng)top指針在-1也就是棧外的時(shí)候表面棧是空的
2)棧滿的條件是s->top==MaxSize-1? ?(data數(shù)組最大下標(biāo)）
3)元素e入棧的操作流程：? ?
? ? ?將棧頂指針top+1，將元素e放在棧頂指針處
4)出棧的操作：
? ? ?將棧頂指針top的元素去出放在e中，然后將棧頂指針top-1
共享?xiàng)Ｓ幸韵聨讉€(gè)特點(diǎn)
1）?？盏臈l件是? 棧1空 top1==-1? 棧2空 top2==MaxSize
2）棧滿的條件? ?top1==top2-1
3）元素x進(jìn)棧的操作
? ? ? 進(jìn)棧1 top++；data[top1]=x
? ? ? 進(jìn)棧2 top--； data[top2]=x
4)出棧的操作
? ? ? 出棧1 x=data[top1]; top1--;
? ? ? 出棧2 x=data[top2]; top++;
隊(duì)列的基礎(chǔ)知識(shí)
對(duì)列簡(jiǎn)稱隊(duì)，它也是一種操作受限的線性表，其限制為僅允許在表的一端進(jìn)行插入操作，而在表的另外一端只能夠進(jìn)行刪除操作
我們通常把插入的一端稱為隊(duì)尾（rear），把進(jìn)行刪除操作的一端稱為隊(duì)頭或者隊(duì)首（front），新元素入隊(duì)之后成為新的隊(duì)尾元素，從隊(duì)列中刪除元素稱為出隊(duì)或者離隊(duì)，元素出隊(duì)后，下一個(gè)元素成為新的隊(duì)首元素
由于隊(duì)列的刪除和插入在表的不同兩端進(jìn)行，隊(duì)列也被稱為先進(jìn)先出表
隊(duì)列有以下特點(diǎn)
1）隊(duì)空的條件? q->front==q->rear=-1
2）隊(duì)滿的條件? q->rear==MaxSize-1 (data數(shù)組最大下標(biāo)）
3）元素e入隊(duì)的操作 將rear+1，將元素放在rear指針處
4）出隊(duì)的操作 將front+1,取出data數(shù)組中front位置的元素??
環(huán)形隊(duì)列的幾種狀態(tài)
為了增加空間利用率，防止隊(duì)列假溢出問(wèn)題的發(fā)生，產(chǎn)生了環(huán)形隊(duì)列
環(huán)形隊(duì)列/循環(huán)隊(duì)列
空棧的條件? ? q->rear==q->front
隊(duì)滿的條件? ? （q->rear+1）%MaxSize==q->front
出隊(duì)操作和入隊(duì)操作將隊(duì)尾和隊(duì)首指針都循環(huán)進(jìn)1
題目練習(xí)
第四章 串
4.1串的基本概念
? ? 串是由零個(gè)或者多個(gè)字符組成的有限序列，含零個(gè)字符稱為空串，串包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度
? ? 兩個(gè)串相等當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度相等，且各個(gè)對(duì)應(yīng)位置上的字符相同，一個(gè)串中任意連續(xù)兩個(gè)字符組成的序列稱為該串的子串
4.2串的儲(chǔ)存結(jié)構(gòu)
? ??和線性表一樣，串的順序儲(chǔ)存結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)，前者稱為順序串，后者稱為鏈串
4.2.1 串的順序儲(chǔ)存結(jié)構(gòu)----順序串
? ? 順序串中的字符被依次存放在一組連續(xù)的存儲(chǔ)單元里，與順序表類似
4.2.2?串的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)----鏈串
? ? 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的串被稱為鏈串，鏈串的組織形式與一般的單鏈表類似，區(qū)別在于鏈串中的一個(gè)節(jié)點(diǎn)可以存放多個(gè)字符
4.3 串的模式匹配
? ? 設(shè)置兩個(gè)串s和t，s稱為目標(biāo)串，t稱為模式串，在串s中找到一個(gè)與t相等的子串稱為模式匹配
4.3.1BF算法
? ? BF算法也成為暴力算法，簡(jiǎn)單匹配算法主要在于采用窮舉法進(jìn)行計(jì)算
4.3.2KMP算法
? ??重難點(diǎn)：在BF算法上從串中提取出來(lái)有用的匹配信息進(jìn)行計(jì)算
題目練習(xí)
一、KMP算法是BF算法的改進(jìn)，以目標(biāo)串s="aabaaabc"、模式串t="aaabc"為例說(shuō)明next的作用
二、給出以下模式串next的值和nextval的值
nextval[0]=-1
t j=t next[j]時(shí) nextval[j]=nextval[next[j]]
否則nextval[j]=next[j]?
第五章 遞歸
5.1 什么是遞歸
5.1.1遞歸的定義
? ? ?在定義一個(gè)過(guò)程或函數(shù)時(shí)出現(xiàn)調(diào)用自身過(guò)程或者本函數(shù)成分的稱為遞歸，若是自己調(diào)用自己，則被稱為直接遞歸，若是函數(shù)f1調(diào)用f2，f2調(diào)用f1則被稱為間接遞歸?
例[5-1]求解N！
int fact(int n){
if(n==1){
return 1;
}else{
return n*fact(n-1);
}
}? ? 遞歸算法經(jīng)常把一個(gè)大的復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)或者多個(gè)原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)進(jìn)行求解
5.1.2何時(shí)使用遞歸
1、定義是遞歸的
2、數(shù)據(jù)結(jié)構(gòu)是遞歸的
3、問(wèn)題求解的方法是遞歸的
5.1.3遞歸模型
? ? 一般情況下，一個(gè)遞歸模型由遞歸出口和遞歸體兩部分組成，遞歸出口確定遞歸何時(shí)結(jié)束，指出明確的遞歸結(jié)束條件，遞歸體是確定遞歸求解的遞推關(guān)系
? ? 實(shí)際上遞歸就是將一個(gè)大問(wèn)題轉(zhuǎn)化成幾個(gè)小問(wèn)題
5.2 棧和遞歸 遞歸算法的設(shè)計(jì)?
? ? 在此不做詳細(xì)解釋，詳情見(jiàn)書P145-156
題目練習(xí)
一、有以下遞歸函數(shù),分析調(diào)用fun(5)的輸出結(jié)果
void fun(int n){
if(n==1){
printf("a:%d\n",n)
}else{
printf("b:%d\n",n)
fun(n-1);
printf("c:%d\n",n)
}
}? ? ??由題可知，該遞歸函數(shù)由f5->f4->f3->f2->f1->f2->f3->f4->f5
? ? 輸出的結(jié)果依次是
? ? ? ? b=5 b=4 b=3 b=2 a=1 c=1 c=2 c=3 c=4 c=5文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-809702.html
第六章 數(shù)組和廣義表
6.1數(shù)組
6.1.1數(shù)組的基本概念
? ? 從邏輯結(jié)構(gòu)上面來(lái)看，一堆數(shù)組A是n(n>1)個(gè)相同類型的數(shù)據(jù)元素a1、a2、a3、......、an構(gòu)成的有限序列，其邏輯結(jié)構(gòu)表示?A=(a1,a2,a3,......,an)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-809702.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)（期末復(fù)習(xí)篇） 清華大學(xué)出版社的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
