22线性表
2.2线性表
22线性表及运算 线性表是n个元素的有限序列,它们之间的关系可以 排成一个线性序列: a1,a2,……,a; ·。·●●9 n 其中n称作表的长度,当n=0时,称作空表 线性表的特点: 1线性表中所有元素的性质相同。 2除第一个和最后一个数据元素之外,其它数据元素有 且仅有一个前驱和一个后继。第一个数据元素无前驱, 最后一个数据元素无后继 3数据元素在表中的位置只取决于它自身的序号
线性表是n个元素的有限序列，它们之间的关系可以 排成一个线性序列： a1，a2，…… ，ai，……，an 其中n称作表的长度，当n=0时，称作空表。 2.2.1线性表及运算 2.除第一个和最后一个数据元素之外，其它数据元素有 且仅有一个前驱和一个后继。第一个数据元素无前驱， 最后一个数据元素无后继。 线性表的特点： 1.线性表中所有元素的性质相同。 3.数据元素在表中的位置只取决于它自身的序号
在线性表上常用的运算有: 初始化、求长度、取元素、修改、 前插、删除、检索、排序
在线性表上常用的运算有： 初始化、求长度、取元素、修改、 前插、删除、检索、排序
2.2.2线性表的存储结构 1顺序存储结构 2.链式存储结构
2.2.2 线性表的存储结构 1.顺序存储结构 2.链式存储结构
1.顺序存储结构 特点 线性表中数据元素类型一致,只有数据域 存储空间利用率高。 做插入、删除时需移动大量元素 空间估计不明时,按最大空间分配
1. 顺序存储结构 特点： 线性表中数据元素类型一致，只有数据域， 存储空间利用率高。 做插入、删除时需移动大量元素。 空间估计不明时，按最大空间分配
师席存储结构示意图(顺序表): 首地址 储地址内存状态 起始地址「b 元素a1 基地址 b+m 元素a2 b+(i-1)*m 元素a; 每个元素所占用 元素an b+(maxlen-1)*m 的存储单元个数 Loc(元素i)=b+(i-1)*m
元素an …….. 元素ai …….. 元素a2 元素a1 b b+m b+(i-1)*m b+(maxlen-1)*m 存储地址 内存状态 Loc(元素i)=b +（i-1)*m 顺序存储结构示意图(顺序表)： 首地址 起始地址 基地址 每个元素所占用 的存储单元个数
线性表的顺序存储结构可用C语言中的一维数组来描述 define n100定义M为常数100,M的值作为数组的最大容量 int VIM];/V是数组的名字,假设数组中的元素是整型类型 V[0] 元素a10 V[1] 元素a21 vi]元素a+ 第i个元素的a存储地址: Loc(ai= Loc(a1)+(i-1)* m VIm
元素a1 元素a2 …….. 元素ai+1 …….. 0 1 i 线性表的顺序存储结构——可用C语言中的一维数组来描述. #define M 100 /*定义M为常数100，M的值作为数组的最大容量*/ int V[M]; /*V是数组的名字，假设数组中的元素是整型类型*/ 第i个元素的ai存储地址： Loc(ai )=Loc(a1 )+(i-1)*m V[０] V[１] V[i] V[m-1]
1-1插入运算 X a 0 a 2 a2 a i-1 a计1 length i-1 a i+1 a n-1 n a a 2 a a a i+1 length
….. a2 a1 an ….. ai+1 ai 0 1 i-1 i n-1 1- 1插入运算 a1 a2 ….. ai-1 alength … ai ai+1 x a1 a2 ….. ai-1 axi ai+1 a…i+1 …alength alength
int insq(inti,intx, int VI,intM,int卹p)/*顺序表插入子函数 {/在线性表V中第i个元素之前插入x,i的合法值为1≤还≤n* Int n, J: n=“p /*获取表长 if (n==M) /*M是存储空间的大小,p是指向存储表长的指针变量* i printf(overflow n"); return(0); if(i1)(i>n+1) { printf(" iis error n"); return(0);}/*值不合法* else i for〔=nji;jVi-i-l:/插入位置后的元素依次右移*/ VI-X 注意数组元入 *p=++n; 由p返回到函数调用处* return (1); 素从0开始 }
int insq(int i，int x , int V[ ], int M, int *p）/ *顺序表插入子函数*/ { /*在线性表V中第i个元素之前插入x，i的合法值为1 i n */ int n，j： n=*p; / *获取表长*/ if（n==M) / *M是存储空间的大小，p是指向存储表长的指针变量*/ { printf("overflow \n"); return (0);} if((in+1)) {printf("i is error \n");return (0);} /*i值不合法*/ else { for (j=n; j>=i; j- -) V[j]=V[j-1]; /*插入位置后的元素依次右移*/ V[j]=x; /* 插入x */ p=++n; /* 表长加1,由p返回到函数调用处*/ return (1); } } 注意数组元 素从0开始
实现顺序表插入元素的主函数 viod maino intM=10;n=4;/M是数组的大小,n是表中已有元素个数即表长 int result, k; static int v10={3,5,7,10};/数组赋初值* result=-insq(2,4,V,10,&n);体执行函数调用,在第2个元素前插入4*/ if result==1i printf success ! n") for(k0; k<n; k++) printf(%d",V[kD;) else printf("failure! ) 运行结果: success! 345710
实现顺序表插入元素的主函数 viod main( ) { int M=10;n=4; /*M是数组的大小,n是表中已有元素个数,即表长*/ int result, k; static int V[10]={3,5,7,10}; /*数组赋初值*/ result=insq(2,4,V,10,&n); /*执行函数调用,在第2个元素前插入4*/ if ( result==1) { printf ("success ! \n"); for (k=0; k<n; k++) printf ("%d",V[k]);} else printf("failure!"); } 运行结果: success! 3 4 5 7 10