数据结构常用算法实现printWord文档格式.docx
《数据结构常用算法实现printWord文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构常用算法实现printWord文档格式.docx（44页珍藏版）》请在冰点文库上搜索。
29ﻩteｍp= l。
lｉstａｒray［ｐos]；
30ﻩﻩfoｒ（i ＝pos；
i<
ｌ。
ｌｅngｔｈ-1；
i+＋）
３1ﻩﻩl。
ｌｉsｔaｒrａy[i]=ｌ。
ｌistarraｙ[ｉ+1]；
３2l.lｅngtｈ--;
３３ﻩretｕｒｎtemp;
｝
３5ﻩｉntlength（）
｛
３7ﻩreｔｕrnl.leｎｇth;
｝
3９iｎｔｆiｎd（ELＥMTYＰＥitｅm）
４0{iｎti；
４２foｒ（ｉ=0；
leｎgｔｈ;
i++）
43ﻩﻩiｆ（ｌ.lｉstarｒay[i］ ＝=itｅm）
44ﻩrｅｔurｎ i；
45ﻩﻩrｅturn -1；
}
47ﻩvoｉdｐrint（）
4８ﻩ｛iｎti;
5０ﻩｆor（i=0；
i〈ｌ．lｅngｔｈ;
i＋+）
51ﻩﻩpｒintf（”％d”，l．lｉｓtarrａｙ［i］）；
５2pｒinｔf（”\n”）；
５4vｏidmain（）
5５｛clrscｒ（）;
57ﻩｃlear（）；
５８appeｎd（1０）；
ﻩ／＊Lis 10*／
5９ﻩﻩａｐpend（20）;
／*Ｌis（10，20）＊/
６0ａppend（30）；
/*Lｉs（10，2０,30）*/
6１ﻩprinｔ（）;
62insert（2，1５）；
/＊Liｓ（10，20，1５，30）＊/
63ﻩｐrint（）;
6４ﻩprｉntf（”\n%d”,find（1０0））;
65ﻩﻩpriｎtf（”\n%d\n”，delete（３））;
/*Lｉs（10,２0，15）*/
6６ pｒiｎt（）;
线性表的链式表示
程序2＿2。
c提供了链式存储结构下线性表的实现。
第３行到第8行包含了线性表中结点的说明,其中eleｍｅｎt表示数据域，存放该结点的数据信息,ｎext为指针域，指明该结点的唯一后继结点在内存中的存放地址,或是在该结点序列中所在的物理位置.线性链表由head和ｔaｉl表示。
接下来从第9行到第７6行线性表运算函数的定义。
第9行到第1４行初始化单链表。
hｅaｄ指针与tail指针指向表头结点。
在单链表的最后一个结点后插入一个结点只要将单链表尾指针tａｉl指向新插入结点,新插入结点成为最后一个结点即可.第15行到第20行函数ａppend实现追加一个新结点到单链表的最后，新结点的元素值为itｅm。
malｌoc是C语言提供的标准函数，其功能是申请存储空间。
设p是指向单链表中一个结点的指针，在p指向的结点后面插入一个结点包括三个步骤。
首先,要创建一个新的结点,并且赋给它一个新的值。
其次,新结点的neｘt指向指针p指向结点的后继结点。
第三,指针ｐ指向的结点的ｎext要指向新插入的结点。
ﻩ第21行到第38行函数inｓert实现在单链表的第i个结点前面插入一个新结点。
新结点的元素值为itｅｍ，ｓ为指向新结点的指针。
算法在实现时，首先查找新结点插入位置，然后根据上面所述修改相应指针。
从单链表删去一个结点只需将被删结点的前趋结点的ｎext域指向被删结点的后继结点即可。
但必须注意,被删结点占据的内存空间应该返回给存储器.因此可设一个临时指针指向要删去的结点，而后调用Ｃ语言提供的标准过程fｒee将被删去的结点占据的内存空间返回给存储器。
第3９行到第5７行的函数deletｅ实现删除结点运算。
第5８行到第6５求单链表中所含结点的个数。
为求单链表的结点个数,我们必须从单链表表头开始，沿着每个结点的链指针,依次向后访问并计数，直到最后一个结点位置。
程序2_2。
c
１ﻩ＃iｎclude〈alloc.h〉
２typeｄeｆ inｔEＬEMＴYＰE；
3sｔrｕctlist｛
4ELＥMTYPE ｅlｅment;
５ﻩstruｃtlisｔ*nｅｘｔ；
6｝；
7ﻩsｔrｕctlｉst *heaｄ；
８ﻩstrｕctlisｔ*tail；
9ﻩvoｉdiｎｉt（）
10ﻩ｛
11ﻩﻩhead =ｍaｌlｏc（siｚｅｏf（ｓｔruｃtlｉsｔ））;
12ﻩheａd—〉ｎext=NＵLＬ;
13ﻩｔａil=hｅａd；
１4｝
15void aｐpend（ＥＬEMTYPＥiｔem）
1６ﻩ｛
１7ﻩtail=ｔail—〉nｅｘｔ=（sｔrｕctlisｔ *）malloc（siｚeoｆ（structlｉst））；
1８ﻩtail－〉elｅmenｔ =item；
19ﻩtail—〉next =NULL;
20｝
21intinseｒt（ｉnt pos，ＥLEMTＹPＥ iteｍ）
２２ﻩ｛
23ﻩｓtrucｔlｉst＊ｐ,*s；
24ﻩintj;
25ﻩﻩs = （sｔruｃtｌｉst*）mａｌloc（ｓizｅoｆ（struct lisｔ））;
２６ﻩﻩs－>
element=ｉteｍ；
27ﻩｐ =ｈｅａd;
２8ﻩｊ ＝ 1;
29ﻩｗｈile（（p！
=NUＬＬ）&
＆（j〈pos））｛
3０ﻩﻩp=p－>
nｅxt；
31ﻩj＋+;
32ﻩ｝
３３ﻩﻩiｆ（（!
ｐ）||（j〉pｏｓ））retｕｒn0;
３4ﻩs-＞ｎeｘt=p->
ｎeｘt；
35p->
nｅxt=s;
３6ﻩﻩif（tａil==p）ｔail＝s；
37ｒetuｒｎ 1；
38｝
３9ELEMＴＹPE deｌetｅ（intpos）
４0ﻩ｛
41ﻩｓtrｕctlist＊p,＊ｑ；
4２ﻩELEMＴYPＥ teｍp;
43ﻩint j；
44ﻩｑ＝p；
ｐ=heaｄ—>
next；
４5ﻩﻩj=1;
４6ﻩｗhile（（p！
=NUＬL）&
&
（j＜pｏｓ）） {
47q＝p;
p=p—＞nｅｘt;
48ﻩﻩj＋+;
4９｝
50ﻩﻩif（（!
p）|｜（j>
pos））
51ﻩreturn 0
52q—>
ｎｅxt ＝ｐ－>
53ﻩtｅmｐ=ｐ—＞element；
54ﻩiｆ（ｔａｉl＝=p）taｉｌ=q;
５5ﻩﻩｆrｅｅ（ｐ）;
5６retuｒn ｔemp;
５7｝
58iｎtlengｔh（）
59ﻩ｛
60stｒuct list＊ｐ；
61ﻩint cnt ＝ 0;
６2ﻩｆor （p＝head-〉nｅｘt；
p!
= NＵLＬ;
ｐ ＝p-＞nexｔ）
63ﻩﻩcnt＋+;
6４ﻩﻩreｔurｎcnt;
65｝
6６ﻩint find（ＥLEMTYＰＥiteｍ）
67{
6８ﻩｓtrucｔlｉst＊p=head—〉next;
69ﻩwhile（ｐ！
=ＮULL）｛
7０ﻩﻩif（ｐ-＞eｌement=＝item）
71ﻩrｅtuｒｎ1；
７2ﻩﻩelse
７3ﻩﻩp=p-〉nexｔ;
74ﻩﻩ}
75ﻩretｕｒn０;
76}
77ﻩvｏidpｒｉnt（）
78ﻩ{
7９ﻩstructlｉsｔ *ｐ；
8０ｐｒｉntf（”\n"
）；
8１ﻩfｏr（p =ｈead-〉nｅxt;
ｐ!
＝ＮULL；
p＝p-＞neｘｔ）
82ﻩprintｆ（”％d "
p—〉eｌemeｎt）；
83ﻩ}
84void ｍａin（）
8５{
86ﻩclrscｒ（）;
87ｉｎit（）；
88ﻩapｐeｎｄ（10）;
/*liｓtｉｓ（１0）*/
８9ﻩappend（２0）;
／＊ｌｉstiｓ（1０，２0）*/
90apｐｅｎd（30）;
／*ｌistiｓ （1０,20，30） ＊／
91ﻩﻩａppｅｎｄ（４0）;
/＊ｌｉstis （10,20,３0,40）＊/
92insert（3,3５）;
ﻩ/＊list is（10,２０,３0，3５,40）＊/
93ﻩｐrint（）;
９4ﻩﻩprintｆ（"
\n％d＼ｎ"
，ｄelｅte（4））；
/*list is（10,20，30，35）*／
95ﻩﻩprinｔ（）;
96｝
栈
程序２_3.ｃ是栈数据结构的实现，第3行到第6行包含栈类型的说明，ｔｏp被定义为表示栈中最上面那个元素的位置.
push（第13行到第17行）和pop（第18行到第２２行）只是从tｏp指示的数组中的位置插入和删去一个元素,因为ｔop表示栈顶元素的位置,所以push首先把一个值插入到栈顶位置，然后把top加1。
同样，ｐｏｐ首先把tｏp减1，然后删去栈顶元素。
函数toｐVａlue（第23行到２7行）只是将栈顶元素返回。
如果栈中没有元素,函数ｉsEmpｔy（第28行到第31行）返回1，否则返回0。
程序2_3.c
＃inclｕde <
aｓｓeｒｔ.h〉
＃includｅ＜stdio.h>
#ｄefine ＭAXSＩZE100
tｙpｅdeｆintELEMTYPＥ；
strucｔstack{
ﻩＥLEMＴYPElｉｓtarｒay［MAXSIＺE]；
ﻩinｔtoｐ;
｝；
struct sｔａｃｋｓ；
vｏidinｉt（）
s．ｔop=0;
}
voidpｕｓh（ELEMTYPEitｅm）
assert（s。
top＜MＡXSIZＥ）；
s.liｓtaｒｒay［s。
top++] =iｔｅm；
EＬＥMTＹPEｐop（）
{
ﻩintisEmpｔy（）；
asｓert（！
ｉｓEｍptｙ（））；
returns.lｉstarray［—-s.top]；
ELEMTYPE ｔｏpVａｌue（）
ﻩｉnｔisＥmpty（）；
ａsseｒｔ（!
isＥmpty（））；
retuｒn ｓ.listarraｙ[ｓ。
top－1］；
iｎtisEmpｔｙ（）
reｔurns.ｔｏｐ＝=0；
vｏiｄmaiｎ（）
init（）;
push（10）；
/＊ｓis（10） ＊/
ﻩpuｓh（20）;
／＊sｉs （20,10）*/
prｉntf（"
%d"
，topValｕe（））;
/＊rｅturntｏpeｌement 20*/
ｐｒintf（"
\n＂）；
priｎtｆ（＂％d"
，pop（））；
ﻩ/＊s is（10） */
程序2_４．c给出了链式栈表示和各种运算的算法。
其中toｐ是指向链式栈第一个结点（栈顶）的指针。
进栈操作（第13行到第21行）首先申请一个新结点，并初始化该结点,然后修改新产生的结点的neｘｔ域指向栈顶，并设置toｐ指向新的链表结点。
第22行到第3２行是出栈操作.变量ｔemp用来存储栈顶结点的值，ｌtｅmp用于在删去栈顶结点时保持与栈的链接，它指向当前栈顶链接到的结点。
此时把原来的栈顶结点释放回内存,恢复toｐ等于lｔeｍp.也就是指向原来栈顶链接的结点,原来栈顶的值ｔemp作为ｐop函数的返回值.
程序2_4.c
＃ｉncluｄe<
maｌlｏc。
ｈ＞
＃inclｕｄｅ〈stdio．h>
ﻩ＃ｉｎｃlｕde〈asseｒt．h>
ﻩtypedef inｔELEMTＹPE；
ﻩstrｕｃtnode｛
ﻩﻩEＬEMTＹPEｅleｍ；
stｒuct nｏde＊nexｔ；
ﻩ｝;
ﻩｓtrucｔnｏdｅ＊ｔｏｐ；
voiｄiniｔ（）
｛
ﻩtop ＝ＮULL;
ﻩ｝
ﻩvｏiｄpush（ELEMTYPＥitem）
stｒuctnodｅ*p；
ﻩｉｆ（（p=（ｓtructnode＊）malｌoc（sizeｏf（sｔructnodｅ）））！
=NULL）｛
ﻩﻩp—＞ｅlem= iｔeｍ；
ﻩﻩp—>
next ＝tｏｐ；
ﻩﻩﻩｔop=p；
ﻩ｝
ﻩ}
ﻩELEＭTYPEpop（）
ﻩ{
ﻩﻩｉnｔﻩｉsEmpty（）；
ﻩﻩＥLＥMＴYＰE tｅmp；
sｔｒuctnｏdｅ＊lｔemp;
asｓert（！
isEｍpｔy（））；
ﻩtemp＝top—〉eｌem；
ﻩﻩltemp=tｏp—〉ｎｅｘt;
ﻩﻩfree（toｐ）;
ﻩﻩtｏp=ｌteｍp;
ﻩrｅturnｔeｍp;
}
ELEMＴＹPEtoｐVａlue（）
{
ﻩﻩintisEmｐty（）；
ａsｓeｒt（!
iｓＥｍpｔｙ（））;
ﻩreturntop—〉elｅm;
iｎtisEmptｙ（）
ﻩｒeturntop==NＵLL；
ｖoｉdｍain（）
inｉt（）；
ﻩｐush（1０）;
/＊s is（10） */
ﻩpush（20）;
/*s ｉs （２０，1０）*／
ﻩﻩpush（３0）；
/＊ ｓis（3０,20,1０） ＊／
ｐriｎｔf（"
%d\n"
toｐＶａｌue（））;
ﻩprintf（"
%d\n”,ｐop（））；
/*sis（20，1０）＊/
队列
在程序2_５.c中，q表示循环队列（第3行到第9行）,其队头与队尾指示变量分别为fｒont和rear。
队列中的元素类型为inｔ（第3行）.函数enｑueue（第１4行到第19行）执行队列的插入操作，参数item是插入队列的元素.当队列不满时,ｅnqueue首先移动队尾指针，然后将item置入rear所指位置。
函数dｅqueue（第20行到２５行）执行队列的删除操作,返回从队列中取出的元素。
函数fiｒstＶａlｕe（第26行到第30行）返回队列头元素。
程序2_5.c
＃ｉｎcｌｕde〈assert．h>
＃iｎclude<
stdio．h＞
＃ｄefiｎeMAXSＩZE１0０
typeｄｅｆiｎｔELＥMTYPE；
ｓtｒuctqueue{
ｉnｔfront;
ﻩｉｎｔ ｒｅaｒ；
ﻩＥLＥMＴYPEelem［MAXSIZＥ]；
}；
sｔruct queue q；
voiｄｉnit（）
ｑ．ｆroｎt =q．rear=0；
voiｄ ｅｎqueue（ELEMTＹPEiｔｅm）
assｅrｔ（（（q．ｒear+1） %MAXSIＺE） ！
=q.front）；
ﻩq．rear=（q。
rear+ 1） ％MAＸSIZE；
／＊incremｅｎtrear＊/
q。
ｅlem[q.rｅａｒ］＝iｔｅm;
ＥLEMTＹPＥdequeuｅ（）/＊dequeueｅleｍentｆro fｒｏｎｔ ofqｕeue＊/
ﻩｉntisＥmpty（）；
ﻩａsseｒt（！
isEｍpty（））；
ﻩ/＊ therｅ muｓtbeｓomethiｎgｔｏdeqｕeｕe *／
ﻩq．ｆroｎt =（q。
front＋1）％MAXSIＺＥ；
/*incｒemｅnｔ ｆrｏｎt＊/
ｒｅturｎq.elem[q。
front］；
/*rｅtuｒｎ vaｌue*/
ELＥMTYＰEfirstValue（）/＊getvalue offroｎｔ ｅlemenｔ＊/
ﻩ｛
ﻩintｉｓEmpty（）；
ａssert（！
iｓEmｐty（））；
ﻩreturnq．elｅm[（q.frｏnt+1）％ MAXSＩZE］;
ﻩint isＥmpｔy（）ﻩ/*TRUE ｉsqueueis emｐty*/
ﻩﻩreturn q.front =＝ｑ.ｒｅar;
ﻩvoid main（）
ﻩinｉt（）;
ﻩﻩeｎquｅue（１0）；
ﻩ/*ｑis（10）＊/
ﻩenqueue（20）;
ﻩ/*qiｓ（10，20）*/
ﻩﻩｅnquｅｕe（３0）;
/＊qis （10，２０，30）*/
ﻩprｉnｔf（"
%d\ｎ”，firstＶａlue（））;
ﻩ／*ｗｉlldisplay 10 ＊/
ﻩﻩｐriｎｔｆ（"
％ｄ\n”，dequeｕe（））；
ﻩ/＊ willｄｉspｌａ10*／
程序２＿6．c给出了链式队列的说明和函数的实现。
fｒont和rｅaｒ分别是指向队首和队尾元素的指针.链式队列的实现不需要表头结点，当队列为空时,指针ｆronｔ和reaｒ的值均为空（ＮＵLL）。
当在队列中插入一个结点时（第14行到27行），新结点链入rear所指结点的next域,并使rear指向新的结点。
如果在插入之前队列为空,则指针froｎt指向新插入的结点。
当从队列中删除一个结点时（第２8行到3７行）,要把fｒont所指结点的neｘt域的值赋给fｒｏnt,并且释放这个结点。
如果删除之后队列为空，则置指针rear为空（ＮULL）。
程序２_6。
ﻩ#include ＜maｌlｏc。
h〉
＃inclｕdｅ＜stｄｉo。
＃inclｕｄe<
ａssert.ｈ〉
typｅdefintELEMTＹＰE;
stｒuct nｏｄｅ｛
ﻩELEMTYPＥｅlem；
ﻩｓtｒuct nｏde*ｎｅxt;
}；
ﻩstructnode *fｒont;
stｒuｃｔｎoｄe*reａr;
ﻩｖoiｄiｎｉt（）
ﻩﻩrｅar=frｏnt＝NULＬ；
ﻩvｏｉd enqｕｅue（ELEＭTＹPEitｅｍ）
ｉf （rｅａr!
=NULL）{
ﻩｒear－>
nｅxt=（sｔｒuct ｎode *）mａllｏc（siｚeof（sｔrｕct nodｅ））；
rear—〉ｎｅxｔ—＞elem＝ iteｍ；
ﻩﻩreａr－>
next—>
nｅxｔ =ＮＵＬL;
ﻩrｅar =reａr—〉neｘt；
else｛
ﻩﻩﻩfｒｏｎt=ｒear=（strucｔｎｏde *）mａlｌｏc（sizeｏf（sｔｒuｃtｎode））;
ｆroｎt—>
eleｍ=iｔeｍ;
ﻩfronｔ-〉nexｔ ＝NUＬＬ；
ﻩ｝
ELEＭTＹPEdequeue（）
ﻩﻩｉnt ｉsEmptｙ（）;
ＥＬEMTYＰEtemp =ｆroｎt->
ｅlem；
ﻩｓｔruｃt node*ltｅmp=fronｔ;
ﻩassert（!
ﻩfronｔ=frｏnt—〉neｘt；
ﻩﻩfrｅe（lteｍp）；
ﻩif （ｆront=＝NULＬ）ｒear=NUＬL；
ﻩｒｅtuｒnｔemｐ；
ＥLEMＴYPEfirsｔＶaｌue（）
intiｓEmpty（）；
ﻩﻩassert（！
isEmpty（））；
rｅtuｒｎfrｏnｔ-＞elem；
ﻩintｉsＥmpty（）
reｔurnfroｎt==NULＬ；
ｖoid maiｎ（）
ﻩﻩｉｎｉt（）;
ｅnqueuｅ（10）；
ﻩﻩenqueue（20）;
ﻩenqueue（30）；
ﻩprｉｎｔｆ（”％ｄ＼n”，ｆirstValｕe（））;
ﻩpｒｉntf（"
%d\n＂，ｄequeue（））;
稀疏矩阵
程序3＿1.c是按照快速转置算法求矩阵的转置。
程序第2行给出稀疏矩阵ａ的三元组表表示.函数FastTranｓposｅ按照快速转置算法思想将稀疏矩阵a转置为稀疏矩阵b，b也表示为三元组表形式。
第11行到第13行计算矩阵a的每一列的非零元素个数。
第15行计算a中每一列第一个非零元素在ｂ中的起始位置.第16行第22行对a中的元素依此进行转置。
程序３＿1。
1#defineMAXCＯL１00
2ﻩiｎta[]［3］＝｛｛7，6，8｝,｛0，0，5}，｛0，3，2}，{0，5，8}，{１，１,6｝，
ﻩﻩ ｛1，2，9｝,{2，3，3},｛４，０,9}，
升级会员 