头文件Linear.h
// 单链表的类型定义
typedef struct node
{
int data; // 数据域
struct node *next; // 指针域
}Node, *LinkList;
因为单链表头结点和插入的结点要动态生成，所以要引入系统头文件<stdlib.h>或者<malloc.h>，不然会报错。
1. 初始化单链表
LinkList InitiateLinkList()
{
LinkList head; // 头指针
head = malloc(sizeof(Node)); // 动态创建头结点
head->next = NULL;
return head;
}
2. 求单链表的长度：出了头结点的所有结点的个数，包括首结点
int LengthLinkList(LinkList head)
{
int cnt = ;
Node *p = head;
while(p->next != NULL)
{
p = p->next;
cnt++;
}
return cnt;
}
3.读表元素
在单链表head中查找第i个元素结点。若找到，返回指向该节点的指针，否则返回NULL
Node * GetLinkList(LinkList head, int i)
{
int c = ;
Node *p;
p = head -> next; // 初始化时，p指向首结点 while((c < i) && (p != NULL))
{
p = p->next;
c++;
}
if(c == i) return p;
else return NULL;/**/ }
4. 插入元素
在表head的第i个数据元素结点之前插入一个以x为值的新结点
void InsertLinkList(LinkList head, int x, int i)
{
Node *p, *q;
if(i == ) q = head;
else q = GetLinkList(head, i - ); // 找到第i - 1个数据元素结点，方便在其后插入 if(q == NULL) printf("找不到插入位置。\n");
else
{
p = malloc(sizeof(Node));
p->data = x;
p->next = q->next;
q->next = p;
}
}
5. 单链表删除
删除表head的第i个结点
void DeleteLinkList(LinkList head, int i)
{
// 先找到待删结点的直接前驱
Node *q, *p;
if(i == ) q = head;
else q = GetLinkList(head, i - ); // 若前驱结点存在且待删结点存在
if(q != NULL && q->next != NULL)
{
p = q->next;
q->next = p->next;
free(p); // 释放已移出结点p的空间
}
else
{
printf("找不到待删结点\n");
}
}
6.遍历单链表
void traverseList(LinkList head)
{
Node *p;
p = head->next;
while(p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
7. 定位
求表head中第一个值等于x的结点的序号，若不存在这种结点，返回结果为0
int LocateLinkList(LinkList head, int x)
{
int i = ;
Node * p = head; // p是工作指针
p = p->next; // 初始时p指向首结点
while(p != NULL && p->data != x)
{
i++;
p = p->next;
}
if(p != NULL) return i + ;
else return ;
}
全部代码：
#include <stdio.h>
#include <stdlib.h>
#include "Linear.h" // 单链表
// p 是工作指针 // 1. 初始化
LinkList InitiateLinkList()
{
LinkList head; // 头指针
head = malloc(sizeof(Node)); // 动态创建头结点
head->next = NULL;
return head;
} // 2. 求表长
int LengthLinkList(LinkList head)
{
int cnt = ;
Node *p = head;
while(p->next != NULL)
{
p = p->next;
cnt++;
}
return cnt;
} // 3. 读表元素
// 在单链表head中查找第i个元素结点。若找到，返回指向该节点的指针，否则返回NULL
Node * GetLinkList(LinkList head, int i)
{
int c = ;
Node *p;
p = head -> next; // 初始化时，p指向首结点 while((c < i) && (p != NULL))
{
p = p->next;
c++;
}
if(c == i) return p;
else return NULL;/**/ } // 4. 插入元素
// 在表head的第i个数据元素结点之前插入一个以x为值的新结点
void InsertLinkList(LinkList head, int x, int i)
{
Node *p, *q;
if(i == ) q = head;
else q = GetLinkList(head, i - ); // 找到第i - 1个数据元素结点，方便在其后插入 if(q == NULL) printf("找不到插入位置。\n");
else
{
p = malloc(sizeof(Node));
p->data = x;
p->next = q->next;
q->next = p;
}
} // 5. 单链表删除
// 删除表head的第i个结点
void DeleteLinkList(LinkList head, int i)
{
// 先找到待删结点的直接前驱
Node *q, *p;
if(i == ) q = head;
else q = GetLinkList(head, i - ); // 若前驱结点存在且待删结点存在
if(q != NULL && q->next != NULL)
{
p = q->next;
q->next = p->next;
free(p); // 释放已移出结点p的空间
}
else
{
printf("找不到待删结点\n");
}
} // 6.遍历单链表
void traverseList(LinkList head)
{
Node *p;
p = head->next;
while(p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
} // 7. 定位
// 求表head中第一个值等于x的结点的序号，若不存在这种结点，返回结果为0
int LocateLinkList(LinkList head, int x)
{
int i = ;
Node * p = head; // p是工作指针
p = p->next; // 初始时p指向首结点
while(p != NULL && p->data != x)
{
i++;
p = p->next;
}
if(p != NULL) return i + ;
else return ;
} main()
{
// 初始化变量
LinkList head;
int cnt; head = InitiateLinkList();
printf("初始化成功！\n"); cnt = LengthLinkList(head);
printf("单链表的长度：%d\n", cnt); // 单链表插入结点
InsertLinkList(head, , );
InsertLinkList(head, , );
InsertLinkList(head, , );
InsertLinkList(head, , );
InsertLinkList(head, , );
InsertLinkList(head, , );
InsertLinkList(head, , ); cnt = LengthLinkList(head);
printf("单链表的长度：%d\n", cnt); // 遍历单链表
traverseList(head); // 删除结点
DeleteLinkList(head, ); traverseList(head); printf("结点的值为88的序号为：%d\n", LocateLinkList(head, )); }
一般的单链表结束。特殊的没写。