数据结构-线性表_线性表的顺序存储结构和链式存储结构分别是

数据结构-线性表

线性表，全名为线性存储结构。线性表的存储数据的方式可以理解为“把所有数据用一根线串起来，在存储到物理空间中”，我们可以选择以下两种方式

1）顺序存储结构：如左图，将数据以此存储在连续的整块物理空间中，这种存储结构称为顺序存储结构，简称顺序表

2）链式存储结构：如右图，数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构，简称链表

一： 线性表的顺序存储结构

用一段地址连续的存储单元依次存储数据的结构为顺序存储结构

存储器中的每个存储单元都有自己的编号，这个编号称为地址

每个数据元素，不管它是整型，实型，还是字符型，他都是需要占用一定的存储单元空间的，假设占用的是c个存储单元，那么对于线性表的第i个元素ai的存储位置可以由a1推导出

*Loc(ai)=Loc(a1)+(i-1)c

时间复杂度

1）对于存取操作

线性表的顺序存储结构，对于存取操作，其时间复杂度为O(1)，因为元素位置可以直接计算得到

2）对于插入和删除操作

对于插入和删除操作，其时间复杂度为O(n)，因为插入和删除后，需要移动其余的元素

因此，线性表顺序存储结构比较适用于元素存取操作较多，增删操作较少的场景

二：线性表的链式存储结构

一个或多个结点组合而成存储数据的结构称为链式存储结构

结点一般由数据域和指针域两个部分组成，其中，数据域用来存储真实数据元素，指针域用来存储下一个结点的地址

时间复杂度

1）对于存取操作

假设我们需要获取第i个元素，则必须从第一个结点开始依次遍历，知道达到第i个结点，因此对于单链表结构而言，其数据存取的时间复杂度为O(n)

2）对于插入和删除操作

对于单链表而言，对于任何一个位置进行增删操作，其时间复杂度都为O(n)，因为需要先进行遍历找到目标元素

此外常见的还有循环链表和双向链表

循环链表是指使整个单链表形成一个环，将单链表中的终端结点的指针端由空指针改为指向头结点

双向链表指的是，在每个结点中额外设置一个指向前结点的指针域的链表

三：顺序存储结构和链式存储结构哪个好？

1）对于存取操作

线性表的为元素位置可以直接计算得到，时间复杂度为O(1)，而链表需要从第一个元素依次遍历到达第i个结点才能得到他的地址进行读取，时间复杂度为O(n)，因此对于读取操作，顺序表要好于链表

2）对于插入和删除操作

线性表对于插入和删除操作，因为插入和删除后，需要移动其余的元素，因此其时间复杂度为O(n)
链表因为要找到需要进行操作的结点位置之后才能修改指针域，因此其时间复杂对也为O(n)

但是为什么对于插入或删除数据越频繁的操作，单链表的效率就越明显？
链表和数组的插入删除时间复杂度都是O(n)，为什么链表效率高？

因为两个O(n)的具体意义是不同的

写入场景，任意位置写入，定位复杂度：数组O(1)，链表O(n)，写入复杂度：数组O(n)，链表O(1)，在写入场景中，数组链表的复杂度是定位和写入复杂度之和，都是O(n)，但是写入比定位的O(n)慢得多，所以表面上看起来是一样的O(n)，但是实际时间还是会差很多，所以说链表的写入效率更高

四：链表的基本操作

创建链表（尾插）

// 一个简单结构体，只存一个数 
typedef struct Node
{
	int data;
	struct Node *next;
}Node;

// 声明结构体struct Node之后使用Node去定义结构体，用作链表的结点，其中int类型的data用作结点的数据域，struct Node*类型的next指针作为指针域 

Node* creat_tail(int count){
	// 传过来的int类型的count表示链表的结点个数 
	// 使用尾插法初始化以及创建链表，返回的链表的头结点的地址 
	Node* head;
	// 头节点 
	Node* tail;
	// 尾结点 
	Node* temp;
	// 临时中转的结点，负责尾插 
	head = (Node*)malloc(sizeof(Node));
	// malloc（sizeof（Node））用来分配地址空间，同时返回地址，这里给head头结点分配了一个空间 
	tail = head;
	// 最初始的情况头结点和尾结点是一个 
	for(int i=0;i<count;i++){
		// 传过来的int类型的count表示链表的结点个数 
		temp = (Node*)malloc(sizeof(Node));
		// 创建一个结点，分配地址 
		cin>>temp->data;
		// 分配数据域 
		temp->next=NULL;
		// 分配指针域为NULL（因为创建的结点都是要先插在最后） 
		tail->next=temp;
		// 原来的尾结点指向temp之一块区域 
		tail=temp;
		// temp成为新的尾结点，循环创建 
	}
	return head;
}
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

打印链表

void printlist(Node* head){
	// 依次遍历结点，输出数据域直到找不到下一个结点，也就是p->next==NULL，找不到下一个结点，遍历完所有结点 
	cout<<"结点打印"<<endl; 
	Node* p;
	p=head->next;
	while(p!=NULL){
		cout<<p->data;
		p = p->next;
		cout<<endl;
	}
	cout<<"结点打印完成"<<endl<<endl; 
}
1
2
3
4
5
6
7
8
9
10
11
12

查找

int findNode(Node* head,int* num,int find){
	// 输入数值查找在结点中的位置 
	// 查找结点，找到返回1，找不到返回0，同时给传过来的num赋值，赋值为找到的第一个结点的位置 
	Node *p;
	p=head->next;
	int count=0;
	while(p!=NULL){
		count++;
		if(p->data==find){
			*num=count;
			cout<<"findNode找到了，他的位置是:"<<*num<<endl<<endl; 
			return 1;
		}
		p=p->next;
	}
	cout<<"findNode没找到"<<endl<<endl; 
	return 0;
}

int findNodeByKey(Node* head,int* num,int key){
	// 输入数值查找在结点中的位置 
	// 查找结点，找到返回1，找不到返回0（越界不越界），同时给传过来的num赋值，赋值为找到的结点的数据域 
	Node *p;
	p=head->next;
	int count=0;
	while(p!=NULL){
		count++;
		if(count==key){
			*num=p->data;
			cout<<"findNodeByKey找到了，他的数据是:"<<*num<<endl<<endl; 
			return 1;
		}
		p=p->next;
	} 
	cout<<"findNodeByKey没找到"<<endl<<endl; 
	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

修改

int changeData(Node* head,int key,int num){
	// int表示要修改的key，num表示要修改成的值
	Node *p;
	p=head->next;
	int count=0;
	while(p!=NULL){
		count++;
		if(count==key){
			p->data=num;
			cout<<"修改成功"<<endl<<endl;
			return 1;
		} 
	} 
	cout<<"修改失败"<<endl<<endl; 
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

删除

int deleteByKey(Node* head,int key){
	Node *p;
	Node *pNext;
	p=head;
	pNext=p->next; 
	int count=0;
	while(pNext!=NULL){
		count++;
		if(count==key){
			p->next=pNext->next;
			free(pNext);
			// 释放空间 
			cout<<"删除成功"<<endl<<endl;
			return 1;			
		}
		p=p->next;
		pNext=p->next;
	}
	cout<<"删除失败"<<endl<<endl; 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

增添

int addByKey(Node* head,int num,int key){
	Node *p;
	Node *pNext;
	Node *temp;
	p=head;
	pNext=p->next; 
	int count=0;
	while(p!=NULL){
		count++;
		if(count==key){
			temp = (Node*)malloc(sizeof(Node));
			temp->data=num;
			p->next=temp;
			temp->next=pNext;
			cout<<"插入成功"<<endl<<endl;
			return 1;			
		}
		p=p->next;
		pNext=p->next;
	}
	cout<<"插入失败"<<endl<<endl; 
	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

整合

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

// 一个简单结构体，只存一个数 
typedef struct Node
{
	int data;
	struct Node *next;
}Node;

// 声明结构体struct Node之后使用Node去定义结构体，用作链表的结点，其中int类型的data用作结点的数据域，struct Node*类型的next指针作为指针域 

Node* creat_tail(int count){
	// 传过来的int类型的count表示链表的结点个数 
	// 使用尾插法初始化以及创建链表，返回的链表的头结点的地址 
	Node* head;
	// 头节点 
	Node* tail;
	// 尾结点 
	Node* temp;
	// 临时中转的结点，负责尾插 
	head = (Node*)malloc(sizeof(Node));
	// malloc（sizeof（Node））用来分配地址空间，同时返回地址，这里给head头结点分配了一个空间 
	tail = head;
	// 最初始的情况头结点和尾结点是一个 
	for(int i=0;i<count;i++){
		// 传过来的int类型的count表示链表的结点个数 
		temp = (Node*)malloc(sizeof(Node));
		// 创建一个结点，分配地址 
		cin>>temp->data;
		// 分配数据域 
		temp->next=NULL;
		// 分配指针域为NULL（因为创建的结点都是要先插在最后） 
		tail->next=temp;
		// 原来的尾结点指向temp之一块区域 
		tail=temp;
		// temp成为新的尾结点，循环创建 
	}
	return head;
}

void printlist(Node* head){
	
	// 依次遍历结点，输出数据域直到找不到下一个结点，也就是p->next==NULL，找不到下一个结点，遍历完所有结点 
	cout<<"结点打印"<<endl; 
	Node* p;
	p=head->next;
	while(p!=NULL){
		cout<<p->data;
		p = p->next;
		cout<<endl;
	}
	cout<<"结点打印完成"<<endl<<endl; 
}

int findNode(Node* head,int* num,int find){
	// 输入数值查找在结点中的位置 
	// 查找结点，找到返回1，找不到返回0，同时给传过来的num赋值，赋值为找到的第一个结点的位置 
	Node *p;
	p=head->next;
	int count=0;
	while(p!=NULL){
		count++;
		if(p->data==find){
			*num=count;
			cout<<"findNode找到了，他的位置是:"<<*num<<endl<<endl; 
			return 1;
		}
		p=p->next;
	}
	cout<<"findNode没找到"<<endl<<endl; 
	return 0;
}

int findNodeByKey(Node* head,int* num,int key){
	// 输入数值查找在结点中的位置 
	// 查找结点，找到返回1，找不到返回0（越界不越界），同时给传过来的num赋值，赋值为找到的结点的数据域 
	Node *p;
	p=head->next;
	int count=0;
	while(p!=NULL){
		count++;
		if(count==key){
			*num=p->data;
			cout<<"findNodeByKey找到了，他的数据是:"<<*num<<endl<<endl; 
			return 1;
		}
		p=p->next;
	} 
	cout<<"findNodeByKey没找到"<<endl<<endl; 
	return 0;
} 

int changeData(Node* head,int key,int num){
	// int表示要修改的key，num表示要修改成的值
	Node *p;
	p=head->next;
	int count=0;
	while(p!=NULL){
		count++;
		if(count==key){
			p->data=num;
			cout<<"修改成功"<<endl<<endl;
			return 1;
		} 
	} 
	cout<<"修改失败"<<endl<<endl; 
	return 0;
} 

int deleteByKey(Node* head,int key){
	Node *p;
	Node *pNext;
	p=head;
	pNext=p->next; 
	int count=0;
	while(pNext!=NULL){
		count++;
		if(count==key){
			p->next=pNext->next;
			free(pNext);
			// 释放空间 
			cout<<"删除成功"<<endl<<endl;
			return 1;			
		}
		p=p->next;
		pNext=p->next;
	}
	cout<<"删除失败"<<endl<<endl; 
	return 0;
}

int addByKey(Node* head,int num,int key){
	Node *p;
	Node *pNext;
	Node *temp;
	p=head;
	pNext=p->next; 
	int count=0;
	while(p!=NULL){
		count++;
		if(count==key){
			temp = (Node*)malloc(sizeof(Node));
			temp->data=num;
			p->next=temp;
			temp->next=pNext;
			cout<<"插入成功"<<endl<<endl;
			return 1;			
		}
		p=p->next;
		pNext=p->next;
	}
	cout<<"插入失败"<<endl<<endl; 
	return 0;
}

int main(){
	Node* header=creat_tail(10);
	printlist(header);
	int num=0;
	findNode(header,&num,5);
	findNodeByKey(header,&num,5);
	changeData(header,1,10); 
	printlist(header);
	deleteByKey(header,10);
	printlist(header);
	addByKey(header,999,10);
	printlist(header);
}
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170