自数据结构课程设计双向链表Word文件下载.docx
《自数据结构课程设计双向链表Word文件下载.docx》由会员分享，可在线阅读，更多相关《自数据结构课程设计双向链表Word文件下载.docx（14页珍藏版）》请在冰点文库上搜索。
intdata;
ｓtruｃｔ ｄｕlnode*pｒｉｏr;
strucｔｄulｎode *neｘt;
}dｕlnode,＊duliｎｋlist;
●3.算法设计
3.１算法1：
创建双向链表
ｓtatusｃｒeａｔｅ＿dul（dulｉnklist＆ｌ） ／*利用尾插法建立头带头结点的双向链表 */
｛
l=（dulinklisｔ）mａlloc（sizeｏf（dｕｌｎode））;
/*生成头结点 */
l－>
prior＝NUＬＬ;
l->
next=NＵLL;
/* 头结点的指针域初始值为空*/
ｌ-＞data＝－1;
q=l;
／*尾指针初始指向头结点*/
ＦILＥ＊ｆp；
/＊定义文件指针的形式 */
ｉｆ（（fｐ=fopｅn（"
F:
\\test1.txｔ＂,"
r+＂））=＝NUＬL） /*打开文本文件 ＊/
{
pｒintf（"
cannotｏpenfiｌe!
\n"
）;
ｅxit（０）;
}
ﻩinｔn;
fscanｆ（fp,"
%d"
&
ｎ）;
ｆｏr（i=０；
i<
ｎ;
i＋＋）
｛
p =（ｄｕlinklｉｓｔ）ｍalloc（sｉzeof（dulｎｏde））;
ｆscanf（fp,"
%d＂,&
p->
ｄａta）;
/*在文件读取结点的数据＊/
p->
nexｔ=NUＬL；
／*新结点指针域为空*／
p->
prｉor=q；
q－>
next=ｐ;
/*尾结点指针域指向新结点 */
ｑ=p;
/*q指针后移，始终指向尾指针 *／
fclosｅ（fp）；
/＊关闭文本文件*/
}
3.２算法2:
双向链表的查找
sｔaduslocaｔｅelem_dｕl（dｕｌｉnkｌiｓtl,elｅmｔype e） ／* 查找双线链表中第一个值为e的结点位置＊/
{
p＝ｌ->
neｘt;
/* p指向第一个结点 */
ｊ＝1;
/*ｊ表示结点位置＊/
while（（p－>
data!
＝ｅ）＆&
ｐ）｛
ｐ=ｐ->
next；
＋+j;
} /*寻找第一个值为e的结点位置 */
if（!
p） return-1;
elｓe ｒｅｔｕrn1;
3.3算法3:
双向链表的插入
stａtus listiｎｓerｔ＿dul（duｌinklist&
l,int i,eleｍｔypｅe） /＊在双向链表l中的第i个位置之前插入新结点s*/
ｐ=l;
／＊p指向头结点 */
ｊ=0；
/* ｊ表示结点位置*/
whｉｌe（p&
&
（j<
ｉ－1））{
p=p->
next;
＋+ｊ;
｝ /＊寻找第i-1个结点位置＊/
if（!
p||j>
i-1） ｒetｕｒn ＥRROR；
/＊在l中确定插入位置,p=ＮULL或ｊ>
i-1时，即插入位置不合法 */
ｉf（!
（s=（duliｎｋlist）mａlloc（sｉｚeof（dulnodｅ）））） returnERＲOR;
/*动态生成新结点失败，则返回错误 */
ｓ－＞daｔa=e;
／*给新结点的数据域赋值＊/
ｓ－＞next=ｐ－>
nｅxｔ;
ｐ->
ｎext->
prior＝s;
s->
ｐrｉor=p;
p->
next＝s；
／*在双向链表中插入新结点时指针的变化＊/
retuｒn０;
3．4算法４:
双向链表的删除
staｔuslistdｅleｔｅ_dul（duliｎklist &
l，ｉnti，elemtyｐｅ &
e） ／* 在双向链表l中，删除第i个结点*/
ｐ=l->
/*p指向第一个结点*/
ｉntj＝1；
/*j表示结点位置＊／
while（p&
ｉ））{
p=p->
nexｔ；
++j;
} /＊寻找第i个结点 */
if（！
i）ｒeｔｕrnＥRROR;
/*在l中确定第ｉ个元素的位置指针p，ｐ＝NＵLL,即第ｉ个元素不存在＊/
e=p－>
ｄaｔa;
/＊把指针p的数据域的值赋给e*/
ｐ－>
prioｒ->
ｎexｔ=p－＞nexｔ;
ｐ－>
ｎeｘt-＞pｒioｒ＝p->
pｒior；
/＊在双向链表中删除结点时指针的变化*/
frｅe（ｐ）;
／*把结点ｐ删掉 */
retuｒn 0；
●４.程序清单
＃iｎclｕde<
ioｓｔreaｍ＞
#ｉncludｅ<
ｓｔｄiｏ.h＞
usingｎamespacｅｓtd;
typedefｓtructdｕlｎodｅ{
ｉntｄata；
/*数据域*／
sｔructdulnｏde*prioｒ;
/*指向前驱的指针域 */
stｒｕctｄｕlnｏde＊nｅxｔ;
/＊ 指向后继的指针域*/
}ｄulnｏｄe,*dｕｌｉnklist;
vｏidcreaｔe_dul（dulｉnkｌist&
ｌ）／*利用尾插法建立头带头结点的双向链表＊/
dulinklｉstp,q;
inti;
l＝（dulｉnklist）malloｃ（ｓizeof（dulnode））；
/* 生成头结点 */
l->
pｒior＝ＮUＬL；
ｌ->
next＝ＮUＬL;
/*头结点的指针域初始值为空*／
l->
dａta＝－１;
q=l；
/*尾指针初始指向头结点 */
FIＬE* fp;
／＊定义文件指针的形式*/
if（（fp=fopen（"
Ｈ:
＼\tesｔ1．txt"
，"
r+＂））＝=ＮＵLL）/*打开文本文件*/
{
priｎｔｆ（"
caｎnotopｅn filｅ!
＼n"
）；
exit（0）;
｝
int ｎ;
ﻩｆscaｎf（fp,＂%d"
for（i＝0;
n;
ﻩ p=（dulinklist）malｌoc（siｚeoｆ（dｕlnodｅ））;
ﻩ ｆscaｎf（fｐ,"
%d＂，＆p－>
data）;
/*在文件读取结点的数据*/
ﻩp->
ｎｅxt=ＮULL;
/*新结点指针域为空＊/
p->
prioｒ=q;
q－>
nｅxt＝ｐ;
/*尾结点指针域指向新结点*/
q=p;
／*q指针后移，始终指向尾指针 */
fclｏse（fp）;
/＊关闭文本文件 *／
dｕlｉｎklisｔlistinｓｅrｔ_ｄuｌ（dulinｋlｉst＆ｌ，ｉｎt i，intｅ） /*在双向链表l中的第i个位置之前插入新结点s ＊/
dulinkliｓｔp，s;
p=ｌ；
/*p指向头结点*／
inｔj=0;
／*j表示结点位置＊／
whiｌe（p&
＆（j<
ｉ-1））{
p=ｐ-＞next；
++j;
} ／*寻找第i-1个结点位置*/
ｉf（!
p｜|j>
i－1）ｒｅtｕrｎ NULL；
/*在l中确定插入位置，p=ＮUＬL或j>
ｉ-１时,即插入位置不合法*/
if（!
（s＝（duｌｉnｋliｓt）mａｌｌｏｃ（sizeoｆ（dulｎode））））rｅturnNULL;
/*动态生成新结点失败,则返回错误 ＊／
s－>
dａtａ=ｅ;
/*给新结点的数据域赋值*/
s->
next=p->
ｐ-＞nｅｘt-＞prioｒ=s;
s-＞priｏr=ｐ；
p－＞ｎexｔ=s;
/＊在双向链表中插入新结点时指针的变化 */
reｔｕrn0；
dulｉnｋｌｉstｌistdeｌｅte_ｄuｌ（dulinkｌist &
l,iｎｔi，iｎt＆e） /*在双向链表ｌ中,删除第ｉ个结点＊/
dulｉnklist p;
p＝ｌ->
ｎeｘｔ；
/* ｐ指向第一个结点 *／
intj=1;
/*j表示结点位置 */
whｉｌe（p＆＆（j<
i））{
p=p-＞ｎｅｘｔ；
＋+j;
} ／*寻找第i个结点 *／
iｆ（!
i）returｎ NULL;
/*在l中确定第i个元素的位置指针p,p=NＵＬL，即第ｉ个元素不存在*/
e=p->
daｔa;
/*把指针p的数据域的值赋给e*／
p->
prior-＞ｎｅxt=p-＞ｎext;
p－>
next->
pｒiｏｒ=p->
prｉｏr;
／＊在双向链表中删除结点时指针的变化 *／
freｅ（p）;
/＊把结点p删掉＊/
reｔuｒn ０;
intlocatｅelｅｍ_ｄul（dulinkｌistl,ｉnｔe） /＊查找双线链表中第一个值为e的结点位置＊／
｛
duｌinklistp；
ｉntj;
ﻩ
p=ｌ->
nexｔ;
/＊p指向第一个结点*/
ｊ=1；
／＊ j表示结点位置＊/
whiｌｅ（（p－>
＝e）＆&
p）｛
p=p－>
}/*寻找第一个值为e的结点位置*/
p）
return -1;
/*返回第一个值为ｅ的结点位置*／
elｓe
ｒｅturn1；
void print_dｕl（dｕliｎklｉstl） /*打印双向链表ｌ */
dulｉnklistp;
ｐ=ｌ；
／*p指向头结点*/
ｗhiｌｅ（p）{
ｐｒinｔf（"
％d"
p->
ｄata）;
p=p－>
ｎexｔ;
} /*把双向链表中的数据都打印出来＊／
｝
voidｓave＿duｌ（ｄuｌiｎｋlｉstl）
FＩＬE＊fｐ;
if（（ｆp=fopen（"
H：
\\test2．txｔ＂,"
w+＂））==NUＬL）
priｎtｆ（＂canｎot ｏpenｆiｌe!
\ｎ"
ｅxit（0）;
wｈｉle（l）
ﻩ{
ﻩfprintf（fp，"
%d＂，l->
l =l->
ﻩ}
voidmain（）{
duliｎｋlｉstl;
intｉ,e,x;
ｉntpos；
create_ｄuｌ（l）;
／＊调用双向链表建立函数＊/
ｐrinｔ_dul（l）;
/＊调用双向链表的打印函数*／
ｗhile
（1）{
ﻩprｉntf（＂ｉnｐutxtocｈooｓe （1.查找,2.插入,3.删除，4.０ver）:
\ｎ"
ｓｃanf（＂%d"
＆x）；
ﻩ ｓｗitch（ｘ）{
ｃａse1：
ﻩprintf（＂\npｌeaseｉｎｐuttheｄａtayouｗａnttｏlｏcate:
\ｎ"
sｃanf（"
ｅ）;
/*输入要查找的值*/
ﻩ pos=locateｅｌem_ｄul（l,e）；
／*调用双向链表的查找函数＊/
ﻩ if（pos==-1）ｐriｎｔf（＂Thｅ dａｔａiｓnｏtfouｎd!
＼n"
ﻩﻩeｌse ｐrintf（"
Theｄatａisfｏund！
\n"
ｂrｅａk;
ﻩﻩ
casｅ2：
prｉnｔf（＂pleaseinputｔhｅ posiｔion yoｕwanttｏinsert:
＼n＂）;
sｃａnf（"
i）;
/*输入要插入的位置＊/
prｉntf（"
pleａseinpｕｔthｅｄａtayｏｕwant toinsｅrt:
scaｎf（"
％d"
，&
e）;
/＊ 输入新结点的数据 */
ｌistinｓｅrt_duｌ（l，i,e）；
ﻩ/*调用双向链表的插入函数*/
pｒinｔ_dul（l）;
break;
/* 调用双向链表的打印函数＊/
case 3:
prinｔf（"
＼ｎ pｌｅasｅｉnputtｈepｏsｉtionyouwａntto deleｔe:
scａnf（"
ｉ）;
/*输入要删除结点的位置 */
ｌistdeｌeｔe_dul（l，i,ｅ）;
/* 调用双向链表的删除函数 *／
print_duｌ（ｌ）;
breａｋ;
/* 调用双向链表的打印函数*/
casｅ４:
ﻩﻩ sａｖe＿dul（ｌ）;
ﻩ exit（0）；
ﻩ}ﻩﻩ
}
●５.程序运行结果
●6.总结:
通过此次数据结构的课程设计,我对程序的编程,编译,执行等有了更深的认识。
理解到思路对于一个程序的重要性，在整个设计过程中,遇到了很多不同的问题,但通过尝试，努力和老师的帮助最终都解决了,感到很有成就感。
从中,我意识到程序的成功不仅仅是消除语法上的错误,而且还要执行成功。
缺乏完整的思路，尽管语法正确，程序还是无法执行。
数据结构的设计考验的不仅仅是我们对书本知识的理解,还考验了我们分析事物时思维的逻辑紧密性，加深并巩固了我对数据结构的认识。
总的来说,这次的数据结构课程设计加深了我对数据结构的认识,也学到了相关的知识,并且巩固了课堂上所学的知识，还锻炼了实践的应用操作能力,感受颇深,也收获了成功的喜悦。
升级会员 