头插法和尾插法最大区别在于，尾插法可以顺序输出用户输入的元素，头插法则是逆序输出的
1.尾插法建立单链表
带头结点
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; } LNode, *LinkList; LinkList InitList(LinkList &L) { L = (LNode*)malloc(sizeof(LNode)); if (L == NULL) { return NULL; } L->next = NULL; return L; } bool ListInsert(LinkList &L, int i, ElemType e) { if (i < 1) { return false; } LNode* p = L; int j = 0; while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) { return false; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true; } int GetLen(LinkList &L) { int len = 0; LNode* p = L->next; while (p != NULL) { p = p->next; len++; } return len; } int main() { LinkList L=NULL; if (InitList(L) == NULL) { printf("链表初始化失败\n"); return 0; } int length = GetLen(L); LNode* p = L; int e = 3; ListInsert(L, length, e); // 将e元素插到链表的尾部 printf("链表长度：%d\n", GetLen(L)); // 释放链表所占用的内存 p = L->next; // p指向第一个节点 while (p != NULL) { LNode* q = p->next; // q指向下一个节点 free(p); // 释放当前节点 p = q; // 将p指向下一个节点 } return 0; }
不带头节点
只需要对i=1时做单独判断，即
if (i < 1) { return false; } if (i == 1) { LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = L; L = s; return true; }
最终代码为
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; } LNode, *LinkList; LinkList InitList(LinkList &L) { L = NULL; return L; } bool ListInsert(LinkList &L, int i, ElemType e) { if (i < 1) { return false; } if (i == 1) { LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = L; L = s; return true; } LNode* p = L; int j = 1; while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) { return false; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true; } int GetLen(LinkList &L) { int len = 0; LNode* p = L; while (p != NULL) { p = p->next; len++; } return len; } int main() { LinkList L=NULL; if (InitList(L) == NULL) { printf("链表初始化失败\n"); return 0; } int length = GetLen(L); LNode* p = L; int e = 3; ListInsert(L, length+1, e); // 将e元素插到链表的尾部 printf("链表长度：%d\n", GetLen(L)); // 释放链表所占用的内存 p = L; while (p != NULL) { LNode* q = p->next; // q指向下一个节点 free(p); // 释放当前节点 p = q; // 将p指向下一个节点 } return 0; }
用户输入建立单链表
带头结点
LinkList(LinkList &L) { int x; L=(LinkList)malloc(sizeof(LNode)); LNode=*s,*r=L; scanf("%d",&x); while(x!=100) { s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; scanf("%d",&x); } r->next=NULL; return L; }
r总是指向表尾节点，每输入一个新值，就存入s指向的新开辟的空间,即r指向的尾节点的后面当再输入下一个值时，令r=s；将r指向这个新开辟的空间作为新的尾节点，重复上一操作
不带头结点
LinkList ListInsert(LinkList &L) { int x; LNode *s, *r; scanf("%d", &x); if (x == 100) { L = NULL; // 若输入第一个元素为 100，则直接返回空链表 return L; } L = (LNode*)malloc(sizeof(LNode)); L->data = x; r = L; scanf("%d", &x); while (x != 100) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; scanf("%d", &x); } r->next = NULL; return L; }
2.头插法建立单链表
头插法建立单链表其实是对头节点做尾插法
带头结点
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; } LNode, *LinkList; LinkList InitList(LinkList &L) { L = (LNode*)malloc(sizeof(LNode)); if (L == NULL) { return NULL; } L->next = NULL; return L; } bool InsertNextNode(LNode *p, ElemType e) { if (p == NULL) return false; LNode *s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) return false; s->data = e; s->next = p->next; p->next = s; return true; } int main() { LinkList L = NULL; if (InitList(L) == NULL) { printf("链表初始化失败\n"); return 0; } LNode* p = L; // 指向头节点 int e = 3; InsertNextNode(p, e); // 将元素3插入到头节点 p = L->next; // p指向第一个节点 while (p != NULL) { printf("%d ", p->data); // 打印节点数据 p = p->next; // 将p指向下一个节点 } printf("\n"); // 释放链表所占用的内存 p = L->next; // p指向第一个节点 while (p != NULL) { LNode* q = p->next; // q指向下一个节点 free(p); // 释放当前节点 p = q; // 将p指向下一个节点 } return 0; }
用户输入建立单链表
带头结点 LinkList ListInsert(LinkList &L) { L = (LNode*)malloc(sizeof(LNode)); // 创建头节点 L->next = NULL; // 头节点的next指针置为空 LNode *s; int x; scanf("%d", &x); while (x != 100) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; scanf("%d", &x); } return L; } 不带头结点 LinkList ListInsert(LinkLinst &L) { LNode *s; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;//在这里必须初始化 int x; scanf("%d",&x); while(x!=100) { s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=L->next; L->next=s; scanf("%d",&x); } return L; }
若不执行 L->next=NULL;
头插法插入的结果
可以看到头插法输入的元素是逆序输出的，尾插法则是顺序输出的
