线性表的基本操作.docx
《线性表的基本操作.docx》由会员分享，可在线阅读，更多相关《线性表的基本操作.docx（26页珍藏版）》请在冰点文库上搜索。
线性表的基本操作
实验二线性表的基本操作
一、实验目的
1．掌握用C++/C语言调试程序的基本方法。
2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。
二、实验要求
1．C++/C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3． 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
三、实验内容：
1.分析并运行以下各子程序的主要功能。
程序1：
顺序存储的线性表和运算
#include
#defineMAXSIZE100
intlist[MAXSIZE];
intn;
/*insertinaseqlist*/
intsq_insert（intlist[],int*p_n,inti,intx）
{intj;
if（i<0||i>*p_n）return
（1）;
if（*p_n==MAXSIZE）return
（2）;
for（j=*p_n+1;j>i;j--）
list[j]=list[j-1];
list[i]=x;
（*p_n）++;
return（0）;
}
/*deleteinaseqlist*/
intsq_delete（intlist[],int*p_n,inti）
{intj;
if（i<0||i>=*p_n）return
（1）;
for（j=i+1;j<=*p_n;j++）
list[j-1]=list[j];
（*p_n）--;
return（0）;
}
voidmain（）
{inti,x,temp;
printf（"pleaseinputthenumberforn\n"）;
printf（"n="）;
scanf（"%d",&n）;
for（i=0;i<=n;i++）
{printf（"list[%d]=",i）;
scanf（"%d",&list[i]）;}
printf（"Thelistbeforeinsertionis\n"）;
for（i=0;i<=n;i++）printf（"%d",list[i]）;
printf（"\n"）;
printf（"pleaseinputthepositionwhereyouwanttoinsertavalue\nposition="）;
scanf（"%d",&i）;
printf（"pleaseinputthevalueyouwanttoinsert.\nx="）;
scanf（"%d",&x）;
temp=sq_insert（list,&n,i,x）;
switch（temp）
{case0:
printf（"Theinsertionissuccessful!
\n"）;
printf（"Thelistisafterinsertionis\n"）;
for（i=0;i<=n;i++）printf（"%d",list[i]）;
printf（"\n"）;
printf（"%d\n",n）;
break;
case1:
case2:
printf（"Theinsertionisnotsuccessful!
\n"）;break;}
/*deleting*/
printf（"Thelistbeforedeletingis\n"）;
for（i=0;i<=n;i++）printf（"%d",list[i]）;
printf（"\n"）;
printf（"pleaseinputthepositionwhereyouwanttodeleteavalue\nposition="）;
scanf（"%d",&i）;
temp=sq_delete（list,&n,i）;
switch（temp）
{case0:
printf（"Thedeletingissuccessful!
\n"）;
printf（"Thelistisafterdeletingis\n"）;
for（i=0;i<=n;i++）printf（"%d",list[i]）;
printf（"\n"）;
printf（"%d",n）;
break;
case1:
printf（"Thedeletingisnotsuccessful!
"）;break;}
}
2.分析并运行以下各子程序的主要功能。
程序2链式存储的线性表和运算
#include
#include
structnode{
chardata;
structnode*next;
};
typedefstructnodeNODE;
/*Thisfunctioncreatesalink_listwithNnodes.*/
NODE*create_link_list（intn）
{inti;
NODE*head,*p,*q;
if（n==0）returnNULL;
head=（NODE*）malloc（sizeof（NODE））;
p=head;
printf（"Pleaseinput%dcharsforthelinklist\n",n）;
for（i=0;i{scanf（"%c",&（p->data））;
q=（NODE*）malloc（sizeof（NODE））;
printf（"test3\n"）;
p->next=q;
p=q;}
scanf（"%c",&（p->data））;
getchar（）;
p->next=NULL;
return（head）;}
/*Thisfunctioninsertsanodewhosevalueisb*/
/*beforethenodewhosevalueisa,ifthenodeisnotexist,*/
/*theninsertitattheendofthelist*/
voidinsert（NODE**p_head,chara,charb）
{NODE*p,*q;
q=（NODE*）malloc（sizeof（NODE））;
q->data=b;
q->next=NULL;
if（*p_head==NULL）*p_head=q;
else
{p=（NODE*）malloc（sizeof（NODE））;
p=*p_head;
while（p->data!
=a&&p->next!
=NULL）
p=p->next;
q->next=p->next;
p->next=q;}
}
/*Thefunctiondeletesthenodewhosevalueisa,*/
/*ifsuccess,return0,orreturn1*/
intdeletenode（NODE**p_head,chara）
{NODE*p,*q;
q=*p_head;
if（q==NULL）return
（1）;
if（q->data==a）
{*p_head=q->next;
free（q）;
return（0）;}
else
{while（q->data!
=a&&q->next!
=NULL）
{p=q;
q=q->next;}
if（q->data==a）
{p->next=q->next;
free（q）;
return（0）;}
elsereturn
（1）;}
}
voidmain（）
{NODE*my_head,*p;
/*createalinklistwithmnodes*/
intm;
charch_a,ch_b;
printf（"pleaseinputthenumberofnodesforthelink_list\nm="）;
scanf（"%d",&m）;
getchar（）;
printf（"test1\n"）;
my_head=（NODE*）malloc（sizeof（NODE））;
my_head=create_link_list（m）;
/*Outputthelinklist*/
printf（"Thelinklistislike:
\n"）;
p=my_head;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
/*insertanodewhosevalueisbbeforea*/
printf（"Pleaseinputthepositionfora\nch_a="）;
getchar（）;
scanf（"%c",&ch_a）;
getchar（）;
printf（"Pleaseinputthevaluethatyouwanttoinsert\nch_b="）;
scanf（"%c",&ch_b）;
getchar（）;
insert（&my_head,ch_a,ch_b）;
printf（"Thelinklistafterinsertionislike:
\n"）;
p=my_head;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
/*deleteanodewhosevalueisa*/
printf（"Pleaseinputthepositionforaa="）;
scanf（"%c",&ch_a）;
getchar（）;
deletenode（&my_head,ch_a）;
printf（"Thelinklistafterdeletingislike:
\n"）;
p=my_head;
while（p!
=NULL）
{printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
3.运行以下程序并分析各子函数的主要功能。
#include
#include
structtagNode
{
intdata;
structtagNode*pNext;
};
typedefstructtagNode*pNode;
//将结点插入到链表的适当位置，这是一个降序排列的链表
//
voidinsertList（pNodehead,//链表头结点
pNodepnode）//要插入的结点
{
pNodepPri=head;
while（pPri->pNext!
=NULL）
{
if（pPri->pNext->datadata）
{
pnode->pNext=pPri->pNext;
pPri->pNext=pnode;
break;
}
pPri=pPri->pNext;
}
if（pPri->pNext==NULL）//如果要插入的结点最小
{
pPri->pNext=pnode;
}
}
//输出链表
voidprintLinkedList（pNodehead）
{
pNodetemp=head->pNext;
while（temp!
=NULL）
{
printf（"%d",temp->data）;
temp=temp->pNext;
}
}
//从链表中删除结点
voiddelformList（pNodehead,intdata）
{
pNodetemp=head->pNext;
pNodepPri=head;
while（temp!
=NULL）
{
if（temp->data==data）
{
pPri->pNext=temp->pNext;
free（temp）;
break;
}
pPri=temp;
temp=temp->pNext;
}
}
voidmain（）
{
pNodehead=（pNode）malloc（sizeof（structtagNode））;//给头指针分配空间
pNodepTemp=NULL;
inttemp;
head->pNext=NULL;//比较好的习惯就是分配好空间，马上赋值
printf（"请输入要放入链表中的数据，以-1结尾：
"）;
//读入数据，以-1结尾，把数据插入链表中
scanf（"%d",&temp）;
while（temp!
=-1）
{
pTemp=（pNode）malloc（sizeof（structtagNode））;
pTemp->data=temp;
pTemp->pNext=NULL;
insertList（head,pTemp）;
scanf（"%d",&temp）;
}
printf（"降序排列的链表为：
\n"）;
printLinkedList（head）;
printf（"\n"）;
//下面的代码当删除函数编写成功后，可以取消注释，让其执行,主要是调用函数实现链表结点的删除
//printf（"请输入要删除数，以-1结尾：
"）;
//scanf（"%d",&temp）;
//while（temp!
=-1）
//{
//delformList（head,temp）;
//scanf（"%d",&temp）;
//}
//printf（"删除节点后，链表中剩余数据为：
"）;
//printLinkedList（head）;
//printf（"\n"）;
}
四、思考与提高
试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点？
库函数载和常量定义：
（代码,C++）
#include
usingnamespacestd;
constintMaxSize=100;
（1）顺序表存储结构的定义（类的声明）：
（代码）
template//定义模板类SeqList
classSeqList
{
public:
SeqList（）;//无参构造函数
SeqList（datatypea[],intn）;//有参构造函数
~SeqList（）{};//析构函数为空
intLength（）;//求线性表的长度
datatypeGet（inti）;//按位查找，取线性表的第i个元素
intLocate（datatypeitem）;//查找元素item
voidInsert（inti,datatypeitem）;//在第i个位置插入元素item
datatypeDelete（inti）;//删除线性表的第i个元素
voiddisplay（）;//遍历线性表，按序号依次输出各元素
private:
datatypedata[MaxSize];//存放数据元素的数组
intlength;//线性表的长度
};
（2）初始化顺序表算法实现（不带参数的构造函数）
/*
*输入：
无
*前置条件：
顺序表不存在
*功能：
构建一个顺序表
*输出：
无
*后置条件：
表长为0
*/
实现代码：
template
SeqList:
:
SeqList（）
{
length=0;
}
（3）顺序表的建立算法（带参数的构造函数）
/*
*输入：
顺序表信息的数组形式a[],顺序表长度n
*前置条件：
顺序表不存在
*功能：
将数组a[]中元素建为长度为n的顺序表
*输出：
无
*后置条件：
构建一个顺序表
*/
实现代码：
template
SeqList:
:
SeqList（datatypea[],intn）
{
if（n>MaxSize）
{
cout<<"数组元素个数不合法"<}
for（inti=0;idata[i]=a[i];
length=n;
}（4）在顺序表的第i个位置前插入元素e算法
/*
*输入：
插入元素e,插入位置i
*前置条件：
顺序表存在，i要合法
*功能：
将元素e插入到顺序表中位置i处
*输出：
无
*后置条件：
顺序表插入新元素，表长加1
*/
实现代码：
template
voidSeqList:
:
Insert（inti,datatypeitem）
{
intj;
if（length>=MaxSize）
{
cout<<"溢出"<}
if（i<1||i>length+1）
{
cout<<"i不合法！
"<}
for（j=length;j>=i;j--）
data[j]=data[j-1];
data[i-1]=item;
length++;
}（5）删除线性表中第i个元素算法
/*
*输入：
要删除元素位置i
*前置条件：
顺序表存在,i要合法
*功能：
删除顺序表中位置为i的元素
*输出：
无
*后置条件：
顺序表册除了一个元素，表长减1
*/
实现代码：
template
datatypeSeqList:
:
Delete（inti）
{
intitem,j;
if（length==0）
{
cout<<"表为空,无法删除元素!
"<}
if（i<1||i>length）
{
cout<<"i不合法!
"<}
item=data[i-1];//获得要删除的元素值
for（j=i;jdata[j-1]=data[j];//注意数组下标从0记
length--;
returnitem;
}（6）遍历线性表元素算法
/*
*输入：
无
*前置条件：
顺序表存在
*功能：
顺序表遍历
*输出：
输出所有元素
*后置条件：
无
*/
实现代码：
template
voidSeqList:
:
display（）
{
if（length==0）
{
cout<<"表为空，无法输出!
"<}
for（inti=0;i{
cout<}
}
（7）获得线性表长度算法
/*
*输入：
无
*前置条件：
顺序表存在
*功能：
输出顺序表长度
*输出：
顺序表长度
*后置条件：
无
*/
实现代码：
template
intSeqList:
:
Length（）
{
returnLength;
}
（8）在顺序线性表中查找e值，返回该元素的位序算法
/*
*输入：
查询元素值e
*前置条件：
顺序表存在
*功能：
按值查找值的元素并输出位置
*输出：
查询元素的位置
*后置条件：
无
*/
实现代码：
template
intSeqList:
:
Locate（datatypeitem）
{
for（inti=0;iif（data[i]==item）
returni+1;
//下标为i的元素等于item，返回其序号i+1
return0;//查找失败
}
（9）获得顺序线性表第i个元素的值
/*
*输入：
查询元素位置i
*前置条件：
顺序表存在，i要合法
*功能：
按位查找位置为i的元素并输出值
*输出：
查询元素的值
*后置条件：
无
*/
实现代码：
template
datatypeSeqList:
:
Get（inti）
{
if（i<0||i>length）
{
cout<<"i不合法!
"<}
elsereturndata[i-1];
}
（10）判表空算法
/*
*输入：
无
*前置条件：
无
*功能：
判表是否为空
*输出：
为空返回1，不为空返回0
*后置条件：
无
*/
实现代码：
template
boolSeqList:
:
Empty（）
{
if（length==0）
{
return1;
}
else
{
return0;
}
}
（11）求直接前驱结点算法
/*
*输入：
要查找的元素e，待存放前驱结点值e1
*前置条件：
无
*功能：
查找该元素的所在位置，获得其前驱所在位置。
*输出：
返回其前驱结点的位序。
*后置条件：
e1值为前驱结点的值
*/
实现代码：
template
intSeqList:
:
Pre（datatypeitem）
{
intk=Locate（item）-1;
if（k>0）
returnk;
else
{
cout<<"无前驱结点！
"<return0;
}
}
（12）求直接后继结点算法
/*
*输入：
要查找的元素e，待存放后继结点值e1
*前置条件：
无
*功能：
查找该元素的所在位置，获得其后继所在位置。
*输出：
返回其后继结点的位序。
*后置条件：
e1值为后继结点
升级会员 