（1）单链表
编程实现一个单链表的建立/测长/打印。
#include <stdio.h>
#include <string.h>
typedef struct student
{
int data;
struct student *next;
}node;
//建立单链表
node *creat()
{
node *head,*p,*s;
int x,cycle=1;
head = (node*)malloc(sizeof(node));//最初头部没有值，只是用来指向第一个元素
p=head;
while(cycle)
{
printf("
please input the data");
scanf("%d",&x);
if(x!=0)
{
s=(node *)malloc(sizeof(node)); //为元素分配内存
s->data = x;
printf("
%d",s->data);
p->next = s; //前一个元素的指针指向现在的元素
p=s; //现在的元素成为前一个元素
}
else cycle = 0;
}
head = head->next; //将头指向第一个元素
p->next = NULL; //尾部指向NULL
printf("
yyy %d",head->data);
return(head);
}
//单链表测长
int length(node *head)
{
int n=0;
node *p;
p = head; //链表初始
while(p!=NULL) //链表结束
{
p=p->next;
n++;
}
return(n);
}
//单链表打印
void print(node *head) //链表初始
{ //链表结束
node *p;int n;
n = length(head);
printf("
Now,These %d records are:
",n);
p = head;
if(head!=NULL)
while(p!=NULL)
{
printf("
uuu %d ",p->data);
p = p->next;
}
}
编程实现单链表删除节点。
如果删除的是头节点，则把head指针指向头节点的下一个节点。同时free p1;
如果删除的是中间节点，则把p2的next指向p1的next，同时free p1;
代码如下：
node *del(node *head, int num)
{
node *p1,*p2;
p1 = head;
while(num!=p1->data && p1->next!=NULL) //挨着遍历,p2为找到的那个元素的前一个元素
{
p2=p1;
p1=p1->next;
}
if(num==p1->data)
{
if(p1==head) //要删除的是头节点
{
head = p1->next;
free(p1);
}
else
{
p2->next = p1->next;//要删除的是中间节点（含尾节点）
free(p1);
}
}
else
printf("
%d cound not be found",num);
return(head); //链表操作一般返回头节点
}
编写程序实现单链表的插入。
如果插入在头节点以前，则p0的next指向p1,头节点指向p0;
如果插入中间节点，则先让p2的next指向p0,再让p0指向p1;
如果插入尾节点，则先让p1的next指向p0,再让p0指向空；
代码如下：
/*这里链表默认按从小到达排序*/
node *insert(node *head, int num)
{
node *p0,*p1,*p2;
p1 = head;
p0 = (node *)malloc(sizeof(node));
p0->data = num;
while(p0->data>p1->data && p1->next!=NULL)
{
p2=p1;
p1=p1->next;
}
if(p0->data<=p1->data)//判断不可少，因为可能到链表末尾了
{
if(head==p1)
{
p0->next = p1;
head = p0;
}
else
{
p2->next = p0;
p0->next = p1;
}
}
else
{
p1->next = p0;
p0->next = NULL;
}
return(head);
}
编程实现单链表的排序
代码如下：
/*单链表排序 双重循环 两两比较 每次找出剩下元素中最大的*/
node *sort(node *head)
{
node *p,*p2,*p3;
int n; int temp;
n = length(head);
if(head==NULL || head->next ==NULL)
return head;
p = head;
for(int i=1;i<n;i++)
{
for(int j=1;j<=n-i;j++)
{
if(p->data>p->next->data) //两两比较，比后者大则互换
{
temp = p->data;
p->data = p->next->data;
p->next->data = temp;
}
p = p->next;
}
}
return head;
}
编程实现单链表的逆置。
代码如下：
/*进行单链表逆置，首先要让p2的next指向p1
再让p1等于p2，p2等于p3,也就是说每次只调换一个箭头，
形成一个循环
*/
node *reverse(node *head)
{
node *p1,*p2,*p3;
if(head==NULL||head->next==NULL)
return head;
p1=head,p2=p1->next;
while(p2)
{
p3=p2->next;
p2->next = p1;
p1 = p2;
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 <stdio.h>
#include <string.h>
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("
please input the data:");
scanf("%d",&x);
if(x!=0)
{
s=(dnode*)malloc(sizeof(dnode));
s->data=x;
printf("
%d",s->data);
p->next = s;
s->pre = p;
p = s;
}
else
cycle = 0;
}
head = head->next;
head->pre = NULL;
p->next = NULL;
printf("
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("
%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 <stdio.h>
#include <stdlib.h>
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 node));
head->next = NULL;
head->data = 1;
q = head;
for(int i=2;i<=n;i++)
{
p=(node *)malloc(sizeof(struct node));
p->data = i;
p->next = NULL;
q->next = p;
q = q->next;
}
q->next = head;
pri =q;p = head;
people = 0;password = 1;
while(peopel<n)
{
pri = pri->next;
p = p->next;
password++;
if(password==m)
{
printf("%d",p->data);
node *temp;
temp = p;
pri->next = p->next;
p = p->next;
free(temp);
people++；
password=1;
}
}
printf("
");
return 0;
}
int main()
{
int n,m;
printf("请输入人数和密码")；
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m<0||n<0)
{
printf("输入错误，请重新输入
");
continue;
}
linktype(n,m);
}
system("pause");
return 0;
}
再给一个版本：大同小异，不过一开始把指针移动到K处的位置，两个版本结合理解
//初始位置从K开始
#include <stdlib.h>
#include <stdio.h>
#define ERROR 0
typedef struct LNode{
int data;
struct LNode *link;
}LNode,*LinkList;
void JOSEPHUS(int n,int k, int m)
//n为总人数，k为第一个开始报数的人，m为出列者喊道的数
{
/*p为当前节点，r为辅助节点，指向p的前驱节点，list为头节点*/
LinkList p,r,list,curr;
/*建立循环链表*/
p = (LinkList)malloc(sizeof(LNode));
p->data = 0;
p->link = p;
curr = p;
for(int i=1;i<n;i++) //与xuanhuanlianbiao1的区别在于始终保持了尾节点指向了头节点，前者则是尾节点指向NULL，最后出循环后再指向头节点
{
LinkList t = (LinkList)malloc(sizeof(LNode));
t->data = i;
t->link = curr->link;
curr->link = t;
curr = t;
}
/*把当前指针移动到第一个报数的人*/
r = curr;
while(k--)
{
r=p;p=p->link;
}
while(n--)
{
for(int s=m-1;s--;r=p,p=p->link);
r->link = p->link;
printf("%d->",p->data);
free(p);
p=r->link;
}
}
main()
{
JOSEPHUS(15,5,8);
}
附录：单链表 双链表 循环链表 完整.c文件下载(http://www.t00y.com/file/31447179)。