【考研】数据结构(更新到顺序表)

线性表的定义和基本操作

学习目标

线性表定义：具有相同数据类型的n个数据元素的有序序列。
顺序表定义：

特点

基本操作

1. 定义
   静态：

#include
#include

#define MaxSize 10

//静态 
typedef struct{
	int data[MaxSize];
	int length;
}SqList;

void InitList(SqList &L)//初始化 
{
	for(int i=0;i<MaxSize;i++){
		L.data[i]=0;
	}
    L.length=0;
}

int main(void)
{
	SqList L;
	InitList(L);
	
	for(int i=0;i<L.length;i++){
		printf("the data %d is %d",i,L.data[i]);
	}
	
	return 0;
}
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

动态：

#include
#include

#define InitSize 10

typedef struct{
	int *data;
	int MaxSize;//最大容量 
	int length;//当前长度 
}SeqList;

void Init(SeqList &L)
{
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}

int main(void){
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 插入
   静态：

//插入操作,bool用于判断操作是否成功 (处理异常情况) 
bool ListInsert(SqList &L,int i,int e){
	if(i<1 || i>L.length+1) return false;//条件判断 
	if(L.length >= MaxSize) return false;
	
	for(int j=L.length;j>=i;i--){
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
}
1
2
3
4
5
6
7
8
9
10
11

动态：

1

3. 删除
   静态：

bool ListDelete(SqList &L,int i,int &e){
	if(i<1||i>L.length) return false;
	e=L.data[i-1];
	for(int j=i;j<L.length;j++)
	{
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return true;
}
1
2
3
4
5
6
7
8
9
10

动态顺序表以及各个操作

#include
#include
#define InitSize 10

typedef struct{
	int *data;
	int MaxSize;
	int length;
}SqList;

void debug(SqList L){
	printf("当前顺序表的数据为length=%d maxsize=%d\n",L.length,L.MaxSize);
}
//初始化
void InitList(SqList &L){
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}
 
//增加动态数组的长度
void IncreaseSize(SqList &L,int len){
	int *p=L.data;
	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];//将数据复制到新区域 
	}
    L.MaxSize=L.MaxSize+len;//顺序表最大长度增加len 
	free(p);//释放空间		
} 

//插入操作
bool ListInsert(SqList &L,int i,int e){
	//范围判断 
	if(i<1 || i>L.length+1)
		return false;
	if(L.length>L.MaxSize)
	return false;
	
	for(int j=L.length;j>=i;j--)
	{
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
	return true;
} 

删除操作,删除第i个数据并且返回被删除的数据 
bool ListDelete(SqList &L,int i,int &e)
{
	//范围判断
	 if(i<1 || i>L.length+1) return false;
	 else{
	 	//保存删除元素
		 e=L.data[i]; 
	 	for(int j=i;j<L.length;j++)
	 	{
		 L.data[j]=L.data[j+1];
	    }
	    L.length--;
	 } 
	 return true;
 } 

//按位查找
int getElemBybit(SqList L,int i){
	//Check if the line has been crossed
	if(i<1 || i>L.length){
		printf("Cross the border!");
		return 0;
	}
	
	return L.data[i-1];
} 

//按值查找
int getElemByValue(SqList L,int value){
	for(int i=0;i<L.length;i++)
	{
		if(L.data[i] == value)
		{
			return i-1;
		}
	}
	printf("Can`t find the elem!");
	
	return 0;
} 

//打印操作
void print(SqList L){
	for(int i=0;i<L.length;i++)
	{
		printf("%d ",L.data[i]);
	}
	printf("\n");
} 

//测试函数 
int main(void){
	SqList L;debug(L);
	InitList(L);debug(L);
	
	for(int i=0;i<L.MaxSize;i++)
	{
		L.data[i]=i;
	    L.length++;
	}
	IncreaseSize(L,5);debug(L);
	
	print(L);
	if(ListInsert(L,2,5)){
	printf("插入成功,插入后数值");
		print(L);
	}else printf("插入失败");
	
	int e=0;
	if(ListDelete(L,3,e))
	{
		print(L);
		printf("被删除元素为：%d",e);
	}

    int value,position;
	printf("\nPlease input the value and the position:");  
    scanf("%d %d", &value, &position);  
	printf("\nget the emlem by value :the elem position is%d\n",getElemByValue(L,value));
	printf("\nget the emlem by positon:the value is%d\n",getElemBybit(L,position));
	
	return 0;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132