算法与数据结构程序实例.docx

算法与数据结构程序实例.docx

《算法与数据结构程序实例.docx》由会员分享，可在线阅读，更多相关《算法与数据结构程序实例.docx（91页珍藏版）》请在冰点文库上搜索。

算法与数据结构程序实例

算法与数据结构

0_双向循环链表

/*#############################################################*/

/*************************main.c*******************************/

/*=======================================================

工程名称：

Link

组成文件：

main.clink.clink.h

功能描述：

链表综合练习

程序分析：

完成链表建立，结点删除，结点插入等操作

维护记录：

2010-09-12v1.1addbydxh

=======================================================*/

#include

#include

#include"link.h"

voiddisplay（void）

{

printf（"/**************************/\n"）;

printf（"/***1:

创建链表***/\n"）;

printf（"/***2:

插入链表***/\n"）;

printf（"/***3:

删除链表***/\n"）;

printf（"/***4:

搜索链表***/\n"）;

printf（"/***5:

输出链表***/\n"）;

printf（"/***0:

退出链表***/\n"）;

printf（"/**************************/\n"）;

}

intmain（void）

{

TYPE*head=NULL,*Lsearch=NULL,*ins=NULL;

intdelnum=0,searnum=0;

intmenu=0,link_num=0;

while

（1）

{

display（）;

scanf（"%d",&menu）;

switch（menu）

{

caseCREATE_CMD:

printf（"inputcreatelinkNumber:

\n"）;

scanf（"%d",&link_num）;

head=creat（link_num）;

print（head）;//打印创建的链表

break;

caseINSERT_CMD:

ins=（TYPE*）malloc（sizeof（TYPE））;

printf（"insertNumberandAge:

\n"）;

scanf（"%d%d",&ins->num,&ins->age）;

head=insert（head,ins）;

print（head）;//打印插入节点后的链表

break;

caseDELETE_CMD:

printf（"inputdeleteNumber:

\n"）;

scanf（"%d",&delnum）;

head=delete（head,delnum）;

print（head）;//打印删除一个节点后的链表

break;

caseSEARCH_CMD:

printf（"inputsearchNumber:

\n"）;

scanf（"%d",&searnum）;

Lsearch=search（head,searnum）;

print（Lsearch）;//从搜索到的节点开始打印

break;

casePRINT_CMD:

print（head）;//从搜索到的节点开始打印

break;

caseEXIT_CMD:

return0;

break;

default:

printf（"请按提示菜单,输入有效数据进行操作！

\n"）;

break;

}

}

}

/*************************link.h*******************************/

#ifndef__linker_h__

#define__linker_h__

#include

#defineEXIT_CMD0

#defineCREATE_CMD1

#defineINSERT_CMD2

#defineDELETE_CMD3

#defineSEARCH_CMD4

#definePRINT_CMD5

typedefstructnode

{

intnum;

intage;

structnode*prior;

structnode*next;

}TYPE;

externTYPE*creat（intn）;

externTYPE*delete（TYPE*head,intnum）;

externTYPE*insert（TYPE*head,TYPE*pi）;

externTYPE*search（TYPE*head,intnum）;

externvoidprint（TYPE*head）;

#endif

/*****************************Link.c*****************************/

#include

#include

#include"link.h"

//==========================================================

//语法格式：

creat（intn）

//实现功能：

创建一个具有n个节点的链表，并对其值进行初始化

//参数：

n:

链表的长度，即节点的个数

//返回值：

所创建链表的首地址

//==========================================================

TYPE*creat（intn）

{

TYPE*head=NULL,*ins;

inti;

for（i=0;i

{

ins=（TYPE*）malloc（sizeof（TYPE））;

printf（"insertNumberandAge:

\n"）;

scanf（"%d%d",&ins->num,&ins->age）;

head=insert（head,ins）;

}

return（head）;

}

//==========================================================

//语法格式：

delete（TYPE*head,intnum）

//实现功能：

删除给定序号所指向的节点

//参数：

*head:

待删除链表

//num：

所需删除的节点

//返回值：

删除指定节点后的新链表首址

//==========================================================

TYPE*delete（TYPE*head,intnum）

{

TYPE*pf,*pb=head;

if（head==NULL）

{

printf（"\nemptylist!

\n"）;

gotoend;

}

while（pb->num!

=num&&pb->next!

=head）

{

pf=pb;

pb=pb->next;

}

if（pb->num==num）

{

if（pb==head）

{

if（pb->next==head&&pb->prior==head）//如果只有一个节点

{

free（pb）;

head=NULL;

gotoend;

}

pb->next->prior=head->prior;//头节点指向尾

head->prior->next=pb->next;//尾节点指向头

head=pb->next;//得到新头节点地址

}

else

{

pf->next=pb->next;

pb->next->prior=pf;

}

free（pb）;

printf（"Thenodeisdeleted\n"）;

}

else

printf（"Thenodenotbeenfound!

\n"）;

end:

returnhead;

}

//========================================================

//语法格式：

insert（TYPE*head,TYPE*pi）

//功能：

将新申请的节点加入到指定链表中，并按num从小到大排序

//参数：

*head:

待插入链表

//*pi：

带插入节点

//返回值：

插入指定节点后的新链表首址

//========================================================

TYPE*insert（TYPE*head,TYPE*pi）

{

TYPE*pb=head,*pf;

if（head==NULL）//如果为空就建立，空间在传入前申请好

{

head=pi;

pi->prior=head;

pi->next=head;

}

else

{

while（（pi->num>pb->num）&&（pb->next!

=head））

{

pf=pb;//pf指向前，pb指向后

pb=pb->next;//节点后移

}//找到一个比插入值大的节点，然后插在它的前面

if（pi->num<=pb->num）//找到所要插入节点位置，插到pb的前面

{

if（head==pb）//在第一结点之前插入

{

pi->next=pb;

pi->prior=head->prior;

pb->prior=pi;

head->prior->next=pi;//尾节点

head=pi;//保存头节点

}

else

{

pf->next=pi;//在中间位置插入

pb->prior=pi;

pi->next=pb;

pi->prior=pf;

}

}

else//只有pb->head为空才会成立

{

pb->next=pi;//在表末插入

pi->next=head;

pi->prior=pb;

head->prior=pi;//头始终指向新插入的节点

}

}

returnhead;

}

//========================================================

//语法格式：

search（TYPE*head,intnum）

//实现功能：

搜索给定序号所指向的节点

//参数：

*head:

待搜索链表

//num：

按所需进行节点搜索

//返回值：

搜索到的节点首址

//========================================================

TYPE*search（TYPE*head,intnum）

{

TYPE*pb=head;

if（head==NULL）

{

returnhead;

}

while（（pb->num!

=num）&&（pb->next!

=head））

{

pb=pb->next;//节点后移

}

if（pb->num==num）

{

returnpb;

}

else

returnhead;

}

//======================================================

//语法格式：

print（TYPE*head）

//功能：

打印指定链表中的全部节点数据，由于循环双向表没有头节点，

//每个节点性质完全一样，只要给出任意节点就可以遍历

//参数：

*head：

待打印的链表首址

//返回值：

无

//======================================================

voidprint（TYPE*Lnode）

{

TYPE*pb=Lnode;

printf（"\n链表所有信息如下：

\n"）;

printf（"address\t\tNumber\t\tAge\n"）;

if（pb==NULL）

{

printf（"\n"）;

return;

}

while（pb->next!

=Lnode）

{

printf（"%x\t\t%d\t\t%d\n",pb,pb->num,pb->age）;

//printf（"addr:

p=%x\tn=%x\n\n",pb->prior,pb->next）;

pb=pb->next;

}

printf（"%x\t\t%d\t\t%d\n",pb,pb->num,pb->age）;

//printf（"addr:

p=%x\tn=%x\n\n",pb->prior,pb->next）;

printf（"\n"）;

}

/*#############################################################*/

1_线性表

/*#############################################################*/

多维数组

---------------------------------------------------------------------------------------------

/*************************MoreArray.c****************************/

#include

intmain（void）

{

inti,j,k;

intstr[2][3][4]={{{1,2,3,4},\

{5,6,7,8},\

{9,10,11,12}},\

{{13,14,15,16},\

{17,18,19,20},\

{21,22,23,24}}};

int（*p1）[3][4]=str;

int*p2=str;

int***p3=str;

printf（"\n标准多维指针访问:

\n"）;

for（i=0;i<24;i++）

{

printf（"%d",*（*（*（p1））+i））;

}

printf（"\n一维指针访问:

\n"）;

for（i=0;i<24;i++）

{

printf（"%d",*（p2+i））;

}

printf（"\n多维指针访问:

\n"）;

for（i=0;i<24;i++）

{

printf（"%d",*（p3+i））;

//printf（"%d",*（*（*（p3））+i））;//段错误

//printf（"%d",***（p3+i））;//段错误

}

printf（"\n指针下标法访问:

\n"）;

for（i=0;i<2;i++）

{

for（j=0;j<3;j++）

{

for（k=0;k<4;k++）

printf（"%d",p1[i][j][k]）;

}

}

printf（"\n"）;

return0;

}

---------------------------------------------------------------------------------------------

共享链表

---------------------------------------------------------------------------------------------

单向>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

/*==========================================================

工程名称：

Link

组成文件：

main.clink.clink.h

功能描述：

链表综合练习

程序分析：

完成链表建立，结点删除，结点插入等操作

维护记录：

2010-09-12v1.1addbydxh

=========================================================*/

/*************************main.c****************************/

#include

#include

#include"link.h"

voiddisplay（void）

{

printf（"/**************************/\n"）;

printf（"/***1:

创建链表***/\n"）;

printf（"/***2:

插入链表***/\n"）;

printf（"/***3:

删除链表***/\n"）;

//printf（"/***4:

搜索链表***/\n"）;

printf（"/***5:

输出链表***/\n"）;

printf（"/***0:

退出链表***/\n"）;

printf（"/**************************/\n"）;

}

intmain（void）

{

NODE*head=NULL;

TYPE*ins=NULL;

intdelnum=0,searnum=0;

intmenu=0,link_num=0;

while

（1）

{

display（）;

scanf（"%d",&menu）;

switch（menu）

{

caseCREATE_CMD:

printf（"inputcreatelinkNumber:

\n"）;

scanf（"%d",&link_num）;

head=creat（link_num）;

print（head）;//打印创建的链表

break;

caseINSERT_CMD:

ins=（TYPE*）malloc（sizeof（TYPE））;

printf（"insertNumberandAge:

\n"）;

scanf（"%d%d",&ins->num,&ins->age）;

head=insert（head,&ins->list）;

print（head）;//打印插入节点后的链表

break;

caseDELETE_CMD:

printf（"inputdeleteNumber:

\n"）;

scanf（"%d",&delnum）;

head=delnode（head,delnum）;

print（head）;//打印删除一个节点后的链表

break;

caseSEARCH_CMD:

break;

casePRINT_CMD:

print（head）;//从搜索到的节点开始打印

break;

caseEXIT_CMD:

return0;

break;

default:

printf（"请按提示菜单,输入有效数据进行操作！

\n"）;

break;

}

}

}

/*************************link.c****************************/

#include

#include

#include"link.h"

//=====================================================

//语法格式：

creat（intn）

//实现功能：

创建一个具有n个节点的链表，并对其值进行初始化

//参数：

n:

链表的长度，即节点的个数

//返回值：

所创建链表的首地址

//======================================================

NODE*creat（intn）

{

NODE*head=NULL;

TYPE*ins=NULL;

inti;

for（i=0;i

{

ins=（TYPE*）malloc（sizeof（TYPE））;

printf（"insertNumberandAge:

\n"）;

scanf（"%d%d",&ins->num,&ins->age）;

head=insert（head,&ins->list）;

}

return（head）;

}

//=======================================================

//语法格式：

insert（TYPE*head,TYPE*pi）

//功能：

将新申请的节点加入到指定链表中，并按照num进行从小到大排序

//参数：

*head:

待插入链表

//*pi：

带插入节点

//返回值：

插入指定节点后的新链表首址

//====