-
前面讲了线性表的初始化，接下来继续探讨它的其它操作，但是如果线性表里面没数据元素的话，也就没办法讲其它元素了。所以先探讨下线性表是如何插入数据元素的。插入操作是ADT的一个基本操作。
-
当时ADT是这么设计插入操作的：bool listInsert(*L,i,e); //插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1])，成功返回true.
插入操作会改变原有链表，所以要用地址传递。函数设计如下：
/* 初始条件：顺序线性表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;
}
举个例子：在春运时去买火车票，大家都排队排的好好的。这时来了一个美女，对着队伍中排在第三位的你说，“大哥，求求你帮帮忙，我家母亲有病，我得急着回去看她，这队伍这么长，你可否让我排在你的前面？ ”你心一软，就同意了。这时，你必须得退后一步，否则她是没法进到队伍来的。这可不得了，后面的人像蠕虫一样，全部都得退一步，骂起四声。但后面的人也不清楚这加塞是怎么回事，没什么办法。
-
这个例子其实已经说明了线性表的顺序存储结构，在插入数据时的实现过程：如果插队的元素不在表尾（在表尾就不叫插队了），那么让原先i位置及以后的元素全部后退一位。具体过程为，最后一位 L->data[k+1] = L->data[k]，然后倒数第二位……如此循环，直到 k>=i-1。最后，把 i-1 的位置给e，整个线性表长度 +1，插入完成。
插入算法的思路：
- 如果插入位置不合理，抛出异常；
- 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
- 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
- 将要插入元素填入位置i处；
- 表长加1。
要演示程序，还需要一些操作，比如给线性表随机赋10个值：
//顺序表的建立
SqList Create(SqList L)
{
int i;
srand((unsigned)time(NULL));
for(i=0; i < 10; i++)
{
L.data[i] = rand()%100;
L.length++;
}
return L;
}
// 调用
L = Create(L);
-
每插入一个元素，注意表长要加1. 下面是遍历操作的函数：
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i < L.length;i++)
visit(L.data[i]);
printf("\n");
return OK;
}
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
-
遍历操作比较简单，代码就说明问题了。下面是完整的程序演示，你可以试着运行一下：
#include "stdio.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length; /* 线性表当前长度 */
}SqList;
/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
//顺序表的建立
SqList Create(SqList L)
{
int i;
srand((unsigned)time(NULL));
for(i=0; i < 10; i++)
{
L.data[i] = rand()%100;
L.length++;
}
return L;
}
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i < L.length;i++)
visit(L.data[i]);
printf("\n");
return OK;
}
/* 初始条件：顺序线性表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;
}
int main()
{
SqList L;
ElemType e;
Status i;
char opp;
int j,k;
int pos;
ElemType value;
i=InitList(&L);
printf("初始化成功，L.length=%d\n",L.length);
printf("\n1.遍历线性表 \n2.线性表赋值 \n3.线性表插入 \n0.退出 \n请选择你的操作：\n");
while(opp != '0'){
scanf("%c",&opp);
switch(opp){
case '1':
ListTraverse(L);
printf("\n");
break;
case '2':
L = Create(L);
printf("在L的表头依次插入1～5后：L.data=");
ListTraverse(L);
printf("\n");
break;
case '3':
printf("请输入插入元素位置：");
scanf("%d",&pos);
printf("请输入插入元素的值：");
scanf("%d",&value);
i = ListInsert(&L,pos,value);
printf("插入完毕，现在线性表为：\n");
ListTraverse(L);
printf("\n");
break;
case '0':
exit(0);
}
}
}
延伸阅读
此文章所在专题列表如下：
- 第01话：线性表的概念与定义
- 第02话：线性表的抽象数据类型ADT定义
- 第03话：线性表的顺序存储结构
- 第04话：线性表的初始化
- 第05话：线性表的遍历、插入操作
- 第06话：判断线性表是否为空与置空操作
- 第07话：线性表的查找操作
- 第08话：线性表删除某个元素
- 线性表顺序存储的优缺点
- 线性表链式存储结构的由来与基本概念
- 单链表的头指针、头结点与首元结点
- 单链表的结构体定义与声明
- 单链表的初始化
- 单链表的插入与遍历操作
- 单链表的删除某个元素的操作
- 获取单链表中的指定位置的元素
- 查找某数在单链表中的位置
- 用头插法实现单链表整表创建
- 用尾插法实现单链表整表创建
- 将单链表重置为空表
- 单链表反转/逆序的两种方法
- 单链表反转/逆序的第三种方法
- 求单链表倒数第N个数
- 用标尺法快速找到单链表的中间结点
- 如何判断链表是否有环的存在
- 单链表建环，无环链表变有环
- 删除单链表中的重复元素
本文地址：http://www.nowamagic.net/librarys/veda/detail/2202，欢迎访问原出处。
