数据结构读书笔记(一)(C语言)
第一章 关于数据结构1.数据结构研究什么?(计算机加工的对象由数值——>非数值)将现实生活中大量而复杂的问题(非数值问题)以特定的数据类型(逻辑结构)和特定的存储结构(物理结构)保存到主存储器中,以及在此基础上为实现某个功能(删除、排序)相对应的操作。2.数据的逻辑结构:3.存储结构(物理结构):1)顺序存储结构(借助元素在存储器中的相对位置)2)链式存储结构(借助元素存储地址的指针)4.抽象数据类型ADT:[cpp]ADT抽象数据类型名{数据对象:<数据对象的定义>数据关系:<数据对象之间关系的定义>基本操作:<基本操作的定义>}5、时间复杂度:取决定性作用语句的重复次数第二章 线性表1.线性结构的基本特征:1)集合中必存在唯一的一个“第一个元素”;2)集合中必存在唯一的一个“最后元素”;3)除最后元素外,均有唯一的后继;4)除第一元素之外,均有唯一的前驱;2.ADT[cpp]ADT List{数据对象:D={ a1,a2, a3, ... an};数据关系:R={<a1, a2>, <a2, a3>, <a3, a4> … <an-1, an>};基本操作:InitList(&L); //操作结果:构造线性表;DestroyList(&L); //操作结果:销毁线性表;ListEmpty(L); //操作结果:若L为空表,则返回TRUE,否则FALSE;ListLength(L); //操作结果:返回L中元素个数;PriorElem(L,cur_e,&pre_e)//操作结果:cur_e是L的元素,但不是第一个//则用pre_e返回它的前驱。若操作失败,pre_e无定义NextElem(L,cur_e,&next_e)//操作结果:cur_e是L的元素,但不是最后一个,//则用next_e返回它的后继。若操作失败,next_e无定义GetElem(L,i,&e) // 1<= i <=LengthList(L) 操作结果:用e返回L中第i个元素的值。LocateElem(L,e,compare())//compare()是元素判定函数。返回L中第一个与e满足compare()的元素位序。//若这样的元素不存在,则返回值为0。ListTraverse(L,visit( )) //依次对L的每个元素调用函数visit( ).一旦visit( )失败,则操作失败ClearList(&L) //操作结果将L重置为空表。PutElem(L,i,&e) //1<=i<=LengthList(L) 结果:L中第i个元素赋值为eListInsert(&L,i,e) //1<=i <=LengthList(L) +1 结果:在L的第i个元素之前插入新的元素e,L的长度增1ListDelete(&L,i,&e)//1<=i <=LengthList(L) 结果:删除L的第i个元素,并用e返回其值,,L的长度减1}ADT List3.顺序实现1)存储结构:[cpp]#define LIST_INIT_SIZE 10#define INCREAMENT 2struct SqList{ElemType * elem;int length;int listsize;};2)基本操作[cpp]void InitList(SqList & L ){L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType) );L.length = 0;L.listsize = LIST_INIT_SIZE;}void DestroyList(SqList & L){free(L.elem);L.elem = NULL;L.length = 0;L.listsize = 0;}void ClearList( SqList & L){L.length = 0;}Status ListEmpty( SqList L){if( L.length != 0 )return FALSE;elsereturn TRUE;}int ListLength(SqList L){return L.length;}Status GetElem(SqList L, int i , ElemType & e){if( i < 1 || i > L.length )return ERROR;e = *(L.elem + i - 1);return OK;}int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType , ElemType)){ElemType * p;p = L.elem;int i = 1;while(i < L.length && !(compare(e, *p))){i++;p++;}if( i< L.length)return i;elsereturn 0;}Status PriorElem(SqList L, ElemType cur_e, ElemType & pre_e){ElemType * p;p = L.elem + 1; //p 和 i 之间进行合作int i = 2;while(i < L.length && *p!=cur_e){i++;p++;}if( i< L.length){pre_e = *(--p);return OK;}elsereturn I补充:软件开发 , C++ ,
上一个:c++中vector与list的区别
下一个:引用作为函数返回值
- 更多C/C++疑问解答:
- 关于c++的cout输出的问题。
- 在学校里学过C和C++,不过学的很一般,现在自学C#,会不会很难?
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点,3个3度结点,4个4度结点,问有几个叶子结点?
- c++数据结构内部排序问题,整数排序
- 2012九月计算机二级C语言全国题库,,急求急求
- 如果assert只有一个字符串作为参数,是什么意思呢?
- C语言中,哪些运算符具有左结合性,哪些具有右结合性,帮忙总结下,谢谢了!
- 为什么用结构体编写的程序输入是,0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型,用C或C++都行,多谢各位大侠啊,非常感谢!
- 为什么这个程序求不出公式?
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊