数据结构_1

发表于
字数统计 902 | 阅读时长 3

学习过程主要依照中国MOOC课程，感谢MOOC，感谢浙大授课大佬。

什么是数据结构

首先，何为数据结构？官方目前没有统一的定义，但数据结构常和算法结合在一起，“精心选择的数据结构可以带来最优效率的算法”。

  1. 图书的摆放：解决问题方法的效率，和数据的组织方式有关。
  2. 循环与递归：解决问题方法的效率，和空间的利用效率有关。
  3. 多项式计算：解决问题方法的效率，和算法的巧妙程度有关。
    所以，到底什么是数据结构？数据结构是数据在计算机中的组织方式。数据对象必定与一系列加在其上的操作相关联，这些操作就是“算法”。
  • 抽象数据类型：首先，数据类型包括数据对象集和相关联的操作集，而抽象指的是只描述数据类型的方法而不涉及具体实现，也就是只描述数据集和操作集“是什么”，而不管“如何实现”。

什么是算法

  • 一个有限指令集
  • 有或没有输入，但必须有输出
  • 每一条指令有明确目标，在计算机可处理范围之内
    算法衡量指标
  • 空间复杂度S(n)
  • 时间复杂度T(n)

2019/3/5 10:56:00

课后编程题

最大子序列

第一题只需要给出最大子序列的和，按照授课视频讲的在线处理方法还是比较简单；第二题在此基础上还要求给出最大子序列的首尾元素，作者的想法就是继续按照刚才在线处理的思想，当ThisSum > MaxSum要更新MaxSum时，这时更新last，同时，只要ThisSum没有被重新置为0，说明当前的最大子序列仍在增长，计数的num继续++，最后last的位置减去num也就是first的位置。另外还有一些如全为负数，存在零等情况需要特殊考虑一下，具体代码如下：

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
// MaxSubSum.cpp : 定义控制台应用程序的入口点。
//思想：在线处理

#include "stdafx.h"
#include<iostream>
using namespace std;

int main()
{
	int K;//输入序列长度
	int num = 0;//最大子序列元素个数统计
	int temp = 0;//负数元素统计
	int first=0,last = 0;//最大子序列起始、结尾序号
	int L[100000];
	int ThisSum=0, MaxSum= 0 ;
	cin >> K;
	for (int i=0; i < K; i++)
		cin >> L[i];
	for (int i = 0; i < K; i++) {
		if (L[i] < 0) temp++;
	}
	if (temp == K) 
		printf("%d %d %d", 0, L[0], L[K-1]);
	else{
		for (int i = 0; i < K; i++) {
			ThisSum += L[i];
			if (ThisSum > MaxSum) {
				MaxSum = ThisSum;
				last = L[i];
				num += 1;
				first = L[i - num + 1];
			}
			else if (ThisSum <= MaxSum && ThisSum >= 0) {
				num += 1;
			}
			else if (ThisSum < 0) {
				ThisSum = 0;
				num = 0;
			}
		}
		printf("%d %d %d", MaxSum, first, last);
	}
	return 0;
}

二分查找

这道题已经给出了其他代码，只需要写一个二分查找的函数，由于函数给出的是链表，所以在写的时候绕了一些弯子，这里不表，注意学习一下链表的相关内容，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Position BinarySearch(List Tbl, ElementType K) {
	int left;
	int right;
	if (Tbl->Last) {
		left = 1;
		right = Tbl->Last; 
		while(left <= right) {
			if (K == Tbl->Data[(left + right) / 2])
				return (left + right) / 2;
			else {
				if (K < Tbl->Data[(left + right) / 2])
					right = (left + right) / 2 - 1;
				else 
					left = (left + right) / 2 + 1;
			}
		}
	}
	return NotFound;
}

以上。

注：转载文章请注明出处，谢谢~