继上文《数据结构:线性表的顺序表示》,我们知道线性表的主要操作如下:
InitList(&L)
: 初始化表length(L)
: 求表长LocateElem(L, e)
: 按值查找操作GetElem(L, i)
: 按位查找操作ListInsert(&L,i,e)
: 插入操作ListDelete(&L,i,&e)
: 删除操作PrintList(L)
:输出操作Empty(L)
:判空操作DestroyList(&L)
: 销毁操作
本文将讨论如何用链式表示的方法定义线性表
一般来说,默认链表是带头结点的
代码部分
线性表的定义
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
第二个typedef
语句本质上是,先定义一个结构体LNode
, 再为LNode*
类型取一个别名LinkList
;可以说,链式表示用头节点来代表一个线性表。
单链表的初始化
带头结点的单链表初始化时,需先创建一个头结点,并让头指针指向头结点,头结点的next
域初始化为NULL
。
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode)); // 创建头节点
L->next = NULL; // 头节点指向空
return true;
}
关键语句解释:
L = (LNode*)malloc(sizeof(LNode));
sizeof(LNode)
表示 LNode 结构体的大小,即需要多少字节的内存空间来存储这个结构体的数据。
malloc(...)
调用malloc函数,在堆内存中分配指定大小的空间
L = (LNode*)...
是将 malloc 返回的指向分配的内存空间的指针转换为 LNode* 类型,并将其赋值给 L 这个指针变量。
求表长操作
求表长操作是计算单链表中数据结点的个数。
int length(LinkList L) {
int len = 0; // 计数变量
LNode* p = L;
while (p->next != NULL) {
p = p->next;
len++;
}
return len;
}
按序号查找结点
从单链表的第一个结点开始,沿着next域从前向后依次搜索,直到找到第i个结点为止,则返回该结点的指针;若i大于单链表的表长,则返回NULL
LNode* GetElem(LinkList L, int i) {
LNode* p = L; // 指向当前扫描到的节点
int j = 0;
while (p != NULL && j<i) {
p = p->next;
j++;
}
return p; // 返回节点i得指针或NULL
}
按值查找结点
LNode* LocateElem(LinkList L, ElemType e) {
LNode* p = L->next;
while (p != NULL && p->data != e)
p = p->next;
return p;
}
插入结点操作
插入结点操作将值为x的新结点插入到单链表的第i个位置。先检查位置的合法性,然后找到待插入位置的前驱a,插入时遵循下列操作:
- 先将新结点指向a的后驱b(b=a->next
- 再将前驱a指向新结点
具体代码如下:
bool ListInsert(LinkList& L, int i, ElemType e) {
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;
}
删除结点操作
先检查位置的合法性,然后找到待插入位置的前驱a,删除时遵循如下步骤:
- 定义指针q,将待删除的结点指针赋值给q
- 将前驱a指向q的下一个结点
- 释放指针q指向的内存
bool ListDelete(LinkList& L, int i, ElemType& e) {
LNode* p = L;
int j = 0;
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || p->next == NULL)
return false;
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
标签:结点,NULL,return,LNode,int,next,链式,数据结构,线性表
From: https://www.cnblogs.com/SXWisON/p/18303864