线性表的链接存储
线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双向循环链表,其中最简单的是单链表。
单链表的类型定义
// 假定数据元素类型为 DataType
typedef struct
{
int num; // 学号
char name[8]; // 姓名
char sex[2]; // 性别
int age; // 年龄
int score; // 入学成绩
} DataType;
// 单链表的类型定义
typedef struct node
{
DataType data; // 数据域
struct node *next; // 指针域或链域
} Node, *LinkList; // 通过 typedef 语句把 struct node 类型定义为 Node,把 struct node 指针类型定义为 LinkList
LinkList head; // head 为链表的名称
单链表的初始化
LinkList InitiateLinkList()
{
// 建立一个空的单链表
LinkList head; // 头指针
head = (LinkList)malloc(sizeof(Node)); // 动态构建一结点,它是头结点
head->next = NULL; // 如果为非空单链表,头结点的指针域指向首结点
return head;
}
读表元素
Node *GetLinkList(LinkList head, int i)
{
// 在单链表 head 中查找第 i 个元素结点。若找到,则返回指向该结点的指针;否则返回 NULL
Node *p;
p = head->next; // 初始时,p 指向首结点
int c = 1;
while ((c < i) && (p != NULL)) { // 当未到第 i 个结点且未到尾结点时继续后移
p = p->next;
c++;
}
if (i == c) { // 找到第 i 个结点
return p;
} else { // i<1 或 i>n,i 值不合法,查找失败
return NULL;
}
}
单链表的插入
void InsertLinkList(LinkList head, DataType x, int i)
{
// 在表 head 的第 i 个数据元素结点之前插入一个以 x 为值的新结点
Node *p, *q;
if (i == 1) {
q = head;
} else {
q = GetLinkList(head, i - 1); // 找到第 i-1 个数据元素结点
}
if (q == NULL) {
exit('找不到插入的位置');
} else {
p = (Node *)malloc(sizeof(Node));
p->data = x; // 生成新结点
p->next = q->next; // 新结点指针域指向 *q 的后继结点
q->next = p; // 修改 *q 的指针域
}
}
单链表的删除
void DeleteLinkList(LinkList head, int i)
{
// 删除表 head 的第 i 个结点
Node *p, *q;
if (i == 1) {
q = head;
} else {
q = GetLinkList(head, i - 1); // 先找到待删结点的直接前驱
}
if (q != NULL && q->next != NULL){ // 若直接前驱存在且待删结点存在
p = q->next; // p 指向待删结点
q->next = p->next; // 移除待删结点
free(p); // 释放已移除结点 p 的空间
} else {
exit('找不到要删除的结点');
}
}