?单链表的结构是数据结构中最简单的，它的每一个节点只有一个指向后一个节点的指针。
单链表的创建:
typedef struct node
{
int data; //节点内容
node *next; //下一个节点
}node;
//创建单链表
node *create()
{
int i=0; //链表中数据的个数
node *head, *p, *q;
int x = 0;
head = (node *)malloc(sizeof(node)); //创建头节点
while(1)
{
printf("Please input the data: ");
scanf("%d", &x);
if(0 == x) //data为0时创建结束
{
break;
}
p = (node *)malloc(sizeof(node));
p->data = x;
if(++i == 1) //链表只有一个元素
{
head->next = p; //连接到head的后面
}
else
{
q->next = p; //连接到链表尾端
}
q = p; //q指向末节点
}
q->next = NULL; //链表的最后一个指针为NULL
return head;
}
上面的代码中，while循环每次从终端读入一个整型数据，并调用malloc动态分配链表节点内存存储这个整型数据，然后在插入到单链表的末尾；最后当数据为0时表示插入数据结束，此时把末尾节点的next指针置为NULL。
//单链表的测长
int length(node *head)
{
int len = 0;
node *p = head->next;
while(NULL != p)
{
len++;
p = p->next;
}
return len;
}
//打印链表
void print(node *head)
{
int pos = 0;
node *p = NULL;
if(NULL == head->next)
{
printf("Link is empty!\n");
return ;
}
p = head->next;
while(NULL != p) //遍历链表
{
printf("The %dth node is: %d\n", ++pos, p->data);
p = p->next;
}
}
//单链表的节点查找
//查找pos位置的节点，返回节点指针
//pos从0开始，0返回head节点
node *search_node(node *head, int pos)
{
node *p = head->next;
if(pos < 0) //pos位置不正确
{
printf("incorrect position to search node!\n");
return NULL;
}
if(0 == pos)
{
return head;
}
if(NULL == p)
{
printf("Link is empty!\n"); //链表为空
return NULL;
}
while(--pos)
{
if((p = p->next) == NULL)
{
printf("incorrect position to search node!\n");
break; //超出链表返回
}
}
return p;
}
//单链表节点插入
//在单链表pos位置处插入节点，返回链表头指针
//pos从0开始计算，0表示插入到head节点后面
node *insert_node(node *head, int pos, int data)
{
node *item = (node *)malloc(sizeof(node));
node *p = NULL;
item->data = data;
if(0 == pos) //插入链表头后面
{
head->next = item; //head后面是item
return head;
}
p = search_node(head, pos); //获得位置pos的节点指针
if(NULL != p)
{
item->next = p->next; //item指向原pos节点的后一个节点
p->next = item; //把item插入到pos的后面
}
return head;
}
//单链表节点删除
//删除单链表的pos位置的节点，返回链表头指针
//pos从1开始计算，1表示删除head后的第一个节点
node *delete_node(node *head, int pos)
{
node *del;
node *p = head->next;
if(NULL == p) //链表为空
{
printf("Link is empty!\n");
return NULL;
}
p = search_node(head, pos-1); //获得位置pos的节点指针
if(NULL != p && NULL != p->next)
{
del = p->next;
p->next = del->next;
delete del;
}
return head;
}
下面代码是上面各个函数的测试主程序:
int main()
{
node *head = create(); //创建单链表
printf("Length: %d\n", length(head)); //测量单链表长度
head = insert_node(head, 2, 5); //在第2个节点之后插入5
printf("insert integer 5 after 2th node: \n");
print(head); //打印单链表
head = delete_node(head, 2); //删除第2个节点
printf("delete the 2th node: \n");
print(head);
return 0;
}
下面是程序执行结果:
Please input the data: 1
Please input the data: 2
Please input the data: 3
Please input the data: 4
Please input the data: 0
Length: 4
insert integer 5 after 2th node:
The 1th node is: 1
The 2th node is: 2
The 3th node is: 5
The 4th node is: 3
The 5th node is: 4
delete the 2th node:
The 1th node is: 1
The 2th node is: 5
The 3th node is: 3
The 4th node is: 4
Press any key to continue