[Data Structure]数据结构学习之链表小结[中]---经典问题
4基于指针的链表的求逆算法:
(注:以下这些代码全部由Emil Matthew :思考+实现+测试)
/*
All these code -------thinked ,coded , testd by EmilMatthew,You can modify and use them as you wish, but I do not promise these code can fit all your needs.
05/09/12
*/
/*
All these code -------thinked ,coded , testd by EmilMatthew,You can modify and use them as you wish, but I do not promise these code can fit all your needs.
05/09/12
*/
//求逆算法1:递归版本
//Coded by EmilMatthew 05/9/08
先深度优先探到底,然后从后往前做反转的动作,即: (*inNode)->link->link=*inNode;
最后把头指针指向尾部即可,这里通过在参数列表中增加一个指针参数来实现.
void reverseLinkList(PNode* inNode,int iterLevel,PNode* lastNode)
{
assertF((*inNode)!=NULL,"in reverseLinkList sub,*inNode is null\n");
if((*inNode)->link!=NULL)
{
reverseLinkList(&((*inNode)->link),iterLevel+1,lastNode);
}
else
{
*lastNode=*inNode;
return;
}
(*inNode)->link->link=*inNode;
if(iterLevel==0)
{
(*inNode)->link=NULL;
*inNode=*lastNode;
}
}
//求逆算法:非递归版本:
//Coded by EmilMattehw 05/9/11
与前一个递归版本从后往前做不同,这个非递归版本则是从前往后来实现的.主要需要三个指针,pre , mid , last ,
核心的是这样的一个过程:
last=mid->link;//save mid's next node
mid->link=pre;//point to pre node
pre=mid;//update pre,move forward.
mid=last;//update mid,move forward.
主要实现的是将mid指向其前驱的过程,并准备好下一个结点的反转工作.
当然,在开始的时候及结束时都需要做一些工作.(具体见代码)
void reverseLinkList2(PNode* head)
{
PNode pre,mid,last;
assertF(head!=NULL,"pass in node is null\n");
pre=(PNode)malloc(sizeof(struct Node));
mid=(PNode)malloc(sizeof(struct Node));
last=(PNode)malloc(sizeof(struct Node));
assertF(pre!=NULL&&mid!=NULL&&last!=NULL,"mem apply failure\n");
if((*head)->link)//node num from 2...n.If there is only one node ,there is no need to do this.
{ //prepare for the iterator
pre=*head;
mid=(*head)->link;
//main loop body
while(mid->link)
{
last=mid->link;//save mid's next node
mid->link=pre;//point to pre node
pre=mid;//update pre,move forward.
mid=last;//update mid,move forward.
}
/* these code are no needed.
assertF(mid->link==NULL,"out of iteratro,mid->next!=NULL\n");
len=2: mid->link==null,
len>2: mid->link!=null.
*/
//rear consult.
mid->link=pre;
//head consult.
(*head)->link=NULL;
*head=mid;
}
pre=NULL;
mid=NULL;
last=NULL;
}
5将一个链表中所有重复的元素全部删除,直至最后形成一个没有相异元素的链表.
这个问题的思路也是简单的,我准备一个达到链表长度的数组,来存放所有不同元素的值.然后将指向链表头的指针从头往链表尾搜索,将每次搜索到当前结点中的值与记录数组中的值比较,如果结点中的值与记录数组中的元素有重复,那么就将当前结点退链,这显然需要一个指向当前结点前驱的结点来配合.而如果结点中的值与记录数组中的元素没有重复,则将这个相异元素的值加入到记录数组中,然后将链表继续后移.就是这样:
void delDifferentDataInLinkList(LinkList inSeqList)
{
Type* tmpAns;
int len;
int count;
int flag,i;//aid value in iterator
PNode tmpNode,aidNode,delNode;
len=getLinkListLen(inSeqList);
/*answer list*/
tmpAns=(Type*)malloc(sizeof(Type)*len);
/*aid pointers*/
aidNode=(PNode)malloc(sizeof(struct Node));
tmpNode=(PNode)malloc(sizeof(struct Node));
delNode=(PNode)malloc(sizeof(struct Node));
/*init data*/
aidNode=tmpNode=inSeqList;
//num of different data.
count=0;
count++;
if(tmpNode->link)//only one node ,no need to forward.
{
while(tmpNode)
{
flag=1;
for(i=0;i<count;i++)
{
if(tmpAns[i]==tmpNode->info)
{
flag=0;
break;
}
}
if(!flag)//del current node
{ //aidNode,always point to the tmpNode's preNode.
aidNode->link=tmpNode->link;
delNode=tmpNode;
tmpNode=tmpNode->link;
free(delNode);
}
else//add now differ data to answer list.
{
tmpAns[count]=tmpNode->info;
count++;
aidNode=tmpNode;
tmpNode=tmpNode->link;
}
}
}
aidNode=NULL;
delNode=NULL;
tmpNode=NULL;
}
6JosePhu问题,Jose Phu问题是这样的了个问题,一群小朋友手拉手围成一个圈子,然后从某个人开始报数,报到某个数字时,当时报数的人出圈.接下来的人继续从1开始报数,直到还剩下最后一个人为止,要求输出这个人的位置.
显然,这不是一个很难问题,用一个循环链表即可解决战斗.我在实现中遇到的最大问题在于对一些特殊情况有欠考虑,比如说报数的上限为1时我就做了特殊处理,这就要求在思考算法时,除了最通用的情况外,一定不要忘记考虑特殊情况,否则在调试上花去大量的工夫,而且,这样修改出的代码也不会显得很美观.
void JosePhuProblem(int startPosIndex,int numOfGuys,int countNum)
{
PNode myList,tmpNode,unUsedNode;
int i,j;
FILE* outputFile;
assertF(startPosIndex<numOfGuys&&startPosIndex>=0,"in JosePhuProblem,startPosIndex is error\n");
assertF(countNum>=1,"in josePhuProblem,countNum<1\n");
myList=(PNode)malloc(sizeof(struct Node));
unUsedNode=(PNode)malloc(sizeof(struct Node));
outputFile=createFile('w',"output.txt");
myList->info=0;
tmpNode=myList;
//construct the person list
for(i=1;i<numOfGuys;i++)
{
tmpNode->link=(PNode)malloc(sizeof(struct Node));
tmpNode=tmpNode->link;
tmpNode->info=i;
}
tmpNode->link=myList;//to form a circle
tmpNode=myList;
i=0;//move to the start pos
while(tmpNode&&i<startPosIndex)
{
tmpNode=tmpNode->link;
i++;
}
assertF(tmpNode!=NULL,"in jose phu problem,tmpNode is null\n");
printf("the sequence of the person de from the list:\n");
fprintf(outputFile,"the sequence of the person de from the list:\n");
i=0;
while(i<numOfGuys-1)
{
if(countNum==1)
{
unUsedNode=tmpNode;
while(tmpNode->link!=unUsedNode)//want let itself dequeue.
tmpNode=tmpNode->link;
}
else
{
j=0;
//pre tmpNode has bao shu:n=1
while(tmpNode->link&&j<countNum-2)
{
tmpNode=tmpNode->link;
j++;
}//after,in iter:tmpN=countNum-3+1=countNum-2.
assertF(tmpNode->link!=NULL,"in jose phu problem,tmpNode is null\n");
unUsedNode=tmpNode->link;
}
tmpNode->link=tmpNode->link->link;
//output the info of the deList person.
printf("%d-",unUsedNode->info);
fprintf(outputFile,"%d-",unUsedNode->info);
free(unUsedNode);
//move to next start person.
tmpNode=tmpNode->link;
//process control,only need n-1 num of person de from the list.
i++;
}
//output the last node
printf("%d",tmpNode->info);
fprintf(outputFile,"%d-",tmpNode->info);
fprintf(outputFile,"\r\n");
printf("\n");
//reoutput the last person.
assertF(tmpNode!=NULL,"in jose phu problem,tmpNode is null\n");
printf("in josePhu Problem,the last person's no. is: %d\n",tmpNode->info);
fclose(outputFile);
}
7用游标来模拟最简单的内存申请与释放
游标是这样一种数据结构,首先,它是基于数组的,这个数组中的元素除了自身有个存放数据的单元外,还有一个单元是存放它指向的下一个数组中的元素的下标的.这样,就相当于基于指针中的next的实现了.而C语言中的malloc和free的基础便是基于这样的一种想法(当然,肯定是要比这复杂多的),我下面实现了基于游标的模拟C语言内存申请与释放的malloc2和free2,呵呵,还是蛮不错的.:)
typedef struct
{
Type inData;
int next;
}youBiaoNode;
youBiaoNode gVirtualMemPool[MAXLENGTH];
youBiaoNode gAvailMemListHead;
int gAvailPos;//这个变量很重要,记录了当前空闲链表中的表头在模拟内存数组中的位置,便于在下面的操作中使用.
//创建模拟中的内存区域
void constructMemPool()
{
int i=0;
//gVirtualMemPool[MAXLENGTH]
for(i=0;i<MAXLENGTH-1;i++)
{
gVirtualMemPool[i].next=i+1;
gVirtualMemPool[i].inData=i+100;
}
gVirtualMemPool[i].next=-1;
gVirtualMemPool[i].inData=i+100;
gAvailMemListHead=gVirtualMemPool[0];
gAvailPos=0;
}
//模以C语言的内存申请:
youBiaoNode malloc2(int applySize)
{
int i,availIndex,tmpIndex;
availIndex=gAvailPos;//starting pos,for later returning use.
/*init data*/
i=0;
assertF(gAvailMemListHead.next!=-1,"waning,no more mem space.\n");
/*to find the new applyed space's end*/
while(i<applySize-2)//only need jump applySize steps,because the first node is included.
{ //Move forward.
gAvailMemListHead=gVirtualMemPool[gAvailMemListHead.next];
i++;
}
tmpIndex=gAvailMemListHead.next;//to get the be -1 node's index.
gAvailPos=gVirtualMemPool[tmpIndex].next;
gAvailMemListHead=gVirtualMemPool[gAvailMemListHead.next];//move to the new applyed list's rear.
gAvailMemListHead=gVirtualMemPool[gAvailMemListHead.next];//move to the new avail list's head.
gVirtualMemPool[tmpIndex].next=-1;//to get the be -1 node's index,to end the new applyed list.
// traversalYouBiaoNode(gAvailMemListHead);
return gVirtualMemPool[availIndex];
}
//模拟C语言的内存释放
void free2(youBiaoNode inYouBiaoNode)
{
youBiaoNode tmpNode;//to add the unused space to the avail list's rear.
int freedHeadIndex;
freedHeadIndex=findHeadPos(inYouBiaoNode.next);
tmpNode=gAvailMemListHead;
while(tmpNode.next!=-1)
tmpNode=gVirtualMemPool[tmpNode.next];//Move.
tmpNode.next=freedHeadIndex;//add to the rear.
}
void traversalYouBiaoNode(youBiaoNode inYouBiaoNode)
{
youBiaoNode tmpNode;
tmpNode=inYouBiaoNode;
printf("===starting of traversalYouBiaoNode===\n");
while(tmpNode.next!=-1)
{
printf("%d->",tmpNode.inData);
tmpNode=gVirtualMemPool[tmpNode.next];
}
printf("%d",tmpNode.inData);
printf("\n===end of traversalYouBiaoNode===\n");
}
int findHeadPos(int targetPos)
{
int ansPos;
int i;
assertF(targetPos!=-1,"in findHeadPos,pass in targetPos is invalid\n");
for(i=0;i<MAXLENGTH;i++)
if(gVirtualMemPool[i].next==targetPos)
{
ansPos=i;
break;
}
return ansPos;
}
8多项式的链表操作
多项式或者是特别大的数组其实都可以用基于邻接表的链表来表示.数据区做两个,一个存放多项式的系数,另一个存放多项式该项的幂.就是这样.与之相关的操作有:合并两个表示多项式的链表,关于多项式链表求某点的导数值,求某两点值前的定积分.
这里主要的当然是合并操作了,和归并排序中的merge一样,这里归并的思路同样是简单的,但我在实现中遇到的最大问题却是在最后有那么一个没有用的结点多出来的,怎么办呢,用个二级指针,强指那个无效点的地址,再用*指其为null,呵呵~~~
//合并两个多项式链表:
pPolyNode mergePolyList(pPolyNode polyList1,pPolyNode polyList2)
{
pPolyNode returnNode,tmpNode;
pPolyNode* pElimate;
int firstFoundedLevel=-1,i;
int len;
tmpNode=(pPolyNode)malloc(sizeof(struct polyNode));
returnNode=tmpNode;
len=0;
while(polyList1!=0&&polyList2!=0)
{
if(polyList1->power>polyList2->power)
{
tmpNode->link=(pPolyNode)malloc(sizeof(struct polyNode));
tmpNode->power=polyList1->power;
tmpNode->argu=polyList1->argu;
if(firstFoundedLevel==-1)
{
returnNode=tmpNode;
firstFoundedLevel=1;
}
polyList1=polyList1->link;
}
else if(polyList1->power==polyList2->power)
{
tmpNode->link=(pPolyNode)malloc(sizeof(struct polyNode));
tmpNode->power=polyList1->power;
tmpNode->argu=polyList1->argu+polyList2->argu;
if(firstFoundedLevel==-1)
{
returnNode=tmpNode;
firstFoundedLevel=1;
}
polyList1=polyList1->link;
polyList2=polyList2->link;
}
else
{
tmpNode->link=(pPolyNode)malloc(sizeof(struct polyNode));
tmpNode->power=polyList2->power;
tmpNode->argu=polyList2->argu;
if(firstFoundedLevel==-1)
{
returnNode=tmpNode;
firstFoundedLevel=1;
}
polyList2=polyList2->link;
}
tmpNode=tmpNode->link;
//printf("poly1->argu:%f,poly2->argu:%f\n",polyList1->argu,polyList2->argu);
len++;
}
if(polyList1==NULL&&polyList2!=NULL)
while(polyList2!=NULL)
{
tmpNode->link=(pPolyNode)malloc(sizeof(struct polyNode));
tmpNode->power=polyList2->power;
tmpNode->argu=polyList2->argu;
polyList2=polyList2->link;
tmpNode=tmpNode->link;
len++;
}
else if(polyList2==NULL&&polyList1!=NULL)
while(polyList1!=NULL)
{
tmpNode->link=(pPolyNode)malloc(sizeof(struct polyNode));
tmpNode->power=polyList1->power;
tmpNode->argu=polyList1->argu;
polyList1=polyList1->link;
tmpNode=tmpNode->link;
len++;
}
/*rear adjust*/
pElimate=&returnNode;
for(i=0;i<len;i++)
pElimate=&((*pElimate)->link);
*pElimate=NULL;
return returnNode;
}
//计算某个x代入下的多项式的值
Type caculatePolyData(pPolyNode head,Type inArgu)
{
pPolyNode iterNode;
Type sum;
assertF(head!=NULL,"in showPolyList,the pass in head is null\n");
iterNode=(pPolyNode)malloc(sizeof(struct polyNode));
assertF(iterNode!=NULL,"in iterNode,the pass in head is null\n");
iterNode=head;
sum=0;
while(iterNode)
{
sum+=iterNode->argu*(float)pow(inArgu,(float)iterNode->power);
iterNode=iterNode->link;
}
free(iterNode);
return sum;
}
//计算某个区间上的多项式定积分的值
Type calIntegrate(pPolyNode head,Type downLimit,Type upLimit)
{
pPolyNode iterNode;
Type sum;
assertF(head!=NULL,"in showPolyList,the pass in head is null\n");
iterNode=(pPolyNode)malloc(sizeof(struct polyNode));
assertF(iterNode!=NULL,"in iterNode,the pass in head is null\n");
iterNode=head;
sum=0;
while(iterNode)
{
sum+=iterNode->argu*((float)1/(iterNode->power+1))*((float)pow(upLimit,iterNode->power+1)-(float)pow(downLimit,iterNode->power+1));
iterNode=iterNode->link;
}
//free(iterNode);
return sum;
}
//计算多项式在革个点处的导数值
Type calDy(pPolyNode head,Type inArgu)
{
pPolyNode iterNode;
Type sum;
assertF(head!=NULL,"in showPolyList,the pass in head is null\n");
iterNode=(pPolyNode)malloc(sizeof(struct polyNode));
assertF(iterNode!=NULL,"in iterNode,the pass in head is null\n");
iterNode=head;
sum=0;
while(iterNode)
{
if(iterNode->power!=0)
sum+=iterNode->argu/iterNode->power*(float)pow(inArgu,iterNode->power-1);
iterNode=iterNode->link;
}
//free(iterNode);
return sum;
}
//打印多项式链表中的内容
void showPolyList(pPolyNode head)
{
pPolyNode iterNode;
assertF(head!=NULL,"in showPolyList,the pass in head is null\n");
iterNode=(pPolyNode)malloc(sizeof(struct polyNode));
assertF(iterNode!=NULL,"in iterNode,the pass in head is null\n");
iterNode=head;
printf("===start of showPolyList===\n");
while(iterNode->link)
{
printf("%fx^%d+",iterNode->argu,iterNode->power);
iterNode=iterNode->link;
}
printf("%fx^%d\n",iterNode->argu,iterNode->power);
printf("===end of showPolyList===\n");
// iterNode->link=NULL;
// free(iterNode);
}
//得到多项式链表的长度
int getPolyListLen(pPolyNode head)
{
pPolyNode iterNode;
int count=0;
assertF(head!=NULL,"in showPolyList,the pass in head is null\n");
iterNode=(pPolyNode)malloc(sizeof(struct polyNode));
assertF(iterNode!=NULL,"in iterNode,the pass in head is null\n");
iterNode=head;
while(iterNode->link)
{
iterNode=iterNode->link;
count++;
}
return count;
}
