数据结构之线性表的顺序表（c语言）

线性表的定义

线性表是具有相同元素的n个元素的有限序列，其中n为表长，当n=0，线性表是一个空表，若用L命名线性表，则其一般表示为
L=（a1，a2，a3，a4，…，an，an+1，…，an）

线性表分为顺序表和链表两类

链表有可以细分为
单链表，双向链表，静态链表，循环链表（可恶的约瑟夫环）

如图

线性表的基本操作

这种当时的执行后x是不变的
在栈中新建一个int x
而不是主函数的x发生的变化

在c语言中就需要用指针来操作

#include 
void test(int * x){
	*x=1024;
	printf("test函数内部x=%d\n",*x);	
}
int main(){
	int x=1;
	int *p=&x;
	printf("调用test前x=%d\n",x);
	test(p);
	printf("调用test后x=%d\n",x);
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

c++中就能用&引用来进行地址传递

#include 
void test(int & x){
	x=1024;
	printf("test函数内部x=%d\n",x);	
}
int main(){
	int x=1;
	
	printf("调用test前x=%d\n",x);
	test(x);
	printf("调用test后x=%d\n",x);
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

运行结果是一致的

顺序表

顺序表的定义和实现

1.定义

及里面的InitList函数

void InitList(SqList &L){
for(int i=0;i<MaxSize;i++){
	L.data[i]=i;
	}//数据的初始化
	L.length=0;//length用来记录我们存储的数据，便于循环操作有价值的（我们定义的）数据
		}

1
2
3
4
5
6
7

2.静态分配

这种顺序表的方式，一开始定义的初始长度是不能改变的，所以，用完了就寄，也不能一开始就赋值一个很大的，会浪费内存空间

所以静态分配是有局限性的

所以引出动态分配的方式

3.动态分配

malloc申请一片连续的内存空间
返回这片空间的其实位置的指针，强制转化为我们想要的对应类型指针

代码纯享版

就是把原数据复制到，新扩展的空间内，新空间比原空间大，可以存放更多数据呗

注意malloc和free函数在 中
+注释版本

当然这种动态分配的执行效率也是非常低的
需要复制原来的数据到新的内存空间

4.两种分配的共有特性

5.小总结

顺序表的插入的删除

插入

在某个位置插入元素，其原占位元素及其以后的元素都要往后移一位

c代码

#include 
typedef struct 
{
    int data[10];
    int length;
}Sqlist;
void InitList(Sqlist *L){
    L->length=0;
}

void ListInsert(Sqlist *L,int i,int e){
    for (int j=L->length;j>=i;j--)
    L->data[j]=L->data[j-1];
    L->data[i-1]=e;
    L->length+=1;
    
}

int main(){
    Sqlist L;
    Sqlist* a;
    a=&L;
    InitList(a);
    for(int i=0;i<5;i++){
        L.data[i]=i;
        L.length++;
    }
    for ( int i = 0; i <L.length ; i++)
    {
        printf("%d\n",L.data[i]);
    }
    ListInsert(a,3,3);
    for ( int i = 0; i <L.length ; i++)
    {
        printf("%d\n",L.data[i]);
    }
    

    InitList(a);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

原来是01234
在第三个位置上插入3
变为013234

官方版

可以在里面加入一个判断，增强代码的健壮性
防止，元素已经存满，或者插入到不合理的位置，导致的程序报错
如图

删除

删除需要先把所在位置元素删除，然后把该元素后面的元素都向前移一位
还要使L.length-1

#include 
typedef struct 
{
    int data[10];
    int length;
}Sqlist;
void InitList(Sqlist *L){
    L->length=0;
}

void ListInsert(Sqlist *L,int i,int e){
    for (int j=L->length;j>=i;j--)
    L->data[j]=L->data[j-1];
    L->data[i-1]=e;
    L->length+=1;
    
}
void ListDelete(Sqlist *L,int i){
    for(int j=i-1;j<L->length;j++)
    {
        L->data[j]=L->data[j+1];

    }
    L->length--;
}

int main(){
    Sqlist L;
    Sqlist* a;
    a=&L;
    InitList(a);
    for(int i=0;i<5;i++){
        L.data[i]=i;
        L.length++;
    }
    for ( int i = 0; i <L.length ; i++)
    {
        printf("%d\n",L.data[i]);
    }
   
   ListDelete(a,3);
   for ( int i = 0; i <L.length ; i++)
    {
        printf("%d\n",L.data[i]);
    }

    InitList(a);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

删除第三个位置的元素，原来为01234
后变为0134
官方版

顺序表的查找

按位查找

对应的getelem函数

按值查找

依次查找
返回i+1位序

小总结