🌺博客汇总：🌃Summary And Schedule🌠

🌸考研相关内容汇总：考研Schedule&&Summary

🌼408王道《数据结构》课程目录：

考纲：

  • 算法时间复杂度和空间复杂度的分析和计算

本章需要掌握：

  • 1、数据结构基础概念：数据、数据元素、数据对象、数据类型、数据结构
  • 2、数据结构三要素：逻辑结构、存储结构、数据的计算
  • 3、算法（特性5，“好”4）、程序
  • 4、T(n)，常对幂指阶，设最高频次语句执行k次
  • 5、S(n)，递归=深度、O(1)不使用额外空间

考纲：

  • （一）线性表的基本概念
  • （二）线性表的实现（顺序存储；链式存储）
  • （三）线性表的应用

本章需要掌握：

  • 1、
  • 2、
  • 3、
  • 4、
  • 5、
  • 6、
  • 7、结构体不能直接比较

1、Linear List

1.1 Definition

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

前趋（predecessor）后继（successor）

直接前趋（immediate predecessor）直接后继（immediate successor）

1.2 Basic Operations

创：InitList(&L)、销：DestroyList(&L)、增：ListInsert(&L,i,e)、删：ListDelete(&L,i,&e)

改：直接改、查：LocateElem(L,e)、GetElem(L,i)

打印：PrintList(L)、判空：Empty(L)、表长：Length(L)

2、Linear List Sequential Storage

逻辑顺序与其存储的物理顺序相同

优：①随机访问，O(1)时间内找到第i个元素②存储密度高

缺：①插入删除不方便②需要一段连续的存储空间，不灵活

2.1 Static Storage

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
#include <stdio.h>
#define MaxSize 50

typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

//1、初始化
void initList(SqList &L){
    L.length=0;
}

//2、销
void DestroyList(SqList &L){
    L.length=0;
}

//3、增
bool ListInsert(SqList &L,int i,ElemType element){
    if(i<1 || i>L.length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=element;
    L.length++;
    return true;
}

//4、删
bool ListDelete(SqList &L,int i,ElemType &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;
}

//5、改(直接索引改值就行)

//6、查（按位查/按值查）
int LocateElem(SqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(e==L.data[i])
            return i+1;
    return 0;
}
ElemType GetElem(SeqList L,int i){
    if(i<1 || i>L.length)
        return false;
    return L.data[i-1];
}

//7、输出
void PrintList(SqList L){
    for(int i=0;i<L.length;i++)
        printf("%3d",L.data[i]);
}

//8、判空
int Empty(SqList L){
    return L.length==0;
}

//9、求长
int Length(SqList L){
    return L.length;
}

2.2 Dynamic Storage

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
#include <stdio.h>
#include <stdlib.h>
#define InitSize 100

typedef int ElemType;
typedef struct{
    ElemType *data;
    int MaxSize,length;
}SeqList;

//1、初始化
void initList(SeqList &L){
    L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
    // L.data = new ElemType[InitSize]; //C++可以这么写
    L.length = 0 ;
    L.MaxSize = InitSize ; //初始化存储容量
}
void IncreaseSize(SeqList &L,int len){
    ElemType *p = L.data;
    L.data = (ElemType*)malloc(sizeof(ElemType)*(L.MaxSize+len));
    for (int i = 0; i < L.length; ++i) 
        L.data[i]=p[i];
    L.MaxSize = L.MaxSize + len ;
    free(p);
}

//2、销
void DestroyList(SeqList &L){
    free(L.data);
    L.data = NULL;
    L.length = 0;
    L.MaxSize = 0;	
}

//3、增
bool ListInsert(SeqList &L,int i,ElemType 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;
}

//4、删
bool ListDelete(SeqList &L,int i,ElemType &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;
}

//5、改(直接索引改值就行)

//6、查（按位查/按值查）
int LocateElem(SeqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(e==L.data[i])
            return i+1;
    return 0;
}
ElemType GetElem(SeqList L,int i){
    if(i<1 || i>L.length)
        return false;
    return L.data[i-1];
}

//7、输出
void PrintList(SeqList L){
    for(int i=0;i<L.length;i++)
        printf("%3d",L.data[i]);
}

//8、判空
int Empty(SeqList L){
    return L.length==0;
}

//9、求长
int Length(SeqList L){
    return L.length;
}

3、 Linear List Linked Storage

LinkList强调链表，LNode*强调结点

优：①随机访问，O(1)时间内找到第i个元素②存储密度高

缺：①插入删除不方便②需要一段连续的存储空间，不灵活

3.1 Singly Linked List（）

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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;
}LNode,*LinkList;

//1、初始化
bool InitList(LinkList &L){
    L = NULL;
    return true;
}

//2、头插法创建单链表
LinkList List_HeadInsert(LinkList &L)
{
    InitList(L);
    ElemType x;
    scanf("%d",&x);
    LNode* s; //s指向新结点
    while (x != 9999)
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L;
        L = s;
        cin >> x;
    }
    return L;
}

//3、尾插法创建单链表
//有一个小操作，*r=L（此时rL指向同一位置）之后r->next=s，相当于L->next=s
void list_tail_insert(LinkList &L)
{
  	InitList(L);
    ElemType x;
    scanf("%d",&x);
    LNode *s,*r=L;//s指向新结点，r始终指向链表尾部
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;//r要指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL;//让尾结点的next为NULL
}

//4、销
//L=NULL相当于已释放节点，不需要free(L)
void DestroyList(LinkList &L){
    LNode *p;
    while(L!=NULL){
      p = L;
      L = L -> next;
      free(p);
    }
}

//5、增
//不带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e)
{
    if (i < 1)
      return false;
    if (i == 1)//在第一个位置插入
    {
      LNode* s = (LNode*)malloc(sizeof(LNode));
      s->data = e;
      s->next = L;
      L = s;
      return true;
    }
    LNode* p;//不在第一个位置插入；
    p = L;
    int j = 1;
    while (p!=NULL && j<i-1)
    {
        p = p->next;
        j++;
    }
    if (p==NULL)
      return false;
    return InsertNextNode(p, e);
}


//按位查找，不带头节点
LNode* GetElem(LinkList L, int i)
{
	if (i < 1)
	{
		return false;
	}
	int j = 1;
	LNode* p = L;
	while (p&& j < i)
	{
		p = p->next;
		j++;
 
	}
 
	return p;
}
//按值查找
LNode* LocateElem(LinkList L, int e)
{
	LNode* p = L;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
 
}
//统计单链表的长度
int Length(LinkList)
{
	int len = 0;
	LNode* p = L;
	while (p)
	{
		len++;
		p = p->next;
	}
	return len;
 
 
}
//后插操作。在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e)
{
	if (!p)
	{
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
		if (!s)
		{
			return false;
		}
		s->data = e;
		s->next = p->next;
		p->next = s;
 
		return true;
}

//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e)
{
	if (!p)
	{
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (!s)
	{
		return false;
	}
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
 
	return true;
}
//前插操作，在p节点前插入节点s;
bool InsertPriorNode(LNode* p, LNode* s)
{
	if (!p || !s)
	{
		return false;
 
	}
	s->next = p->next;
	p -> next = s;
	swap(s->data, p->data);
		return true;
 
}
//删除位序为i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e)
{
	if (L == NULL)
	{
		e = -1;
		return false;
	}
	if (i < 1)
	{
		return false;
	}
	if (i > 1)
	{
		LNode* p = GetElem(L, i - 1);//安值查找，找到数据域等于e的节点
		if (!p || !(p->next))
		{
			return false;
		}
		LNode* q = p->next;//q指针指向位序为i的节点
		e = q->data;//将数值复制给e,
		p->next = q->next;//p指针跳过q指针指向下一个节点
		free(q);//这时q指针变为一个空节点，将这个结点释放
	}
	else//i==1;
	{
		if (L->next == NULL)//只有一个头节点，直接将这个节点变为空，
		{
			e = L->data;
			L = NULL;
		}
		else//L->next!==NULL;//头节点后还有节点，将下一个节点变为头节点.
		{
			e = L->data;
			L = L->next;
		}
	}
	
	return true;
}
//删除指定节点P，核心在于找p的下一个节点，将下一个节点的值覆盖P节点，p指向下下一个节点。
bool DeleteNode(LNode* p)
{
	if (p->next == NULL)//bug,不能删除最后一个节点
	{
		return false;
	}
	LNode* q = p->next;
	p->data = q->data;
	p->next = q->next;
	free(q);
	return true;
 
}
//尾插法创建不带节点的单链表
LinkList List_Taillnsert(LinkList& L)
{
	InitList(L);
	int x = 0;
	cout << "请输入数据" << endl;
	cin >> x;
	LNode* s, * r = L;//r=L->next;
	
	while ( x!= 9999) {
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = NULL;
		if (L == NULL) {//第一次插入，L==NULL；
			L = s;//将覆盖L；
			r = s;//指针还是指向最后
		}
		else {//从第二此插入开始，L!=NULL
			r->next = s;//此次表尾指针指向最后
			r = s;//
		}
		cin >> x;
	}
	r->next = NULL;//退出的时候表尾指针指向NULL
	return L;
}
 
void print(LinkList L)//打印单链表
{
	LNode* s = L;
	while (s != NULL)
	{
		cout << s->data << " ";
		s = s->next;
	}
	cout << endl;
 
}





//3、增
bool ListInsert(LinkList &L, int i, ElemType e){
  	if(i<1)
      	return false;
  	LNode *p; //指向当前扫描节点
    int j = 0; //当前p指向第几个节点
    p = L; //L指向头结点，第0个节点
    while(p!=NULL && j<i-1){ //循环找到i-1个节点
        p = p->next;
        j++;
    }
    if(p==NULL)
      	return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//4、删
bool ListDelete(SeqList &L,int i,ElemType &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;
}

//5、改(直接索引改值就行)

//6、查（按位查/按值查）
int LocateElem(SeqList L,ElemType e){
    for(int i=0;i<L.length;i++)
        if(e==L.data[i])
            return i+1;
    return 0;
}
ElemType GetElem(SeqList L,int i){
    if(i<1 || i>L.length)
        return false;
    return L.data[i-1];
}

//7、输出
void PrintList(SeqList L){
    for(int i=0;i<L.length;i++)
        printf("%3d",L.data[i]);
}

//8、判空
int Empty(SeqList L){
    return L==NULL;
}

//9、求长
int Length(SeqList L){
    return L.length;
}

void print_list(LinkList L)
{
    L=L->next;
    while(L!=NULL)
    {
        printf("%3d",L->data);
        L=L->next;
    }
    printf("\n");
}

//按位置查找
LinkList GetElem(LinkList L,int SearchPos)
{
    int j=0;
    if(SearchPos<0)
    {
        return NULL;
    }
    while(L&&j<SearchPos)
    {
        L=L->next;
        j++;
    }
    return L;
}
//按值查找
LinkList LocateElem(LinkList L,ElemType SearchVal)
{
    while(L)
    {
        if(L->data==SearchVal)//如果找到对应的值，就返回那个结点的地址
        {
            return L;
        }
        L=L->next;
    }
    return NULL;
}
//i代表插入到第几个位置
bool ListFrontInsert(LinkList L,int i,ElemType InsertVal)
{
    LinkList p= GetElem(L,i-1);
    if(NULL==p)
    {
        return false;
    }
    LinkList q;
    q=(LinkList)malloc(sizeof(LNode));//为新结点申请空间
    q->data=InsertVal;
    q->next=p->next;
    p->next=q;
    return true;
}




3.2 Singly Linked List（+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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;
}LNode,*LinkList;

//1、初始化
bool InitList(LinkList &L){
  L = (LNode *)malloc(sizeof(LNode));
  if(L==NULL)    //内存分配不足
    return false;
  L->next = NULL
  return true;
}

//2、头插法新建链表
void list_head_insert(LNode* &L)
{
    L= (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);
    LNode *s;//用来指向申请的新结点
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;//s的next指向原本链表的第一个结点
        L->next=s;//头结点的next，指向新结点
        scanf("%d",&x);
    }
}
//3、尾插法新建链表
void list_tail_insert(LNode* &L)
{
    L= (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点
    L->next=NULL;
    ElemType x;
    scanf("%d",&x);
    LNode *s,*r=L;//s是用来指向申请的新结点，r始终指向链表尾部
    while(x!=9999)
    {
        s=(LinkList)malloc(sizeof(LNode));//为新结点申请空间
        s->data=x;
        r->next=s;//新结点给尾结点的next指针
        r=s;//r要指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL;//让尾结点的next为NULL
}

//4、


//8、判空
int Empty(SeqList L){
    return L->next==NULL;
}

3.3 Doubly Linked List

3.4 Circular Linked List

3.4

6、Wrong Question

1、顺序表是顺序存储的线性表，表中所有元素类型必须相同且必须连续存放，一维数组中的元素可以不连续。

2、顺序表的顺序存储结构 是 随机存取的存储结构。

3、长度位n的非空线性表序号用1开始，有n+1个插入位置。

4、malloc会申请连续的内存空间，动态存储顺序表扩容会申请m+n个连续空间。