数据结构基础（一）：单链表 双链表 循环链表(二)
p2 = p3;
}
head->next = NULL;
head = p1;
return head;
}
有一个C语言用来删除单链表的头元素的函数，请找出其中的问题并加以纠正。
void RemoveHead(node* head)
{
free(head);
head = head->next;
}
当然不对，先free(head)之后，就找不到head了，下一句head = head->next 就不能正确链接了
正确答案如下：
(1)
void RemoveHead(node* head)
{
node *p;
p = head->next;
head->next = p->next;
free(p);
}
(2)
void removeHead(node* head)
{
node * p1;
p1 = head;
head = p1->next;
free(p1);
}
给出一个单链表，不知道节点N的值，怎样只遍历一次就可以求出中间节点，写出算法。
想法很巧妙：设立两个指针，比如*p和*q。每次移动两个位置，即p=p->next->next,q每次移动一个位置，即q = q->next。当p到达最后一个节点时，q就是中间节点了。
void searchmid(node* head, node* mid)
{
node *temp = head;
while(head->next->next!=NULL)
{
head = head->next->next;
temp = temp->next;
mid = temp;
}
}
（2）双链表
双链表与单链表类似，只是增加了一个前置链而已。
代码如下：
/*双链表建立仅仅比单链表建立多一个指向前一个元素的指针*/
#include
#include
typedef struct student
{
int data;
struct student *next;
struct student *pre;
}dnode;
dnode *creat()
{
dnode *head,*p,*s;
int x,cycle = 1;
head = (dnode*)malloc(sizeof(dnode));
p = head;
while(cycle)
{
printf("\nplease input the data:");
scanf("%d",&x);
if(x!=0)
{
s=(dnode*)malloc(sizeof(dnode));
s->data=x;
printf("\n %d",s->data);
p->next = s;
s->pre = p;
p = s;
}
else
cycle = 0;
}
head = head->next;
head->pre = NULL;
p->next = NULL;
printf("\n yyy %d",head->data);
return (head);
}
编程实现双链表删除/插入节点。
代码如下:
dnode *del(dnode *head, int num)
{
dnode *p1,*p2;
p1 = head;
while(num!=p1->data && p1->next!=NULL)
p1 = p1->next;
if(num==p1->data)
{
if(p1==head)
{
head = head->next;
head->pre = NULL;
free(p1);
}
else if(p1->next ==NULL)
{
p1->pre->next = NULL;
free(p1);
}
else
{
p1->next->pre = p1->pre;
p1->pre->next = p1->next;
//free(p1);
}
}
else
printf("\n%d cound not been found",num);
return(head);
}
/*
双链表插入节点
*/
dnode *insert(dnode *head,int num)
{
dnode *p0,*p1;
p1 = head;
p0 = (dnode *)malloc(sizeof(dnode));
p0->data = num;
while(p0->data>p1->data && p1->next!=NULL)
p1= p1->next;
if(p0->data<=p1->data)
{
if(head==p1) //删除头
{
p0->next = p1;
p1->pre = p0;
head = p0;
}
else //删除中间
{
p1->pre->next = p0;
p0->next = p1;
p0->pre = p1->pre;
p1->pre = p0;
}
}
else //删除尾
{
p1->next = p0;
p0->pre = p1;
p0->next = NULL;
}
return(head);
}
（3）循环链表
已知n个人（以编号1,2,3,...,n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依次规律重复下去，直到圆桌周围的人全部出列。试用c++编程实现。
先给一个简单的版本，即没有k，直接从1开始的：
//初始位置从1开始
#include
#include
int linktype(int n, int m)
{
int people,password;
struct node
{
int data;
struct node *next;
}NODE:
node *p,*head,*q,*pri;
head = (node *)malloc(sizeof(struct nod