数据结构实验.docx
《数据结构实验.docx》由会员分享，可在线阅读，更多相关《数据结构实验.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构实验
一、实验目的
1、学习线性表的顺序表示和实现，会进行顺序表的插入、删除、合并
2、学习线性表的链式表示和实现，会进行链表的插入、删除、合并
二、实验内容
1、编程实现：
（1）在顺序表ajcniydu的第三个位置插入p。
（2）删除顺序表ajcniydu第三个位置的元素。
2、编程实现将顺序表acdijtuy和cfklns合并。
3、编程实现：
（1）在链表asdfghjkl的第四个位置插入z。
（2）删除顺序表asdfghjkl第四个位置元素。
4、编程实现两个有序链表adfi和cefi的合并。
三、实验步骤
1.+2.代码：
#include
#include
typedefcharElemType;
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
//定义结构体
voidInitList（SqList&L）
{
L.elem=（ElemType*）malloc（10*sizeof（ElemType））;
L.length=0;
L.listsize=10;
}//初始化
voidCreateList（SqList&L,intn）
{
printf（"输入字符串：
"）;
inti=0;
for（i;i{
scanf（"%c",&L.elem[i]）;
L.length++;
}
}//赋值
voidShow（SqListL）
{
inti=0;
printf（"字符串：
"）;
for（i;iprintf（"%c",L.elem[i]）;
printf（"\n"）;
}//显示
intListInsert（SqList&L,inti,ElemTypee）
{
ElemType*p;
if（i<1||i>L.length+1）
printf（"插入位置不合法！
\n"）;
else
{
ElemType*q=&（L.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）*（p+1）=*p;
*q=e;
++L.length;
}
}//插入
intListDelete（SqList&L,inti）
{
if（i>L.length||i<=0）
printf（"位置不合法\n"）;
else
{
intj=i-1;
for（j;jL.elem[j]=L.elem[j+1];
L.length--;
}
}//删除
voidMergelist（SqListLa,SqListLb,SqList&Lc）
{
ElemType*pa,*pb,*pc,*pa_last,*pb_last;
pa=La.elem;
pb=Lb.elem;
pa_last=pa+La.length-1;
pb_last=pb+Lb.length-1;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=（ElemType*）malloc（Lc.length*sizeof（ElemType））;
while（pa<=pa_last&&pb<=pb_last）
{
if（*pa>=*pb）
*pc++=*pa++;
else
*pc++=*pb++;
}
while（pa<=pa_last）
*pc++=*pa++;
while（pb<=pb_last）
*pc++=*pb++;
}//合并
intmain（）
{
SqListLa;
InitList（La）;
CreateList（La,8）;
ElemTypee;
inti;
printf（"输入插入位置及字符：
"）;
scanf（"%d%c",&i,&e）;
ListInsert（La,i,e）;
Show（La）;
printf（"\n"）;
fflush（stdin）;
SqListLb;
InitList（Lb）;
CreateList（Lb,8）;
Show（Lb）;
printf（"输入删除位置：
"）;
intj;
scanf（"%d",&j）;
ListDelete（Lb,j）;
Show（Lb）;
printf（"\n"）;
fflush（stdin）;
SqListL1,L2,L3;
InitList（L1）;
InitList（L2）;
CreateList（L1,8）;
Show（L1）;
fflush（stdin）;
CreateList（L2,6）;
Show（L2）;
Mergelist（L1,L2,L3）;
Show（L3）;
}
3.+4.代码：
#include
#include
typedefcharElemType;
typedefstructLNode{
chara;
ElemTypedata;
structLNode*next;
}LNode,*LinkList;//定义结构体
intcount=0;
voidCreatelist（LinkList&L,intn）
{
printf（"输入字符串：
"）;
L=（LinkList）malloc（sizeof（LNode））;
L->next=NULL;
inti;
LinkListp=（LinkList）malloc（sizeof（LNode））;
L=p;
for（i=0;i{
LinkListq=（LinkList）malloc（sizeof（LNode））;
scanf（"%c",&q->a）;
q->next=NULL;
p->next=q;
p=q;
count++;
}
}//创建链表
voidShow（LinkListL）
{
LinkListp=（LinkList）malloc（sizeof（LNode））;
p=L->next;
printf（"字符串为：
"）;
while（p）
{
printf（"%c",p->a）;
p=p->next;
}
printf（"\n"）;
}//输出链表
intListInsert（LinkList&L,intn,charK）
{
if（L->next==NULL）
{
printf（"链表为空！
\n"）;
return0;
}
elseif（n>count+1）
{
printf（"插入位置不合法！
\n"）;
return0;
}
else
{
LinkListp=（LinkList）malloc（sizeof（LNode））;
if（n==1）
{
p->a=K;
p->next=L->next;
L->next=p;
}
elseif（n==count+1）
{
p=L->next;
while（p->next）
p=p->next;
LinkListq=（LinkList）malloc（sizeof（LNode））;
p->next=q;
q->a=K;
q->next=NULL;
}
else
{
inti;
p=L;
for（i=1;ip=p->next;
LinkListq=（LinkList）malloc（sizeof（LNode））;
q->a=K;
q->next=p->next;
p->next=q;
}
count++;
}
}
//插入
intListDelete（LinkList&L,intn）
{
if（L->next==NULL）
{
printf（"链表为空！
\n"）;
return0;
}
elseif（n>count）
{
printf（"删除位置不合法！
\n"）;
return0;
}
else
{
LinkListp=（LinkList）malloc（sizeof（LNode））;
p=L->next;
if（n==1）
{
L->next=p->next;
free（p）;
}
else
{
inti;
for（i=1;ip=p->next;
if（n==count）
p->next=NULL;
else
{
LinkListq=（LinkList）malloc（sizeof（LNode））;
q=p->next;
p->next=q->next;
free（q）;
}
}
}
}//删除
voidMergeList（LinkList&La,LinkList&Lb,LinkList&Lc）{
LinkListpa,pb,pc;
pa=La->next;pb=Lb->next;
Lc=pc=La;
while（pa&&pb）{
if（pa->data<=pb->data）{
pc->next=pa;pc=pa;pa=pa->next;
}
else{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?
pa:
pb;
free（Lb）;
}//合并
intmain（）
{
LinkListL1;
Createlist（L1,9）;
Show（L1）;
charb;inti;
printf（"输入插入位置和插入元素：
"）;
scanf（"%d%c",&i,&b）;
ListInsert（L1,i,b）;
Show（L1）;
fflush（stdin）;
printf（"\n"）;
LinkListL2;
Createlist（L2,9）;
Show（L2）;
intj;
printf（"输入删除元素的位置：
"）;
scanf（"%d",&j）;
ListDelete（L2,j）;
Show（L2）;
fflush（stdin）;
printf（"\n"）;
LinkListLa;
printf（"输入需合并的两组字符串！
\n"）;
Createlist（La,4）;
Show（La）;
fflush（stdin）;
LinkListLb;
Createlist（Lb,4）;
Show（Lb）;
LinkListLc;
MergeList（La,Lb,Lc）;
Show（Lc）;
return0;
}
四、实验小结
通过本章学习学会了线性表的顺序表示和实现，会进行顺序表的插入、删除、合并，也学会了线性表的链式表示和实现，会进行链表的插入、删除、合并。
但是写码的熟练度有待提高。
升级会员 