⽤c语⾔实现在带头结点的单链线性表l中的第i个位置之后插⼊
元素e,（1）线性表...
(⼀)线性表
⼀、线性表的定义
1、线性结构的特点
在数据元素的⾮空有限集中，(1)存在唯⼀的⼀个被称作“第⼀个”的数据元素；(2)存在惟⼀的⼀个被称作“最后⼀个”的数据元素；(3)除第⼀个之外，集合中的每个数据元素均只有⼀个前驱；(4)出最后⼀个之外，集合中每个数据元素均只有⼀个后继。
2、线性表
⼀个线性表n个数据元素(或结点)的有序序列：
a0，a1，a2，···，an-1
其中a0是开始结点，an-1是终端结点，ai是ai+1的前驱结点，ai+1是ai的后继结点。⼀个数据元素可以由
若⼲个数据项组成。在这种情况下，常把数据元素称为记录。含有⼤量记录的线性表称为⽂件。
3、线性表的常⽤基本操作
ElemType GetElement(Sqlist L,int i,EleType &e) //⽤e返回L中第i个数据元素的值
status ListInsert(Sqlist &L,int i,EleType e) //在L中第i个位置之前插⼊新的数据元素e，L长度加1
status ListDelete(Sqlist &L,int i,EleType &e); //删除L的第i个数据元素，并⽤e返回s其值，L长度减1
注：
以上操作均限定1<=i<=ListLength(L)
&这个符号并不是C语⾔中的取地址操作，⽽是为了便于C语⾔的算法描述，除了值调⽤以外，增添了C++语⾔的引⽤调⽤的参数传递⽅式。
⼆、线性表的顺序表⽰和实现
1、线性表的顺序表⽰
指的是⽤⼀组地址连续的存储单元依次存储线性表的数据元素。这样，线性表中第0个元素的存储位置就是指定的存储位置，第i个元素
(1<=i<=n-1)的存储位置紧接在第i-1个元素的存储位置的后⾯。顺序存储的线性表可简称为顺序表。线性表的顺序存储⽰意图见下图1.1
(图1.1 线性表的顺序存储⽰意图)
假设线性表的元素类型为ElemType，那么每个元素占⽤的存储空间⼤⼩即为sizeof(ElemType)，图中令l = sizeof(ElemType)。因此我们可以得出，在顺序存储⽅式下，只要我们知道线性表的⾸址以及数据元素的为序以及⼤⼩，我们就能够得到这个数据元素的存储地址，因此线性表的顺序存储是可以实现随机存取的。
maxlen定义为⼀个整型常量，为线性表中的最⼤元素数。如果线性表最多只有100个元素，可定义如下：
#define maxlen 100
typedef struct{
ElemType element[maxlen];//存放数据元素
int len; // 存放线性表的长度
}Sqlist;    2、顺序表基本操作的实现
(1)ElemType GetElement(Sqlist L,int i)：返回L中第i个数据元素的值
ElemType GetElem(Sqlist L,int i)
{
if(i<0 || i>L.len-1)
Error("顺序表下标访问越界");
else
return(L.element[i]);
}    (2)status ListInsert(Sqlist &L,int i,EleType e)：在L中第i个位置之前插⼊新的数据元素e，L长度加1  status ListInsert(Sqlist &L,int i,EleType e)
{
int j;
if(i<0 || i>L.len-1) //顺序表下界访问越界
return ERROR;
else
{
for(j=L.len-1;j>=i;j--) //结点后移，为插⼊腾出位置
{
L.data[j+1] = L.data[j];
}
L.data[i] = e; //插⼊e
L.len++;
return OK; //成功插⼊
}
}
说明：顺序表进⾏插⼊时要移动i后的所有元素，因此，插⼊效率不⾼。
(3)status ListDelete(Sqlist &L,int i,EleType &e) ：删除L的第i个数据元素，并⽤e返回s其值，L长度减1 status ListDelete(Sqlist &L,int i,EleType &e)
{
int j;
if(i<0 || i>L.len-1) //顺序表下界访问越界
return ERROR;
else
{
e = L.data[i];
for(j=i;j
L.data[j] = L.data[j+1];
L.len--;
return OK;
}
}    说明：对顺序表进⾏删除时要将删除位置后的所有元素前移，因此删除的效率也不⾼。
3、线性表的链式存储及其实现
链式存储就是使⽤链表实现的存储结构，它不需要⼀组连续的存储单元，⽽是可以使⽤⼀组任意的，甚⾄是在存储空间中零散分布的存储单元存放线性表的数据，从⽽解决了顺序存储线性表需要⼤块连续存储单元的缺点。
(1)线性链表
为了表⽰每个数据元素与其直接后继元素之间的逻辑关系，我们在每个节点中除包含有数据域外，还设置了⼀个指针域，⽤来指向其后续结点。这样构成的链表称为线性链表或者单链表。
单链表分为带头节点和不带头节点两种。单链表带头节点好处有⼆：第⼀，有头结点后，插⼊和删除数据元素的算法统⼀了，不再需要判断是否在第⼀个元素之前插⼊和删除第⼀个元素；第⼆，不论链表是否为空，链表指针不变。因此，为了简便，以下讨论的都是带头节点的单链表。如果为空表，那么头结点的指针域为空(NULL)。
头指针是指指⽰链表中第⼀个结点存储位置的指针。头结点是指在单链表第⼀个结点前所附设的⼀个结点，这个结点的指针域存储指向第⼀个结点(包括头结点)的 指针。图1.2中，L为头指针，带阴影的结点为头结点。
由以上描述可知，如果想知道链表中某⼀个结点的信息，就必须知道这个结点的直接前驱结点的信息，因为此节点的存储位置保存在其直接前驱的地址域⾥。所以，链表是⽆法实现随机存取的。
下⾯定义线性链表的存储结构：
typedef struct LNode
{
ElemType data; //数据域
struct LNode * next; //指针域
}LNode, *LinkList;        (2)线性链表基本操作的实现
1)ElemType GetElem(Linklist L, int i)：⽤e返回L中第i个数据元素的值。
ElemType GetElem(Linklist L, int i)
{
//L为带头节点的单链表的头指针
p = L->next; //让p指向L中的第⼀个元素
j = 1 ; //j为计数器，
while(p&&j
//顺指针往下，直到p指向第i个元素或者p为空(即下标越界)
p = p->next;
j++;
}
if(!p || j>i)
error(0);
e = p->data;
return e;
}      说明：在给出线性表某⼀节点的位序后，我们必须从单链表的头结点开始，将位置标志指针p⼀直往下移动，如果我们需要的是线性表的最后⼀个元素，那么这个指针就将从链表头移动到链表尾，因此⽤单链表存储的线性表在对结点进⾏随机查询上效率是⾮常低的。
2)status ListInsert(LinkList &L,int i,ElemType e)：在L中第i个位置之前插⼊新的数据元素e
假设我们要在线性表的两个元素a和b之间插⼊⼀个元素x，指针的指向情况如图1.3所⽰。图1.3：单链表插⼊结点的指针变化情况：
⾸先要⽣成⼀个数据域是x的结点，然后使得x的指针域指向b结点，最后修改a结点的指针域，使其指向x结点。注意：这个步骤是不能调换顺序的！简单描述如下：
s->next = p->next;    p->next = s;
完整算法描述如下：
status ListInsert(LinkLiST &l,int i,ElemType e)
{
//在带头结点的单链表L中第i个位置之前插⼊元素e
p = L;
j = 0;
while(p&&j
p = p->next;
j++;
}
if(!p || j>i-1)
return ERROR;c语言listinsert函数
s = (LinkList)malloc(sizeof(LNode));//⽣存新节点
s->data = e; //插⼊结点
s->next = p->next;
p->next = s;
return OK;
}
说明：单链表中插⼊数据时，不再需要像顺序表⼀样⼤量移动⼤量的结点已完成结点的插⼊，⽽只需要简单的修改⼏个指针即可，插⼊效率提⾼。并且还能很⽅便的实现线性表长度的动态变化，更加灵活的使⽤计算机内存资源。
(未完待续......)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。