当前位置:编程学习 > C/C++ >>

数据结构读书笔记(一)(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个元素赋值为e  
  ListInsert(&L,i,e) //1<=i <=LengthList(L) +1  结果:在L的第i个元素之前插入新的元素e,L的长度增1  
  ListDelete(&L,i,&e)//1<=i <=LengthList(L) 结果:删除L的第i个元素,并用e返回其值,,L的长度减1  
}ADT List  
3.顺序实现
 
 1)存储结构:
 
 
[cpp]  
#define LIST_INIT_SIZE   10  
#define INCREAMENT   2  
struct 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;  
    else  
        return 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;  
    else  
        return 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;  
    }  
    else  
        return I
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,