标题:【不知道能不能发学习帖】我是小白,刚刚学数据结构想开一学习帖
取消只看楼主
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
结帖率:50%
已结贴  问题点数:20 回复次数:9 
【不知道能不能发学习帖】我是小白,刚刚学数据结构想开一学习帖
首先,我是小白,感觉学习数据结构,有点难度,所以想立一学习帖,记录自己学习情况。
其次,我想把这个帖作为我对数据结构理解和整理笔记的地方。
第三,个人缺乏坚持的毅力,以此敦促自己学习数据结构。
PS:我不会每天都更帖,但我会保持一定的频率。
鼓励一下自己。
加油
搜索更多相关主题的帖子: 学习 数据 
2012-04-03 09:46
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
今天先发一些数据结构的基本概念和术语
数据
数据元素(是数据的基本单位):指的是一个结点的记录。比如一张成绩表里,一个学生的学号,成绩,性别等合起来就是一个数据元素。
数据项(数据不可分割的在最小单位):如上一个学生的学号就是一个数据项
数据结构:相互之间存在一种或多种特定关系的数据元素的集合
4类基本结构:a.集合 b.线性结构 c.树形结构 d.图状结构或网状结构
逻辑结构:只反映数据元素之间的逻辑关系(是抽象的)
物理结构:数据结构在计算机里的表示
         【重点】逻辑结构与物理结构的关系
                 1.物理结构是其逻辑结构在RAM中的映像
                 2.算法设计思想依赖于逻辑结构
                   而算法的实现依赖于所采用的存储结构
算法(程序是算法,但算法不一定是程序)
     5个重要特性:有穷性(有穷步,有穷时间内完成)、确定性(唯一一条执行路径)、可行性(能实现)、输入(零个或多个)、输出(一个或多个)
     设计要求:a.正确性(不解释) b.可读性(算法主要是与人交流,所以要写上必要的注释) c.健壮性(对非法的输入有适当的反应)(尤其在边界问题上要考虑算法的
               健壮性,以后再说)
【重点】算法的时间复杂度:
          T(n)=O(f(n))               //O是一个数学符号,当n趋向于无穷时,是f(n)/g(n)是常数,则f(n)与g(n)同阶,一般来说,一个函数的增长速度与该函数的最高次同
                                        阶。
          算法的时间复杂性与问题规模和序列的初始值有关,若与初始值有关则时间复杂度按最坏情况考虑
2012-04-03 10:12
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
不知道哪位大神能跟我讲解一下ADT
看到现在,我还是不太能理解诶
2012-04-03 11:00
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
回复 4楼 lsnaimei
谢谢你。
2012-04-08 00:30
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
由于我最近忙于期中考试,所以搁置了一会。
明天继续学习线性表的有关内容
2012-04-08 00:32
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
总觉得这里太冷清了。。。
2012-04-08 00:33
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
回复 8楼 OoDreamParty
与君共勉哦
2012-04-09 18:47
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
首先,我想先向自己道歉.说好昨天复习线性表的。结果自己放了自己的鸽子。
我想,原因自知。
一诺千金,是每个人必须做到的,不是吗。
2012-04-09 19:00
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
现在复习线性表:
一、概念就不说了。
        【注意】线性表的特点是:只有一个第一个数据元素,也只有一个最后一个数据元素。只有一个直接前驱,也只有一个直接后继。
二、顺序表[线性表的顺序表示]
         1.用计算机里地址连续的存储单元存储。[在逻辑结构上相邻的元素,在物理结构上亦是相邻的]
                  地址计算公式(1)LOC(ai) = LOC(a1) + (i-1)*L    [L表示一个数据元素所占字节]
                              (2)LOC(ai+1) = LOC(ai) + L oudin
         2.顺序表的基本运算/操作
                  (1)插入:线性表的插入是指在第i(1<i<n+1)个元素之前插入一个新的数据元素x,使长度为n的线性表(a1,... ,ai-1,ai,ai+1 ,...,an)变成长度为n+1的线
                             性表(a1,...,ai-1,x,ai,ai+1,...,an), 这时需将第i至第n共(n-i+1)个数据元素后移。
                             实现插入操作的核心C语言代码:for(j=n;j>=i;j--)
                                                                v[j]=v[j-1];  
                                                          v[j]=x;
                             算法的时间复杂度:T(n)=O(n);[这个可以思考一下为什么,不解释]
                  (2)删除:线性表的删除是指将第i(1<i<n)个元素删除,使长度为n的线性表(a1,...,ai-1,ai,ai+1,...,an)变成长度为n-1的线性表
                             (a1,...,ai-1,ai+1,...,an),这时需将第i+1至第n共(n-i)个数据元素前移。
                             核心代码:for(j=i;j<n;j++)  v[j-1]=v[j];
                             算法的时间复杂度:T(n)=O(n);
                   【综述】在一个有N个元素的顺序表中插入或删除一个元素,平均需要移动N/2个元素,且具体移动的元素个数与表长和该元素在表中的位置有关;
         3.顺序表的优缺点:
                  优点:(1)采用顺序存储方式,便于直接获得某个特定的元素
                        (2)操作直观
                  缺点:(1)操作需要移动大量元素
                        (2)预先分配空间需要按最大空间分配,RAM利用不充分
         4.顺序表在计算机中是借助一位数组表示的。
           【顺序表与数组的区别】:(1)表的长度可变,而数组的长度是不变的(一旦定义后)
                                   (2)表中的元素是可变的(dynamic),而数组中的元素是不变的(static)
三、链表[线性表的链式表示]
         1.几个概念:结点,单链表,头指针与头结点
                 【头结点的作用】:(1)头指针的数据域可以存储额外信息,如表的长度等
                                   (2)设置头结点后,头指针指向头结点,不论链表是否为空,头指针总是非空,即表示的一致性。
                                   (3)头结点使得对链表的第一个元素的操作与其他元素无异,因为都在某一结点之后,即操作上的兼容性。
         2.链表的基本运算/操作        
                (1)查找:核心代码:p=head->next;      
                                     while(p&&p->data!=x)   
                                          p=p->next;      
                                     return(p);  
                           算法的时间复杂度:T(n)=O(n);
                (2)插入:核心代码:s=(Node*)malloc(sizeof(Node));      
                                     s->data = x;      
                                     s->next = p->next;      
                                     p->next = s; //若该语句和上一条语句次序互换,则出错
                           算法的时间复杂度:T(n)=O(1);
                 (3)删除:核心代码:if(p){
                                          q = p->next;                  
                                          p->next = q->next;                  
                                          free(q); }
                          算法的时间复杂度:如上
                (4)动态链表的建立:核心代码:head = (Node *)malloc(sizeof(Node));      
                                               head->next = NULL;      
                                               for ( i = n; i > 0; i-- ) {         
                                                        p = (Node *)malloc(sizeof(Node));         
                                                        p->data = a[i-1];            
                                                        p->next = head->next;         
                                                        head->next = p; }      
                                               return  head;
         3.单链表的优缺点:
                          优点:(1)他是一种动态存储结构,不需要预先分配空间
                                (2)插入,删除操作简便
                          缺点:(1)指针占用额外存储空间(特别当元素本身信息量很少时不划算)
                                (2)顺序存取数据元素(不能随机存取),查找速度慢
                           
2012-04-09 19:57
渭平
Rank: 2
等 级:论坛游民
帖 子:22
专家分:14
注 册:2011-12-11
得分:0 
双向链表及循环链表,不再赘述
2012-04-09 19:59



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-365079-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.830212 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved