`
junjie314
  • 浏览: 60260 次
  • 性别: Icon_minigender_1
  • 来自: 宁波
文章分类
社区版块
存档分类
最新评论

程序员数据结构笔记(一)

阅读更多
1.数据结构中对象的定义,存储的表示及操作的实现.
  2.线性:线性表、栈、队列、数组、字符串(广义表不考)
   树:二叉树
   集合:查找,排序
   图(不考)
能力:
  分析,解决问题的能力
过程:
  ● 确定问题的数据。
  ● 确定数据间的关系。
  ● 确定存储结构(顺序-数组、链表-指针)
  ● 确定算法
  ● 编程
  ● 算法评价(时间和空间复杂度,主要考时间复杂度)
一、数组
  1、存放于一个连续的空间
  2、一维~多维数组的地址计算方式
  已知data[0][0]的内存地址,且已知一个元素所占内存空间s求data[i][j]在内存中的地址。
   公式:(add+(i*12+j)*S)(假设此数组为data[10][12])
  注意:起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况;
  3、顺序表的定义
   存储表示及相关操作
  4、顺序表操作中时间复杂度估计
  5、字符串的定义(字符串就是线性表),存储表示
   模式匹配算法(简单和KMP(不考))
  6、特殊矩阵:存储方法(压缩存储(按行,按列))
   三对角:存储于一维数组
   三对角问题:已知Aij能求出在一维数组中的下标k;已知下标k求Aij。
  7、稀疏矩阵:定义,存储方式:三元组表、十字链表(属于图部分,不考) 
  算法
  ● 数组中元素的原地逆置; 对换
  ● 在顺序表中搜索值为X的元素;
  ● 在有序表中搜索值为X的元素;(折半查找)
  ● 在顺序表中的第i个位置插入元素X;
  ● 在顺序表中的第i个位置删除元素X;
  ● 两个有序表的合并;算法?
  线性表数据结构定义:
   Typedef struct {
    int data[max_size];
    int len;
   }linear_list;
  ● 模式匹配
  ● 字符串相加
  ● 求子串
  ● (i,j)<=>K 注意:不同矩阵所用的公式不同;
  ● 稀疏矩阵的转置(两种方式,后种为妙)
  ● 和数组有关的算法 
--------------------------------------------------------------------------------
  例程:求两个长整数之和。
  a=13056952168
  b=87081299
  数组:
  a[]:1 3 0 5 6 9 5 2 1 6 8
  b[]:8 7 0 8 1 2 9 9 
由于以上的结构不够直观(一般越是直观越容易解决) 将其改为:
  a[]:11 8 6 1 2 5 9 6 5 0 3 1 a[0]=11(位数)
  b[]: 8 9 9 2 1 8 0 7 8 0 0 0 b[0]=8
  c进位 0 1 1 0 0 1 1 1 1 0 0 
  c[]:11 7 6 4 3 3 0 4 4 2 3 1 c[0]的值(C位数)由c[max_s+1]决定!
  注意:在求C前应该将C(max_s+1)位赋0.否则为随机数; 较小的整数高位赋0.
  算法:已知a,b两个长整数,结果:c=a+b;
  总共相加次数: max_s=max(a[],b[])
  程序:
  for(i=1;i<=max_s;i++) {
   k=a[i]+b[i]+c[i];
   c[i]=k;
   c[i+1]=k/10;
  }
  转贴于 学生大考试站 http://www.stsj86.com求c位数:
  if(c[max_s+1]==0)
   c[0]=max_s;
  else
   c[0]=max_s+1;
  以下代码是我编的(毕竟是初学者.不太简洁大家不要见怪!):
  /*两长整数相加*/
   #include<stdio.h></stdio.h>
   #include<string.h></string.h>
  #define PRIN printf(" ");
  int flag=0; /*a[0]>b[0]?1:0*/
  /* max(a[],b[]) {}*/
  change(char da[],char db[],int a[],int b[],int c[]) {
   int i;
   if(a[0]>b[0]) {
    for(i=1;i<=a[0];a[i]=da[a[0]-i]-’0’,i++); /*a[0]-’0’ so good!*/
    for(i=1;i<=b[0];b[i]=db[b[0]-i]-’0’,i++);
    for(i=b[0]+1;i<=a[0];b[i]=0,i++);
    for(i=1;i<=a[0]+1;c[i]=0,i++);
    flag=1;
   }
   else {
    for(i=1;i<=b[0];b[i]=db[b[0]-i]-’0’,i++);
    for(i=1;i<=a[0];a[i]=da[a[0]-i]-’0’,i++);
    for(i=a[0]+1;i<=b[0];a[i]=0,i++);
    for(i=1;i<=b[0]+1;c[i]=0,i++);
   }
  }
  add(int a[],int b[],int c[]) {
   int i,sum;
   if(flag==1) {
    for(i=1;i<=a[0];i++) {
     sum=a[i]+b[i]+c[i];
     c[i+1]=sum/10;
     c[i]=sum;
    }
    if(c[a[0]+1]==0)
     c[0]=a[0];
    else
     c[0]=a[0]+1;
   }
   else {
    for(i=1;i<=b[0];i++) {
     sum=a[i]+b[i]+c[i];
     c[i+1]=sum/10;
     c[i]=sum;
    }
    if(c[b[0]+1]==0)
     c[0]=b[0];
    else
     c[0]=b[0]+1;
   }
  }
  void print(int m[]) {
   int i;
   for(i=m[0];i>=1;i--)
    printf("%d,",m[i]); PRIN
  }
  main(){
   int s;
   int a[20],b[20],c[20];
   char da[]={"123456789"};
   char db[]={"12344443"};
   a[0]=strlen(da);
   b[0]=strlen(db);
   printf("a[0]=%d ",a[0]);
   printf("b[0]=%d",b[0]); PRIN
 change(da,db,a,b,c);
   printf("flag=%d ",flag); PRIN
   printf("----------------- ");
   if(flag==1) {
    print(a); PRIN
    s=abs(a[0]-b[0]);
    printf("+");
     for(s=s*2-1;s>0;s--)
      printf(" ");
      print(b); PRIN
   }
   else {
    s=abs(a[0]-b[0]);
    printf("+");
    for(s=s*2-1;s>0;s--)
     printf(" ");
     print(a); PRIN
     print(b); PRIN
   }
   add(a,b,c);
   printf("----------------- ");
   print(c);
  }
时间复杂度计算:
  ● 确定基本操作
  ● 计算基本操作次数
  ● 选择T(n)
  ● lim(F(n)/T(n))=c
  ● 0(T(n))为时间复杂度
  上例子的时间复杂度为O(max_s); 
--------------------------------------------------------------------------------
二:链表
  1、知识点
  ●逻辑次序与物理次序不一致存储方法
  ●单链表的定义:术语(头结点、头指针等)
  ●注意带头结点的单链表与不带头结点的单链表区别。(程序员考试一般不考带头结点,因为稍难理解)
  ●插入、删除、遍历(p==NULL表明操作完成)等操作
  ● 循环链表:定义,存储表示,操作;
  ● 双向链表:定义,存储方法,操作;
  单链表和循环链表区别在最后一个指针域值不同。
 转贴于 学生大考试站 http://www.stsj86.com 2、操作
  ●单链表:插入X,删除X,查找X,计算结点个数
  ●单链表的逆置(中程曾考)
  head->NULL/p->a1/p->a2/p->a3/p……an/NULL 注:p代表指针;NULL/p代表头结点
  =》 head->NULL/p->an/p->an-1/p->an-2/p……a1/NULL 
  ●循环链表的操作:插入X,删除X,查找X,计算结点个数;
    用p=head->next来判断一次计算结点个数完成;
  程序段如下:
  k=0;
  do{
   k++;
   p=p->next;
  }while(p!=head->next);
  ● 双向链表
  ●多项式相加
  ● 有序链表合并 
--------------------------------------------------------------------------------
  例程:已知两个字符串S,T,求S和T的最长公子串;
  1、逻辑结构:字符串
  2、存储结构:数组
  3、算法: 精化(精细化工)**老顽童注:此处“精细化工”说明好像不对!
  s="abaabcacb" 
  t="abdcabcaabcda"
  当循环到s.len-1时,有两种情况:s="abaabcacb"、s="abaabcacb" 
      s.len-2时,有三种情况:s="abaabcacb"、s="abaabcacb"、s="abaabcacb" 
       .
       .
       .
      1 s.len种情况
  程序思路:
tag=0 //没有找到
  for(l=s.len;l>0&&!tag;l--) {
   判断长度为l的s中的子串是否为t的子串;
   若是:tag=1;
  }
  长度为l的s的子串在s中有(s.len-l+1)个。
  子串0: 0~l-1
    1:    1~l      
    2:    2~l+1      
    3:    3~l+2
     …… 
     ……
    s.len-l: s.len-l~s.len-1
  由上面可得:第j个子串为j~l+j-1。
  判断长度为l的s中的子串是否为t的子串:
  for(j=0;j   判断s中长度为l的第j个子串是否为t的子串;
   如果是:tag=1;
  }
  模式结构:
  tag=0;
  for(l=s.len;l>0&&tag==0;l--) {
   for(j=0;j    ?? 用模式匹配方法确定s[j]~s[l+j-1]这个字符串是否为t的子串; //好好想想
     若是,tag=1;
   }
  }
  在前面笔者编了一些程序:链表,长整型数相加,三元组表转置以及一些简单的函数.其实有些算法想想是很简单,不过写起来还是需要一定耐心和C基础的,如果你自己觉得各算法都很懂了,不妨开机编编试试.或许会有一些新的发现与体会.
栈和队列
  1、知识点:
  ● 栈的定义:操作受限的线性表
  ● 特点:后进先出
  ● 栈的存储结构:顺序,链接
   / push(s,d)
  ● 栈的基本操作:
    pop(s)
  栈定义:
  struct {
   datatype data[max_num];
   int top;
  };
  ●队列定义
  特点:先进先出
  /入队列 in_queue(Q,x)
  ●队列的操作:
  出队列 del_queue(Q)
  ●队列存储结构:
  链队列:
  Typedef struct node{
   Datatype data;
   Struct node *next;
  }NODE;
  Typedef struct {
   NODE *front;
   NODE *rear;
  }Queue;
  顺序队列:
  struct {
   datatype data[max_num];
   int front,rear;
  };
  问题:
  队列ó线性表
  假溢出<=循環队列
  队列满,队列空条件一样<=浪费一个存储空间
  递归
  定义:问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。
  包括二个步骤:
分享到:
评论

相关推荐

    程序员数据结构笔记

    在程序员数据结构的学习中,以下几个关键知识点不容忽视: 1. **数据结构的基本概念**:数据结构指的是数据的组织方式,它定义了数据之间的关系以及操作这些数据的方法。在学习数据结构时,我们需要理解对象的定义...

    程序员数据结构笔记 程序员数据结构笔记

    本篇笔记主要涵盖数据结构的基本概念、线性结构、树形结构、集合与排序,以及与数组相关的算法。 1. **数据结构的定义**: 数据结构是指一组数据的存储结构,包括数据对象、数据关系和对数据的操作。数据结构的选择...

    程序员数据结构笔记 知识 能力 过程

    程序员在面对纷繁复杂的编程挑战时,数据结构的知识和能力是他们手中最锋利的武器。数据结构不仅是计算机科学的基石,更是程序员高效编程的保障。在深入理解数据结构的过程中,程序员需要关注知识的掌握、能力的提升...

    程序员数据结构笔记.doc

    总的来说,程序员数据结构笔记涵盖了数据结构的基本概念、常见数据结构的操作及其时间复杂度分析,同时提供了具体的编程实例,帮助程序员理解和应用数据结构。掌握这些知识对于提升编程能力,特别是解决复杂问题的...

    程序员 数据 结构 笔记

    程序员在日常工作中,无论是开发系统软件、应用程序还是处理大数据,都需要掌握数据结构的相关知识。 首先,我们要理解数据结构中的“对象”指的是在计算机中表示的数据单元,它们可以是基本类型如整数、字符,也...

    程序员数据结构笔记很好很强大!

    程序员在日常工作中,无论是开发系统软件、应用软件还是进行数据分析,都会频繁地与各种数据结构打交道。下面我们将深入探讨数据结构的一些核心知识点。 首先,数据结构中的对象定义指的是数据的组织形式,它可以是...

    软考程序员数据结构笔记.doc

    在软考程序员的准备过程中,理解并掌握数据结构是必不可少的。以下是一些关于数据结构的关键知识点: 1. **数据结构的定义**:数据结构指的是数据的逻辑结构、存储结构以及在其上定义的操作的集合。它可以是简单的...

    黑马程序员Javase笔记

    Map是一个键值对的数据结构,可以嵌套使用,例如`HashMap, HashMap, String&gt;&gt;`。同时,可以使用匿名内部类创建自定义的比较器来定制排序规则。 总结来说,"黑马程序员Javase笔记"涵盖了Java的基础语法、内存管理、...

    程序员数据结构学习笔记

    数组是基本且重要的数据结构,笔记中提到的数组存储在一连续的内存空间中。数组的地址计算涉及数组的维度和元素大小。顺序表的操作包括插入、删除、查找,以及元素的原地逆置。字符串的模式匹配算法,如KMP算法,...

    数据结构笔记

    这篇“数据结构笔记”可能包含了关于这个主题的深入理解和实践应用。结合给出的标签“源码”和“工具”,我们可以推测这份文档不仅讨论了理论知识,可能还涉及到了实际编程实现和相关工具的使用。 在数据结构的学习...

    程序员考试补课笔记(doc格式)

    在程序员考试中,指针相关的知识点无疑是非常重要的,尤其是在数组、字符串以及数据结构等方面的应用。 第二天的补课内容主要集中在数据类型的复习上,包括整型、字符型和浮点型等。作者通过数据类型表格对这些基础...

    程序员面试宝典笔记总结

    在程序员的求职过程中,面试和笔试是至关重要的环节,而一份详实的面试宝典笔记能为准备阶段提供极大的帮助。这份笔记涵盖了多个方面的知识点,旨在帮助程序员巩固基础,提升技能,从而在面试中表现出色。 一、编程...

    程序员考试补课笔记,程序员考试补课笔记

    - 数据结构:数组、链表、栈、队列、树(二叉树、平衡树)、图等,以及它们的操作和应用。 - 算法:排序(冒泡、选择、插入、快速、归并)、搜索(线性、二分、深度优先、广度优先)等基本算法的理解与实现。 2. ...

    黑马程序员Android学习笔记

    《黑马程序员Android学习笔记》是一份专为初学者设计的详尽教程,旨在帮助那些希望踏入安卓开发领域的人员快速掌握核心知识。这份笔记涵盖了从基础到进阶的多个主题,帮助学习者系统地理解Android应用开发的过程。 ...

Global site tag (gtag.js) - Google Analytics