线性表实验代码.docx
- 文档编号:18222635
- 上传时间:2023-08-14
- 格式:DOCX
- 页数:16
- 大小:17.80KB
线性表实验代码.docx
《线性表实验代码.docx》由会员分享,可在线阅读,更多相关《线性表实验代码.docx(16页珍藏版)》请在冰点文库上搜索。
线性表实验代码
#include
#include
#include
#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量
#defineLISTINCREMENT10//线性表存储空间的分配增量
typedefintElemType;
typedefenum{FALSE,TURE}Status;
/*顺序表*/
typedefstruct
{
ElemType*elem;//存储空间的基址
intlength;//当前长度
intlistsize;//当前分配的容量
}SqList;
StatusInitList_Sq(SqList*L)//建表
{
L->elem=(ElemType*)calloc(LIST_INIT_SIZE,sizeof(ElemType));
if(!
L->elem)exit(0);//申请空间失败
L->length=0;//空表长度为0
L->listsize=LIST_INIT_SIZE;//初始的存储容量
returnTURE;
}//InitList_Sq
StatusListInsert_Sq(SqList*L,inti,ElemTypee)//插入元素
{
//在顺序线性表L中第i个位置之前插入新的元素e,i的合法值为1<=i<=L->length.
ElemType*newbase,*q,*p;
if(i<1||i>L->length+1)returnFALSE;//i数值不合法
if(L->length>=L->listsize)//判断存储空间是否满了,如果满了就增加分配
{
newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
if(!
newbase)exit(0);
L->elem=newbase;
L->listsize+=LISTINCREMENT;
}
q=&(L->elem[i-1]);
for(p=&(L->elem[L->length-1]);p>=q;--p)*(p+1)=*p;//移动插入位置之后的元素
*q=e;
++L->length;
returnTURE;
}//ListInsert_Sq
StatusListDelete_Sq(SqList*L,inti,ElemType*e)//在顺序表L中删除第i个元素,并用e返回其值
{
ElemType*p,*q;
if(i<1||i>L->length)returnFALSE;//i值不合法
q=&(L->elem[i-1]);
e=q;
for(p=&(L->elem[L->length-1]),q++;q<=p;q++)*(q-1)=*q;//删除元素,左移后面的元素
--L->length;
returnTURE;
}//ListDelete_Sq
intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))
{
//在顺序线性表L中查找第1个值为e满足compare()的元素的位序,若找到,返回在L中的位序,否则返回0
inti=1;
ElemType*p=L.elem;
while(i<=L.length&&!
(*compare)(*p++,e))++i;
if(i<=L.length)returni;
elsereturn0;
}//LocateElem_Sq
StatusnumCompare(ElemTypep,ElemTypeq)//比较函数
{
if(p==q)returnTURE;
elsereturnFALSE;
}
voidprint_List(SqList*L,void(*printElemType)(ElemType))//输出整个表L,用到函数指针
{
inti;
for(i=0;i
{
(*printElemType)(L->elem[i]);
putchar('\n');
}
}
voidprintElem(ElemTypee)//输出一个元素
{
printf("%-8d",e);
}
/*线性链表----双向链表*/
typedefstructLNode{//结点类型
structLNode*prior;
ElemTypedata;
structLNode*next;
}LNode,*Link;
typedefstruct{//链表类型
Linkhead,tail;//分别指向线性链表中的头结点和最后一个结点
intlength;//指示线性表中数据元素的个数
}LinkList;
StatusMakeNode(LNode**p,ElemTypee)//动态申请一个结点
{
if((*p=(LNode*)malloc(sizeof(ElemType)))!
=NULL)
{
(*p)->data=e;
returnTURE;
}
elsereturnFALSE;
}
StatusInitList_LL(LinkList*LL)//初始化链表
{
LNode*p;
ElemTypee=0;
if(!
MakeNode(&p,e))returnFALSE;//建立头结点
LL->head=LL->tail=p;
p->prior=p->next=p;
LL->length=0;
returnTURE;
}//InitList_LL
LinkLocateElem_LL(LinkListLL,ElemTypee,Status(*compare)(ElemType,ElemType))
{
//在链表LL中查找第1个值为e满足compare()的元素的结点,若找到,返回其地址
Linkp=LL.head->next;
while(p!
=LL.head&&!
(*compare)(e,p->data))p=p->next;
if((*compare)(e,p->data)==TURE)returnp;
elsereturnNULL;
}//LocateElem_LL
StatusListInsert_LL(LinkList*LL,inti,ElemTypee)
{
//在带头结点的链表第i个位置插入结点,存放元素e
Linkp,p1;
intj;
p1=LL->head;
if(!
MakeNode(&p,e))returnFALSE;//申请结点
if(i>LL->length+1||i<1)returnFALSE;//判断i的合法性
if(i==LL->length+1)//当插入到表尾的情况
{
p->prior=LL->tail;
p->next=LL->head;
LL->tail->next=p;
LL->tail=p;
}
else
{
for(j=0;jnext;//插入到其他位置时的情况,先将p1指向第i个有效结点
p->prior=p1->prior;
p->next=p1;
p1->prior->next=p;
p1->prior=p;
}
LL->length++;
returnTURE;
}//ListInsert_LL
StatusListDelete_LL(LinkList*LL,inti,Links)
{
//删除链表中第i个有效结点
intj;
Linkp=LL->head;
if(i>LL->length||i<1)returnFALSE;//判断i的合法性
for(j=0;jnext;//先将p1指向第i个有效结点
p->prior->next=p->next;
p->next->prior=p->prior;
*s=*p;
LL->length--;
returnTURE;
}//ListDelete_LL
voidprint_LL(LinkList*LL,void(*printElemType)(ElemType))
{
inti;
LNode*p=LL->head->next;
if(LL->length==0)printf("\n表中没有元素!
\n");
else
{
for(i=0,p=LL->head->next;i
{
(*printElemType)(p->data);
p=p->next;
printf("\n");
}
}
}//print_LL
voidzhuJieMian()
{
printf("***********************************************************\n"
"*****************线性表*****************\n"
"****---------------------------------------------------****\n"
"****-------------------****\n"
"****------1------顺序表-----------------****\n"
"****-------------------****\n"
"****------2------链表-----------------****\n"
"****-------------------****\n"
"****------0------退出-----------------****\n"
"****-------------------****\n"
"****~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~****\n"
"*************请输入各个功能对应得数字*****************\n"
"-----------------------------------------------------------\n"
);
}
voidshunXuBiao()
{
printf("***********************************************************\n"
"*****************顺序表*****************\n"
"****---------------------------------------------------****\n"
"****------1------插入-----------------****\n"
"****------2------删除-----------------****\n"
"****------3------查询-----------------****\n"
"****------4------输出-----------------****\n"
"****------5------表长-----------------****\n"
"****------0------退出-----------------****\n"
"****~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~****\n"
"*************请输入各个功能对应得数字*****************\n"
"-----------------------------------------------------------\n"
);
}
voidlianBiao()
{
printf("***********************************************************\n"
"*****************链表*****************\n"
"****---------------------------------------------------****\n"
"****------1------插入-----------------****\n"
"****------2------删除-----------------****\n"
"****------3------查询-----------------****\n"
"****------4------输出-----------------****\n"
"****------5------表长-----------------****\n"
"****------0------退出-----------------****\n"
"****~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~****\n"
"*************请输入各个功能对应得数字*****************\n"
"-----------------------------------------------------------\n"
);
}
voidmain()
{
SqListL;
LinkListLL;
intchoice;
inti;
InitList_LL(&LL);
InitList_Sq(&L);
for(i=1;i<=10;i++)
{
ListInsert_LL(&LL,i,i);
ListInsert_Sq(&L,i,i*10);
}
do
{
zhuJieMian();
printf("请输入:
");
scanf("%d",&choice);
switch(choice)
{
case1:
{
intchoice;
system("cls");
do
{
shunXuBiao();
printf("请输入:
");
scanf("%d",&choice);
switch(choice)
{
case1:
{
inti;
ElemTypee;
printf("\n进行插入操作!
\n");
printf("请输入要插入元素的值:
");
scanf("%d",&e);
printf("请输入要将该元素插入的位置:
");
scanf("%d",&i);
if(ListInsert_Sq(&L,i,e))printf("插入成功!
\n");
elseprintf("插入失败!
\n");
system("PAUSE");
}
break;
case2:
{
inti;
ElemTypee;
printf("\n进行删除操作!
\n");
printf("请输入将要删除元素的的位置:
");
scanf("%d",&i);
if(ListDelete_Sq(&L,i,&e))printf("删除成功!
\n");
elseprintf("删除失败!
\n");
system("PAUSE");
}
break;
case3:
{
intlocation;
ElemTypee;
printf("\n进行查找工作!
\n");
printf("请输入要查找的值:
");
scanf("%d",&e);
if(location=LocateElem_Sq(L,e,numCompare))
printf("该值在表中第%d的位置!
\n",location);
elseprintf("该表中没有该值!
\n");
system("PAUSE");
}
break;
case4:
{
printf("表里元素如下:
\n");
print_List(&L,printElem);
system("PAUSE");
}break;
case5:
{
printf("\n顺序表表长为**%d**!
\n",L.length);
system("PAUSE");
}
break;
case0:
break;
default:
printf("输入有误,请重新输入!
\n");system("PAUSE");break;
}
system("cls");
}while(choice);
}
break;
case2:
{
intchoice;
system("cls");
do
{
lianBiao();
printf("请输入:
");
scanf("%d",&choice);
switch(choice)
{
case1:
{
inti;
ElemTypee;
printf("\n进行插入操作!
\n");
printf("请输入要插入元素的值:
");
scanf("%d",&e);
printf("请输入要将该元素插入的位置:
");
scanf("%d",&i);
if(ListInsert_LL(&LL,i,e))printf("插入成功!
\n");
elseprintf("插入失败!
\n");
system("PAUSE");
}
break;
case2:
{
inti;
LNodee;
printf("\n进行删除操作!
\n");
printf("请输入将要删除元素的的位置:
");
scanf("%d",&i);
if(ListDelete_LL(&LL,i,&e))printf("删除成功!
\n");
elseprintf("删除失败!
\n");
system("PAUSE");
}break;
case3:
{
Linklocation;
ElemTypee;
printf("\n进行查找工作!
\n");
printf("请输入要查找的值:
");
scanf("%d",&e);
if(location=LocateElem_LL(LL,e,numCompare))
printf("该值在表中位置的地址为---%d---!
\n,结点中存的值为%d.\n",location,location->data);
elseprintf("该表中没有该值!
\n");
system("PAUSE");
}
break;
case4:
{
print_LL(&LL,printElem);
printf("\n");
system("PAUSE");
}break;
case5:
{
printf("\n链表长为**%d**!
\n",LL.length);
system("PAUSE");
}break;
case0:
break;
default:
printf("输入有误,请重新输入!
\n");system("PAUSE");break;
}
system("cls");
}while(choice);
}
break;
case0:
break;
default:
printf("输入有误,请重新输入!
\n");system("PAUSE");break;
}
system("cls");
}while(choice);
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 实验 代码
![提示](https://static.bingdoc.com/images/bang_tan.gif)