结构之美:线性表的查找、插入与删除操作

顺序存储结构的操作
服务器君一共花费了325.807 ms进行了8次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

上一篇讲了线性表的定义与初始化,接下来需要了解一下线性表的一些基本操作。

查找

查找线性表是最基本的操作之一,比如根据序号查找元素的值,或者根据值查找该值是否在线性表中,如果在,那么序号是几等等。

我们来看下面一段代码:

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;          /* Status是函数的类型,其值是函数结果状态代码,如OK等 */

/* 初始条件:顺序线性表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;
}

以上代码就是用来获得某一元素的操作。

插入

有了以上的基础,我们就能对顺序存储结构的插入与删除做一个讲解了。首先,我们来了解下插入操作。

  1. 如果插入的位置不合理,那么就抛出异常。
  2. 如果线性表长度大于等于数组长度,则抛出异常或者动态增加容量。
  3. 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置。
  4. 将要插入的元素填入位置i处。
  5. 表长加1。

C语言实现代码如下:

/* 初始条件:顺序线性表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;
}

删除

然后,我们一起看看删除操作。还是从思路开始说:

  1. 如果删除位置不合理,抛出异常
  2. 取出删除元素
  3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们向前移动一个位置
  4. 表长减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 (ilength)                /* 如果删除不是最后位置 */
    {
        for(k=i;klength;k++)/* 将删除位置后继元素前移 */
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

分析上述插入和删除两段代码和更早的获取元素代码,我们可以发现,线性表的顺序存储结构,在存/读数据时,不管是哪个位置,时间复杂度O(1),而插入或删除时,时间复杂度都是O(n)。

说完了顺序存储结构,我们可以总结下它的优缺点了,喜欢先听优点还是先听缺点呢?

好吧,从优点开始说。当我们在使用线性表的时候,我们不需要为表中元素之间的逻辑关系而增加额外的存储空间,而且可以快速的存取表中任意位置的元素。接下来谈谈缺点。如我们所见,如果我们要插入或者删除的元素是在第一个位置,那么无疑的,我们需要移动大量的元素来完成这样的操作,而且限于线性表长度必须小于数组长度,如果我们需要插入大量数据,那么很难保证空间是否充足,而如果我们要删除大量数据的时候,无疑又会造成空间的浪费。

下面附上本例的完整代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

//顺序表的初始化
SqList Init()
{   //构造一个空的线性表L,时间复杂度O(1)
    SqList L;       //定义一个顺序表
    L.length = 0;   //顺序表的长度为0
    return L;       //返回空顺序表
}

//顺序表的建立
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已存在,1≤i≤ListLength(L) */
/* 操作结果:用e返回L中第i个数据元素的值,注意i是指位置,第1个位置的数组是从0开始 */
ElemType GetElem(SqList L,int i)
{//
    if(i < 1 || i > L.length)
    {
        printf("查找位置错误!\n");//检查查询位置是否合法
        return 0;
    }
    else
        return L.data[i-1];
}

//顺序表的插入
SqList SqListInsert(SqList L, int i, ElemType x)
{   //在顺序表中的第i个位置插入元素x
    if(L.length == MAXSIZE)
        printf("表已经满了\n");//插入时,必须检查表是否已经满了。否则会出现溢出错误
    else if(i < 1 || i > L.length)
        printf("插入位置错误\n");//判断插入位置的有效性

    int j;
    for(j = L.length-1; j >= i - 1; j--)//第i个位置元素逐个后移
        L.data[j+1] = L.data[j];
    L.data[i-1] = x;                        //插入元素x
    L.length++;                         //顺序表长度增1
    return L;
}

SqList SqListDelete(SqList L,int i)
{//删除顺序表中的第i个位置的元素
    if(i < 1 || i > L.length)
        printf("删除位置错误\n");     //检查删除位置是否合法
    int j;
    for(j = i-1; j < L.length; j++)
        L.data[j] = L.data[j+1];        //将第i个位置之后的元素前移

    L.length--;                         //顺序表长度-1
    return L;
}

int main()
{
    SqList nmList;
    nmList = Init();
    nmList = Create(nmList);
    int find;
    int found;
    int pos;
    ElemType value;
    char opp;

    int i;
    printf("顺序表初始化为:");
    for(i=0; i < nmList.length; i++)
	{
        printf("%d ", nmList.data[i]);
	}

    printf("\n1.查看顺序表 \n2.查找 \n3.插入 \n4.删除 \n0.退出 \n请选择你的操作:\n");
    while(opp != '0'){
        scanf("%c",&opp);
        //printf("\n 1.查找 \n 2.插入 \n 3.排序 \n 0.退出 \n 请选择你的操作:\n");
        switch(opp){
            case '1':
                printf("\n查看顺序表:");
                for(i=0; i < nmList.length; i++)
                {
                    printf("%d ", nmList.data[i]);
                }
                printf("\n");
                break;
            case '2':
                printf("\n进入查找功能,请问需要查找第几个元素:");
                scanf("%d",&find);
                printf("%d",find);
                found = GetElem(nmList, find);
                printf("第%d个值为%d ", find, found);
                printf("\n");
                break;
            case '3':
                printf("进入插入功能,请输入插入元素位置:");
                scanf("%d",&pos);
                printf("请输入插入元素的值:");
                scanf("%d",&value);
                nmList = SqListInsert(nmList,pos,value);

                printf("\n插入元素后顺序表为:");
                for(i=0; i < nmList.length; i++)
                {
                    printf("%d ", nmList.data[i]);
                }
                printf("\n");
                break;
            case '4':
                printf("进入删除功能,请输入删除元素位置:");
                scanf("%d",&pos);
                nmList = SqListDelete(nmList,pos);

                printf("\n删除元素后顺序表为:");
                for(i=0; i < nmList.length; i++)
                {
                    printf("%d ", nmList.data[i]);
                }
                printf("\n");
                break;
            case '0':
                exit(0);
        }
    }

}

延伸阅读

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

  1. 结构之美:定义一个线性表
  2. 结构之美:线性表的查找、插入与删除操作
  3. 结构之美:线性表的链式存储结构——链表
  4. 结构之美:单链表的初始化、创建与遍历
  5. 结构之美:单链表的头结点与头指针
  6. 结构之美:使用头插法创建单链表
  7. 结构之美:使用尾插法创建单链表
  8. 结构之美:单链表的销毁删除
  9. 结构之美:查找单链表指定位置结点的数据
  10. 结构之美:在单链表指定位置插入数据
  11. 结构之美:删除单链表指定位置的数据
  12. 结构之美:单链表逆序
  13. 结构之美:判断单链表中是否有环
  14. 结构之美:获取单链表倒数第N个结点值
  15. 单循环链表的初始化、创建、删除、查找与遍历
  16. 结构之美:双向循环链表的结构与定义

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

不打个分吗?

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

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

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

大家都在看

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

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

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

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

《算法导论(原书第2版)》 科曼(Cormen T.H.) (作者), 等 (作者, 译者), 潘金贵 (译者)

《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明,对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

更多计算机宝库...