标签：结点单链线性表 ai 元素 next

【知识框架】

1.线性表的定义

线性表（List）：零个或多个数据元素的有限序列。

若将线性表记为(a₁,…,a_i-1,a_i,a_i+1,…,a_n)，则表中a_i-1领先于a_i，引领先于a_i+1，称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素。当i=1,2,…,n-1时，a_i 有且仅有一个直接后继，当i=2,…,n-1,n时，a_i中有且仅有一个直接前驱。如图所示。

所以线性表元素的个数n (n>O)定义为线性表的长度，当n=0时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如a₁是第一个数据元素，a_n是最后一个数据元素，a_i是第i个数据元素，称i为数据元素a_i在线性表中的位序。

2.线性表的抽象数据类型

线性表的数据元素插入

/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void unionL(SqList *La,SqList Lb)
{
	int La_len,Lb_len,i;
	ElemType e;                        /*声明与La和Lb相同的数据元素e*/
	La_len=ListLength(*La);            /*求线性表的长度 */
	Lb_len=ListLength(Lb);
	for (i=1;i<=Lb_len;i++)
	{
		GetElem(Lb,i,&e);              /*取Lb中第i个数据元素赋给e*/
		if (!LocateElem(*La,e))        /*La中不存在和e相同数据元素*/
			ListInsert(La,++La_len,e); /*插入*/
	}
}

3.线性表的顺序存储结构

3.1顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表(a₁,…,a_i-1,a_i,a_i+1,…,a_n)的顺序存储示意图如下：

3.2顺序存储方式

#define MAXSIZE 20          /* 存储空间初始分配量 */
typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
    ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
    int length;             /* 线性表当前长度 */
}SqList;

3.3数组长度与线性表长度区别

数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

在任意时刻，线性表的长度应该小于等于数组的长度。

3.4地址计算方法

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数）。

\[LOC(a_{i+1}) = LOC(a_{i})+c \]

所以对于第i个数据元素a_i的存储位置可以由a₁推算得出：

\[LOC(a_{i}) = LOC(a_{1})+(i-1)*c \]

结合下图理解：

它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

4.顺序存储结构的插入与删除

4.1获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
            return ERROR;
    *e=L.data[i-1];

    return OK;
}

4.2插入操作

插入算法的思路：

■如果插入位置不合理，抛出异常；

■如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

■从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；

■将要插入元素填入位置i处；

■表长加1。

实现代码如下：

/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{ 
	int k;
	if (L->length==MAXSIZE)  /* 顺序线性表已经满 */
		return ERROR;
	if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
		return ERROR;

	if (i<=L->length)        /* 若插入数据位置不在表尾 */
	{
		for(k=L->length-1;k>=i-1;k--)  /* 将要插入位置之后的数据元素向后移动一位 */
			L->data[k+1]=L->data[k];
	}
	L->data[i-1]=e;          /* 将新元素插入 */
	L->length++;

	return OK;
}

4.3删除操作

删除算法的思路：

■如果删除位置不合理，抛出异常；

■取出删除元素；

■从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；

■表长减1。

实现代码如下：

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e) 
{ 
    int k;
    if (L->length==0)               /* 线性表为空 */
		return ERROR;
    if (i<1 || i>L->length)         /* 删除位置不正确 */
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)                /* 如果删除不是最后位置 */
    {
        for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */
			L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。当然，它的优缺点还不只这些…...

4.4线性表顺序存储结构的优缺点

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

5.1顺序存储结构不足的解决办法

线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢？

5.2线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

为了表示每个数据元素a_i与其直接后继数据元素a_i+1之间的逻辑关系，对数据元素a_i来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的倍息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素a_i的存储映像，称为结点(Node)。
n个结点(a_i的存储映像）链结成一个链表，即为线性表(a₁,a₂,…,…,a_n) 的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里？

最后一个，就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为 “空” （通常用NULL或 “ ^ ” 符号表示）。

为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

5.3头指针与头结点的异同

5.4线性表链式存储结构代码描述

改用更方便的存储示意图来表示单链表

带有头结点的单链表

空链表如图

单链表中，我们在C语言中可用结构指针来描述。

//线性表的单链表存储结构
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */

结点由存放数据元素的数据域存放后继结点地址的指针域组成。假设p是指向线生表第i个元素的指针，则该结点a_i的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点a的指针域可以用 p->next 来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i+1个元素，即指向a_i+1的指针。也就是说，如果p->data=a,, 那么p->next->data=a_i+1，如图。

5.6单链表的读取

获得链表第1个数据的算法思路：

(1)声明一个指针p指向链表第一个结点，初始化j从1开始；

(2)当j<i时，就遍历链表，让p的指针向后移动，不断指向下结点，j累加1;

(3)若到链表末尾p为空，则说明第i个结点不存在；

(4)否则查找成功，返回结点p的数据。

实现代码算法如下：

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
	int j;
	LinkList p;		/* 声明一结点p */
	p = L->next;		/* 让p指向链表L的第一个结点 */
	j = 1;		/*  j为计数器 */
	while (p && j<i)  /* p不为空或者计数器j还没有等于i时，循环继续 */
	{   
		p = p->next;  /* 让p指向下一个结点 */
		++j;
	}
	if ( !p || j>i ) 
		return ERROR;  /*  第i个元素不存在 */
	*e = p->data;   /*  取第i个元素的数据 */
	return OK;
}

5.7单链表的插入与删除

5.7.1单链表的插入

假设存储元素e的结点为s，要实现结点p、p->next和s之间逻辑关系的变化，只需将结点s插入到结点p和p->next之间即可。

代码实现：

s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
p->next = s;          /* 将s赋值给p的后继 */

解读这两句代码，也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点。

插入结点s后，链表如图所示。

对于单链表的表头和表尾的特殊情况，操作是相同的，如图所示。

单链表第i个数据插入结点的算法思路：

1.声明一结点p指向链表第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;

3.若到链表末尾p为空，则说明第i个元素不存在；

4.否则查找成功，在系统中生成一个空结点s;

5.将数据元素e赋值给s->data;

6.单链表的插入标准语句s->next=p->next; p->next=s;

7.返回成功。

/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{ 
	int j;
	LinkList p,s;
	p = *L;   
	j = 1;
	while (p && j < i)     /* 寻找第i个结点 */
	{
		p = p->next;
		++j;
	} 
	if (!p || j > i) 
		return ERROR;   /* 第i个元素不存在 */
	s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
	s->data = e;  
	s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
	p->next = s;          /* 将s赋值给p的后继 */
	return OK;
}

5.7.2单链表的删除

现在我们再来看单链表的删除。设存储元素a的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可，如图所示。

代码实现：

q = p->next;
p->next = q->next;			/* 将q的后继赋值给p的后继 */

单链表第i个数据删除结点的算法思路：
(1)声明一指针p指向链表头结点，初始化j从1开始；

(2)当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；

(3)若到链表末尾p为空，则说明第i个元素不结点；

(4)否则查找成功，将欲删除的结点p->next赋值给q;

(5)指单链表的删除标准语句p->next=q->next;

(5)将q结点中的数据赋值给e，作为返回；

(6)释放q结点；

(7)返回成功。

实现代码算法如下：

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e) 
{ 
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while (p->next && j < i)	/* 遍历寻找第i个元素 */
	{
        p = p->next;
        ++j;
	}
	if (!(p->next) || j > i) 
	    return ERROR;           /* 第i个元素不存在 */
	q = p->next;
	p->next = q->next;			/* 将q的后继赋值给p的后继 */
	*e = q->data;               /* 将q结点中的数据给e */
	free(q);                    /* 让系统回收此结点，释放内存 */
	return OK;
}

分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实都是由两部分组成。第一部分就是遍历查找第i个元素；第二部分就是插入和删除元素。
从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

5.8单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的悄况和实际的需求即时生成。
所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建的算法思路：

1.声明一结点p和计数器变量i;

2.初始化—空链表L;

3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表；

4.循环：
♦生成一新结点赋值给p;
♦随机生成一数字赋值给p的数据域p->data;
♦将p插入到头结点与前一新结点之间。

实现代码算法如下（头插法）：

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L, int n) 
{
	LinkList p;
	int i;
	srand(time(0));                         /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
	for (i=0; i<n; i++) 
	{
		p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;             /*  随机生成100以内的数字 */
		p->next = (*L)->next;    
		(*L)->next = p;						/*  插入到表头 */
	}
}

实现代码算法如下（尾插法）：

/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
void CreateListTail(LinkList *L, int n) 
{
	LinkList p,r;
	int i;
	srand(time(0));                      /* 初始化随机数种子 */
	*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
	r=*L;                                /* r为指向尾部的结点 */
	for (i=0; i<n; i++) 
	{
		p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
		p->data = rand()%100+1;           /*  随机生成100以内的数字 */
		r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
		r = p;                            /* 将当前的新结点定义为表尾终端结点 */
	}
	r->next = NULL;                       /* 表示当前链表结束 */
}

这里需解释一下，r->next=p;的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p，如图所示，当中①位置的连线就是表示这个意思。

循环结束后，那么应该让这个链表的指针域置空，因此有了“r->next=NULL;"。

参考资料来源：

大话数据结构

标签：结点,单链,线性表,ai,元素,next
From： https://www.cnblogs.com/codemagiciant/p/17516485.html

1.线性表