数据结构实验报告顺序表与链表Word文件下载.docx
- 文档编号:5575143
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:28
- 大小:21.04KB
数据结构实验报告顺序表与链表Word文件下载.docx
《数据结构实验报告顺序表与链表Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告顺序表与链表Word文件下载.docx(28页珍藏版)》请在冰点文库上搜索。
/*定义表元素的类型*/
/*
(1)---补充顺序表的存储分配表示,采用定长和可变长度存储均可*/
//基地址
//分配的空间
/*函数声明*/
intInitList_sq(Sqlist*L);
intCreateList_sq(Sqlist*L,intn);
intListInsert_sq(Sqlist*L,inti,ElemTypee);
intPrintList_sq(Sqlist*L);
intListDelete_sq(Sqlist*L,inti,ElemType*e);
intListLocate(Sqlist*L,ElemTypee,int*pos);
intmenu_select();
/*
(2)---顺序表的初始化*/
intInitList_sq(Sqlist*L)
L->
slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
if(!
L->
slist)
{
returnERROR;
}
length=0;
listsize=INIT_SIZE;
//初始空间容量
returnOK;
}/*InitList*/
/*(3)---创建具有n个元素的顺序表*/
intCreateList_sq(Sqlist*L,intn)
ElemTypee;
inti;
for(i=0;
i<
n;
i++)
printf("
inputdata%d:
"
i+1);
scanf("
%d"
&
e);
ListInsert_sq(L,i+1,e))
}/*CreateList*/
/*(4)---输出顺序表中的元素*/
intPrintList_sq(Sqlist*L)
for(i=1;
=L->
length;
%5d"
L->
slist[i-1]);
}/*PrintList*/
/*(5)---在顺序表的第i个位置之前插入新元素e*/
intListInsert_sq(Sqlist*L,inti,ElemTypee)
intk;
if(i<
1||i>
length+1)
if(L->
length>
listsize)//当前空间已满,申请新的空间
slist=(ElemType*)realloc(L->
slist,(L->
listsize+INCREM)*sizeof(ElemType));
listsize+=INCREM;
for(k=L->
length-1;
k>
=i-1;
k--)
slist[k+1]=L->
slist[k];
slist[i-1]=e;
length++;
}/*ListInsert*/
/*(6)---在顺序表中删除第i个元素,e返回删除的元素*/
intListDelete_sq(Sqlist*L,inti,ElemType*e)
intj;
length)
*e=L->
slist[i-1];
for(j=i;
j++)
slist[j-1]=L->
slist[j];
length--;
}/*ListDelete_sq*/
/*(7)---在顺序表中查找指定值元素,pos为返回其位置序号*/
intListLocate(Sqlist*L,ElemTypee,int*pos)
ElemType*end=L->
slist+L->
ElemType*p=L->
slist;
p<
end;
p++)
if(*p==e)
*pos=i;
break;
i++;
if(p>
=end)
else
}/*ListLocate*/
/*定义菜单字符串数组*/
intmenu_select()
char*menu[]={"
\n***************MENU******************\n"
"
1.CreateList\n"
/*创建顺序表*/
2.GetElement\n"
/*查找顺序表中的元素*/
3.Insertdata\n"
/*插入数据*/
4.Deletedata\n"
/*删除数据*/
0.Quit\n"
/*退出*/
};
chars[3];
/*以字符形式保存选择号*/
intc,i;
/*定义整形变量*/
for(i=0;
7;
i++)/*输出主菜单数组*/
%s"
menu[i]);
do
\nEnteryouchoice(0~4):
);
/*在菜单窗口外显示提示信息*/
s);
/*输入选择项*/
c=atoi(s);
/*将输入的字符串转化为整形数*/
while(c<
0||c>
4);
/*选择项不在0~4之间重输*/
returnc;
/*返回选择项,主程序根据该数调用相应的函数*/
}
/*主函数*/
intmain()
Sqlistsl;
InitList_sq(&
sl);
intn;
intm,k;
pleaseinputn:
/*输入顺序表的元素个数*/
n);
if(n==0)printf("
ERROR"
for(;
;
)/*无限循环*/
switch(menu_select())/*调用主菜单函数,返回值整数作开关语句的条件*/
case1:
\n1-CreateSqlist:
\n"
CreateList_sq(&
sl,n);
\nPrintSqlist:
PrintList_sq(&
case2:
\n3-GetElemfromSqlist:
pleaseinputsearchdata:
k);
intpos;
if(!
ListLocate(&
sl,k,&
pos))
Notfound"
foundtheelement,positionis%d\n"
pos);
case3:
\n4-InsertfromSqlist:
\ninputinsertlocationanddata:
(location,data)\n"
%d,%d"
m,&
if(ListInsert_sq(&
sl,m,k))
\nOK\n"
\nERROR!
case4:
\n5-DeletefromSqlist:
\npleaseinputdeletelocation\n"
intdeldata;
if(ListDelete_sq(&
deldata))
\nDeletedatais%d\n"
deldata);
\nPrintSqlist:
case0:
exit(0);
/*如菜单返回值为0程序结束*/
return0;
2、按照要求完成程序exp2_2.c,实现单链表的相关操作。
exp2_2.c部分代码如下:
/*
(1)---线性表的单链表存储表示*/
typedefstructLNode
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
LNode*InitList(LinkListL);
/*带头结点单链表初始化*/
voidPrintList(LinkListL);
/*输出带头结点单链表的所有元素*/
intGetElem(LinkListL,inti,ElemType*e);
/*查找第i位置的元素,并由e返回其值*/
intInsertElem(LinkListL,inti,ElemTypee);
/*在第i个位置插入元素e*/
intDeleteElem(LinkListL,inti,ElemType*e);
/*删除第i位置的元素,并由e返回其值*/
voidDestroyLinkList(LinkListL);
/*释放链表及其空间*/
LinkListCreateList(intn);
/*创建n个结点的单链表*/
/*菜单函数*/
/*带头结点单链表初始化*/
LNode*InitList(LinkListL)
L=(LNode*)malloc(sizeof(LNode));
/*申请一个头结点*/
L)returnERROR;
/*申请失败*/
next=NULL;
/*头结点的指针域置空*/
returnL;
/*
(1)---输出带头结点单链表的所有元素*/
voidPrintList(LinkListL)
LNode*p;
p=L->
next;
while(p!
=NULL)
p->
data);
p=p->
/*
(2)---在单链表的第i个位置插入元素e,若插入成功返回OK,插入失败返回ERROR*/
intInsertElem(LinkListL,inti,ElemTypee)
LNode*p=L,*s;
intj=0;
while(p&
&
j<
i-1)//寻找插入位置
j++;
p||j>
i-1)
s=(LNode*)malloc(sizeof(LNode));
s)
s->
data=e;
next=p->
p->
next=s;
}/*InsertElem*/
/*(3)---查找第i位置的元素,若存在返回OK并由e返回其值,若不存在返回ERROR*/
intGetElem(LinkListL,inti,ElemType*e)
intj=1;
i)
*e=p->
data;
}/*GetElem*/
/*(4)---删除第i位置的元素,成功返回OK,并由e返回其值,若不成功返回ERROR,注意删除的结点必须释放其所占空间*/
intDeleteElem(LinkListL,inti,ElemType*e)
s=p->
next=s->
*e=s->
free(s);
}/*DeleteElem*/
/*(5)---创建具有n个结点的单链表,创建成功返回其头指针*/
LinkListCreateList(intn)
LNode*p,*q,*head;
head=(LinkList)malloc(sizeof(LNode));
head->
p=head;
q=(LinkList)malloc(sizeof(LNode));
inputdata%d"
q->
q->
//节点指针域置空
next=q;
//新节点连接在表末尾
p=q;
returnhead;
voidDestroyLinkList(LinkListL)
LNode*p=L,*q;
while(p)
q=p->
free(p);
}/*DestroyLinkList*/
1.InitLinkList\n"
/*初始化链表*/
/*查找元素*/
/*插入元素*/
/*删除元素*/
5.CreateLinkList\n"
/*创建具有n个元素的链表*/
0.DestroyLinkList&
Quit\n"
/*释放链表所占空间&
退出*/
8;
\nEnteryouchoice(0~5):
5);
/*选择项不在0~5之间重输*/
inti,n;
LinkListL=NULL;
/*定义指向单链表的指针*/
/*值不同,执行的函数不同,break不能省略*/
\n1-InitLinkList:
L=InitList(L);
if(L!
\nInitLinkListOK!
\nInitLinkListError!
\n2-GetElemfromLinkList:
inputpos="
i);
if(L!
=NULL&
GetElem(L,i,&
e))
No%iis%d"
i,e);
\nPrintfList:
PrintList(L);
Error&
Notexists!
\n3-InserteintoLinkList:
inpute="
InsertElem(L,i,e))
\nInsertOK!
\nInsertError!
\n4-DeletefromLinkList:
DeleteElem(L,i,&
e);
\nDeleteError!
case5:
/*输入单链表的元素个数*/
if(n<
0)
\nCreateLinkList......\n"
L=CreateList(n);
if(L==NULL)
Error!
\nDestroylinklistandfreememory......\n"
DestroyLinkList(L);
L=NULL;
3、循环链表的应用(约瑟夫回环问题)
用整数序列1,2,3,…,n表示顺序坐在圆桌周围的人,并采用循环链表作为存储结构。
任意位置k开始计数,计到m让此位置的人出局,重复上述过程,直至只剩下最后一个人。
依次输出每个出局的人的序号。
提示:
用一个无头结点的循环单链表来实现n个元素的存储。
exp2_3.c部分代码如下:
typedefstructLNode/*线性表的单链表存储*/
}LNode,*
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 顺序