当前位置：移动技术网 > IT编程>开发语言>C/C++ > 数据结构之顺序表的实现

数据结构之顺序表的实现

2020年04月07日 | 移动技术网IT编程 | 我要评论

小灰熊3.416,甬台温线,龙女无忧

数据结构之顺序表的实现

一、原理

1.定义

顺序表是在计算机中以数组形式保存的。

2.特点

在计算机中占用连续的一段内存
一旦声明，空间大小一般不变

二、初始化相关操作

包括：

结构体的定义
顺序表的创建
顺序表清空
判断顺序表是否为空

1.结构体定义

即定一个满足顺序表定义的结构体，其中包含数组、存储长度、总长度。

typedef int elemtype; //将int抽象为elemtype，表明顺序表也可以存储其他类型（如将int改为char）
struct list
{
	elemtype *list; 
	//声明数组用于给顺序表存储数据，等价于以下声明方式
	//elemtype[] list;
	int length; //用于记录顺序表存储的数据长度
	int maxsize; //用于记录顺序表最大长度（即最多存储数据）
}

2.初始化

对顺序表进行初始化，包括分配自定义长度的数组空间，设定存储长度为0，存储长度为规定值

//初始化，传入需要初始化的顺序表和初始化长度
void initlist(struct list *l,int maxsize){
  //初始化长度合法性判断
  if(maxsize<0){
    printf("初始化长度非法!\n");
    exit(1); //退出程序
  }
  //对顺序表长度进行赋值
  l->maxsize = maxsize;
  //根据初始化长度和存储数据类型来动态分配数组
  l->list = malloc(sizeof(maxsize*sizeof(elemtype)));
  //分配成功判定
  if(!l->list){
    printf("动态分配存储失败\n");
    exit(1);
  }
  //初始化存储数据为0个
  l->length = 0;
}

3.清空

将顺序表内容清空，用于某些题目要求或节省空间

//清空，传入需要清空的顺序表
void clearlist(struct list *l){
  //判断顺序表是否已经为空
  if(l->list!=null){
    free(l->list); //释放顺序表中数组内存
    l->list = 0; 
    l->length = 0;
    l->maxsize = 0;
  }
}

4. 判断是否为空

判断顺序表是否为空，在某些操作之前，先要判断顺序表是否为空，防止出错

int isempty(struct list *l){
  return l->length==0?1:0; //顺序表最大长度为0则为空返回1，否则返回0
}

三、增加相关操作

包括：

向表头插入元素x
向表尾插入元素x
向第n个位置插入元素x
向递增的线性表中插入元素x，之后仍然保持有序

进行操作之前，还需要一个方法，当插入元素超过数组长度时，将数组容量扩大，即重新申请空间

tip:将顺序表扩大一倍空间

void remalloc(struct list *l){
	elemtype *p = realloc(l->list,2*l->maxsize*sizeof(elemtype));
  if(!p){
    printf("空间分配失败\n");
    exit(1);
  }
  l->list = p; //使list重新指向新生成的空间
  l->maxsize = 2*l->maxsize;
  printf("存储空间已经扩大为2倍\n");
}

1.向表头插入元素x

void insertelemtohead(struct list *l,elemtype x){
  int i;
  //判断存储空间是否已满
	if(l->length==l->maxsize){
    printf("存储空间已满，重新分配中...");
    remalloc(l);
  }
  //所有元素后移
  for(i=l->length;i>0;i--){
    l->list[i+1]=l->list[i];
  }
  l->list[i]=x;
  l->length++;
}

2.向表尾插入元素x

void insertelemtotail(struct list *l,elemtype x){
	 //判断存储空间是否已满
	if(l->length==l->maxsize){
    printf("存储空间已满，重新分配中...");
    remalloc(l);
  }
  l->list[l->length++]=x;
}

3.向线性表l的第n个位置插入元素x

void insertelemsomewhere(struct list *l,elemtype x,int n){
   //判断存储空间是否已满
   if(l->length==l->maxsize){
   printf("存储空间已满，重新分配中...");
   remalloc(l);
 }
 int i;
 for(i=l->length;i>=n;i--){
 	l->list[i] = l->list[i-1];
 }
 l->list[i] = x;
 l->length--;
}

四、删除相关操作

包括：

删除表头元素并返回被删除的值
删除第n个元素并返回被删除元素
从线性表l中删除值为x的第一个元素

1.删除表头元素并返回被删除的值

删除表头第一个元素，长度减少1，返回被删除的值

elemtype delheadelem(struct list *l){
	elemtype x = l->list[0];
	//合法性判断
	if(l->length==0){
		 printf("线性表为空，不能删除\n");
     exit(1);
	}
	for(int i=0;i<l->length;i++){
		l->list[i] = l->list[i+1];
	}
	l->length--;
	return x;
}

2.删除第n个元素并返回被删除元素

elemtype delsomeelem(struct list *l,int n){
  if(n<l->length){
    printf("n位置越界，不能删除");
    exit(1);
  }
  elemtype x = l->list[n-1];
  for(int i=n;i<l->length;i++){
    l->list[i]=l->list[i+1];
  }
  l->length--;
  retur x;
}

3.从线性表l中删除值为x的第一个元素

从线性表l中删除值为x的第一个元素，若删除成功则返回1，否则返回0

int delelemknown(struct list *l,elemtype x){
	int i,j;
  //先找出值为x的下标
  for(i=0;i<l->length;i++){
    if(l->list[i]==x){
      break;
    }
  }
  for(j=i;i<l->length;j++){
    l->list[j]=l->list[j+1];
  }
  l->length--;
  return 1;
}

五、修改相关操作

包括：

把线性表中第n个元素修改为x

1.把线性表中第n个元素修改为x

把线性表中第n个元素修改为x，若成功则返回1，失败返回0

int updateelemknown(struct list *l,elemtype x,int n){
	if(n>l->length||n<1){
    return 0;
  }
  l->list[n]=x;
  return 1;
}

六、查找相关操作

包括：

查找第n个位置的值
顺序遍历输出所有值
返回值等于x的下标

1.查找第n个位置的值

输入要查找的坐标，若合法则范围对应的值，若非法则提示并推出

int getelem(struct list *l,int n){
  if(n<0||n>l->maxsize){
    printf("查找位置超出长度!\n");
    exit(1);
  }
  return l->list[n-1]; //n-1的原因是查找的第n个是从1开始计数，而数组是从0开始计数
}

2.顺序遍历输出所有值

输出顺序表中的所有值

void getall(struct list *l){
	int i = 0;
	while(i<l->length){
		printf(l->list[i]+"\t");
		i++;
	}
	printf("\n");
}

3.查找值为x的节点并返回其坐标

输入要查找的值x，若存在则范围首次出现的下标，否则返回0

void findelem(struct list *l,elemtype x){
	int i;
	for(i=0;i<l->length;i++){
		if(l->list[i]==x){
			return i;
		}
	}
}

七、总结

1.优点

查找方便
空间利用率高

2.缺点

删除和增加操作效率低
空间固定，不易扩展

八、完整代码

#include "stdio.h"
#include <stdlib.h>
/**
 * =======顺序表的定义=========
 */
typedef int elemtype;
//结构体定义
struct list{
    elemtype *list;//存储数据
    int length;//存储长度
    int maxsize;//最大长度
};

//初始化
void initlist(struct list *l,int maxsize){
    //初始化长度合法性判断
    if(maxsize<0){
        printf("初始化长度非法!\n");
        exit(1); //退出程序
    }
    l->maxsize = maxsize;
    l->list = malloc(sizeof(maxsize* sizeof(elemtype)));
    //判断分配空间是否成功
    if(!l->list){
        printf("空间分配失败");
        exit(1);
    }
    l->length=0;
}

//清空
void clearlist(struct list *l){
    if(l->list!=null){
        free(l->list);
        l->list=0;
        l->maxsize=0;
        l->length=0;
    }
}

//判空
int isempty(struct list *l){
    return l->length==0?1:0;
}

/**
 * =======增加操作=========
 */

//空间再分配
void remalloc(struct list *l){
    elemtype *p = realloc(l->list,2*l->maxsize* sizeof(elemtype));
    if(!p){
        printf("空间分配失败");
        exit(1);
    }
    l->list = p;
    l->maxsize = 2*l->maxsize;
    printf("空间已扩大两倍");
}

//向表头插入元素
void insertelemtohead(struct list *l,elemtype x){
    if(l->length==l->maxsize){
        remalloc(l);
        printf("空间已满，重新分配中");
    }
    for(int i=l->length;i>0;i++){
        l->list[i-1] = l->list[i];
    }
    l->list[0] = x;
    l->length++;
}

//向表尾插入元素
void insertelemtotail(struct list *l,elemtype x){
    if(l->length==l->maxsize){
        remalloc(l);
        printf("空间已满，重新分配中");
    }
    l->list[l->length++] = x;
}

//向线性表l的第n个位置插入元素x
void insertelemsomewhere(struct list *l,elemtype x,int n){
    int i;
    if(l->length==l->maxsize){
        remalloc(l);
        printf("空间已满，重新分配中");
    }
    for(i=l->length;i>=n;i--){
        l->list[i]=l->list[i-1];
    }
    l->list[i]=x;
    l->length++;
}

/**
 * =======删除操作=========
 */

//删除表头元素并返回被删除的值
void delheadelem(struct list *l){
    elemtype x = l->list[0];
    if(l->length==0){
        printf("顺序表为空，删除失败!");
        exit(1);
    }
    for(int i=1;i<l->length;i++){
        l->list[i-1] = l->list[i];
    }
    l->length--;
}

//删除第n个元素并返回被删除元素
elemtype delsomeelem(struct list *l,int n){
    elemtype x = l->list[n-1];
    if(n>l->length){
        printf("n位置越界，不能删除");
        exit(1);
    }
    for(int i=n;i<l->length;i++){
        l->list[i-1] = l->list[i];
    }
    l->length--;
    return x;
}

//从线性表l中删除值为x的第一个元素
int delelemknown(struct list *l,elemtype x){
    int i,j;
    for(i=0;i<l->length;i++){
        if(l->list[i]==x){
            break;
        }
    }
    for(j=i;j<l->length;j++){
        l->list[j]=l->list[j+1];
    }
    l->length--;
    return 1;
}

/**
 * =======修改操作=========
 */
//把线性表中第n个元素修改为x
int updateelemknown(struct list *l,elemtype x,int n){
    if(n>l->length||n<1){
        return 0;
    }
    l->list[n]=x;
    return 1;
}

/**
 * =======查找操作=========
 */
 //查找第n个位置的值
 int getelem(struct list *l,int n){
     if(n<0||n>l->maxsize){
         printf("查找位置超出长度!\n");
         exit(1);
     }
     return l->list[n-1]; //n-1的原因是查找的第n个是从1开始计数，而数组是从0开始计数
 }

 //顺序遍历输出所有值
 void getall(struct list *l){
     int i = 0;
     while(i<l->length){
         printf("%d\t",l->list[i]);
         i++;
     }
     printf("\n");
 }
//查找值为x的节点并返回其坐标
int findelem(struct list *l,elemtype x){
    int i;
    for(i=0;i<l->length;i++){
        if(l->list[i]==x){
            return i;
        }
    }
}

//主函数
int main()
{
     //初始化操作测试
    struct list l;
    initlist(&l,20);
    //插入操作测试
    insertelemtohead(&l,2);
    insertelemsomewhere(&l,4,2);
    insertelemtotail(&l,5);
    printf("%d\n",l.list[0]);
    printf("%d\n",l.list[1]);
    //删除操作测试
    delelemknown(&l,2);
    printf("%d\n",l.list[0]);
    //修改操作测试
    updateelemknown(&l,8,1);
    //查找操作测试
    printf("%d\n",getelem(&l,2));
    printf("%d\n",findelem(&l,8));
    printf("%d\n",l.list[0]);
    getall(&l);
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！点击进行留言回复

C++ 作用域

作用域：名称在翻译单元（包括文件）的可见范围局部：只在定义它的代码块中可用，如自动变量全局（文件作用域）：从定义位置到文件结尾都可用注意：静... [阅读全文]
Prim计算最小生成树权值 C语言

题目描述现在，你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先，你会给定在区域里面的一系列结点，和连接这些结点的一组线路。对于每条可能使用... [阅读全文]
C打印楼梯，同时在楼梯上方打印两个笑脸

题目：打印楼梯，同时在楼梯上方打印两个笑脸。程序分析：用 ASCII 1 来输出笑脸；用i控制行，j来控制列，j根据i的变化来控制输出黑方格的个数。 ... [阅读全文]
算法笔记刷题6 ( PAT 1003我要通过 )

算法笔记刷题6 ( PAT1003我要通过 ) 题目本体 “ 答案正确 ”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“ 答案正确 ”大派... [阅读全文]
聚合类型与POD类型

Lippman在《深度探索C++对象模型》的前言中写道： I have heard a number of people over the years ... [阅读全文]
GetAsyncKeyState 获取键盘按键消息

1 #include <Windows.h> 2 #include <iostream> 3 using namespace s... [阅读全文]
c primer plus(中文版)第一章的一处错误

c primer plus(中文版)1.8.8 第三段第三段第一句：“UNIX系统内置Mac OS X”。这句话讲不通，UNIX系统内置MAC OS ... [阅读全文]
如何在没有core文件的情况下用dmesg+addr2line定位段错误

前言在现网环境下，程序奔溃后不一定会留下core文件，原因有很多，比如存储空间不足就是其中一个常见的原因。此时我们只能依据linux记录的错误日志来定位... [阅读全文]
用QT制作3D点云显示器——QtDataVisualization

因为QT的三维显示模块QtDataVisualization已经对个人开发免费开放了，所以在制作点云，地图，表格之类的东西的时候，其实我们都不需要使用Q... [阅读全文]
判断一个数是否为素数（质数）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 ... [阅读全文]

网友评论


验证码：

数据结构之顺序表的实现

2020年04月07日 | 移动技术网IT编程 | 我要评论

数据结构之顺序表的实现

一、原理

1.定义

2.特点

二、初始化相关操作

1.结构体定义

2.初始化

3.清空

4. 判断是否为空

三、增加相关操作

tip:将顺序表扩大一倍空间

1.向表头插入元素x

2.向表尾插入元素x

3.向线性表l的第n个位置插入元素x

四、删除相关操作

1.删除表头元素并返回被删除的值

2.删除第n个元素并返回被删除元素

3.从线性表l中删除值为x的第一个元素

五、修改相关操作

1.把线性表中第n个元素修改为x

六、查找相关操作

1.查找第n个位置的值

2.顺序遍历输出所有值

3.查找值为x的节点并返回其坐标

七、总结

1.优点

2.缺点

八、完整代码

您可能感兴趣的文章:

相关文章:

网友评论