数据结构-头插法和尾插法建立单链表

在数据结构的学习中，链表是一种重要的数据结构，头插法和尾插法是两种常用的建立单链表的方法。下面将详细介绍这两种方法的实现。

首先，定义链表的结点结构，如下所示：
typedef int ElementType;
typedef struct {
ElementType data;
LinkList *next;
} LinkList, *PtrLinkList;

接着，我们定义一个主函数，用于创建链表：
int main() {
ElementType *array = new LinkList[10];
for(int i = 0; i<10; i++) {
array[i] = i;
}
PtrLinkList pList = NULL;
CreateListF(pList, array, 10);
return 0;
}

在这个主函数中，我们首先定义了一个数组，用于存储结点的数据。然后，我们遍历数组，为每个结点分配数据。接着，我们初始化一个空链表头指针pList，用于指向链表的头结点。最后，我们调用CreateListF函数，使用头插法创建链表。

头插法创建链表的实现如下：
void CreateListF(PtrLinkList &pList, ElementType *array, int n) {
for(int i = n-1; i >= 0; i--) {
PtrLinkList p = new LinkList;
p->data = array[i];
p->next = pList;
pList = p;
}
}

在这个函数中，我们从数组的最后一个元素开始，依次为每个元素创建一个结点，并将这些结点依次插入到链表的头部。这样，最后得到的链表是一个逆序排列的链表。

除了头插法，我们还可以使用尾插法创建链表。尾插法的实现如下：
void CreateListR(PtrLinkList &pList, ElementType *array, int n) {
PtrLinkList p, q;
p = new LinkList;
p->data = array[0];
p->next = NULL;
pList = p;
q = p;
for(int i = 1; i < n; i++) {
p = new LinkList;
p->data = array[i];
p->next = NULL;
q->next = p;
q = p;
}
}

在这个函数中，我们首先创建链表的第一个结点，并将其作为链表的头结点。然后，我们遍历数组，为每个元素创建一个结点，并将这些结点依次插入到链表的尾部。这样，最后得到的链表是一个顺序排列的链表。

通过这两种方法，我们可以根据具体需求灵活地创建单链表。头插法适合在创建链表时需要频繁插入结点的情况，而尾插法则适合在创建链表时需要保持数据顺序的情况。

本文如未解决您的问题请添加抖音号：51dongshi（抖音搜索懂视），直接咨询即可。