数据结构上机指导源程序.docx
《数据结构上机指导源程序.docx》由会员分享，可在线阅读，更多相关《数据结构上机指导源程序.docx（340页珍藏版）》请在冰点文库上搜索。
数据结构上机指导源程序
/*文件名:
algo2-1.cpp*/
#include
#include
#defineMaxSize50
typedefcharElemType;
typedefstruct
{
ElemTypeelem[MaxSize];
intlength;
}SqList;
voidInitList（SqList*&L）
{
L=（SqList*）malloc（sizeof（SqList））;
L->length=0;
}
voidDestroyList（SqList*L）
{
free（L）;
}
intListEmpty（SqList*L）
{
return（L->length==0）;
}
intListLength（SqList*L）
{
return（L->length）;
}
voidDispList（SqList*L）
{
inti;
if（ListEmpty（L））return;
for（i=0;ilength;i++）
printf（"%c",L->elem[i]）;
printf（"\n"）;
}
intGetElem（SqList*L,inti,ElemType&e）
{
if（i<1||i>L->length）
return0;
e=L->elem[i-1];
return1;
}
intLocateElem（SqList*L,ElemTypee）
{inti=0;
while（ilength&&L->elem[i]!
=e）i++;
if（i>=L->length）
return0;
else
returni+1;
}
intListInsert（SqList*&L,inti,ElemTypee）
{
intj;
if（i<1||i>L->length+1）
return0;
i--;/*将顺序表位序转化为elem下标*/
for（j=L->length;j>i;j--）/*将elem[i]及后面元素后移一个位置*/
L->elem[j]=L->elem[j-1];
L->elem[i]=e;
L->length++;/*顺序表长度增1*/
return1;
}
intListDelete（SqList*&L,inti,ElemType&e）
{
intj;
if（i<1||i>L->length）
return0;
i--;/*将顺序表位序转化为elem下标*/
e=L->elem[i];
for（j=i;jlength-1;j++）
L->elem[j]=L->elem[j+1];
L->length--;
return1;
}/*文件名:
algo2-2.cpp*/
#include
#include
typedefcharElemType;
typedefstructLNode/*定义单链表结点类型*/
{
ElemTypedata;
structLNode*next;
}LinkList;
voidInitList（LinkList*&L）
{
L=（LinkList*）malloc（sizeof（LinkList））;/*创建头结点*/
L->next=NULL;
}voidDestroyList（LinkList*&L）
{
LinkList*p=L,*q=p->next;
while（q!
=NULL）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
}
intListEmpty（LinkList*L）
{
return（L->next==NULL）;
}
intListLength（LinkList*L）
{
LinkList*p=L;inti=0;
while（p->next!
=NULL）
{
i++;
p=p->next;
}
return（i）;
}
voidDispList（LinkList*L）
{
LinkList*p=L->next;
while（p!
=NULL）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
intGetElem（LinkList*L,inti,ElemType&e）
{
intj=0;
LinkList*p=L;
while（j=NULL）
{
j++;
p=p->next;
}if（p==NULL）
return0;
else
{
e=p->data;
return1;
}
}
intLocateElem（LinkList*L,ElemTypee）
{
LinkList*p=L->next;
intn=1;
while（p!
=NULL&&p->data!
=e）
{
p=p->next;
n++;
}
if（p==NULL）
return（0）;
else
return（n）;
}
intListInsert（LinkList*&L,inti,ElemTypee）
{
intj=0;
LinkList*p=L,*s;
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）/*未找到第i-1个结点*/
return0;
else/*找到第i-1个结点*p*/
{
s=（LinkList*）malloc（sizeof（LinkList））;/*创建新结点*s*/
s->data=e;
s->next=p->next;/*将*s插入到*p之后*/
p->next=s;
return1;
}
}
intListDelete（LinkList*&L,inti,ElemType&e）
{intj=0;
LinkList*p=L,*q;
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）/*未找到第i-1个结点*/
return0;
else/*找到第i-1个结点*p*/
{
q=p->next;/*q指向要删除的结点*/
p->next=q->next;/*从单链表中删除*q结点*/
free（q）;/*释放*q结点*/
return1;
}
}/*文件名:
algo2-3.cpp*/
#include
#include
typedefcharElemType;
typedefstructDNode/*定义双链表结点类型*/
{
ElemTypedata;
structDNode*prior;/*指向前驱结点*/
structDNode*next;/*指向后继结点*/
}DLinkList;
voidInitList（DLinkList*&L）
{
L=（DLinkList*）malloc（sizeof（DLinkList））;/*创建头结点*/
L->prior=L->next=NULL;
}
voidDestroyList（DLinkList*&L）
{
DLinkList*p=L,*q=p->next;
while（q!
=NULL）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
}
intListEmpty（DLinkList*L）
{return（L->next==NULL）;
}
intListLength（DLinkList*L）
{
DLinkList*p=L;inti=0;
while（p->next!
=NULL）
{
i++;
p=p->next;
}
return（i）;
}
voidDispList（DLinkList*L）
{
DLinkList*p=L->next;
while（p!
=NULL）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
intGetElem（DLinkList*L,inti,ElemType&e）
{
intj=0;
DLinkList*p=L;
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）
return0;
else
{
e=p->data;
return1;
}
}
intLocateElem（DLinkList*L,ElemTypee）
{
intn=1;
DLinkList*p=L->next;
while（p!
=NULL&&p->data!
=e）{
n++;
p=p->next;
}
if（p==NULL）
return（0）;
else
return（n）;
}
intListInsert（DLinkList*&L,inti,ElemTypee）
{
intj=0;
DLinkList*p=L,*s;
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）/*未找到第i-1个结点*/
return0;
else/*找到第i-1个结点*p*/
{
s=（DLinkList*）malloc（sizeof（DLinkList））;/*创建新结点*s*/
s->data=e;
s->next=p->next;/*将*s插入到*p之后*/
if（p->next!
=NULL）p->next->prior=s;
s->prior=p;
p->next=s;
return1;
}
}
intListDelete（DLinkList*&L,inti,ElemType&e）
{
intj=0;
DLinkList*p=L,*q;
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）/*未找到第i-1个结点*/
return0;
else/*找到第i-1个结点*p*/
{q=p->next;/*q指向要删除的结点*/
if（q==NULL）return0;/*不存在第i个结点*/
p->next=q->next;/*从单链表中删除*q结点*/
if（p->next!
=NULL）p->next->prior=p;
free（q）;/*释放*q结点*/
return1;
}
}
voidSort（DLinkList*&head）/*双链表元素排序*/
{
DLinkList*p=head->next,*q,*r;
if（p!
=NULL）/*若原双链表中有一个或以上的数据结点*/
{
r=p->next;/*r保存*p结点后继结点的指针*/
p->next=NULL;/*构造只含一个数据结点的有序表*/
p=r;
while（p!
=NULL）
{
r=p->next;/*r保存*p结点后继结点的指针*/
q=head;
while（q->next!
=NULL&&q->next->datadata）/*在有序表中找插入*p的
前驱结点*q*/
q=q->next;
p->next=q->next;/*将*p插入到*q之后*/
if（q->next!
=NULL）q->next->prior=p;
q->next=p;
p->prior=q;
p=r;
}
}
}/*文件名:
algo2-4.cpp*/
#include
#include
typedefcharElemType;
typedefstructLNode/*定义单链表结点类型*/
{
ElemTypedata;
structLNode*next;
}LinkList;
voidInitList（LinkList*&L）
{
L=（LinkList*）malloc（sizeof（LinkList））;/*创建头结点*/
L->next=L;
}voidDestroyList（LinkList*&L）
{
LinkList*p=L,*q=p->next;
while（q!
=L）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
}
intListEmpty（LinkList*L）
{
return（L->next==L）;
}
intListLength（LinkList*L）
{
LinkList*p=L;inti=0;
while（p->next!
=L）
{
i++;
p=p->next;
}
return（i）;
}
voidDispList（LinkList*L）
{
LinkList*p=L->next;
while（p!
=L）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
intGetElem（LinkList*L,inti,ElemType&e）
{
intj=0;
LinkList*p;
if（L->next!
=L）/*单链表不为空表时*/
{
if（i==1）
{
e=L->next->data;return1;
}
else/*i不为1时*/
{
p=L->next;
while（j=L）
{
j++;
p=p->next;
}
if（p==L）
return0;
else
{
e=p->data;
return1;
}
}
}
else/*单链表为空表时*/
return0;
}
intLocateElem（LinkList*L,ElemTypee）
{
LinkList*p=L->next;
intn=1;
while（p!
=L&&p->data!
=e）
{
p=p->next;
n++;
}
if（p==L）
return（0）;
else
return（n）;
}
intListInsert（LinkList*&L,inti,ElemTypee）
{
intj=0;
LinkList*p=L,*s;
if（p->next==L||i==1）/*原单链表为空表或i==1时*/
{
s=（LinkList*）malloc（sizeof（LinkList））;/*创建新结点*s*/
s->data=e;s->next=p->next;/*将*s插入到*p之后*/
p->next=s;
return1;
}
else
{
p=L->next;
while（j=L）
{
j++;
p=p->next;
}
if（p==L）/*未找到第i-1个结点*/
return0;
else/*找到第i-1个结点*p*/
{
s=（LinkList*）malloc（sizeof（LinkList））;/*创建新结点*s*/
s->data=e;
s->next=p->next;/*将*s插入到*p之后*/
p->next=s;
return1;
}
}
}
intListDelete（LinkList*&L,inti,ElemType&e）
{
intj=0;
LinkList*p=L,*q;
if（p->next!
=L）/*原单链表不为空表时*/
{
if（i==1）/*i==1时*/
{
q=L->next;/*删除第1个结点*/
L->next=q->next;
free（q）;
return1;
}
else/*i不为1时*/
{
p=L->next;
while（j=L）
{
j++;
p=p->next;}
if（p==L）/*未找到第i-1个结点*/
return0;
else/*找到第i-1个结点*p*/
{
q=p->next;/*q指向要删除的结点*/
p->next=q->next;/*从单链表中删除*q结点*/
free（q）;/*释放*q结点*/
return1;
}
}
}
elsereturn0;
}/*文件名:
algo2-5.cpp*/
#include
#include
typedefcharElemType;
typedefstructDNode/*定义双链表结点类型*/
{
ElemTypedata;
structDNode*prior;/*指向前驱结点*/
structDNode*next;/*指向后继结点*/
}DLinkList;
voidInitList（DLinkList*&L）
{
L=（DLinkList*）malloc（sizeof（DLinkList））;/*创建头结点*/
L->prior=L->next=L;
}
voidDestroyList（DLinkList*&L）
{
DLinkList*p=L,*q=p->next;
while（q!
=L）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
}
intListEmpty（DLinkList*L）
{
return（L->next==L）;
}
intListLength（DLinkList*L）{
DLinkList*p=L;inti=0;
while（p->next!
=L）
{
i++;
p=p->next;
}
return（i）;
}
voidDispList（DLinkList*L）
{
DLinkList*p=L->next;
while（p!
=L）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
intGetElem（DLinkList*L,inti,ElemType&e）
{
intj=0;
DLinkList*p;
if（L->next!
=L）/*双链表不为空表时*/
{
if（i==1）
{
e=L->next->data;
return1;
}
else/*i不为1时*/
{
p=L->next;
while（j=L）
{
j++;
p=p->next;
}
if（p==L）
return0;
else
{
e=p->data;
return1;}
}
}
else/*双链表为空表时*/
return0;
}
intLocateElem（DLinkList*L,ElemTypee）
{
intn=1;
DLinkList*p=L->next;
while（p!
=NULL&&p->data!
=e）
{
n++;
p=p->next;
}
if（p==NULL）
return（0）;
else
return（n）;
}
intListInsert（DLinkList*&L,inti,ElemTypee）
{
intj=0;
DLinkList*p=L,*s;
if（p->next==L）/*原双链表为空表时*/
{
s=（DLinkList*）malloc（sizeof（DLinkList））;/*创建新结点*s*/
s->data=e;
p->next=s;s->next=p;
p->prior=s;s->prior=p;
return1;
}
elseif
升级会员 