发文章
发文工具
撰写
网文摘手
文档
视频
思维导图
随笔
相册
原创同步助手
其他工具
图片转文字
文件清理
AI助手
留言交流
1、 数据结构
逻辑结构
集合结构:元素之间没有关系
线性结构:一对一
树形结构:一对多
图形结构:多对多
物理结构
定义:指数据的逻辑结构在计算机中的存储形式
储存类型
顺序存储结构
链式存储结构
1 算法定义
算法是解决待定问题求解步骤的描述,在计算机中表现为指令的有序序列, 并且每条指令表示一个或多个操作
2 算法特性
输入
输出
有穷性
确定性
可行性
3 算法时间复杂度
T(n) = O(f(n)), 表示随着问题规模n的增大, 算法执行时间的增长率和f(n)的增加率相同, 称作算法的渐进时间复杂度
4 算法时间复杂度推导方法
常数阶
对数阶
平方阶
5 算法的设计要求
正确性
可读性
健壮性
高效性
低存储量需求
1 线性表的物理结构
线性表的顺序存储结构
线性表的链式存储结构
2 线性表的顺序存储结构
优点
无需为表示表中元素间的逻辑关系增加额外的存储空间
可以快速的存取表中任意位置的元素
缺点
插入和删除需要移动大量元素
造成存储空间的碎片
3 线性表的链式存储结构
链表结构图
代码描述
Typeof strcut Node
{
ElemType data,
Struct *next
} Node;
Typeof stuct Node *LinkList;
数据描述
Ai元素数据域p->data, 指针域p->next
Ai+1元素数据域p->next->data = ai+1
4 单链表结构和数据存储结构优缺点
存储分配方式
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
单链表存储结构采用链式存储结构, 用一组任意的存储单元存放线性表的元素
时间性能
查找:顺序存储结构为O(1) 单链表O(n)
插入和删除:顺序存储为O(n), 单链表在现出某位置的指针后仅为O(1)
空间性能
顺序存储需要预分配存储空间,单链表不需要预分配存储空间, 元素个数不受限制
工程结构如下:
DataStructure.CustomArray
DataStructure.CustomLinkList
DataStructure.Test
1、线性表的顺序存储:
public class CustomArray { private const int MAXLENGTH = 10000; private object[] _array; private readonly int _maxLength; private int _length; public CustomArray() : this(MAXLENGTH) { } public CustomArray(int maxLength) { if (maxLength > MAXLENGTH) { throw new ArgumentOutOfRangeException(string.Format("数组长度必须小于{0}", MAXLENGTH)); } _maxLength = maxLength; _array = new object[100]; } public void AddValue(object value) { if (GetLength() == _maxLength) { throw new ArgumentOutOfRangeException("数组已经达到最大值"); } ExpandCustomArray(); _array[GetLength()] = value; _length++; } /// <summary> /// 获取所引处的值 /// </summary> /// <param name="index">具体位置, 从1开始</param> /// <returns></returns> public object GetValue(int index) { if (index < 1 || index > GetLength()) { throw new ArgumentOutOfRangeException(); } return _array[index - 1]; } /// <summary> /// 在指定的索引位置插入值 /// </summary> /// <param name="value">插入的值</param> /// <param name="index">索引位置</param> public void Insert(object value, int index) { if (GetLength() == _maxLength) { throw new ArgumentOutOfRangeException("数组已经达到最大值"); } if (index < 1 || index > GetLength()) { throw new ArgumentOutOfRangeException("索引已超出数组范围"); } ExpandCustomArray(); for (var i = GetLength() ; i >= index; i--) { _array[i] = _array[i - 1]; } _array[index - 1] = value; _length++; } private void ExpandCustomArray() { if (_array.Length == GetLength()) { var tempArray = new object[_array.Length + 100]; for (var i = 0; i < _array.Length; i++) { tempArray[i] = _array[i]; } _array = tempArray; } } public int GetLength() { return _length; } public int IndexOf(object value) { for (var index = 1; index <= GetLength(); index++) { if (_array != null &&_array[index - 1].Equals(value)) { return index; } } return -1; } public object Delete(int index) { if (index > GetLength() || index < 1) { throw new ArgumentOutOfRangeException(); } var deletedValue = _array[index - 1]; for (var i = index - 1; i < GetLength() - 1; i++) { _array[i] = _array[i + 1]; } _length--; return deletedValue; } public void Clear() { _array = new object[0]; _length = 0; } }
2、线性表的链式存储
public class CustomLinkList { private int _length; private CustomLinkNode _headerNode; private CustomLinkNode _lastNode; public CustomLinkList() { _headerNode = new CustomLinkNode(null); _lastNode = _headerNode; } public int GetLength() { return _length; } public int IndexOf(CustomLinkNode node) { var index = 1; var compareNode = _headerNode.Next; while (compareNode != null) { if (Object.ReferenceEquals(compareNode, node)) { break; } compareNode = compareNode.Next; index++; } if (index > GetLength()) { return -1; } return index; } public CustomLinkNode GetNode(int index) { if (index < 1 || index > GetLength()) { throw new ArgumentOutOfRangeException("索引已经超出链表范围"); } var beforeNode = GetContainHeaderNode(index - 1); if (beforeNode == null || beforeNode.Next == null) { throw new NoNullAllowedException(); } return beforeNode.Next; } public void AddNode(CustomLinkNode node) { _lastNode.Next = node; _lastNode = node; _length++; } public void InsertNode(CustomLinkNode node, int index) { if (index < 1 || index > GetLength()) { throw new ArgumentOutOfRangeException("索引已经超出链表范围"); } var beforeNode = GetContainHeaderNode(index - 1); if (beforeNode == null || beforeNode.Next == null) { throw new NoNullAllowedException(); } var insertedNode = beforeNode.Next; node.Next = insertedNode; beforeNode.Next = node; _length++; } public CustomLinkNode DeleteNode(int index) { if (index < 1 || index > GetLength()) { throw new ArgumentOutOfRangeException("索引已经超出链表范围"); } var beforeNode = GetContainHeaderNode(index - 1); if (beforeNode == null || beforeNode.Next == null) { throw new NoNullAllowedException(); } var deletedNode = beforeNode.Next; beforeNode.Next = deletedNode.Next; if (index == GetLength()) { _lastNode = beforeNode; } _length--; return deletedNode; } private CustomLinkNode GetContainHeaderNode(int index) { var i = 0; var beforeNode = _headerNode; while (beforeNode != null) { if (i == index) { break; } i++; beforeNode = beforeNode.Next; } if (beforeNode == null) { throw new NoNullAllowedException(); } return beforeNode; } }
3、单元测试
private static void TestCustomArray() { var customArray = new CustomArray.CustomArray(10); Assert.IsEqual(customArray.GetLength(), 0); for (var i = 1; i <=10; i++) { customArray.AddValue(i * 100); } Assert.IsEqual(customArray.GetLength(), 10); Assert.IsException(customArray.AddValue, (object)210, typeof(ArgumentOutOfRangeException)); var deleteValue = customArray.Delete(5); Assert.IsEqual(customArray.GetLength(), 9); Assert.IsEqual((int) deleteValue, 500); Assert.IsEqual((int)customArray.GetValue(5), 600); customArray.Insert(500, 5); Assert.IsEqual(customArray.GetLength(), 10); Assert.IsEqual((int)customArray.GetValue(5), 500); Assert.IsEqual((int)customArray.GetValue(6), 600); Assert.IsException(customArray.Insert, (object)1000, 0, typeof(ArgumentOutOfRangeException)); Assert.IsException(customArray.Insert, (object)1000, 10, typeof(ArgumentOutOfRangeException)); Assert.IsEqual(customArray.IndexOf(100), 1); Assert.IsEqual(customArray.IndexOf(200), 2); Assert.IsEqual(customArray.IndexOf(500), 5); } private static void TestCustomLinkList() { var customLinkList = new CustomLinkList.CustomLinkList(); var node1 = new CustomLinkNode(1); customLinkList.AddNode(node1); var node2 = new CustomLinkNode(2); customLinkList.AddNode(node2); var node3 = new CustomLinkNode(3); customLinkList.AddNode(node3); var node4 = new CustomLinkNode(4); customLinkList.AddNode(node4); var node5 = new CustomLinkNode(5); customLinkList.AddNode(node5); Assert.IsEqual(customLinkList.GetLength(), 5); Assert.IsEqual( (int)customLinkList.GetNode(1).Data, 1); Assert.IsEqual((int)customLinkList.GetNode(3).Data, 3); Assert.IsEqual((int)customLinkList.GetNode(5).Data, 5); var node11 = new CustomLinkNode(11); var afterNode = customLinkList.GetNode(1); customLinkList.InsertNode(node11, 1); Assert.IsEqual((int)customLinkList.GetNode(1).Data, 11); Assert.IsEqual((int)customLinkList.GetNode(2).Data, (int)afterNode.Data); var node33 = new CustomLinkNode(33); afterNode = customLinkList.GetNode(4); customLinkList.InsertNode(node33, 4); Assert.IsEqual((int)customLinkList.GetNode(4).Data, 33); Assert.IsEqual((int)customLinkList.GetNode(5).Data, (int)afterNode.Data); afterNode = customLinkList.GetNode(7); var node55 = new CustomLinkNode(55); customLinkList.InsertNode(node55, 7); Assert.IsEqual((int)customLinkList.GetNode(7).Data, 55); Assert.IsEqual((int)customLinkList.GetNode(8).Data, (int)afterNode.Data); Assert.IsEqual(customLinkList.GetLength(), 8); var deletedNode = customLinkList.DeleteNode(1); Assert.IsEqual((int)deletedNode.Data, 11); Assert.IsEqual((int)customLinkList.GetNode(1).Data, 1); deletedNode = customLinkList.DeleteNode(3); Assert.IsEqual((int)deletedNode.Data, 33); Assert.IsEqual((int)customLinkList.GetNode(3).Data, 3); deletedNode = customLinkList.DeleteNode(5); Assert.IsEqual((int)deletedNode.Data, 55); Assert.IsEqual((int)customLinkList.GetNode(5).Data, 5); Assert.IsEqual(customLinkList.GetLength(), 5); Assert.IsEqual(customLinkList.IndexOf(node1), 1); Assert.IsEqual(customLinkList.IndexOf(node3), 3); Assert.IsEqual(customLinkList.IndexOf(node5), 5); Assert.IsEqual(customLinkList.IndexOf(node11), -1); Assert.IsException<int, CustomLinkNode>(customLinkList.DeleteNode, 0, typeof(ArgumentOutOfRangeException)); Assert.IsException<int, CustomLinkNode>(customLinkList.DeleteNode, 6, typeof(ArgumentOutOfRangeException)); Assert.IsException(customLinkList.InsertNode, node1, 0, typeof(ArgumentOutOfRangeException)); Assert.IsException(customLinkList.InsertNode, node1, 6, typeof(ArgumentOutOfRangeException)); }
来自: 昵称10504424 > 《工作》
0条评论
发表
请遵守用户 评论公约
CString常用方法一_无处&&心灵
CString::Compareint Compare( LPCTSTR lpsz ) const;// CString::GetBuffer 例子CString s( "abcd" );#ifdef _DEBUGafxDump <<"CString s "<<s <<"\n&quo...
VC:CString用法整理(转载)
VC:CString用法整理(转载)CString s;CString::MidCString Mid( int nFirst ) const;CString::CString //构造函数。CString( const CString& stringSrc );CString str1,str2,str3;如果你使用由GetBu...
CString截取字符串全攻略&CString::Find()函数(转载)
CString截取字符串全攻略 & CString::Find()函数(转载)CString::Find作用 在一个较大的字符串中查找字符或子字符串 int Find( TCHAR ch ) const; int Find(LPCTSTR lpszSub ) const; ...
JS判断两个对象内容是否相等的方法示例及开发面试题汇总(图)
JS判断两个对象内容是否相等的方法示例及开发面试题汇总(图)var obj1={name:"liu",age:22};var obj2={name:"liu"...
2个js对象如何进行比较类似java的compare
OpenLayers项目分析——(四)空间数据的组织与实现-睁眼瞎看-3sNew...
OpenLayers项目分析——(四)空间数据的组织与实现 - 睁眼瞎 看 - 3sNew...OpenLayers项目分析——(四)空间数据的组织与实现。在Open...
在窗体上创建自己的光标并输入文字
我们知道在文本框等可以接收输入的组件中,我们可以看到闪烁的光标,并可以输入文字,如果我们在,比如窗体上时,因为不支持输入,也无法显示闪烁的光标,那我们 有办法做自己的输入吗?type TForm...
【算法】验证码识别基础方法及源码
while (next <width - 7) { var matched = Match(table, next);} private bool[,] ToTable(Bitmap...
vs2008 MFC访问Access 2010数据库
}BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)END_MESSAGE_MAP()// CAccessDemoDlg dialogCAccessDemoDlg::CAccessDemoDlg(CWnd* pParent /*=...
微信扫码,在手机上查看选中内容