第05话:线性表的遍历、插入操作

详细介绍插入操作的算法思路
服务器君一共花费了269.132 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议
  • 前面讲了线性表的初始化,接下来继续探讨它的其它操作,但是如果线性表里面没数据元素的话,也就没办法讲其它元素了。所以先探讨下线性表是如何插入数据元素的。插入操作是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);
        }
    }
}

延伸阅读

此文章所在专题列表如下:

  1. 第01话:线性表的概念与定义
  2. 第02话:线性表的抽象数据类型ADT定义
  3. 第03话:线性表的顺序存储结构
  4. 第04话:线性表的初始化
  5. 第05话:线性表的遍历、插入操作
  6. 第06话:判断线性表是否为空与置空操作
  7. 第07话:线性表的查找操作
  8. 第08话:线性表删除某个元素
  9. 线性表顺序存储的优缺点
  10. 线性表链式存储结构的由来与基本概念
  11. 单链表的头指针、头结点与首元结点
  12. 单链表的结构体定义与声明
  13. 单链表的初始化
  14. 单链表的插入与遍历操作
  15. 单链表的删除某个元素的操作
  16. 获取单链表中的指定位置的元素
  17. 查找某数在单链表中的位置
  18. 用头插法实现单链表整表创建
  19. 用尾插法实现单链表整表创建
  20. 将单链表重置为空表
  21. 单链表反转/逆序的两种方法
  22. 单链表反转/逆序的第三种方法
  23. 求单链表倒数第N个数
  24. 用标尺法快速找到单链表的中间结点
  25. 如何判断链表是否有环的存在
  26. 单链表建环,无环链表变有环
  27. 删除单链表中的重复元素

本文地址:http://www.nowamagic.net/librarys/veda/detail/2202,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2202

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《C程序设计语言(第2版新版)》 克尼汉 (作者), 等 (作者, 译者), 徐宝文 (译者)

《C程序设计语言》(第2版新版)是由C语言的设计者Brian W.Kernighan和Dennis M.Ritchie编写的一部介绍标准C语言及其程序设计方法的权威性经典著作。全面、系统地讲述了C语言的各个特性及程序设计的基本方法,包括基本概念,类型和表达式、控制流、函数与程序结构、指针与数组、结构、输入与输出、UNIX系统接口、标准库等内容。

更多计算机宝库...