顺序表是线性表的一种存储结构。
什么是线性表? 线性表是一种常用的数据结构。其数据元素之间在逻辑上具有“一对一”的关系。所谓的“一对一”,就是除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表)。类似的,在逻辑上具有“一对多”的关系的数据结构是:树。在逻辑上具有“多对多”的关系的数据结构是:图。 什么是顺序表? 线性表在逻辑上是是“一对一”的关系,把这些具有“一对一”关系的数据存储到物理内存中有两种方式:一是,存储在连续的内存中,这就是顺序存储结构,即顺序表。二是,存储在不连续的内存中,这就是链式存储结构,即链表。请看下图: 顺序表与数组有何不同? 顺序表,最终是借助数组(静态数组或动态数组)来实现的,所以,顺序表,简单理解就是数组。如果要做区分的话,简单地认为顺序表是数据结构里的概念,数组是编程语言中的概念。 顺序表的基本操作(用静态数组实现)
1、顺序表的结构定义 2、创建一个顺序表:(5,2,0,13,14) 3、查找操作 4、替换旧元素old_elem为新元素new_elem 5、替换位置pos上的数据为elem 6、插入操作 7、删除操作 以上就是关于顺序表的一些介绍及线性表的一些操作,如:插入、删除、查找、替换等。可以发现,顺序表的插入与删除操作代价很高,插入或者删除元素都要移动很多元素。 欢迎关注小编,每天与小编一起打卡学习。每天进步一点点,加油! 程序运行结果: 完整代码: /*---------------------------------------------------------------------------------------- 程序说明:顺序表 创建日期:2018.12.08 by LiZhengNian
----------------------------------------------------------------------------------------*/ #include <stdio.h> #include <stdlib.h>
/* 数组长度及顺序表的初始化长度 */ #define MAX_SIZE 10 #define LEN 5
/* 数据元素类型 */ typedef int SqType;
/* 顺序表的结构定义 */ typedef struct Sqlist { SqType elem[MAX_SIZE]; // 存放顺序表元素的数组 int length; // 顺序表的长度 }Sqlist;
//函数的声明 Sqlist create_list(void); // 初始化顺序表 void printf_list(Sqlist l); // 打印顺序表 int serch(Sqlist l, SqType elem); // 查找元素位置 Sqlist replace_elem(Sqlist l, SqType old_elem, SqType new_elem);// 替换旧元素old_elem为新元素new_elem Sqlist replace_pos(Sqlist l, int pos, SqType elem); // 替换位置pos上的元素为elem Sqlist insert(Sqlist l, int pos, SqType elem); // 插入新元素 Sqlist delete(Sqlist l, int pos); // 删除元素
int list[LEN] = {5, 2, 0, 13, 14}; // 用于初始化顺序表
/******************************************************************************************************* ** 函数: main,主函数 **------------------------------------------------------------------------------------------------------ ** 参数: void ** 返回: 无 ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ int main(void) { Sqlist l; int pos = 0; int serch_elem = 13; /* 创建一个顺序表:(5, 2, 0, 13, 14) */ l = create_list(); printf("创建的顺序表为:"); printf_list(l); // 打印输出顺序表 /* 把旧元素0替换为新元素1 */ l = replace_elem(l, 0, 1); printf("把0替换为1得到的新顺序表为:"); printf_list(l); /* 把第1个位置上的元素改为10 */ l = replace_pos(l, 1, 10); printf("第一个位置改为10得到的新顺序表为:"); printf_list(l); /* 往第二个位置插入新元素99 */ l = insert(l, 2, 99); printf("第二个位置插入99得到的新顺序表为:"); printf_list(l); /* 删除第二个位置上的元素 */ l = delete(l, 2); printf("删除第二个位置元素得到的新顺序表为:"); printf_list(l); pos = serch(l, serch_elem); // 查找serch_elem在该顺序表l中的第几个位置 printf("元素%d在顺序表的第%d个位置\n", serch_elem, pos); return 0; }
/******************************************************************************************************* ** 函数: create_list,创建一个顺序表 **------------------------------------------------------------------------------------------------------ ** 参数: void ** 返回: 创建成功的顺序表 ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ Sqlist create_list(void) { Sqlist l; for(int i = 0; i < LEN; i++) { l.elem[i] = list[i]; } l.length = LEN; // 顺序表长度 return l; // 创建成功的顺序表 }
/******************************************************************************************************* ** 函数: serch,查找元素elem在顺序表l的第几个位置 **------------------------------------------------------------------------------------------------------ ** 参数: l:顺序表 elem:要查找的元素 ** 返回: pos:元素elem的位置 -1:查找失败 ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ int serch(Sqlist l, SqType elem) { int i; int pos = 0; for (i = 0; i < l.length; i++) { if (elem == l.elem[i]) { pos = i + 1; return pos; } } return -1; //查找失败 }
/******************************************************************************************************* ** 函数: replace_elem,把旧元素old_elem替换为新元素new_elem **------------------------------------------------------------------------------------------------------ ** 参数: l:顺序表 old_elem:旧元素 new_elem:新元素 ** 返回: 替换完成后的新的顺序表l ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ Sqlist replace_elem(Sqlist l, SqType old_elem, SqType new_elem) { int old_elem_pos; old_elem_pos = serch(l, old_elem); // 首先查找旧元素所在的位置 l.elem[old_elem_pos - 1] = new_elem; return l; // 返回新生成的顺序表 }
/******************************************************************************************************* ** 函数: replace_pos,把第pos个位置上的元素替换为elem **------------------------------------------------------------------------------------------------------ ** 参数: l:顺序表 pos:位置 elem:元素 ** 返回: 替换完成后的新的顺序表l ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ Sqlist replace_pos(Sqlist l, int pos, SqType elem) { l.elem[pos - 1] = elem; return l; // 返回新生成的顺序表 }
/******************************************************************************************************* ** 函数: insert,把元素elem插入到顺序表l的第pos个位置 **------------------------------------------------------------------------------------------------------ ** 参数: l:顺序表 pos:位置 elem:元素 ** 返回: 插入元素后得到的新的顺序表l ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ Sqlist insert(Sqlist l, int pos, SqType elem) { int i; /* 插入的位置不存在或则表长已经达到顺序表的最大允许值 */ if (pos < 0 || pos > l.length || l.length >= MAX_SIZE) { printf("%s:插入错误!\n", __FUNCTION__); return l; } l.length += 1; // 插入新元素,表长加一 /* 从第pos个位置开始所有元素往后移一个元素长度 */ for (i = l.length-1; i >= pos-1; i--) { l.elem[i+1] = l.elem[i]; } l.elem[pos-1] = elem; // 插入的新元素 return l; // 返回新生成的顺序表 }
/******************************************************************************************************* ** 函数: delete,把第pos个位置的元素删除 **------------------------------------------------------------------------------------------------------ ** 参数: l:顺序表 pos:位置 ** 返回: 删除元素后得到的新的顺序表l ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ Sqlist delete(Sqlist l, int pos) { int i; /* 要删除的位置不存在 */ if (pos < 0 || pos > l.length) { printf("%s:删除错误!\n", __FUNCTION__); return l; } /* 从第pos个位置开始所有元素前移一个元素长度 */ for (i = pos-1; i < l.length-1; i++) { l.elem[i] = l.elem[i+1]; } l.length -= 1; // 删除一个元素后表长减一 return l; // 返回新生成的顺序表 }
/******************************************************************************************************* ** 函数: printf_list,打印输出顺序表 **------------------------------------------------------------------------------------------------------ ** 参数: l:顺序表 pos:位置 ** 返回: 删除元素后得到的新的顺序表l ** 日期: 2018.12.08 by LiZhengNian ********************************************************************************************************/ void printf_list(Sqlist l) { int i; for(i = 0; i < l.length; i++) { printf("%d ",l.elem[i]); } printf("(表长为%d)", l.length); printf("\n\n"); }
|