1 逆向链表
逆向链表是将一个单向链表进行转置,使其头变尾,尾变头,各个结点指向它的前个结点;
void ReverseList(node**head)
{
node*p,*q,*r;
p=*head;
q=p->next;
while(q!=NULL)
{
r=q->next;
q->next=p;
p=q;
q=r;
}
(*head)->next=NULL;
*head=p;
}
2 链表排序
指针不变,值改变;
void SortList(node*head)
{
node*p,*q,*s;
int t;
p=head;
while(p)
{
s=p;
q=p->next;
while(q)
{
if(q->value<s->value)
{
s=q;
}
q=q->next;
}
if(s!=p)
{
t=s->value;
s->value=p->value;
p->value=t;
}
p=p->next;
}
}
3 链栈
//创建栈,并初始化
int CreateStack(node**stack)
{
*stack=NULL;
return 1;
}
//入栈
int Push(node**stack,void*data)
{
node* elem;
elem=(node*)malloc(sizeof(node));
if(!elem)
{
return 0;
}
elem->data=data;
elem->next=*stack;
*stack=elem;
return 1;
}
//出栈
int Pop(node**stack,void**data)
{
node*elem;
if((elem=*stack)==NULL)
{
return 0;
}
*data=elem->data;
*stack=elem->next;
free(elem);
return 1;
}
//销毁栈
int DeleteStack(node**stack)
{
node* next;
while(*stack)
{
next=(*stack)->next;
free(*stack);
*stack=NULL;
}
return 1;
}
5 链队
typedef struct Qnode_
{
int data;
struct Qnode_*next;
}Qnode;
Qnode*front;//队头指针
Qnode*rear;//队尾指针
//创建队列
int CreateQue(Qnode**que)
{
*que=NULL;
front=rear=NULL;
return 1;
}
//销毁队列
int DeleteQue(Qnode**que)
{
Qnode*next;
while(*que)
{
next=(*que)->next;
free(*que);
*que=next;
}
return 1;
}
//尾插
int EnQueue(int*e)
{
Qnode*p;
p=(Qnode*)malloc(sizeof(Qnode));
if(p==NULL)
{
return 0;
}
p->data=*e;
p->next=NULL;
if(rear==front)
{
front=rear=p;
}
else
{
rear->next=p;
rear=p;
}
return 1;
}
//队头出队
int DeQueue(int*e)
{
Qnode*p;
if(front==rear)
{
return 0;
}
p=front->next;
*e=p->data;
front->next=p->next;
if(p==rear)
{
front=rear;
}
free(p);
return 1;
}
6 链表删除结点
int Delete(node*elem)
{
node*curPos=head;
//特殊情况1:欲删除的结点为NULL
if(elem==NULL)
return 0;
//特殊情况2:欲删除的结点为head
if(elem==head)
{
head=elem->next;
free(elem);
if(head==NULL)
{
tail=NULL;
}
return 1;
}
while(curPos)
{
if(curPos->next==elem)
{
curPos->next=elem->next;
free(elem);
//特殊情况3:删除的结点是tail
if(curPos->next==NULL)
{
tail=curPos;
}
return 1;
}
curPos=curPos->next;
}
return 0;
}
7 链表插入新结点
int InsertAfter(node*elem,int data)
{
node*newElem,*curPos=head;
newElem=(node*)malloc(sizeof(node));
if(newElem==NULL)
{
return 0;
}
newElem->data=data;
if(elem==NULL)
{
newElem->next=head;
head=newElem;
if(tail==NULL)
{
tail=newElem;
}
return 1;
}
while(curPos)
{
if(curPos==elem)
{
newElem->next=curPos->next;
curPos->next=newElem;
if(newElem->next==NULL)
{
tail=newElem;
}
return 1;
}
curPos=curPos->next;
}
free(newElem);
return 0;
}
8 判断单向链表是否存在循环
算法:使用步长法判断链表是否存在循环,设置两个遍历,第一个遍历步长是第二个遍历的步长的两倍,如果这两个遍历相遇,则单向链表有环路;
int FindLoop(node*head)
{
node*p;
node*q;
if(head==NULL)
{
return 0;
}
p=head;
q=head->next;
while(q!=NULL&&q->next!=NULL&&p!=q)
{
p=p->next;
q=q->next->next;
}
if(p==q)
{
return 1;
}
else
{
return 0;
}
}
9 找出倒数第m个元素
1 给定一个单向链表,高效算法找出链表中的倒数第m个元素:
2 规定:当m=0,链表的最后一个元素将被返回;
3 分析:
假设有n个元素,倒数第m个元素即正数的第n-m个元素;
4 思路:
声明两个指针,一个指针首先遍历m个元素,第二个指针与第一个指针同时遍历链表,直到第一个指针遍历结束,第一个指针遍历了剩下的n-m个元素,第二个指针遍历到了第n-m个元素;
node* FindMToLastElement(node*head,int m)
{
node*current,*mBehind;
int i;
//current指针向后移动m个元素
current=head;
for(int i=0;i<m;i++)
{
if(current->next)
{
current=current->next;
}
else
{
return NULL;
}
}
//mBehind从头开始,与current一起向后移动
mBehind=head;
while(current->next)
{
current=current->next;
mBehind=mBehind->next;
}
//此时,current向后移动了n-m个元素,而mBehind和current向后移动了n-m个元素,刚好为倒数第m个元素
return mBehind;
}
|