大数据结构实验报告材料顺序表与链表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/*线性表的单链表存储*/
}LNod
升级会员 