【数据结构】01-绪论《数据结构 C语言版（严蔚敏、吴伟民）》

2024-04-14 06:18
文章标签 数据结构 01 语言版 绪论 伟民 严蔚敏

本文主要是介绍【数据结构】01-绪论《数据结构 C语言版（严蔚敏、吴伟民）》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 教材 > 第1章 绪论
    • 1.1 什么是数据结构
    • 1.2 基本概念和术语
    • 1.3 抽象数据类型的表示与实现
    • 1.4 算法和算法分析
  • 习题集 > 第1章
    • 二、算法设计题
  • 附 > 友情推荐链接

教材 > 第1章 绪论

1.1 什么是数据结构

  • 用计算机解决一个具体问题时的步骤：
    • 首先，从具体问题抽象出一个适当的数学模型
    • 然后，设计一个解此数学模型的算法（分析问题，提取操作对象，找出对象之间关系，用数学语言描述）
    • 最后，编写程序，进行测试，调整直至得到最终解答
  • 数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科；

1.2 基本概念和术语

  • 数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称
  • 数据元素：是数据的基本单位，一个数据元素可由若干个 数据项（是数据的不可分割的最小单位）组成
  • 数据对象：是性质相同的数据元素的集合，是数据的一个子集
  • 数据结构：是相互之间一种或多种特定关系的数据元素的集合
  • 基本结构：（数据元素之相互之间的关系 == 结构）
    • 集合
    • 线性结构（一对一）
    • 树形结构（一对多）
    • 图状结构或网状结构（多对多）
  • 形式定义：Data Structure =（D，S）
  • 逻辑结构（数学模型结构定义中的关系）
    • 顺序映像
    • 非顺序映像
  • 存储结构（存储映射）（位、元素、数据域）
    • 顺序存储结构（数组）
    • 链式存储结构（指针）
  • 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构
  • 虚拟存储结构 和 数据类型
    • 原子类型
    • 结构类型
  • 抽象数据结构（由一个值域和定义在该值域上的一组操作组成）
    • 原子类型
    • 固定聚合类型
    • 可变聚合类型 ADT = （D，S，P）
    • 多形数据结构

1.3 抽象数据类型的表示与实现

  • ADT：利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作

1.4 算法和算法分析

  • 算法 — 是对特定问题求解步骤的一种描述；
  • 算法特性
    • 有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成
    • 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的输出
    • 可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的
    • 输入：有零或多个输入
    • 输出：有一个或多个输出
  • 算法的设计要求
    • 正确性：应当满足具体问题的需求
      • 不含语法错误
      • 对于几组输入能得到满足规格的结果
      • 对于精心选择的典型、苛刻而带有刁难性的输入能够得到满足规格的结果
      • 对于一切合法的输入数据都能得到满足规格的结果
    • 可读性：首先为了人的阅读和交流，其次才是极其执行
    • 健壮性：处理错误的方法应是返回一个表示错误或错误性质的值，而不是打印错误信息或异常
    • 效率与低存储量需求：
  • 算法效率的度量
    • 方法
      • 事后统计
      • 事前分析估算
        • 一句算法选用何种策略
        • 问题的规模
        • 程序语言
        • 编译程序所产生的机器代码的质量
        • 机器执行指令的速度
    • 时间复杂度：T(n) = O(f(n))
      • 一个算法是由控制结构和原操作构成的，算法的时间取决于两者的综合效果
    • 空间复杂度：S(n) = O(f(n))

习题集 > 第1章

二、算法设计题

1.16 试写一算法，自大到小依次输出顺序读入的三个整数X，Y和Z的值。

// 文件名：1_16.c#include <stdio.h>void order(int a, int b, int c){printf("In descending order:\r\n");printf("orgin: a=%d, b=%d, c=%d\r\n", a, b, c);if(a < b){a += b;b = a - b;a = a - b;}if(b < c){b += c;c = b - c;b = b - c;}if(a < b){a += b;b = a - b;a = a - b;}printf("sorted: a=%d, b=%d, c=%d\r\n", a, b, c);
}int main(){int a = 11;int b = 99;int c = 66;order(a, b, c);return 0;
}

# 运行结果
ubuntu@ubuntu:~/work/c/algo$ vim 1_16.c
ubuntu@ubuntu:~/work/c/algo$ gcc 1_16.c 
ubuntu@ubuntu:~/work/c/algo$ ./a.out 
In descending order:
orgin: a=11, b=99, c=66
sorted: a=99, b=66, c=11
ubuntu@ubuntu:~/work/c/algo$

1.17 已知k阶斐波那契序列的定义为

f0=0, f1=0, …, fk-2=0, fk-1=1;

fn=fn-1+fn-2+…+fn-k, n=k,k+1,…

试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

// 注：K阶斐波那契数列的前K-1项均为0,第k项为1,以后的每一项都是前K项的和
// 文件名：1_17.c #include <stdio.h>// 求值（递归）
int k_fib(int k, int m){// 因为第 k-1 项为0，所以此处 k 最小取2if((m<0) || (k<2)){return -1;}int i, v;if((k-1) > m){return 0;}else if((k-1) == m){return 1;}else{for(i=1, v=0; i<=k; i++){v += k_fib(k, m-i);}return v;}
}int main(){int k, m, v;// 1. k < mk = 4;m = 7;v = k_fib(k, m);if(v < 0){printf("error, please check the value of k and m.");}else{printf("if k=%d, m=%d; fib(m) = %d\r\n", k, m, v);}// 2. k == mk = 11;m = 11;v = k_fib(k, m);if(v < 0){printf("error, please check the value of k and m.");}else{printf("if k=%d, m=%d; fib(m) = %d\r\n", k, m, v);}// 3. k > mk = 11;m = 5;v = k_fib(k, m);if(v < 0){printf("error, please check the value of k and m.");}else{printf("if k=%d, m=%d; fib(m) = %d\r\n", k, m, v);}return 0;
}

# 运行结果
ubuntu@ubuntu:~/work/c/algo$ vim 1_17.c 
ubuntu@ubuntu:~/work/c/algo$ gcc 1_17.c 
ubuntu@ubuntu:~/work/c/algo$ ./a.out 
if k=4, m=7; fib(m) = 8
if k=11, m=11; fib(m) = 1
if k=11, m=5; fib(m) = 0
ubuntu@ubuntu:~/work/c/algo$

拓展：斐波那契数列

1.18 假设有A、B、C、D、E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为

项目名称性别校名成绩得分

编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

// 注：首先结构化表格，采集数据，根据定义的数据结构计算目标值
// 文件名：1_18.c #include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>typedef enum{FEMALE,MALE
}SexType;typedef enum{A,B,C,D,E
}SchoolName;typedef struct{char sport; 				// 项目名称int gender; 				// 性别（女：0；男：1）SchoolName school_name; 	// 校名为'A','B','C','D'或'E'char result; 				// 成绩int score; 					// 得分
}ResultType;typedef struct{int male_score; 	// 男子总分int female_score; 	// 女子总分int total_score; 	// 男女团体总分
}ScoreType;void Scores(ResultType *result, ScoreType *score, int num){ int i = 0;for(i=0; i<num; i++){int n = result[i].school_name + 1;score[n].total_score += result[i].score;if(result[i].gender == 1){score[n].male_score += result[i].score;}else{score[n].female_score += result[i].score;}}
}int main(){ int i, n;ResultType *result;ScoreType score[5] = {0};printf("请输入各院校参赛的总人数:");scanf("%d", &n);result = malloc(n * sizeof(ResultType));memset(result, 0, n*sizeof(ResultType));printf("请输入各院校运动员的项目名称、性别、校名、成绩、得分:\n");int school_type;for(i=0; i<n; i++){setbuf(stdin, NULL);printf("< 运动员%d >\n", i+1);setbuf(stdin, NULL);printf("输入项目：\n");scanf("%c", &result[i].sport);setbuf(stdin, NULL);printf("输入性别：\n");scanf("%d", &result[i].gender);setbuf(stdin, NULL);printf("输入校名：\n");scanf("%d", &school_type);result[i].school_name = school_type;setbuf(stdin, NULL);printf("输入结果：\n");scanf("%c", &result[i].result);setbuf(stdin, NULL);printf("输入分数：\n");scanf("%d", &result[i].score);printf("GET: %c %d %d %c %d\r\n", result[i].sport, result[i].gender,result[i].school_name, result[i].result, result[i].score);}Scores(result, score, n);for(i=0; i<5; i++){printf("the school %d: \r\n", result[i].school_name) ; printf("Total score of male: %d\r\n", score[i].male_score);printf("Total score of female: %d\r\n", score[i].female_score);printf("Total score of all: %d\r\n\n", score[i].total_score);}return 0;
}

# 运行结果
ubuntu@ubuntu:~/work/c/algo$ gcc 1_18.c 
ubuntu@ubuntu:~/work/c/algo$ ./a.out 
请输入各院校参赛的总人数:2
请输入各院校运动员的项目名称、性别、校名、成绩、得分:
< 运动员1 >
输入项目：
A
输入性别：
0
输入校名：
1
输入结果：
S
输入分数：
88
GET: A 0 1 S 88
< 运动员2 >
输入项目：
B
输入性别：
1
输入校名：
1
输入结果：
S
输入分数：
99
GET: B 1 1 S 99
the school 1: 
Total score of male: 0
Total score of female: 0
Total score of all: 0the school 1: 
Total score of male: 0
Total score of female: 0
Total score of all: 0the school 0: 
Total score of male: 99
Total score of female: 88
Total score of all: 187the school 0: 
Total score of male: 0
Total score of female: 0
Total score of all: 0the school 0: 
Total score of male: 0
Total score of female: 0
Total score of all: 0ubuntu@ubuntu:~/work/c/algo$

*1.19 试编写算法，计算i!*2i的值并存入数组a[0…arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint，则当n>arrsize或对某个k(1≤k≤n)使k!2k>maxint时，应按出错处理。注意选择你认为较好的出错处理方法。

// 注：重点是错误返回和处理
// 文件名：1_19.c #include <stdio.h>
#include <limits.h>#define OVERFLOW	(-2)
#define ERROR 		(-1)
#define OK     	0#define arrsize	100
#define max_int 	INT_MAXint calc(int i, int *arr){if(i<1 || i>arrsize){return ERROR;}printf("calc %d!*2^%d :\r\n", i, i);int j;for(j=1; j<i; j++){if(j == 1){arr[j-1] = 2;}else{if(max_int/(1*j) < arr[j-2]){return OVERFLOW;}arr[j-1] = 2 * j * arr[j-2];}}printf("< i = %d, i!*2^i > arr[i-1] = %d\r\n", i, arr[j-1]);return OK;
}int main(){int i, res[arrsize];i = 6;int ret = calc(i, res);if(ret == OK){printf("OK!\r\n");}else if(ret == OVERFLOW){printf("overflow.\r\n");}else if(ret == ERROR){printf("error.\r\n");}else{printf("unknown error.\r\n");}return 0;
}

# 运行结果
ubuntu@ubuntu:~/work/c/algo$ vim 1_19.c +27
ubuntu@ubuntu:~/work/c/algo$ gcc 1_19.c 
ubuntu@ubuntu:~/work/c/algo$ ./a.out 
calc 6!*2^6 :
< i = 6, i!*2^i > arr[i-1] = 32767
OK!
ubuntu@ubuntu:~/work/c/algo$

1.20 试编写算法求一元多项式数学公式的值Pn(x)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai(i=0,1,…,n)，x0和n，输出为Pn(x0)。

// 注：多项式求和，重点是计算次数和时间复杂度
// 文件名：1_20.c #include <stdio.h>
#include <math.h>int calc(int *a, int x, int n){int i, res;for(i=1, res=0; i<=n; i++){res += a[i-1]*pow(x, i-1);	// 执行 n 次，时间复杂度O(n)}return res;
}int main(){int a[8] = {3, 4, 8, -2, 1, 5, 7, 6};int n = sizeof(a)/sizeof(a[0]);int x = 2;printf("P%d(%d) = %d\r\n", n, x, calc(a, x, n));return 0;
}

# 运行结果
ubuntu@ubuntu:~/work/c/algo$ vim 1_20.c 
ubuntu@ubuntu:~/work/c/algo$ gcc 1_20.c -lm
ubuntu@ubuntu:~/work/c/algo$ ./a.out 
P8(2) = 1419
ubuntu@ubuntu:~/work/c/algo$

附 > 友情推荐链接

  • 很不错的课本及习题解析：https://www.cnblogs.com/kangjianwei101/p/5221816.html
  • 教材第一章：https://www.cnblogs.com/kangjianwei101/p/5222014.html
  • 习题第一章：https://www.cnblogs.com/kangjianwei101/p/5222150.html

—— 2018-11-27 ——

这篇关于【数据结构】01-绪论《数据结构 C语言版（严蔚敏、吴伟民）》的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/902289。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
集中式版本控制与分布式版本控制——Git 学习笔记01

集中式版本控制与分布式版本控制——Git 学习笔记01

什么是版本控制 如果你用 Microsoft Word 写过东西，那你八成会有这样的经历： 想删除一段文字，又怕将来这段文字有用，怎么办呢？有一个办法，先把当前文件“另存为”一个文件，然后继续改，改到某个程度，再“另存为”一个文件。就这样改着、存着……最后你的 Word 文档变成了这样： 过了几天，你想找回被删除的文字，但是已经记不清保存在哪个文件了，只能挨个去找。真麻烦，眼睛都花了。看
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
01 Docker概念和部署

01 Docker概念和部署

目录 1.1 Docker 概述 1.1.1 Docker 的优势 1.1.2 镜像 1.1.3 容器 1.1.4 仓库 1.2 安装 Docker 1.2.1 配置和安装依赖环境 1.3镜像操作 1.3.1 搜索镜像 1.3.2 获取镜像 1.3.3 查看镜像 1.3.4 给镜像重命名 1.3.5 存储，载入镜像和删除镜像 1.4 Doecker容器操作 1.4
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2