链表试题算法.docx
《链表试题算法.docx》由会员分享,可在线阅读,更多相关《链表试题算法.docx(27页珍藏版)》请在冰点文库上搜索。
链表试题算法
1链表基本操作
typedefstructmyLink
{
intdata;
structmyLink*next;
}Link;
//创建链表包含头节点
intcreatLink(Link**phead)
{
intres=0;
intnum;
Link*ptm=(Link*)malloc(sizeof(Link));
ptm->data=0;
*phead=ptm;
printf("请输入数据,以0结束!
!
!
\n");
scanf("%d",&num);
while(num!
=0)
{
Link*pNew=(Link*)malloc(sizeof(Link));
if(pNew==NULL)
{
res=-1;
printf("pNew==NULL创建链表失败error:
%d\n",res);
}
pNew->data=num;
ptm->next=pNew;
ptm=pNew;
printf("请输入数据,以0结束!
!
!
\n");
scanf("%d",&num);
}
ptm->next=NULL;
returnres;
}
//打印链表
intprintLink(Link*pHead)
{
intres=0;
Link*p=pHead->next;
if(p==NULL)
{
res=-1;
printf("printfLink()err:
%d链表为空打印失败\n",res);
returnres;
}
while(p!
=NULL)
{
printf("data=%d\n",p->data);
p=p->next;
}
returnres;
}
//插入链表在data=x的前面插入data=y;
intinsertLink(Link*pHead,intx,inty)
{
intres=0;
if(pHead==NULL)
{
res=-1;
printf("pHead==NULLinsertLink()err:
%d\n",res);
returnres;
}
Link*pNew=(Link*)malloc(sizeof(Link));
pNew->data=y;
Link*pPre=pHead;
Link*pCurr=pHead->next;
intflag=0;
while(pCurr!
=NULL)
{
if(pCurr->data==x)
{
flag=1;
break;
}
pPre=pPre->next;
pCurr=pCurr->next;
}
if(flag==0)
{
res=-2;
printf("原链表中没有%d\n",x);
returnres;
}
pNew->next=pCurr;
pPre->next=pNew;
returnres;
}
//删除链表中节点删除data=x的节点
intdeleLink(Link*pHead,intx)
{
intres=0;
if(pHead==NULL)
{
res=-1;
printf("pHead==NULLdeleLink()error:
%d\n",res);
returnres;
}
Link*pPre=pHead;
Link*pCurr=pHead->next;
intflag=0;
while(pCurr!
=NULL)
{
if(pCurr->data==x)
{
flag=1;
break;
}
pPre=pPre->next;
pCurr=pCurr->next;
}
if(flag==0)
{
res=-2;
printf("原链表中没有%d\n",x);
returnres;
}
pPre->next=pCurr->next;
returnres;
}
//反转链表
intrevertLink(Link*pHead)
{
intres=0;
if(pHead==NULL||pHead->next==NULL||pHead->next->next==NULL)
{
res=-1;
printf("pHead==NULLrevertLink()error:
%d\n",res);
returnres;
}
Link*pPre=pHead->next;
Link*pCurr=pHead->next->next;
Link*q=NULL;
while(pCurr!
=NULL)
{
q=pCurr->next;
pCurr->next=pPre;
pPre=pCurr;
pCurr=q;
}
pHead->next->next=NULL;
pHead->next=pPre;
returnres;
}
//链表排序
//再创建一个空链表从原链表中找到最大值的那个节点然后往空链表里添加
intsortLink(Link*pHead,Link**pHead1)
{
intres=0;
Link*pNewHead=(Link*)malloc(sizeof(Link));
pNewHead->data=0;
Link*pNewTail=pNewHead;
if(pHead==NULL)
{
res=-1;
printf("pHead==NULLsortLink()erro:
%d\n",res);
returnres;
}
//先从原链表里找出最大值的那个节点
start:
{
Link*pMax=pHead->next;
Link*pPre=pHead;
Link*pCurr=pMax->next;
while(pCurr!
=NULL)
{
if(pCurr->data>pMax->data)
{
pPre=pMax;
pMax=pCurr;
}
pCurr=pCurr->next;
}
pPre->next=pMax->next;//让最大的那个节点脱离原链表
if(pNewHead->next==NULL)
{
pNewHead->next=pMax;
pNewTail=pMax;
pMax->next=NULL;
}
else
{
pNewTail->next=pMax;
pNewTail=pMax;
pMax->next=NULL;
}
if(pHead->next==NULL)//所有的节点都脱离了原链表
{
gotosortEnd;
}
gotostart;
}
sortEnd:
*pHead1=pNewHead;
returnres;
}
intdestoryLink(Link**pHead)
{
intres=0;
if(pHead==NULL)
{
res=-1;
printf("pHead==NULL链表为空释放内存失败erro:
%d\n",res);
returnres;
}
Link*pt=*pHead;
while(pt!
=NULL)
{
Link*tmp=pt->next;
free(pt);
pt=tmp;
}
*pHead=NULL;
returnres;
}
//测试案例
voidmain()
{
Link*pHead=NULL;
intres;
res=creatLink(&pHead);
if(res!
=0)
{
printf("functioncreatLink()err:
%d\n",res);
gotoEnd;
}
res=printLink(pHead);
if(res!
=0)
{
printf("functionprintLink()err:
%d\n",res);
gotoEnd;
}
printf("****************在3的前面插入4**************************\n");
res=insertLink(pHead,3,4);
if(res!
=0)
{
printf("functioninsetrLink()err:
%d\n",res);
gotoEnd;
}
res=printLink(pHead);
if(res!
=0)
{
printf("functionprintLink()err:
%d\n",res);
gotoEnd;
}
printf("****************删除data=4的节点**************************\n");
res=deleLink(pHead,4);
if(res!
=0)
{
printf("functiondeleLink()err:
%d\n",res);
gotoEnd;
}
res=printLink(pHead);
if(res!
=0)
{
printf("functionprintLink()err:
%d\n",res);
gotoEnd;
}
printf("****************逆转链表**************************\n");
res=revertLink(pHead);
if(res!
=0)
{
printf("functionrevertLink()err:
%d\n",res);
gotoEnd;
}
res=printLink(pHead);
if(res!
=0)
{
printf("functionprintLink()err:
%d\n",res);
gotoEnd;
}
printf("****************从大到小排序链表**************************\n");
Link*pHead1=NULL;
res=sortLink(pHead,&pHead1);
if(res!
=0)
{
printf("functionsortLink()err:
%d\n",res);
gotoEnd;
}
res=printLink(pHead1);
if(res!
=0)
{
printf("functionprintLink()err:
%d\n",res);
gotoEnd;
}
End:
if(pHead!
=NULL)
{
res=destoryLink(&pHead);
if(res!
=0)
{
printf("functiondestoryLink()iserror:
%d\n",res);
return;
}
}
system("pause");
}
2、单链表的建立,把‘a’--‘z’26个字母插入到链表中,并且倒叙,还要打印
#include
#include
typedefstructval
{
chardata;
structval*next;
}node,*p;
voidmain(void)
{
node*p=NULL;
node*q=NULL;
node*head=(node*)malloc(sizeof(node));
head->data='';
head->next=NULL;
node*first=(node*)malloc(sizeof(node));
first->data='a';
first->next=NULL;
head->next=first;
p=first;
intlongth='z'-'b';
inti=0;
while(i<=longth)
{
node*temp=(node*)malloc(sizeof(node));
temp->data='b'+i;
temp->data=NULL;
//开始逆转
q=temp;
head->next=temp;
temp->next=p;
p=q;
i++;
}
//打印链表
node*tmp=head->next;
while(tmp!
=NULL)
{
printf("data:
%c",tmp->data);
tmp=tmp->next;
}
}
3约瑟夫问题循环链表
.h文件
#ifndef_CIRCLELIST_H_
#define_CIRCLELIST_H_
typedefvoidCircleList;
/*
typedefstruct_tag_CircleListNodeCircleListNode;
struct_tag_CircleListNode
{
CircleListNode*next;
};
*/
typedefstruct_tag_CircleListNode
{
struct_tag_CircleListNode*next;
}CircleListNode;
CircleList*CircleList_Create();
voidCircleList_Destroy(CircleList*list);
voidCircleList_Clear(CircleList*list);
intCircleList_Length(CircleList*list);
intCircleList_Insert(CircleList*list,CircleListNode*node,intpos);
CircleListNode*CircleList_Get(CircleList*list,intpos);
CircleListNode*CircleList_Delete(CircleList*list,intpos);
//add
CircleListNode*CircleList_DeleteNode(CircleList*list,CircleListNode*node);
CircleListNode*CircleList_Reset(CircleList*list);
CircleListNode*CircleList_Current(CircleList*list);
CircleListNode*CircleList_Next(CircleList*list);
#endif
C.文件
#include
#include
#include"circleList.h"
typedefstruct_tag_CircleList
{
CircleListNodeheader;
CircleListNode*slider;
intlength;
}TCircleList;
CircleList*CircleList_Create()//O
(1)
{
TCircleList*ret=(TCircleList*)malloc(sizeof(TCircleList));
if(ret==NULL)
{
returnNULL;
}
ret->length=0;
ret->header.next=NULL;
ret->slider=NULL;
returnret;
}
voidCircleList_Destroy(CircleList*list)//O
(1)
{
if(list==NULL)
{
return;
}
free(list);
}
voidCircleList_Clear(CircleList*list)//O
(1)
{
TCircleList*sList=(TCircleList*)list;
if(sList==NULL)
{
return;
}
sList->length=0;
sList->header.next=NULL;
sList->slider=NULL;
}
intCircleList_Length(CircleList*list)//O
(1)
{
TCircleList*sList=(TCircleList*)list;
intret=-1;
if(list==NULL)
{
returnret;
}
ret=sList->length;
returnret;
}
intCircleList_Insert(CircleList*list,CircleListNode*node,intpos)//O(n)
{
intret=0,i=0;
TCircleList*sList=(TCircleList*)list;
if(list==NULL||node==NULL||pos<0)
{
return-1;
}
//if(ret)
{
CircleListNode*current=(CircleListNode*)sList;
for(i=0;(inext!
=NULL);i++)
{
current=current->next;
}
//current->next0号节点的地址
node->next=current->next;//1
current->next=node;//2
//若第一次插入节点
if(sList->length==0)
{
sList->slider=node;
}
sList->length++;
//若头插法
if(current==(CircleListNode*)sList)
{
//获取最后一个元素
CircleListNode*last=CircleList_Get(sList,sList->length-1);
last->next=current->next;//3
}
}
returnret;
}
CircleListNode*CircleList_Get(CircleList*list,intpos)//O(n)
{
TCircleList*sList=(TCircleList*)list;
CircleListNode*ret=NULL;
inti=0;
if(list==NULL||pos<0)
{
returnNULL;
}
//if((sList!
=NULL)&&(pos>=0)&&(sList->length>0))
{
CircleListNode*current=(CircleListNode*)sList;
for(i=0;i{
current=current->next;
}
ret=current->next;
}
returnret;
}
CircleListNode*CircleList_Delete(CircleList*list,intpos)//O(n)
{
TCircleList*sList=(TCircleList*)list;
CircleListNode*ret=NULL;
inti=0;
if((sList!
=NULL)&&(pos>=0)&&(sList->length>0))
{
CircleListNode*current=(CircleListNode*)sList;
CircleListNode*last=NULL;
for(i=0;i{
current=current->next;
}
//若删除第一个元素
if(current==(CircleListNode*)sList)
{
last=(CircleListNode*)CircleList_Get(sList,sList->length-1);
}
//求要删除的元素
ret=current->next;
current->next=ret->next;
sList->length--;
//判断链表是否为空
if(last!
=NULL)
{
sList->header.next=ret->next;
last->next=ret->next;
}
//若删除的元素为游标所指的元素
if(s