单链表结构可用如下C语言代码描述
typedef struct Node
{
ElemType data;
struct Node *next;
} Node;
typedef struct Node *LinkList
建立链表操作
// 尾插法建立链表
// 操作结果：产生长度为size的正序链表并返回头指针
LinkList CreateListTail(int size)
{
int count;
// head为头节点，p为工作指针，q为临时指针
LinkList head, p, q;
// 先建立一个空的头节点
head = (LinkList)malloc(sizeof(Node));
head->data = 0;
head->next = NULL;
// 将工作指针指向头节点
p = head;
for (count = 0; count < size; count++)
{
// 临时指针创建节点
LinkList q = (LinkList)malloc(sizeof(Node));
q->data = count;
// 工作指针连接新建节点
p->next = q;
// 工作指针后移
p = q;
}
// 标识链表结束
p->next = NULL;
return head;
}
// 头插法建立链表
// 操作结果：产生长度为size的逆序链表并返回头指针
LinkList CreateListHead(int size)
{
int count;
// head为头节点，p为临时指针
LinkList head, p;
// 先建立一个空的头节点
head = (LinkList)malloc(sizeof(Node));
head->data = 0;
head->next = NULL;
for (count = 0; count < size; count++)
{
p = (LinkList)malloc(sizeof(Node));
p->next = head->next;
p->data = count;
head->next = p;
}
return head;
}
读取操作
// 读取一个节点
// 操作结果：读取head指向的链表的第i个节点并赋值给e指向的内存
int GetNode(LinkList head, int i, int *e)
{
LinkList p = head;
int count;
// 位置不合理
if (i <= 0)
{
return ERROR;
}
// 寻找读取的位置
for (count = 0; count < i; count++)
{
p = p->next;
if (!p)
{
return ERROR;
}
}
*e = p->data;
return OK;
}
插入节点操作
// 插入一个节点
// 操作结果：在head指向的链表的第i个位置插入e
int InsertNode(LinkList head, int i, int e)
{
LinkList p = head, q;
// 插入位置不合理
if (i <= 0)
{
return ERROR;
}
int count;
// 移动到插入的位置
for (count = 1; count < i; count++)
{
p = p->next;
// 插入位置不合理
if (!p)
{
return ERROR;
}
}
q = (LinkList)malloc(sizeof(Node));
q->data = e;
q->next = p->next;
p->next = q;
return OK;
}
删除一个节点操作
// 删除一个节点
// 操作结果：删除head指向链表的第i个节点
int DeleteNode(LinkList head, int i)
{
LinkList p = head, q;
int count;
// 删除位置不合理
if (i <= 0)
{
return ERROR;
}
// 找到需要删除的节点的前一个节点
for (count = 0; count < i - 1; count++)
{
p = p->next;
if (!(p->next))
{
return ERROR;
}
}
// 删除节点
q = p->next;
p->next = p->next->next;
free(q);
return OK;
}
遍历操作
// 遍历链表
// 操作结果：输出head指向的链表的所有节点的值
void Traversal(LinkList head)
{
LinkList p = head->next;
while (p)
{
printf("%d\n", p->data);
p = p->next;
}
}
链式存储结构线性表的优点：
- 不用确定具体的大小
- 插入与删除操作时间复杂度为O(1)
顺序存储结构线性表的缺点：
- 访问操作的时间复杂度比较高
- 需要为存储关系(next指针)消耗额外的存储空间
