单链表的算法操作

1、单链表

在每个结点中除了包含数据域外，还包含了一个指针域，用以指向其后继结点。

2、头插法和尾插法建立链表

（1）算法代码

typedef struct SinglyLinkedLists
{
	int data;
	struct SinglyLinkedLists *next;
}SinglyLinkedLists;
void createListByFront(SinglyLinkedLists *&list, int a[], int n)//头插法
{
	//newList指向新申请的结点
	SinglyLinkedLists *newList;
	int i;
	//申请list的头结点
	list = (SinglyLinkedLists *)malloc(sizeof(SinglyLinkedLists));
	list->next = NULL;
	for (i = 0; i < n; ++i)
	{
		newList = (SinglyLinkedLists *)malloc(sizeof(SinglyLinkedLists));
		newList->data = a[i];
		newList->next = list->next;
		list->next = newList;
	}
}
void createListByRear(SinglyLinkedLists *&list, int a[], int n)//尾插法
{
	//newList指向新申请的结点，rearList始终指向list的终端结点
	SinglyLinkedLists *newList, *rearList;
	int i;
	//申请list的头结点
	list = (SinglyLinkedLists *)malloc(sizeof(SinglyLinkedLists));
	list->next = NULL;
	rearList = list;
	for (i = 0; i < n; ++i)
	{
		newList = (SinglyLinkedLists *)malloc(sizeof(SinglyLinkedLists));
		newList->data = a[i];
		rearList->next = newList;
		rearList = rearList->next;
	}
	rearList->next = NULL;
}
void queryData(SinglyLinkedLists *list)
{
	SinglyLinkedLists *p = list->next;
	while (p != NULL)
	{
		printf("%d\n", p->data);
		p = p->next;
	}
}

void main()
{
	SinglyLinkedLists *list;
	int a[] = { 1, 2, 3, 4, 5 };
	int n = 5;
	createListByFront(list, a, n);
	queryData(list);
	createListByRear(list, a, n);
	queryData(list);
	system("pause");
}

（2）运行结果

5
4
3
2
1
1
2
3
4
5
请按任意键继续. . .

3、单链表的结点插入操作

假设p指向一个结点，要将s所指结点插入p所指结点之后的操作如下：

（1）s->next=p->next;

（2）p->next=s;

4、单链表的结点删除操作

假设p指向一个结点，要删除p所指结点的后继结点的操作如下：

（1）q=p->next;

（2）p->next=p->next->next;

（3）free(q);//释放q所指结点的内存空间