最近软基的作业中，链表十分常用。于是将链表的声明和一些常用的功能封装到头文件里，以后直接引用就可以了。一下是链表的头文件：
list.h：
/************************************************************
* list.h *
* To implement the list. *
* by Eric Brown. *
************************************************************/
#ifndef LIST_H
#define LIST_H
typedef struct node_type
{
int data;
struct node_type *next;
}nodetype;
typedef struct list_type
{
nodetype *head;
int length;
}listtype;
/*list_init: to create a list.*/
listtype * list_create(void);
/*list_print: to print a list.*/
void list_print(listtype *list);
/*list_insert: to insert a node in a list by its address.*/
listtype * list_insert(listtype *list, int location, int data);
/*list_delete: to delete a node by its value.*/
int list_delete(listtype *list, int data);
/*list_input: to input a list.*/
listtype * list_input(listtype *list, int length);
/*list_delete_node: delete a certain node.*/
listtype * list_delete_node(listtype *list, nodetype *node);
/*list_add: to add a node.*/
nodetype * list_add(listtype *list, int data);
#endif
list.c：
/************************************************************
* list.c *
* by Eric Brown. *
************************************************************/
#include "list.h"
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
/*node_insert: to insert a node behind the node.*/
nodetype * node_insert(nodetype *node, int data);
/*node_delete: to delete a node from the list.*/
nodetype * node_delete(nodetype *cur, nodetype *pre);
void error(int err);
listtype * list_create(void)
{
listtype *list;
list = (listtype *)malloc(sizeof(listtype));
if (list == NULL)
error(1);
list->length = 0;
list->head = NULL;
return list;
}
nodetype * node_insert(nodetype *node, int data)
{
nodetype *temp;
temp = (nodetype *)malloc(sizeof(nodetype));
if (temp == NULL)
error(1);
temp->data = data;
temp->next = node->next;
node->next = temp;
return temp;
}
void list_print(listtype *list)
{
nodetype *temp;
if (list->length == 0 || list->head == NULL)
{
printf("This is an empty list!
");
return ;
}
temp = list->head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("
");
}
listtype * list_input(listtype *list, int num)
{
int temp;
nodetype *cur, *next;
if (num <= 0)
error(2);
cur = list->head;
if (cur == NULL)
{
scanf("%d", &temp);
cur = (nodetype *)malloc(sizeof(nodetype));
cur->data = temp;
num--;
list->length = 1;
list->head = cur;
} else{
while (cur->next != NULL)
cur = cur->next;
}
while (num--)
{
scanf("%d", &temp);
next = (nodetype *)malloc(sizeof(nodetype));
next->data = temp;
cur->next = next;
cur = next;
list->length++;
}
cur->next = NULL;
return list;
}
listtype * list_insert(listtype *list, int location, int data)
{
nodetype *temp, *cur;
cur = list->head;
if (location > 0 && location <= list->length)
{
while(--location)
cur = cur->next;
node_insert(cur, data);
}
else if(location == 0)
{
temp = (nodetype *)malloc(sizeof(nodetype));
temp->data = data;
temp->next = list->head;
list->head = temp;
}
else
{
error(3);
}
list->length++;
return list;
}
nodetype * node_delete(nodetype *cur, nodetype *pre)
{
pre->next = cur->next;
free(cur);
return pre;
}
int list_delete(listtype *list, int data)
{
nodetype *cur, *pre;
for (cur = list->head, pre = NULL;
cur->data != data && cur != NULL;
pre = cur, cur = cur->next)
;
if (cur == NULL)
{
printf("Can't find the data!
");
return 0;
}
else if(cur != list->head)
{
node_delete(cur, pre);
}
else if(cur == list->head)
{
list->head = cur->next;
free(cur);
}
list->length--;
return data;
}
listtype * list_delete_node(listtype *list, nodetype *node)
{
nodetype *pre;
if (node == list->head)
{
list->head = node->next;
free(node);
list->length--;
}
else
{
pre = list->head;
while(pre->next != node)
pre = pre->next;
node_delete(node, pre);
}
return list;
}
nodetype * list_add(listtype *list, int data)
{
nodetype *cur, *temp;
for (cur = list->head;
cur != NULL && cur->next != NULL;
cur = cur->next)
;
temp = (nodetype *)malloc(sizeof(nodetype));
temp->data = data;
temp->next = NULL;
if (list->length == 0)
list->head = temp;
else
cur->next = temp;
list->length++;
return temp;
}
void error(int err)
{
switch(err)
{
case 1:
printf("RAM error!
");
break;
case 2:
printf("Length error!
");
break;
case 3:
printf("Location error!
");
break;
default:
printf("Unknown error!
");
}
exit(EXIT_FAILURE);
}
以下是一些功能的测试：
test.c：
#include <stdio.h>
#include "list.h"
int main(void)
{
listtype *list;
int length, location, data;
list = list_create();
for (;;)
{
printf("Please input the length of the list:");
scanf("%d", &length);
if (length <= 0)
break;
list_input(list, length);
list_print(list);
}
for (;;)
{
printf("Please input the data you want to insert:");
scanf("%d", &data);
printf("The location:");
scanf("%d", &location);
if (location < 0)
break;
list_insert(list, location, data);
list_print(list);
}
for(;;)
{
printf("Please input the data you want to delete:");
scanf("%d", &data);
if(data == 0)
break;
list_delete(list, data);
list_print(list);
}
return 0;
}
以下是运行结果：
以下是两个乱序链表应用归并排序的程序：
order.c：
#include "list.h"
#include <stdio.h>
#include <stdlib.h>
/*find_min: to find the min num of the list.*/
nodetype * find_min(listtype *list);
/*order: to order two lists.*/
listtype * order(listtype *listA, listtype *listB);
int main(void)
{
listtype *listA, *listB, *result;
nodetype *node;
int lengthA, lengthB;
listA = list_create();
listB = list_create();
printf("listA:
");
printf("length:");
scanf("%d", &lengthA);
list_input(listA, lengthA);
printf("listB:
");
printf("length:");
scanf("%d", &lengthB);
list_input(listB, lengthB);
result = order(listA, listB);
list_print(result);
return 0;
}
nodetype * find_min(listtype *list)
{
nodetype *cur, *min;
cur = min = list->head;
while (cur != NULL)
{
if (cur->data < min->data)
min = cur;
cur = cur->next;
}
return min;
}
listtype * order(listtype *listA, listtype *listB)
{
nodetype *nodeA, *nodeB, *tail, *temp;
listtype *result;
result = list_create();
nodeA = find_min(listA);
nodeB = find_min(listB);
do
{
if (nodeA->data < nodeB->data)
{
list_add(result, nodeA->data);
list_delete_node(listA, nodeA);
}
else
{
list_add(result, nodeB->data);
list_delete_node(listB, nodeB);
}
nodeA = find_min(listA);
nodeB = find_min(listB);
}while(nodeA != NULL && nodeB != NULL);
for (tail = result->head; tail->next != NULL; tail = tail->next)
;
if (nodeA == NULL)
while (nodeB != NULL)
{
temp = (nodetype *)malloc(sizeof(nodetype));
temp->data = nodeB->data;
tail->next = temp;
tail = temp;
list_delete_node(listB, nodeB);
nodeB =find_min(listB);
}
if (nodeB == NULL)
while (nodeA != NULL)
{
temp = (nodetype *)malloc(sizeof(nodetype));
temp->data = nodeA->data;
tail->next = temp;
tail = temp;
list_delete_node(listA, nodeA);
nodeA =find_min(listA);
}
tail->next = NULL;
return result;
}
以下是运行结果：
