张东1145105494简介：1、算法+数据结构=程序2、数据结构3、数据、数据元素（基本单位）、数据项（最小单位）4、数据结构在计算机中的映像是存储结构；数据元素在计算机中的映像是结点；数据项在计算机中的映像是数据域；逻辑结构在计算机中的映像是关系。

5、四种存储方式6、抽象数据类型1）按不同特性分类●原子类型●固定聚合类型●可变聚合类型2）基本操作●init 构造●destroy 销毁●get 返回●put 改变●isasc 升序●isdesc 降序●Max 最大●min 最小7、时间复杂度技巧1）对于循环程序（for），最大执行次数即为for的乘积。

简言之，程序有多少for出现，就是n的多少次方2）对于顺序结构，可用“求和取最大值“法则3）对于循环程序（while），一般结果是O(log M N)4）若是一般的赋值语句，时间复杂度必为O(1)5）对于选择结构的程序，一般时间复杂度为O(1)加：自加自减++ ——x=2；y=x++;y=++x;第二章线性表1、表长相当于元素个数2、线性表一般下标是1—n，故当n=0时，表示线性表为空表3、list 表示线性表elem 元素length 表示求长度（线性表）locate 定位（位置）insert 插入（元素之前）delete 删除void 空类型（写程序必写）顺序结构（链表相反）优势：随机存取劣势：在做插入或删除时需要移动大量的元素malloc 分配一个连续空间realloc 将已分配的空间进行重新分配顺序表插入时所需移动的元素次数期望值是n/2删除时所需移动的元素次数期望值是（n-1）/2删除：模板语句：q=&(L.elem[i-1]) 表示顺序表中插入元素或者删除元素的地址加：逻辑运算符：！非&&与（一假即假）||或（一真即真）逻辑值：真（1）假（0）比较运算符：< >= <= == !=若在if或者while后面的括号中出现逻辑表达式或者比较表达式，那么结果只能为真或假。

模板语句：if(i<1||i>L.length)return ERROR;表示在顺序表中，删除元素，若输入的删除地址不符合题意，则返回错误。

2、链式结构1）结点=数据域（元素）+指针域（指向后继结点）单链表2）一般在第一个元素之前，会创建一个头结点（头指针），用head表示。

指向第一个元素head->NULL 表示空表head->next=NULLclear 重置create 创建模板语句p=L->next 表示单链表中、头结点为L指向下一个结点N=（linklist）malloc(sizeof(LNode))表示在单链表中生成新结点技巧：做单链表的插入操作1）判断单链表的存在与否2）找到插入位置p=p->next j++3）生成新结点malloc4）赋值p->data=e(插入的元素)5）插入元素单链表删除操作1）2）同插入3）删除结点模板输出逆序顺序for(i=0;i<n;i++) 逆序for(i=n;i>0;i--)循环链表1、判断单链表的最后一个结点，表示方式是指针域为空；判断循环链表的最后结点，表示方式是指针域指向第一个结点2、不需要头结点3、循环链表为空，表达方式为L->next=L双向链表1、插入2、删除3、三部分：data next priorlinklist表示链式结构的线性表第三章栈和队列1、操作受限的线性表栈1、先进后出后进先出2、表头-栈底表尾-栈顶3、必须要有栈顶指针top系列：12345进栈出栈：1234554321 3452124351 412354、stack 栈push 进栈pop 出栈empty 判断是否为空5、当top=0/-1时，表示为空栈top==base(指向栈底指针)top-base=0stacksize=N 表示栈中元素个数模板语句1）S.top==S.base 设置栈顶栈底指针2）S.Stacksize=STACK_INIT_SIZE6、入栈（插入）：栈满（s.top-s.base>=s.stacksize）;s.top++;*s.top=e出栈（删除）：栈空（s.top==s.base）;s.top--;e=*s.top7、加：双栈共享一个空间栈：1,2空间：A[m]1）栈底在空间两端2）栈空：top1==0 top2==m-1 3）栈满：top1+1=top2中缀—后缀（前缀）1）将每一步运算加括号2）将每一括号内的运算符放在所在的括号后（前）3）将括号全部去除4）必须保证一个括号内只有一个运算符加：顺序结构、选择结构、循环结构选择结构：if…elseif(x>=0) y=1;else y=2;递归调用1、每次运行都是相似的操作2、每一项的值都由前一项的值决定3、必须要有一个基础值队列1、先进先出2、在队尾处进行插入、在队头处进行删除3、基本操作1）Queue2）clear 清空3）gethead 取队头元素4）Enqueue 入队Dequeue出队5）queuetraverse 遍历队列（查询队列中每一个元素）模板：Q.front->next==NULL 表示初始化队列Q.front==Q.rear 表示队列为空e=Q.front->next->data 表示队头元素若将队列放入数组base[]中：1、入队：base[rear]=e;rear++;2、出队1）e=base[front];2）front=front+1;注意：入队相当于尾指针自加1，出队相当于头指针自加1。

循环队列1、队空：Q.front==Q.rear2、入队：base[rear]=e;rear=(rear+1)%M;M:循环队列元素个数3、出队：e=base[front];front=(front+1)%M;4、队满front==(rear+1)%M队空：front==rear求循环队列的元素个数（长度）(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE第四章串1、空串空格串“”“”2、字符位置：所在字符串的位置子串位置：子串第一个字符在主串中的位置3、串相等1）长度相等2）元素相同●非平凡子串即非空非主串的子串●任意串为本身子串、空串为任意串子串●一个串的子串个数为n*(n+1)/2+1（空串）●一个串的真子串个数为n*(n+1)/2-1（本身）加：ASCII码0 ---48 0—9（48--57）A---65 A—Z（65--90）a---97 a—z （97--122）concat 串的连接compare 串的比较（ASCII）substring 求子串（表示从左边第N个字符开始截取M 个字符）index 求子串的位置（POS表示从左边第pos个字符开始检索）顺序：1、定长1）0号单元存放的是串的长度2、堆分配1)实际串长和数组长度相等加：数据类型1）整型intint a;a=1; a=123;2）浮点型floatfloat a; a=1.23）字符型charchar ch;ch=’i’; ch=’1’;模式匹配1）若主串长度n，模式串长度为m，则时间复杂度为O(m*n)2）模板语句：if(s[i]=t[j]) {++i; ++j}else {i=i-j+2; j=1}if(j>t[0]) return i-t[0];else return 0;S: abbcbacbabc 11T:abc 3男朋友：9KMP：3Q:模式串p=’abaabcac’,next函数值序列为？t=’abcaabbcabcaabdab’next 01112231123456712第五章数组广义表1、二维数组2、元素个数：行*列3、已知首地址a0和每个数组元素所占用的空间l，求任意数组元素的地址aiai=a0+(i)*l 下标从0开始ai=a0+(i-1)*l 下标从1开始4、二维数组1）以行为先序输入线性表aij=a00+(i*n+j)*L2）以列为先序输入线性表aij=a00+(j*m+i)*L注：二维数组为m*n,首元素为a00Q：数组A，每个元素长度3B,行i下标1—8，列j下标1—10。

首地址SA开始存储，数组按行（列）存放，元素a85的起始地址？解：按行：a85=a00+((8-1)*10+5-1))*3=SA+222按列：a85=a00+((5-1)*8+8-1)*3=SA+117Q:二维数组M的元素占用4B，行下标i(0--4),列下标j(0--5),M按行存储M35的起始地址和M按列存储？的起始地址相同。

M24 M34 M35 M44解：按行M35=a00+(3*6+5)*4=a00+92按列M34=a00+(4*5+3)*42）三维●以行为主序，则行下标变化最慢，纵下标变化最快●以纵为主序，则行下标变化最快，纵下标变化最慢列的变化速度介于行纵之间矩阵的压缩存储1、特殊矩阵1）对称矩阵aij=aji压缩方法：为每一对对称元分配一个存储空间存储：n(n+1)/2个存储空间aij：k=i(i-1)/2+j-1 （i>=j）k=j(j-1)/2+i-1 (i<j)2)三角矩阵压缩方法：同对称矩阵稀疏矩阵1、稀疏因子2、1）根据稀疏矩阵求出三元组表示形式（行、列、值。

非0）2）根据三元组求出转置矩阵的三元组性质稀疏矩阵1）求转置矩阵2）求转置矩阵的三元组3）求每一列非0元素的个数4）每一列第一个非0元素的位置=上一列第一个非0元素的位置+上一列非0元素的个数广义表1、A=() 空表，长度为0B=（e）原子e，长度1C=（a,(b,c,d)）原子a和表（b,c,d）长度2D=(A,B,C)E=(a，E) 递归表2、表头元素（head）：第一个元素表尾：其余的元素（tail）太关键了：表头可以是原子，也可以是子表；表尾必须是子表Q:D=(E,F)=((a,(b,c)),F)1）head（D）=E=(a,(b,c))2）tail( E)=((b,c))3）head(E)=a4）head(tail(E))=(b,c)head((b,c))=（b,c）tail((b,c))=()L=((a,c),(b,d))运算head(head(tail(L))))=bL=((),()) head(L)=（）tail(L)=（（））L长度是2L=((b,c),a)第六章树和二叉树1、树的概念1）根无前驱、有0个或多个后继2）子树有1个前驱、有0个或多个后继2、Q:树用广义表表示1）树→广义表●所有结点均是广义表内的元素●根结点总显示在第一位，其余后继结点将作为其下一级元素出现2）广义表→树●第一位是根结点●分成的部分作为下一层结点出现，以此类推3、术语结点、结点的度、树的度、叶子结点（度数为0）、路径（分支+结点）、双亲结点、孩子结点、祖先结点、兄弟结点、堂兄弟、子孙结点、结点层次（从1开始）、树的深度（叶子结点层次的最大值）、有序树、无序树二、二叉树1、特点：1）每个结点的分支为0、1、2 2）基本形态：5种2、性质1）在第i层上最多有2i-1个结点2）深度为k的二叉树，最多有2k-1个结点3）在任意二叉树中，n0=n2+1.特殊二叉树1、满二叉树：深度为k，必有2k-1个结点2、完全二叉树1）按顺序编号且与满二叉树一一对应2）只有最后一层叶子不满，且全部集中在左边Q：在一4层的满二叉树中，度数为2的结点个数为多少？1）满二叉树结点个数：2^4-1=152）最下面一层结点个数:2^（4-1）=8（叶子结点：度数为0）3）15-8=7或者8-1=7性质4：具有n个结点的完全二叉树的深度必为[log2n]＋1Q:二叉树400结点。