严蔚敏版数据结构所有算法代码.docx
《严蔚敏版数据结构所有算法代码.docx》由会员分享，可在线阅读，更多相关《严蔚敏版数据结构所有算法代码.docx（131页珍藏版）》请在冰点文库上搜索。
严蔚敏版数据结构所有算法代码
严蔚敏版数据结构所有算法代码
------------------------线性数据结构-----------------------------
2013年9月
//线性表、链表
//栈、队列
//数组、广义表
//串
-------------------------线性表----------------------
typedefstruct
{
charname[20];//注意如果应用指针的形式
//在初始化每个结点时一定要先为结点中的每个变量开辟内存空间
charsex;
charaddr[100];
unsignedintage;
charphonenum[20];
}node;//结点描述
typedefstruct
{
node*p;
intlength;//当前顺序表长度
intlistsize;//当前分配的线性表长度
}list;//线性表描述
listL;//定义一个线性表
intinitlist（list&l）//构造一个空的线性表
{
l.p=（node*）malloc（LIST_INIT_SIZE*sizeof（node））;
if（!
（l.p））
exit
（1）;
l.length=0;
l.listsize=LIST_INIT_SIZE;
returntrue;
}
voiddestroylist（list&l）//销毁线性表操作
{
if（l.p!
=NULL）
{
free（l.p）;
printf（"销毁成功!
\n"）;
}
else
printf（"线性表不存在！
\n"）;
}
intclearlist（list&l）//将线性表置空操作
{
if（l.p==NULL）
{
printf（"线性表不存在！
\n"）;
returnfalse;
}
else
{
free（l.p）;
l.p=（node*）malloc（l.listsize*sizeof（node））;
l.length=0;
}
returntrue;
}
intlistempty（list&l）//判断线性表是否为空表
{
if（l.p==NULL）
returntrue;
else
returnfalse;
}
intgetelem（list&l,inti,node&e）//用e返回表中第i个数据元素
{
if（l.p==NULL）
returnfalse;
else
e=l.p[i-1];
returntrue;
}
intpriorelem（list&l,inti,node&pre_e）//得到第i个元素的前驱元素
{
if（i==0||l.p==NULL）
returnfalse;
else
pre_e=l.p[i-1];
returntrue;
}
intnextelem（list&l,inti,node&next_e）//得到表中第i个元素的后继元素
{
if（i>=l.length||l.p==NULL）
returnfalse;
else
next_e=l.p[i+1];
returntrue;
}
intinsertlist（list&l,inti,node&e）//将元素e插入到表l中第i个元素的后面
{
node*q,*k;
if（i<1||i>l.length+1）
returnfalse;
if（l.length>=l.listsize）
{
l.p=（node*）realloc（l.p,（l.listsize+LISTINCREMENT）*sizeof（node））;
if（!
l.p）
exit
（1）;
l.listsize+=LISTINCREMENT;
}
k=&l.p[i-1];
for（q=&l.p[l.length-1];q>k;q--）
*（q+1）=*q;
*k=e;
l.length++;
returntrue;
}
intdeletelist（list&l,inti,node&e）//删除表中第i个元素并用e返回其值
{
node*q;
intj=i-1;
if（i<1||i>l.length）
returnfalse;
e=l.p[i-1];
for（q=&l.p[i-1];j*q=*（++q）;
l.length--;
returntrue;
}
voidmergerlist（listla,listlb,list&lc）//归并两个按非递减排列的线性表
{
intla_len,lb_len,i=1,j=1,k=0;
nodeai,bj;
la_len=la.length;
lb_len=lb.length;
while（i<=la_len&&j<=lb_len）
{
getelem（la,i,ai）;
getelem（lb,j,bj）;
if（ai.a<=bj.a）
{
insertlist（lc,++k,ai）;
i++;
}
else
{
insertlist（lc,++k,bj）;
j++;
}
}
while（i<=la_len）
{
getelem（la,i,ai）;
insertlist（lc,++k,ai）;
i++;
}
while（j<=lb_len）
{
getelem（lb,j,bj）;
insertlist（lc,++k,bj）;
j++;
}
}
intListAscendingOrder（list&l）//按结点中某一元素的比较升序排列线性表中的结点
{
nodee;
inti,j;
if（l.p==NULL||l.length==1）
returnERROR;
for（i=0;ifor（j=i+1;jif（l.p[i].num>=l.p[j].num）
{
e=l.p[i];
l.p[i]=l.p[j];
l.p[j]=e;
}
returnOK;
}//省略降序排列
voidMergerList（listla,listlb,list&lc）//将两线性表升序排列后再归并
{
node*q,*k,e1;
inti=0,j=0,m=0,n;
ListAscendingOrder（la）;
ListAscendingOrder（lb）;
printf（"表a升序排列后为：
\n"）;
for（i=0;iprintf（"%d",la.p[i].num）;
printf（"\n"）;
printf（"表b升序排列后为：
\n"）;
for（i=0;iprintf（"%d",lb.p[i].num）;
printf（"\n"）;
i=0;
while（i{
if（la.p[i].num<=lb.p[j].num）
{
e1=la.p[i];
i++;
}
else
{
e1=lb.p[j];
j++;
}
if（e1.num!
=lc.p[lc.length-1].num）
InsertList（lc,++m,e1）;
}
if（iwhile（i{
if（la.p[i].num!
=lc.p[lc.length-1].num）
InsertList（lc,++m,la.p[i]）;
i++;
}
if（jwhile（j{
if（lb.p[j].num!
=lc.p[lc.length-1].num）
InsertList（lc,++m,lb.p[j]）;
j++;
}
printf（"按升序排列再归并两表为：
\n"）;
for（n=0;nprintf（"%d",lc.p[n].num）;
printf（"\n"）;
}
----------------------链表-----------------------------
typedefstruct
{
intnum;
}node;
typedefstructLIST
{
nodedata;
structLIST*next;
}list,*slist;
intCreatList（slist&head）//此处应为只针对的引用
{
head=（list*）malloc（sizeof（list））;
if（!
head）
returnERROR;
head->next=NULL;
returnOK;
}
voidInvertedList（slist&head1,slist&head2）
{//构造新表逆置单链表函数
list*p,*q;
p=head1->next;
q=p->next;
if（p==NULL）
printf（"链表为空无法实现逆置操作\n"）;
else
{
while（q!
=NULL）
{
p->next=head2->next;
head2->next=p;
p=q;
q=q->next;
}
p->next=head2->next;
head2->next=p;
printf（"逆置成功！
?
\n"）;
}
}
voidInsertList（slist&head,node&e）//此处应为指针的引用
{//而不应该是list*head
list*p,*q;
p=（list*）malloc（sizeof（list））;
q=head;
while（q->next!
=NULL）
q=q->next;
p->next=q->next;
q->next=p;
p->data=e;
}
voidInvertedList（sqlist&head）
{//-------不构造新表逆置单链表函数---------//
list*p,*q,*k;
p=head->next;
q=p->next;
k=q->next;
p->next=NULL;
while（k!
=NULL）
{
q->next=p;
p=q;
q=k;
k=k->next;
}
q->next=p;
head->next=q;
}
//----交换链表中第i个和第j个结点，函数实现如下——//
intSwapListNode（sqlist&head,inti,intj）
{
intm,n,m1,n1,sum=0;
list*p,*q,*k,*c,*d,*ba;
ba=head->next;
while（ba!
=NULL）
{
sum++;
ba=ba->next;
}
if（i==j||i>sum||j>sum||i<1||j<1）
{
printf（"所要交换的两个结点有误！
\n"）;
returnERROR;
}
if（i{m=i;n=j;}
else
{m=j;n=i;}
p=head;q=head;
for（m1=1;m1<=m;m1++）
p=p->next;
for（n1=1;n1<=n;n1++）
q=q->next;
if（p->next==q）
{//如果结点相邻
k=head;
while（k->next!
=p）
k=k->next;
//相邻两结点的交换
p->next=q->next;
q->next=p;
k->next=q;
}
else
{//如果结点不相邻
k=head;c=head;
while（k->next!
=p）
k=k->next;
while（c->next!
=q）
c=c->next;
d=p->next;
//不相邻两结点之间的交换
p->next=q->next;
c->next=p;
k->next=q;
q->next=d;
}
returnOK;
}
//-----将链表中结点按结点中某一项大小升序排列，函数实现如下-----//
intAscendingList（sqlist&head）
{
intm,n,sum=0,i,j;
list*p,*q,*k;
k=head->next;
while（k!
=NULL）
{
sum++;
k=k->next;
}
for（i=1;ifor（j=i+1;j<=sum;j++）
{
p=head->next;
m=1;
while（m!
=i）
{
m++;
p=p->next;
}
q=head->next;
n=1;
while（n!
=j）
{
n++;
q=q->next;
}
if（p->data.exp>q->data.exp）//如果按exp降序排列，则应将>改为<；
SwapListNode（head,i,j）;
}
returnOK;
}
//-----将两链表合并为一个链表------//
intAddList（sqlist&head1,sqlist&head2,sqlist&head3）
{//已将表head1和表head2按某一项升序排列过
sqlistp,q;
nodee;
p=head1->next;
q=head2->next;
while（p!
=NULL&&q!
=NULL）
{
if（p->data.expdata.exp）
{
InsertList（head3,p->data）;
p=p->next;
}
else
if（p->data.exp>q->data.exp）
{
InsertList（head3,q->data）;
q=q->next;
}
else
if（p->data.exp==q->data.exp）
{
e.coefficient=p->data.coefficient+q->data.coefficient;
e.exp=p->data.exp;//e.exp=q->data.exp;
InsertList（head3,e）;
p=p->next;
q=q->next;
}
}
if（p!
=NULL）
while（p!
=NULL）
{
InsertList（head3,p->data）;
p=p->next;
}//如果p中有剩余，则直接将p中剩余元素插入head3中
if（q!
=NULL）
while（q!
=NULL）
{
InsertList（head3,q->data）;
q=q->next;
}//如果q中有剩余，则直接将q中的剩余元素插入head3中
return0;
}
-----------------------栈------------------------------
//---------利用栈结构实现数制之间的转换------书3.2.1//
typedefstruct
{
intnum;
}node;
typedefstruct
{
node*base;
node*top;
intstacksize;
}stack;//顺序栈结构定义
intCreatStack（stack&stackll）
{
stackll.base=（node*）malloc（INITSTACKSIZE*sizeof（node））;
if（!
stackll.base）
exit（OVERFLOW）;
stackll.top=stackll.base;
stackll.stacksize=INITSTACKSIZE;
returnOK;
}
voidpush（stack&s,nodee）
{//进栈操作
if（s.top-s.base>=s.stacksize）
{s.base=（node*）realloc（s.base,（s.stacksize+INCRESTACKMENT）*sizeof（node））;
if（!
s.base）
exit（OVERFLOW）;
s.top=s.base+s.stacksize;//可以不写此语句；
s.stacksize+=INCRESTACKMENT;
}
*（s.top++）=e;//*s.top++=e;
}
voidpop（stack&s,node&e）
{//出栈操作
if（s.top==s.base||s.base==NULL）
printf（"信息有误！
\n"）;
else
e=*--s.top;
}
//-------取栈顶元素函数------//
voidgettop（stack&s,node&e）
{
if（s.base==s.top）
printf（"栈为空，无法取得栈顶元素！
\n"）;
else
{
e=*（s.top-1）;
}
}
//-----栈的应用：
括号匹配的检验------书3.2.2//
//省略了大部分上述已有代码//
intzypd（charc）
{//判断是否为左括号字符
if（c=='['||c=='{'||c=='（'）
returnOK;
else
returnERROR;
}
intmain（void）
{
stacks;
nodee1,e2,e3;
charst[INITSTACKSIZE];
inti=0,j;
CreatStack（s）;
printf（"请输入括号字符，以'#'做结束符：
"）;
scanf（"%c",&st[i]）;
while（st[i]!
='#'）
{
i++;
scanf（"%c",&st[i]）;
}
if（!
zypd（st[0]））
printf（"输入字符不合法！
\n"）;
else
{
for（j=0;j{
if（zypd（st[j]））
{//如果是左括号则将此字符压入栈中
e1.c=st[j];
push（s,e1）;
}
else
{//如果当前st[j]元素不是左括号
//则取出栈顶元素，比较栈顶元素与当前st[j]元素是否项匹配
//如果匹配，则栈顶元素出栈
gettop（s,e2）;
if（e2.c=='['&&st[j]==']'||e2.c=='{'&&st[j]=='}'||e2.c=='（'&&st[j]=='）'）
pop（s,e3）;
else
{
printf（"括号验证失败！
\n"）;
break;
}
}
}
if（s.top==s.base）//当循环结束时，如果栈为空栈说明输入的括号合法
printf（"括号验证成功！
\n"）;
}
getchar（）;
system（"pause"）;
return0;
}
//----------链栈描述---------//
typedefstructNode
{
intnum;
structNode*next;
}node;
typedefstruct
{
Node*top;
Node*base;
}stack;
voidInitStack（stack&s）
{
s.base=（Node*）malloc（sizeof（node））;
if（!
s.base）
exit
（1）;
else
{
s.base->next=NULL;
s.top=s.base;
}
}
voidInsertStack（stack&s,nodee）
{
node*p;
p=（node*）malloc（sizeof（node））;
if（!
p）
exit
（1）;
else
{
*p=e;
p->next=s.top;
s.top=p;
}
}
voidDeleteStack（stack&s,node&e）
{
node*p;
if（s.top==s.base）
printf（"栈为空！
\n"）;
else
{
p=s.top;
s.top=s.top->next;
e=*p;
free（p）;
}
}
--------------------队列----------------------
//------链队列的描述及操作-------//
typedefstructNode
{
inta;
structNode*next;
}Qnode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
voidInitQueue（LinkQueue&Q）
{
Q.front=（Qnode*）malloc（sizeof（Qnode））;
if（!
Q.front）
exit
（1）;
Q.rear=Q.front;
Q.front->next=NULL;
}
void
升级会员 