线性表（下）

2. 线性表的链式存储结构

链式存储：

用一组任意的存储单元来存储线性表的数据元素，这组存储单元可以在内存中的任意位置。也就是说这组存储单元，可以是连续的，也可以是不连续的，可以是部分连续的也可以是部分不连续的。

在链式存储结构中除了要存储数据信息外，还要存储它的后继元素的**存储地址(指针)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中的信息称为指针或链。这两部分信息组成的数据元素称为结点(Node)**。

采用链式储存结构的线性表称为链表。

链表中每个结点的存储地址存放在其前驱结点的next域中，然而首元结点(即第一个结点)无直接前驱，因此，我们需要设置一个头指针(head)用来存放首元结点的存储地址。由于，尾元结点（即最后一个结点）无直接后继，故尾元结点的指针域为空(NULL)。
有时为了在对链表进行操作时能够统一处理空表和非空表的情况，或者能够统一对首元结点和其他结点的处理过程，我们在链表的首元结点之前增设了一个结点，我们称为头结点(Head Node)。相对于头结点而言，其余结点称为表结点。

头指针与头结点的异同：

头指针

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指什。
头指针具有标识作用，所以常用头指针冠以链表的名字(指针变量的名字)。
无论链表是否为空，头指针均不为空。

头结点

头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义(但也可以用来存放链表的长度)。
有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
头结点不一定是链表的必须要素。

1. 单链表

单链表的结点结构：

我们将每个结点中只包含一个指针域的链表称为单链表。
单链表的缺点：

其查找时间复杂度为O(n)，每次查找都需要从头遍历链表
存储密度小，指针域需额外占用存储空间。

不带头结点的单链表

线性表L(a1 , a2 , a3 , a4…an-1,an)的单链表存储结构为：

在这里插入图片描述

带头结点的单链表

线性表L(a1 , a2 , a3 , a4…an-1,an)的带头结点的单链表存储结构为：
在这里插入图片描述

基本操作

//结构体定义
typedef struct Lnode{	
	ElemType data; 
	struct Lnode *next;
}LNode,*LinkList

//单链表的初始化是指构建一个空表。先创建一个空结点，不存放数据，然后令其指针域为空；
bool InitList_L(LinkList &L){
	L = new Lnode; 
	if(!L) return false;
	L -> next = NULL;
	return true;
}


//创建单链表分为头插法和尾插法两种。
//头插法：是指每次将新结点插入到头结点之后，其创建的单链表和数据输入的顺序正好相反，因此也称为逆序建表。
void CreateList_H(LinkList &L){
	int n;
	LinkList s;
	L = new LNode;
	L -> next = NULL;
	cin>>n;
	while(n--){
		s = new LNode;
		cin>>s->data;
		s->next = L->next;
		L->next = s;
	}
}

//尾插法：是指每次把新结点链接到链表的尾部，其创建的单链表和数据输入顺序一致，因此也称为正序建表。
void CreatList_R(LinkList &L){	
	int n;
    LinkList s, r;
    L = new Lnode;
    L -> next = NULL;
    r = L;
    cin>>n;
    while(n--){
		s = new LNode; 
        cin >> s->data;
        s -> next = NULL; 
        r -> next = s;
        r = s; 
    }
}

//按序取值
//从单链表的第一个结点出发，顺指针逐个往下搜索，知道找到第i个结点为止，否则返回最后一个结点的指针NULL。
LinkList GetElem(LinkList L, int i){
	int j = 1; 
    LinkList p = L -> next;
    if(i == 0) return L;
    if(i < 1) return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p;
}

//插入结点
p = GetElem(L, i-1);
s -> next = p -> next;
p -> next = s;

//删除结点
p = GetElem(L, i-1);
q = p -> next;
p -> next = q -> next;