资源描述
第一章 绪论
1. 数据结构:主要研究非数值计算问题中计算机得操作对象有哪些结构(逻辑结构）、这些结构在计算机中得表示及其操作得定义与实现问题。
2. 逻辑结构:不考虑实现，仅瞧问题域中数据元素根据相互间得逻辑关系形成得结构称为数据结构得逻辑结构。通常说得数据结构即此义.分类：如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则(一对多）形成一个树形数据结构，城市间据通路（多对多）形成图状结构，此外还有集合结构（除同属一个集合外,无其它关联),共四类
3. 数据结构（数据元素及关系／结构）在计算机中得表示或者说映像称为该数据结构得物理结构或存储结构.
4. 顺序存储结构：关系采取顺序映像表示,即借助元素在存储器中得位置上得"相邻"关系隐式表示数据元素间具有关系。此时物理结构对应一个数组。优点:可根据起始地址随机访问各元素。缺点：需事先分配一足够大空间，且插入删除结点需移动大量数据。
链式存储结构:关系采取链式映像表示,即借助附加信息指针显式表示元素间得关系,对应一个链表。优点就是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。
5. 度量指标：算法运行时间主要取决于基本操作得执行次数（频度)，执行次数通常随问题规模扩大而增加,增加越快意味着算法随问题规模得扩大,运行时间增长得也快，从而该种算法效果较差；增长越慢算法越好,故可用基本操作得频度随问题规模得增长率反映算法得效率.
6. 时间复杂度：频度函数得增长率基本与函数中“关键项”(去掉低次项与常数项）得增长率相同，故可用“关键项” 反映算法效率。假设关键项为f（n）,用T(n）=O（f(n))表示算法时间增长率与ｆ（n)增长率同阶。称O（f（n))为算法得渐近时间复杂度,简称时间复杂度。f(n）得增长率为f（n+1）／f（n），如对复杂度为O（ｎ）得算法其运行时间随问题规模增长率为1＋１/n，复杂度为O（1）得算法时间增长率为1.
7. 按增长率由小至大得顺序排列下列各函数 （2/3)n —２100 —㏒2n—ｎ１／2—n －n㏒2n—n3/ 2-2ｎ—n！-nn
第二章 线性表
1. 顺序表：借助元素在存储器中位置上得”相邻”关系表示数据元素间具有得关系,如此存储得线性表称为顺序表。顺序表优点就是实现简单方便,可随机访问各元素；缺点就是插入或删除元素时会引起大量得数据元素移动（表尾除外)；对于长度变化较大得线性表,要一次性地分配足够得存储空间，但这些空间常常得不到充分利用。
2. 线性链表：采用链式存储结构得线性表对应一个链表。结点包含数据域与指针域两部分。链表名指向第一个结点 (头指针），尾结点指针域值为NULL。链表优点就是空间利用好，插入删除不移动数据，表头表尾操作快（改进得单链表）,位置概念强；缺点就是需要顺序访问各元素，位序概念弱.
顺序表相关程序：
＃dｅfine LIST_IＮＩＴ_ＳIＺE 1００ /／…
＃ｄｅfine LＩSTINCRＥMENT 10 //…
typedef ＊＊＊*＊ ＥlemＴype;
tｙpedef struｃt｛
ElemTｙpe *eｌem； //存储空间基址
ｉnt leｎｇｔh； //…
ﻩiｎｔ liｓtｓize; //……
ﻩ}SqLｉsｔ；
SｑＬiｓt Lａ,Lb，Lc；
Status ＩnitLiｓt_Sq(SqLiｓt &Ｌ）
｛//构造空线性表L
L、elｅm=（ＥｌeｍType＊）mａlｌoc(LＩST＿INIＴ_SIZＥ
*sizeof(EｌeｍＴype))
ﻩ ｉf(Ｌ、eｌem==0)ﻩexiｔ（OVEＲFLOW）；
L、length＝0; //初始化表长为0,“空”表
ﻩL、lｉstsｉｚｅ＝LIST＿INIT_SIＺＥ；//初始化存储容量
ﻩ retｕrｎ（OK）;
｝//IniｔLiｓｔ_Sq
ｖｏid LisｔDelete(SｑLｉst ＆L，int i，EｌemTyｐe &e）
｛/／在顺序表L中删除第ｉ个元素,用e返回其值。
//i得合法值就是[1，ListLengｔh（L）］
ﻩif（i<1|｜i>Ｌ、lｅngth） ｒｅｔurn ERRＯＲ；//删除位置不合理
ﻩEleｍType *ｐ=&L、ｅleｍ[i－1]，*q＝L、elem+L、lenｇｔh—1;
e＝*p；
wｈｉｌe（p〈ｑ)｛＊p=＊（ｐ+１);＋+ｐ；｝/／删除位置后元素左移
ﻩ--L、lｅngtｈ;
return Ok;
｝/／LｉstDeletｅ_Sq
Ｓtａtus ListInsｅｒｔ_Sｑ（SｑLiｓt &L,iｎt ｉ， ElｅｍTypｅ e)
{／／在顺序表L得第i个位置前插入元素e,i得合法值为1、、Ｌ、length+1
ｉf（i<1｜|i>L、length+1） ｒｅturn ERROR;/／插入不合法
ﻩｉｆ(L、ｌｅngtｈ＞=L、lｉstsize）
｛ //表满,增加存储容量
ＥｌｅmTｙｐe＊newｂａｓe=(EｌeｍTypｅ ＊）ｒealｌoc
（L、elｅｍ,(Ｌ、ｌｉstsize+LIＳTＩＮCREMENＴ）*sizeｏf(EｌeｍTｙpe))
iｆ(！ｎewbase)ﻩexｉt(OVEＲFLＯW);
Ｌ、elem=ｎewｂase;
Ｌ、ｌistｓize＋＝ＬISTＩＮCRＥMENT;
｝
ElｅmTypｅ ＊q=&L、ｅlｅm[i-1], *p=＆L、ｅleｍ［L、length—1]；
ﻩwhiｌｅ（p〉=q）
｛ ＊（p+1)=＊p； ——ｐ； ｝ //插入位置后得元素右移
＊q=e;
ﻩ++L、lenｇth；
ｒeｔｕrｎ ＯK;
}//ＬistInseｒt＿S
线性表相关程序：
tyｐedeｆ ＊***＊ ElemType；
ｔypeｄef strｕct LＮode｛
ElemTyｐe ｄａta; ／/数据域
ｓｔｒuct ＬNｏde ＊ ｎeｘt； //指针域
}LＮｏde，＊LinkList;／/默认带头结点,需说明
LNｏdｅ node1； LiｎkＬｉｓt Lａ;
Stａtｕs ＧetElem_L（ＬｉnkLｉｓt L，ｉｎｔ i，ＥlemType ＆e)
｛／/Ｌ为带头结点得单链表得头指针.第i个元素存在时,其值赋给e并返回OK,否则返回ERＲＯR
ﻩLNode *ｐ＝Ｌ－>ｎexｔ; /／p指向"第１个”结点，
int j=1；ﻩ /／ j为指向结点得位序
while(p&&j＜ｉ)
{ //顺序查找,只要p不空且未到第i结点就前进
ﻩp=p—＞next；
++j;
ﻩ}
ｉf（！ｐ）retuｒｎ ERRＯR； ／／第i个元素不存在
e=p—>ｄatａ; ／/取第ｉ个元素
reｔurn OK;
｝
Stａtuｓ ＬisｔInsｅrt＿Ｌ（LinｋLiｓt ＆L， ｉnｔ ｉ， ＥlｅmＴype e）
｛／/向链表L中第ｉ个位置插入e
LNode ＊p＝L； int j＝0; /＊p始终指向第j个结点＊/
while(p&&j〈ｉ-1)｛p=ｐ—〉nｅxt； ++j；｝/／寻找第i－1个结点
ﻩif(！ｐ) ｒeturn ＥRROR；
LNode ＊temp；
temp=（LＮode *）Maｌｌoc(siｚｅof（LNode))；
if（！tｅｍp)ﻩ ｅxｉt（OVERFLOW）;
temp－〉dａｔa=ｅ;
temp—>next＝ｐ->ｎext；
p->ｎext=teｍｐ；
rｅｔurｎ(OＫ）;
｝／／ListＩnｓeｒt_L
Statuｓ ListＤｅlｅte_Ｌ（LｉnkＬist ＆L, ｉnt ｉ， ElemＴype ＆e)
{
ＬＮoｄe ＊p＝L,＊q； int j＝０； ／＊p始终指向第j个结点＊/
whｉle（ｐ&&j〈i—1）{ｐ＝ｐ-〉neｘt; ++j；｝//寻找第i—1个结点,ｊ 最终为i—1，除非到表尾p空
if（！p||！p—>next）
ｒeturn EＲROR;／/第i个或更前结点不存在
ｑ=ｐ-〉next;
ﻩe=ｑ－〉ｄata;
p—〉ｎeｘｔ＝q—>nｅxt；
frｅe（ｑ）；
ﻩrｅｔuｒn（OＫ)；
｝／/ＬistDｅlete＿L
Ｓtatus CｒｅateList＿L(LinkLiｓt ＆L, ｉnt ｎ）
｛//逆位序输入ｎ个元素得值,建立带头结点得单链表Ｌ。
ＬＮoｄｅ ＊p;
Ｌ＝(LinkList） mａlloc(sｉzeof（LNodｅ））;L-＞nｅxｔ=NUＬL；
ｆor(ｉnt i=1;i<=n；++i)
｛
p=(ＬNoｄe ＊）malloc（sｉzeoｆ(ＬNode））;//LNode ＊等同LinkLisｔ
scaｎf(“…”,＆ｐ—＞data）;
ﻩｐ－〉neｘt=L-〉next;
L->next＝ｐ;／/插入到表头
｝
｝//CreateLｉst_L
相关两表得归并
void MergeＬiｓｔ_Sq (SqLｉst La，SqＬist Lb，Sqliｓt &Ｌｃ)
{//归并非降顺序表Ｌa与Lb构成非降顺序表Lc
Lc、lｉｓtｓize=Lｃ、length=La、lenｇth+Ｌb、ｌｅngth;
Lc、elem=(ＥlｅmTyｐe＊)
malｌoc（Lc、lisｔｓｉze＊sizeof（EleｍType））；
Ｉf（！Lc、eleｍ) exit（OVＥＲFLＯW)； //存储分配失败
EｌｅmTｙｐe ＊pa=Lａ、eleｍ， *pb=Lb、eleｍ， *pc=Lc、eｌem；
ElｅmTypｅ ＊pａ＿lasｔ=Lａ、eleｍ+La、lｉstｓize—1；
ElemType *pb_last=Lb、eleｍ+La、ｌｉsｔsize—1;
ｗhilｅ(ｐa〈=pa_laｓt&＆ｐb<=pｂ_last）
｛／/归并
ﻩｉf(*pa＜＝＊pb)ﻩ*pc++=＊pa++;
ﻩｅlse ﻩ *pc+＋=*pb＋+；
}
while（pa<pa＿lａst） *pc+＋=＊pa++; /／插入La剩余段
whｉle（pｂ＜ｐb_laｓt) ＊pc＋+＝＊ｐb++； //插入Ｌb剩余段
}/／MergeLisｔ_Sq
Sｔatuｓ LisｔMerge＿SｏｒtedL
(ＳoｒｔedSｑList Ｌa,SorteｄSqLisｔ Lb，SoｒtedSqＬist ＆Ｌｃ）
{／/将两个有序顺序表La与Ｌb归并为有序顺序表Lc
int la_len=ListLｅngｔh_Sq(Ｌa）;
ｉnt lｂ_leｎ=LｉsｔLengｔh_Sq(Lb)；
ﻩｉnt ｉ=1，j＝1，k=1；
ﻩElemTyｐｅ a，b;
ﻩＩnｉｔLｉｓt_Sｑ（Ｌc）；
ﻩwhile(ｉ＜＝la_len&＆j<=ｌｂ_len）
｛ //归并
GetElem_Sq(Ｌa，ｉ，ａ）；ＧetＥleｍ_Sq（Lｂ，j,ｂ）；
ﻩiｆ（a<b） {ＬｉstInsert_Sq（Ｌc,k++,a)；++i;｝
else{ ListInsｅｒt＿Sq（Lｃ， k++，b)； ++j；}
}
wｈile（i＜=la_lｅn） //插入La得剩余元素
{GｅtＥlem＿Sq(La，i＋＋，a）； LiｓｔInｓert_Sq（Ｌｃ， k++，a）；｝
wｈile（j〈＝ｌb_lｅn） ／／插入Ｌb得剩余元素
ﻩ{GｅtElｅm＿Sq（Lｂ,ｊ++,ｂ); LiｓtInsert_Ｓq(Ｌc,k++，b)；｝
rｅtｕrn OK；
}／/复杂度 O(ListLength(La）＋ＬiｓtLeｎgth（Lb)，因只在表尾插入）
3. 注意链表中nexｔ指针得应用，如插入，删除等操作各个元素得链接。
4. 顺序表得就地逆置思路：分别设两个指针ｐ与q指向第一个与最后一个元素,当p＜q时{*p与*q互换,之后+＋p,—-q}。单链表得就地逆置思路:令指针p指向首元结点，头结点断开,｛将p所指结点插入到表头后，p后移,直至ｐ为空}
Stａｔuｓ LiｓtInverse＿Ｓｑ(SｑＬist &L)
｛//顺序表就地逆置
ﻩＥleｍＴｙpe ＊p，＊q;
ElemType ｅ;
ﻩ p=Ｌ、elem;q=Ｌ、elｅm＋Ｌ、length-１；
ﻩ whiｌｅ（p＜q）
{
ﻩﻩｔemp＝＊p；ﻩ
*p＝*q；
＊ｑ＝teｍp;
+＋p； —－q；
ﻩ｝
return OK;
}
Status LｉｓtInverse＿L（ＬinkLｉst ＆L)
｛
／/思路：令指针p指向首元结点,头结点断开，{将p所指结点插入到表头后，p后移，至p空}
LNode *p，＊ｑ；
p=L->ｎｅxt;
Ｌ－>nｅxt=ＮULＬ;
ｗhiｌe（p!=ＮULL)
｛
q=p-〉ｎexｔ； ／／令ｑ指向p得后继结点,以便以后p后移接下来两句将p所指向节点插入到头结点后
p—>next=L-＞nｅxt；
Ｌ—>nexｔ=ｐ;
ｐ＝q;//q后移
}
reｔurn OK;
}
有序顺序表插入
Sｔatｕｓ LisｔInsｅrt_SortedSｑ(SqＬist ＆L，ＥlemType ｅ）
｛//在非降顺序表L中插入元素e，使得L中各元素仍然非降。注意插入位置据ｅ求得
//思路:从最后一个元素开始,只要它比待插入元素大就后移.条件不成立时退出循环，将e插入当前位置后即可。顺序表插入操作莫忘表满得处理。只要就是顺序表得插入操作就需要判断就是否表满,对于链表则无此要求
iｆ（Ｌ、ｌeｎgth>=L、lｉstsizｅ）
｛//表满,增加存储容量
EｌemTyｐe ＊ｎewbase=(ElｅmＴｙpe *）
reallｏc(Ｌ、elem,(Ｌ、lｉstｓｉｚe+LIＳTINCREMENT）
＊sｉzｅof（ElemＴyｐｅ））;
ﻩ ﻩif（！newbａse) exit（OVERFＬOW）；
L、eleｍ=ｎeｗbaｓe； L、lisｔｓize＋=LISＴIＮCREMENT；
ﻩ}
/／下面从最后一个元素开始,只要大于e就后移，最后插入当前位置后
ｐ=L、eleｍ＋Ｌ、lengtｈ-１;
ｗhile(ｐ〉＝L、ｅｌem＆＆＊p＞e)｛＊(p＋1）=＊p；－—p;｝
*(p+1）=e;
++L、length; //表长加1
return OＫ;
}
5. 循环链表、双向链表、双向循环链表得特点与基本操作.主要就是插入删除得相关指针操作。
／/－－－线性表得双向（循环）链表存储结构-－—
typedｅf ｓtrｕｃｔ ＤuLNodｅ
｛
ＥｌｅmType data;
sｔrｕct DuLNodｅ ＊ｐｒiｏr；
struct ＤuＬNｏdｅ ＊next;
}DｕＬＮode,＊DｕLｉｎｋList;
Sｔatuｓ LｉstIｎsｅrｔ_DuＬ（DuLinkＬist ＆Ｌ,ｉnt ｉ，EleｍTyｐe ＆ｅ)
｛／／在带头结点得双向链表L得第i个位置插入e，1≤i≤表长+1
ﻩＤｕＬＮoｄe *p=Ｌ； iｎt j=0；
wｈile(j〈i—1&＆p）{p＝ｐ—>next;+＋j;｝
ﻩif(!p） rｅturｎ ERROR；
ﻩs=（DuLNode *）malloｃ(sizeoｆ(ＤuLNoｄｅ))；
ﻩif（！s）exit(OVＥRFLOW）；
ﻩs—〉data＝e；
s-〉prior＝ｐ；
s—〉ｎext=p—>next； //记:注意分析指针改变
p—＞next-〉pｒiｏr=s;
p－〉next=s; /／次序对结果得影响
ﻩreturn OＫ;
｝
另外瞧下多项式得相关课件，老师复习提纲上有写这方面得代码。
第三章 栈与队列
1. 栈（Sｔａｃk)就是定义在线性结构上得抽象数据类型，其操作类似线性表操作，但元素得插入、删除与访问都必须在表得一端进行,为形象起见,称允许操作端为栈顶(Ｔop），另一端为栈底（baｓe)，注意Top指向待插入位置.特性:Last Iｎ Ｆｉrst Out后进先出//总就是访问最近插入得一个//按插入顺序倒着访问。
#definｅ STACＫ_ＩNIＴ_SIZE 100
＃ｄefiｎe ＳTAＣＫINCREMEＮT 10
typｅdeｆ ?？ SEｌeｍType；／/栈元素类型
typedef ｓｔrｕct｛
SElｅmType ＊base; //栈底指针
ＳＥlemＴｙｐe *toｐ； //栈顶指针
int stacksizｅ； ／/栈容量
ﻩ}SqStack
Stａtus InｉtStａcｋ(SqStaｃk &S）
{//构造空栈Ｓ
Ｓ、ｂaｓe=（ＳElｅmType*）
malｌoc(STAＣK_ＩＮＩT_SIZE＊ｓizeｏf(SElｅmType）)；
ｉf（！Ｓ、base)exｉｔ（OVEＲFＬOW）； //存储分配失败
ﻩ S、top=S、base; //空栈
Ｓ、stacksize=STACK_INIT_SＩZE;
ﻩﻩｒetｕrｎ(ＯK）；
｝/／ＩｎｉｔStack 复杂度”O（1）”
Stａtｕs DestroyStacｋ（SｑStａck &Ｓ）
{／/销毁栈S
ｆree（S、ｂａse)；
S、ｂaｓｅ=NULL；
Ｓ、top=NULＬ;
S、sｔacｋsiｚe＝0;
returｎ OK；
} ／／复杂度Ｏ（1）
Statuｓ CleａrStａcｋ(SqStack ＆Ｓ)
｛／／置Ｓ为空栈
S、top=S、base; rｅtｕrｎ OK;
} //复杂度O(1)
Ｓtａtus Puｓｈ（SqStａck &S， SElemType e）
{／／插入e为栈顶元素
ﻩｉf(S、tｏｐ—S、base==S、staｃｋsizｅ）//判断栈满
{//栈满则应重新分配空间
ﻩＳ、ｂaｓｅ=（SElemType ＊）rｅａｌｌｏｃ（S、baｓe，
(S、sｔａcksize+ＳＴＡCＫINCＲEMＥNT)＊ｓｉzeof(ＳEleｍTｙpe)）;
ﻩif（！S、baｓｅ)ﻩeｘit(OVＥＲFＬOW）；
Ｓ、top=（S、base+S、stacksize）;/／使得S、top重新指向栈顶，因rｅalloc
S、ｓtacksiｚｅ＋=STAＣKINCＲEＭENT；
｝
ﻩ＊Ｓ、tｏp ＋+=e； //top指向待插入位置
ﻩreturｎ(OK）；
｝//Pusｈ ，复杂度O(1)
Sｔatuｓ Pop(SqSｔack ＆S,SElemTｙｐe ＆e)
｛//若栈不空则栈顶元素出栈并用e带回其值
ｉf(Ｓ、toｐ==S、ｂasｅ） reｔｕrｎ ERROＲ；//判断栈空
e=＊(—-S、tｏp)； //栈顶元素为＊（S、toｐ—１)
return OK;
｝ ／/复杂度O(１）
Statｕs SｔaｃkEｍpｔy（SqStaｃｋ S)
{
if(S、ｔop＝=S、base)ﻩｒetuｒn TRUE；
ｅlse ﻩretｕｒｎ FALSＥ;
}
int SｔaｃkLenｇth （SqＳtack S）｛ ｒetuｒn (Ｓ、top—S、ｂasｅ）； ｝
Statuｓ GｅtTop（ＳｑStacｋ S，ＳEleｍType ＆e）
｛
ｉｆ（S、top=＝S、baｓe) retuｒn EＲＲOR;
e＝＊(S、toｐ-1)； ／/注意top指向待插入位置
ｒeturn OK；
}
栈得遍历一直没用到，可以自己找找课件瞧。
2. 队列类似线性表与栈，也就是定义在线性结构上得ADT,与线性表与栈得区别在于,元素得插入与删除分别在表得两端进行。类似日常生活中排队,允许插入得一端为队尾(rear),允许删除端称队头(fｒｏｎt）。特性：First In First Ｏuｔ先进先出,如操作系统中得作业队列与打印任务队列、日常生活中各类排队业务等均可用队列模拟。
＃ｄｅfine ＊＊＊ QＥｌeｍＴｙpe
typedｅf sｔruｃt ＱNｏｄe ｛
QEｌemType ｄata;
stｒｕct ＱNｏdｅ *ｎeｘｔ;
｝ QNodｅ， ＊QueｕeＰtｒ;
tｙpｅdef strｕct {
ＱuｅｕePｔr froｎt；//队头指针
ＱueｕePtr ｒeａｒ； /／队尾指针
} LinkＱuｅｕe；/／ 链队列
Statｕｓ InitＱuｅｕｅ （LinｋQueｕe &Q）
{／/ 构造一个空队列Q
Ｑ、ｆront=Ｑ、ｒear=（QｕeｕｅPtr）mａｌｌoc(sｉzeof(QNode）);
if （!Q、ｆront） ﻩｅxit （OVERFLOW);
Q、front—〉next ＝ NULL； //莫忘!！
ｒeｔurn OK；
}／/时间复杂度Ｏ(1）
Statｕｓ ＤestroｙＱuｅue （ＬｉｎkＱueｕe ＆Q）
｛//销毁队列Q,此处不同于教材,先清空元素结点,后释放头结点
ﻩQueuePtr p=Q、frｏｎt-〉nｅxt；
ﻩwhｉle(p）
｛//依次释放首元素至最后一个元素
Ｑ、froｎt-〉next=p—>nｅxt;
ｆｒee(p）；
p=Q、front－＞ｎexｔ；
}
free(Q、front);
Q、fｒonｔ=NUＬＬ；Q、rear=ＮULL；
ｒetｕｒn OＫ;
}//去掉下划线部分为置空操作, 复杂度O（n）
Staｔus EｎＱueue (LｉnkQueue ＆Q, ＱEleｍＴype e）
｛// 插入元素ｅ为Ｑ得新得队尾元素
ＱueuｅＰtr ｐ；
p=(QuｅueＰtr)malloc（sizeof(QＮodｅ）);
ｉf (!p)ﻩｅｘit(ＯVERFLOW)；//存储分配失败
p—＞ｄata = e； p－>ｎext ＝ NULL；//莫忘!！
Q、reaｒ-〉neｘｔ = p； Q、rear ＝ p;
returｎ ＯＫ;
}//复杂度Ｏ(1）
Sｔatus DｅQｕeｕe (LiｎｋQueuｅ &Ｑ， QEｌemＴype ＆ｅ)
｛// 若队列不空,则删除Q得队头元素，用 e 返回其“值”
if （Q、ｆrｏｎt ==Ｑ、ｒeaｒ） ﻩｒetｕrn ERRＯR；/／空队列
ＱｕeuePtr ｐ= Q、front－＞ｎｅxt; e = p—＞daｔa;
Q、front->neｘt = ｐ->next;
if(Q、ｒeａｒ =＝ p) Q、rｅａr=Q、ｆroｎt;／/只1个结点时改尾指针
ｆｒeｅ （p)；
rｅtｕrn OK；
｝//复杂度O（1）
3. 循环队列
#ｄefine ＭAＸQSIＺＥ 10０ //最大队列长度
typedef strｕct ｛
QElemＴype ＊base；// 动态分配存储空间
ｉnt front； ／/ 头指针，队列不空则指向队列头元素
iｎt reａr; ／/ 尾指针， 指向待插入元素位置
} SqＱuｅue；
Status IniｔQueue （SqQuｅue ＆Q)
｛// 构造一个空队列Q
Q、base=(ＱＥlemTyｐe*)mallｏc（MＡXＱSIZE＊ｓizeoｆ
（QElｅmＴypｅ))；
if (!Q、basｅ） ｅxit （OＶERＦＬOW）; // 存储分配失败
Q、frｏｎt ＝ Ｑ、rear = ０;
ｒeｔｕrn OK;
}//复杂度Ｏ(1)
Stａtus DeｓtｒoｙＱｕｅｕe(SqQueue ＆Q）
｛/／ 销毁队列Q
free(Q、bａse）；
Q、frｏnt = Q、rｅar = 0；
returｎ OK;
｝／/时间复杂度O（1），比链队列快
Status CｌeaｒＱｕeue(SqＱｕｅuｅ ＆Q)
｛// 将队列Q置空
Q、ｆroｎt=Q、rｅar=０；／/只要想等即可
ﻩreｔｕrｎ OK;
}//复杂度O（１)比链队列快
Statｕs ＥnＱueue （SqQuｅue ＆Q, ＱElemＴype e)
｛// 插入元素e为Q得新得队尾元素,无法插入（已满）则返回ERROR
ﻩif（（Q、ｒｅar＋１）％MAXＱＳIZE==Ｑ、front）ﻩretuｒn ERROR；
／／判断循环队列满得条件
ﻩQ、base[Q、rear］ ＝ e；
ﻩＱ、reaｒ ＝ (Q、reａr+1) % ＭAXQSＩＺE； /／加便可能越界，故取余
reｔurn ＯK;
}//时间复杂度O(1）
Sｔatuｓ DｅQｕｅue （ＳｑＱｕeｕｅ ＆Q, EｌｅmTyｐe &e）
{ /／队列不空则删除队头元素, 用e带回其值并返OK；否则返ERROR
if (Ｑ、rｅar＝=Q、ｆrｏnt） return ＥRＲOR；//判断循环队列空
ｅ = Q、base［Q、ｆｒoｎｔ］；
Q、fｒｏnｔ = （Q、fｒｏnｔ＋1) % ＭＡXＱSIＺE；
／/加就可能越界,故取余
return ＯK;
} //时间复杂度Ｏ(1）
inｔ ＱueｕeLengｔh（SｑQueuｅ Q）
{ //返回队长
reｔｕrn (Q、rｅａｒ—Ｑ、ｆｒont+MＡXQSIZＥ）%MAXQSIZE；
/／减可能为负
｝/／时间复杂度Ｏ(1)，比链队列快，可修改链队列定义
Sｔａtus QueueEmpty（SqQueuｅ Q)
｛ ／/判断队列空
if （Ｑ、reaｒ＝＝Q、fｒont) rｅturn TRUE;
elｓe reｔurn ＦAＬSE;
}//O(１)
Staｔus GetＨeａｄ（SqＱuｅｕe Q，QElemＴyｐe ＆ｅ）
{
if （Q、rear==Q、froｎt） ﻩｒetuｒｎ ＥRROR；
ｅ=Ｑ、ｂａｓe［Ｑ、froｎｔ];
retｕrｎ ＯＫ;
}// O（1）若要修改对头元素得值可新设SｅtＨead（&Q,e）
4. 证明:若借助栈由输入序列12……n得到得输出序列为p1p2……pｎ（它就是输入序列得一个排列）,则在输出序列中不可能出现这样得情形:存在i＜j＜k使pｊ＜ｐk<ｐi。思路:假设pj<ｐk＜pi往证i＜ｊ<k不成立.进一步假设j＜k成立,则pj在“pk及ｐk以后得元素”入栈前已经出栈，故“pk及pk以后得元素”必然后于ｐj出现,而pi就就是这样得一个元素，其出现次序为i，故i＞ｊ，从而i〈j＜k不成立。
第四章 串
第五章 数组与广义表
1. 三元组顺序表存储结构:
#defｉnｅ MＡXＳIＺＥ 12500
typedｅf struｃt {
inｔ i， j； //非零元得下标
EｌｅmＴｙｐe e; ／/非零元得值
｝ Tripｌe； /／ 三元组类型
tyｐedｅf stｒuct{
Trｉpｌｅ data［ＭAXSＩZＥ + １];/／data[０]不用
iｎｔ mu,ｎu，tu；//行列数与非零元个数
} TSMatｒｉx； // 稀疏矩阵类型
2. 初始化一个“空"得稀疏矩阵，按照目标矩阵中得出现次序对原矩阵中得元素逐个转置，列号cｏl 从1变到ｎ，每次从头至尾扫描M、ｄaｔａ,对列标等于coｌ得三元组,将其行标、列标互换后依次放入T、data［ ］中。
3. 稀疏矩阵得十字链表表示:
typedef Ｓtruct｛
OLink *rheａd,*cheａd； /／行头指针与列头指针数组
int mｕ, ｎｕ， tu
｝CrosｓＬisｔ
4. 上下三角矩阵存到一位数组得下标转换。相关稀疏矩阵得程序可以瞧瞧课件。
第六章 树与二叉树
1. 树得结构特点：树就是一个层次结构,“有且仅有一个根结点无前驱（第一层）;有一或多个叶结点无后继;其余结点有唯一前驱与若干后继”.递归定义:树由根结点（唯一)及该根结点得若干(零或多个）“子树”组成。不含任何结点也就是树，称为空树
2. 树得相关术语如结点，度，见P１２0。
（1） 结点（nｏdｅ)：一个数据元素及其若干指向其子树得分支。
（2） 结点得度（degree） 、树得度：结点所拥有得子树得棵数称为结点得度。树中结点度得最大值称为树得度。
（3） 叶子(leｆt)结点、非叶子结点:树中度为0得结点称为叶子结点（或终端结点)。相对应地，度不为0得结点称为非叶子结点(或非终端结点或分支结点）。除根结点外，分支结点又称为内部结点。
（4） 孩子结点、双亲结点、兄弟结点：一个结点得子树得根称为该结点得孩子结点(cｈild）或子结点；相应地，该结点就是其孩子结点得双亲结点（ｐａreｎt）或父结点。
3. 性质1： 在二叉树得第i层上最多有2ｉ-１个结点（i≥１）
性质2： 深度为K得二叉树最多有２K－１个结点（K≥1）
性质3: 对于任意一棵二叉树ＢT,如果度为０得结点个数为n0，度为２得结点个数为ｎ2,则n0＝ｎ２+1。
证： 二叉树上结点总数 ｎ = n0 + n1 + n２.二叉树上边得总数 e = n1+２n2.根结点外每个结点都有且仅有一条边（分支)"进入”,故e = n-1。由此n-1= ｎ0 + ｎ1 ＋ n2 － 1 ，进而 n０ = n２ ＋ １ 。
性质4:含n个结点得完全二叉树深度为 ëlｏg２nû +1 。
性质5：若对含 ｎ 个结点得完全二叉树从上到下且从左至右进行 1 至 ｎ 得编号,则对完全二叉树中编号为 i 得结点：
（１) 若 i＝１，则该结点就是二叉树得根,无双亲,否则,编号为 ëｉ/2û 得结点为其双亲结点；
(2） 若 2i〉n，则该结点无左孩子，否则,编号为 2i 得结点为其左孩子结点；
（３) 若 2i＋1>n,则该结点无右孩子,否则，编号为2i+1 得结点为其右孩子结点.
4. 含n个结点得树中，只有度为k得分支结点与度为0得叶子结点，试求该树含有得叶子结点数
提示：n0+nｋ=n； e=knk＝k(n-n０)=n－１ﻩ故:n０＝(nk－ｎ+１）/ｋ
5. 二叉树就是度不大于２得有序树（每个结点最多两棵子树,子树有左右之分)。
6. 满二叉树：设深度为k，含2k－1个结点得二叉树。结点数达最大。
7. 完全二叉树:设树中含ｎ个结点， 它们与满二叉树中编号为1至ｎ得结点位置上一一对应（编号规则为由上到下,从左到右）。相比满二叉树仅少“最后得”若干个,不能少中间得。完全二叉树特点：(1)叶子结点出现在最后2层或多或1层。（２）对于任意结点，若其右分支下得子孙得最大层次为L，则左分支下得子孙得最大层次为Ｌ或L+１。
8. 二叉树顺序存储：将二叉树映射到完全二叉树上,不存在得结点以空标记，之后用地址连续得存储单元（一维数组）依次自上而下、自左而右存储完全二叉树上得各元素、（将一般二叉树以完全二叉树形式存储)，最坏情况下k个结点需2k—1个单元。但适合完全二叉树得存储，操作简单方便.
9. 二叉树链表存储：二叉链表包含内容,左孩子及右孩子得指针。三叉链表多了一个指向双亲结点得指针。
typｅdeｆ struct BiTＮode ｛
TElｅｍTｙpe daｔa；
struct BiTNode ＊ｌchild， ＊rｃhiｌd；
｝ BiＴＮodｅ, ＊ＢiTｒee；
ＢiTreｅ T;
ｔypeｄef stｒuct TriTNｏｄe ｛
strｕｃt TrｉＴNｏde *ｐaｒeｎt；
TElｅmＴｙpe ｄａta；
sｔｒuct TrｉTNode *lcｈilｄ， ＊rｃhild;
} TrｉＴＮoｄｅ， ＊TrｉＴrｅ
10. 先(根）序遍历:树非空则访问根结点,后递归地先序遍历其左子树；再递归地先序遍历其右子树；空则无操作。
中（根）序遍历：树非空则递归地中序遍历根左子树;后访问根结点，再递归地中序遍历右子树;空则无操作.
后(根）序遍历:树非空则递归地后序遍历根右子树；后递归地后序遍历右子树,再访问根结点;空则无操作
层次遍历:由上到下，由左到右,不宜递归
tyｐeｄef struct BiTNode ｛
TElemTｙpｅ dａta；
stｒuct BiTＮode *lchilｄ, *rchｉld;
｝ BiTＮode， *ＢiTrｅe;
BｉTｒee T；／/
tyｐedef int TElemTｙpｅ；
Status CreaｔeBiTree(BｉTｒee ＆Ｔ)
｛//递归创建二叉树
TEleｍTyｐe e; sｃａnｆ(＂%ｄ＂,＆e）；
if（e=＝0）ﻩＴ=NUＬL；
elｓe
｛
ﻩ Ｔ=(BｉＴreｅ)mａlloc(sizeof（BｉTＮodｅ)）;
if(！T）ﻩｅｘit(OVERFLＯＷ）;
T－>data=e；
CｒeａｔｅＢiTreｅ(T->lchiｌd);
ﻩ CrｅateＢiTree（Ｔ－＞rcｈilｄ)；
}
ｒetｕｒn OK;
｝／/若元素为字符型则输入时不可随意加空格
Ｓtatus DｅstｒoyBiTreｅ(ＢiTree ＆T)
｛/／二叉链表得后序递归销毁
ｉf(!T） ｒeturｎ OＫ;
ｅlse
｛
ﻩ DesｔｒｏyBiTree(T—＞lchild
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
