软件基础课堂内容。
一绪论 算法与算法分析：
性质：输入性，输出性，有穷性，确定性，可行性。
频度：语句重复执行的次数。
时间复杂度：算法的时间耗费t(n).
二线性表 线性表：一个线性表是n个数据元素（结点）的有限序列。
是有n个数据元素构成的有线序列。
顺序表：顺序映像。
插入运算。删除运算。
链表：存储数据元素信息的域称作数据域。存储后继元素存储位置的域称作指针域。这两部分信息组成数据元素的储存映像，即结点。
单链表：链表的每个结点中只含有一个指针域。
建立单链表的常用方法：头插法建表和尾插法建表
三栈和队列。
栈：栈是限定在表尾进行插入和删除运算的线性表。表尾成为栈顶，表头称为栈底。
把栈称为后进先出，先进后出的数据结构。
栈的顺序存储表示——顺序栈：
1） 置空栈。
2） 判断栈是否为空。
3） 进栈。
4） 出栈。
5） 取栈顶元素。
链栈：栈的链式存储结构。
定义：struct node;
struct node *top;
队列。队列：是一种运算受限的线性表。允许删除的一端称为队头允许插入的称为队尾。也称为先进先出的线性表，简称为fifo表。
顺序队列。struct sequeue;
struct sequeue *sq;
四串和数组。
串：是由零个或多个字符组成的有限序列。
子串：串中任意个连续的字符组成的子序列。
串的存储结构：顺序存储，链式存储，索引存储。
串运算的实现：串的连接运算，求子串运算。
五树。树的基本概念。
定义：树是n（n>=0）个结点的有限集合t。
满足条件：1） 有且仅有一个特定的称为跟的结点，它没有前趋；
2） 其余的结点可分为m个互不相交的有限集合t1，t2，…tm，其中没个集合又是一棵树，并称为跟的子树。
习惯用语：1.结点。
2.结点的度。
3．树的度。
4．叶子。5．孩子。
6．双亲。7．兄弟。
8．节点的层次。
9．树的深度。
10．堂兄弟。
11．路径。
12．子孙和祖先。
13．森林。
14.有序树和无序树。
二叉树。定义：二叉树是n(n>=0)个结点的有限集，它或为空树，或由一个根结点或两棵互不相交的，分别称作这个根的左子树和右子树的二叉树构成。
性质：1 在二叉树的第i层上至多有2^i-1个结点（i>=1）。
2 深度为k的二叉树至多有2^k-1个结点（k>=1）。
3 对任何一棵二叉树，如果其终端结点书为n。，度为2的结点数为n2，则n。=n2+1。
4 具有n个结点的完全二叉树的深度为[ibn]+1或[ib(n+1)]。
二叉树的存储结构。
顺序存储结构，链式存储结构。
二叉树的建立。
二叉树的深度优先遍历。
1 线序遍历法：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。
2 中序遍历法：（1）中序遍历左子树；（2）访问根结点 ；（3）中序遍历右子树。
二叉树的广度优先遍历深度优先遍历的非递归算法。
二叉树的应用。
哈夫曼树及其应用。
哈夫曼树又称最有二叉树，是一类带权路径长度最短的数。
六图。图的基本概念。
图（g）是一种非线性数据结构，它由两个集合v(g)和e(g)组成。
v（g）是顶点的非空有限集合；
e(g)是v(g)中任意两个顶点之间的关系集合，又称为边的有限集合。
当g中的每条边有方向时，则称g为有向图。
若g中的每条边是无方向的，则称g为无向图。
有向边又称为弧：弧的起始顶点称为弧尾，终止顶点称为弧头。
完全无向图；完全有向图；稀疏图；稠密图
图的存储方法。
图的遍历。深度优先搜索遍历。
度优先搜索遍历。
七索引结构与散列技术。
索引结构：线性索引。
散列技术。散列函数的构造。
1 数字选择法。
2 平方取中法。
3 折叠法。
4 除留余数法。
5 基数转换法。
6 随机数法。
《软件基础》大作业
项目名称 双副扑克一人升级游戏 一人与三机器人玩 班级 电气 29 学号 02041271 02041260 02041257 姓名 李余强张亚婷马媛媛 完成时间 2004 11 8 指导老师 卫颜峻。日期 2004 11 24 目录。一 需求分析。1 1开发背景3 1 2项目目标3 1 3运行环境...
软件大作业
班级 02 0912 学号 02091112 软件大作业。题目软件大作业。学院电子工程学院。专业电子信息工程。学生姓名高大容。导师姓名刘丹华。第一题。从键盘输入字符 6个以上的字符 建立一棵二叉树 二叉树形式任意 输出该二叉树的dlr，ldr，lrd序列，统计叶子结点个数，总结点个数，及二叉树深度 ...
软件技术基础2019大作业模版
序号 学号 姓名 一 以你的学号 生日中的每二位为一个数据，如学号为2011109506，生日为1991 09 03 则数据为 依次做如下操作 1.建立一棵二叉排序树 6分 解答 2.以数据作为权值建立一棵哈夫树并给出每个数据的哈夫曼编码 8分 解答 3.用除留余数法建立一个哈希表，选装填因子为0....