JZTXT

第二章 线性表-单链表

发布时间 2023-09-19 17:19:29作者: ww0809

线性表

2.5.1 单链表的定义和表示

存储结构（物理位置）可以不连续。（非顺序映像/链式映像）

typedef struct LNode {
	ElemType data; // 数据域
	struct LNode *next; // 指针域
} LNode, *LinkList; // （同一结构体指针类型起了两个名称）
// LinkList是指向结构体LNode的指针类型
// 如果定义LinkList L 则L就是单链表的头指针
// 如果定义LNode *p 则p就是指向单链表中某个结点的指针

每个结点的指针域指向其直接后继结点。

单链表由表头指针唯一确定，所以可以用表头指针的名字为单链表命名。

头结点（不作为表长计入） 头结点的指针域指向首元结点
首元结点 链表中存储第一个元素的结点
头指针 指向链表中第一个结点的指针

加入头结点的好处：

  1. 首元结点可以和其他结点同样处理。

  2. 判定空表：L == NULL

头指针始终是指向头结点的非空指针。

单链表是顺序存取 意思是只能从头开始遍历

2.5.2 单链表基本操作的实现

  1. 初始化

    Status IntList(LinkList &L) {
	L = new LNode;
    L -> next = NULL; // 头结点指针域置空
    return OK;
}

  2. 取值

    只能从头到尾遍历。

    平均时间复杂度为O(n).

    Status GetElem(LinkList L, int i, ElemType &e) {
	p = L-> next; 
	j = 1; // 计数器
	while(p && j < i) {
		p = p -> next;
		++j;
	}
	if(!p || j > i) return ERROR;
	e = p -> data;
	return OK;
}

  3. 查找

    从头到尾查找。

    平均时间复杂度为O(n).

  4. 插入

    Status ListInsert(LinkList &L, int i, ElemType e) {
	// 在带头结点的链表L中第i个位置插入值为e的结点
	p = L;
	j = 0;
	while(p && j < i - 1) {
		p = p -> next;
		++j;
	}
	if(!p || j > i - 1) return ERROR;
	s = new LNode;
	s -> data = e;
	s -> next = p -> next;
	p -> next = s;
	return OK;
}

    注意指针域赋值的顺序。

    要插入到第i个位置，要找到第i - 1个位置。

    时间复杂度是O(n)，因为要先遍历找到插入位置

  5. 删除

    和插入一样，需要先找到待删除元素的前驱结点。

    然后修改指针域，并释放待删结点的空间。

    Status ListDelete(LinkList &L, int i) {
	p = L;
	j = 0;
	while(p -> next && j < i - 1) {
		p = p -> next;
		++j;
	}
	if(!p || j > i - 1) return ERROR;
	q = p -> next; // 储存被删结点地址 以备释放
	p -> next = q -> next;
	delete q;
	return OK;
}

    时间复杂度是O(n)。

  6. 创建

    （1） 前插法

    ​ 每次生成的新结点插入头结点之后（也就是作为新的首元结点）。

    void CreateList_H(LinkList &L, int n) {
	L = new LNode;
	L -> next = NULL;
	for(int i = 0; i < n; i++) {
		 p = new LNode;
		 cin >> p -> data;
		 p -> next = L -> next;
		 L -> next = p; // 注意顺序
	}
}

    ​ 时间复杂度是O(n)。

    （2） 后插法

    ​ 为了便于每次将新结点插入表尾， 需要一个尾指针指向尾结点。

    void CreateList_R(LinkList &L, int n) {
	L = new LNode;
	L -> next = NULL;
	r = L;
	for(int i = 0; i < n; i++) {
		p = new LNode;
		cin >> p -> data;
		p -> next = NULL;
		r -> next = p;
		r = p;
	}
}

    ​ 时间复杂度是O(n)。