尾插法
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode { //定义单链表结构
int data; //每个节点存放一个数据
struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
LinkList ListTailInsert(LinkList &L);
LNode* GetElem(LinkList L, int i);
int length(LinkList L);
int main(void) {
LinkList L;
L = ListTailInsert(L);
if (!Empty(L)) {
//获取第3个节点的值
int num = GetElem(L,3)->data;
printf("第3个节点的值为:%d\n", num);
printf("链表长度为:%d\n", length(L));
}
return 0;
}
//初始化空的单链表
bool InitList(LinkList &L) {
L = (LNode *)malloc(sizeof(LNode)); //分配头结点
if (L == NULL) { //内存不足,分配失败
return false;
}
L->next = NULL; //头结点之后暂时没有节点
return true;
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
//按位查找,返回第i个元素(带头结点)
LNode* GetElem(LinkList L, int i) {
if (i < 0) {
return NULL;
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while (p!=NULL && j<i) { //循环找到第i个节点
p = p->next;
j++;
}
return p;
}
//尾插法建立单链表(正向建立单链表)
LinkList ListTailInsert(LinkList &L) {
int x;
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
LNode *s, *r = L; //r为表尾指针
scanf("%d", &x);
while(x!=9999) { //输入9999结束
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾节点
scanf("%d", &x);
}
r->next = NULL; //尾节点指针置空
return L;
}
//求表长度
int length(LinkList L) {
int len = 0; //统计表长
LNode *p = L;
while (p->next != NULL) {
p = p->next;
len++;
}
return len;
}
头插法
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode { //定义单链表结构
int data; //每个节点存放一个数据
struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
LinkList ListHeadInsert(LinkList &L);
LNode* GetElem(LinkList L, int i);
int length(LinkList L);
int main(void) {
LinkList L;
L = ListHeadInsert(L);
if (!Empty(L)) {
//获取第3个节点的值
int num = GetElem(L,3)->data;
printf("第3个节点的值为:%d\n", num);
printf("链表长度为:%d\n", length(L));
}
return 0;
}
//初始化空的单链表
bool InitList(LinkList &L) {
L = (LNode *)malloc(sizeof(LNode)); //分配头结点
if (L == NULL) { //内存不足,分配失败
return false;
}
L->next = NULL; //头结点之后暂时没有节点
return true;
}
//判断单链表是否为空(带头结点)
bool Empty(LinkList L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
//按位查找,返回第i个元素(带头结点)
LNode* GetElem(LinkList L, int i) {
if (i < 0) {
return NULL;
}
LNode *p; //指针p指向当前扫描到的节点
int j = 0; //当前p指向的是第几个节点
p = L; //L指向头结点,头结点是第0个节点(不存数据)
while (p!=NULL && j<i) { //循环找到第i个节点
p = p->next;
j++;
}
return p;
}
//头插法建立单链表(逆向建立单链表)
LinkList ListHeadInsert(LinkList &L) {
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode)); //创立头结点
L->next = NULL; //初始为空链表
scanf("%d", &x); //输入节点的值
while (x != 9999) { //输入9999结束
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
//求表长度
int length(LinkList L) {
int len = 0; //统计表长
LNode *p = L;
while (p->next != NULL) {
p = p->next;
len++;
}
return len;
}