数据结构与算法笔记

1、线性表一、线性表的顺序存储结构1 .线性表有两种物理存储结构：顺序存储结构和链式存储结构2 .线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。3 .线性表顺序存储的结构代码：#defineMAXSIZE20typedefintElemTypetypedefstructElemTypedataMAXSIZE;intlength;/线性表当前长度SqList;通过结构对数组进行封装4 .总结：顺序存储结构封装需要三个属性：存储空间的起始位置，数组data,它的存储位置就是线性表存储空间的存储位置线性表的最大存储容量，数组的长度MAXSIZE线性表的当前长度：lengt

2、h二、地址计算方法1. 假设ElemType占用的是c个存储单元(字节)，则LOC(?%1)二LOC(?+cLOC()获得存储位置的函数2 .第i个数据元素？?存储位置可以由?推算出：LOC(?级=LOC(?)+(i-1)*c3 .存储时间性能为O(1)，我们通常称为随机存储结构。三、获得元素操作1.实现GetElem的具体操作，即将线性表L中的第i个位置元素值返回。就程序而言，只需把数组第i-1下标的值返回即可。# defineOK1# defineERROR0# defineTRUE1# defineFALSE0typedefintStatus;StatusGetElem(SqListL,

3、inti,ElemType*e)if(L.length=0|i<1|i>L.length)retureERROR;*e=L.datai-1;returnOK;四、插入操作1 .插入算法思路：如果插入位置不合理，抛出异常如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量从左后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置将要插入的元素填入位置i处线性表长度+12 .实现代码：StatusListInsert(SqList*L,inti,ElemTypee)intk;if(L->length=MAXSIZE)顺序线性表已经满了returnERROR;当i

4、不在范围内时if(i<1|i>L->length+1)returnERROR;)if(i<=L->length)(for(k=L->length-1;k>=i;k-)(L->datak+1=L->datak;)L->datai-1=e;L->length+;returnOK;)3 .插入操作时间复杂度最好情况：O(1)最坏情况：O(n)五、删除操作1 .删除操作思路：如果删除位置不合理，抛出异常取出删除元素从删除元素开始遍历到最后一个元素位置，分别将它们都向前移动一个位置线性表长度-12 .删除操作实现代码：StatusList

5、Delete(SqList*L,inti,ElemType*e)intk;if(L->length=0)(returnERROR;)if(i<1|i>L->length)(returnERROR;)*e=L->datai-1;if(i<L->length)(for(k=i;k<L->Length;k+)(L->datak-1=L->datak;)L->length-;returnOK;)3.删除操作时间复杂度：最好情况：O(1)最坏情况：O(n)六、线性表顺序存储结构的优缺点：1 .优点无须为表示表中元素之间的逻辑关系而增

6、加额外的存储空间可以快速地存取表中任意位置的元素2 .缺点插入和删除操作需要移动大量元素当线性表长度变化较大时，难以确定存储空间的容量七、线性表链式存储结构定义1 .线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可在内存中未被占用的任意位置2 .链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）3 .存储数据元素信息的域称为数据域4 .存储直接后继位置的域称为指针域5 .指针域中存储的信息称为指针或链6 .数据域和指针域组成数据元素称为存储映像，称为结点（Node）7 .链表的每个结点中只包含一个指针域，所以称为单链表八、头指针

7、与头结点的异同1 .头指针链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空（NULL）头指针是指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针头指针具有标识作用，所以常用头指针冠以链表的名字无论链表是否为空，头指针均不为空头指针是链表的必要元素2 .头结点头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义头结点不是链表的必要元素九、单链表存储结构1.用结构指针来描述单链表：typedefstructNodeElemTypedata;/数据域structNode*next;指针域Node;typedefstructNode*LinkLis

8、t;/LinkList相当于是指针十、单链表的读取1 .获得链表第i个数据的算法思路：j+1声明一个结点p指向链表第一个结点，初始化j从1开始当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点,若到链表末尾p为空，则说明第i个元素不存在若查找成功，返回结点p的数据2 .代码实现：StatusGetElem(LinkListL,inti,ElemType*e)(intj;LinkListp;p=L->next;指向第一个结点j=1;while(p&&j<i)(p=p->next;+j;if(!pIIj>i)(returnERROR;*e=p

9、->data;returnOK;)十一、单链表的插入1 .单链表第i个数据插入结点的算法思路：声明一个结点p指向链表头结点，初始化j从1开始当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1若到链表末尾p为空，则说明第i个元素不存在否则查找成功，在系统中生成一个空结点s将数据元素e赋值给s->data将s结点插入链表中：s->next=p->next;p->next=s;返回成功2 .代码实现：StatusListInsert(LinkListL,inti,ElemTypee)LinkListp,s;intj;P=L->next;

10、while(p&&j<i)寻找第i个结点p=p->next;+j;)if(!p|j>i)returnERROR;)s=(LinkList)malloc(sizeof(Node);s->data=e;s->next=p->next;p->next=s;returnOK;)十二、单链表的删除1.2. StatusListDelete(LinkListL,inti,ElemTypee)(intj;LinkListp,q;j=1;while(p&&j<i)(p=p->next;+j;if(!p|j>i)(ret

11、urnERROR;e=p->data;q=p->next;p->next=q->next;returnOK;十三、单链表的整表创建1 .单链表整表创建思路：声明一结点p和计数器变量i初始化一空链表L让L的头结点的指针指向NULL,即建立一个带头结点的单链表循环实现后继结点的赋值和插入2 .头插法voidCreateListHead(LinkList*L,intn)(LinkListp;inti;srand(time(0);初始化随机数种子*L=(LinkList)malloc(sizeof(Node);(*L)->next=null;for(i=0;i<n;

12、i+)(p=(LinkList)malloc(sizeof(Node);p->data=rand()%100+1;p->next=(*L)->next;(*L)->next=p;3 .尾插法voidCreateListTail(LinkList*L,intn)(LinkListr,p;inti;*L=(LinkList)malloc(sizeof(Node);r=*L;for(i=0;i<n;i+)(p=(LinkList)malloc(sizeof(Node);p->data=rand()%100+1;r->next=p;)r->next=NU

13、LL;)十四、单链表的正表删除1 .单链表正表删除的算法思路：申明结点p和q将第一个结点赋值给p,下一结点赋值给q循环执行释放p和将q赋值给p的操作2 .代码实现：StatusClearList(LinkList*L)(LinkListp,q;p=(*L)->next;while(p)(q=p->next;free(p)p=q;)(*L)->next=NULL;returnOK;)十五、单链表结构与顺序存储结构优缺点1 .存储分配方式顺序存储结构用一段连续的存储单元依次存储线性表的数据元素单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素2 .时间性能查找1)顺序存

14、储结构O(1)2) 单链表O(n)插入和删除1)顺序存储结构需要平均移动表长一半的元素，时间为O(n)2)单链表在计算出某位置的指针后，插入和删除时间为0(1)空间性能1)顺续存储结构需要预分配存储空间，分大了，容易造成浪费，分小了，容易发生溢出2)单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制3 .结论：若线性表需要频繁查找，很少插入和删除操作，宜采用顺序存储结构，否则，采用单链表结构当线性表中的元素个数变化较大或根本不知道有多大时，最好采用单链表存储结构十六、静态链表1 .线性表的静态链表存储结构：#defineMAXSIZE1000typedefstruct(ElemTy

15、pedata;/数据intcur;游标Component,StaticLinkListMAXSIZE;2 .对静态表进行初始化相当于初始化数组：StatusInitList(StaticLinkListspace)(inti;for(i=0;i<MAXSIZE-1;i+)spacei.cur=i+1;spaceMAXSIZE-1.cur=0;returnOK;)十七、静态链表的插入操作1 .首先获得空闲分量的下标：intMalloc_SLL(StaticLinkListspace)inti=space0.cur;if(space0.cur)space0.cur=spacei.cur;re

16、turni;)2 .在静态链表L中第i个元素之前插入新的数据元素eStatusListInsert(StaticLinkListL,intI,ElemTypee)intj,k,l;k=MAXSIZE-1;/数组最后一个元素if(i<1|i>ListLength(L)+1)returnERROR;)j=Malloc_SLL(L);if(j)Lj.data=e;for(l=1;l<=i-1;l+)k=Lk.cur;Lj.cur=Lk.cur;Lk.cur=j;returnOK;)returnERROR;)十八、静态链表的删除操作1 .删除在L中的第i个数据元素StatusList

17、Delete(StatusLinkListL,inti)(intj,k;if(i<1|i>ListLength(L)(returnERROR;)k=MAXSIZE-1;for(j=1;j<=i-1;j+)(k=Lk.cur;获取第i-1元素的下标)j=L(k).cur;/获取第i-1元素的游标，即第i元素下标L(k).cur=L(j).cur;Free_SLL(L,j);returnOK;将下标为k的空闲结点回收到备用链表voidFree_SLL(StaticLinkListspace,intk)(spacek.cur=space0.cur;space0.cur=k;/返回L

18、中数据元素个数intListLength(StaticLinkListL)(intj=0;inti=LMAXSIZE-1.cur;while(i)(i=Li.cur;j+;returnj;十九、静态链表优缺点：1 .优点在插入和删除操作时，只需要修改游标，不需要移动元素，改进了顺序存储结构中的插入和删除需要移动大量元素的缺点2 .缺点没有解决连续存储分配(数组)带来的表长难以确定的问题失去了顺序存储结构随机存取的特性3 .总的来说，静态链表其实是为了给没有指针的编程语言设计的一种实现单链表功能的方二十、获取未知长度单链表的中间结点1 .利用快慢指针StatusGetMidNode(LinkLi

19、stL,ElemType*e)(LinkListsearch,mid;mid=search=L;while(search->next!=NULL)(if(search->next->next!=NULL)(search=search->next->next;mid=mid->next;else(search=search->next;*e=mid->data;returnOK;2. 一个程序，实现随机生成20个元素的链表(尾插法和头插法)，并查找中间结点的值并显示。二十一、循环链表1 .将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单

20、链表形成一个环，这种头尾相连的单链表成为单循环链表，简称循环链表。2 .特点：有了头节点，可以用O(1)的时间访问第一个结点，但要访问最后一个结点，必须遍历全部，复杂度为O(n),bm)连接成一个线性表3. 题目：实现将两线性表(a1,a2,an)和(b1,b2,(a1,a2,an,b1,b2,bm)的运算。思路：假设A、B分别为链表a和链表b的尾指针声明一个结点P,初始化为链表a的头节点将B改为指向链表a的第一个结点将A改为指向链表b的第一个结点删除链表b的头结点代码实现：LinkListconnect(LinkListA,LinkListB)(LinkListp=A->next;A-

21、>next=B->next->next;free(B->next);B->next=p;return(B->next);二十二、判断单链表中是否有环1 .有环：链表的尾结点指向了链表中的某个结点2 .判断单链表是否有环:第二H一讲双向链表一、双向链表1 .双向链表结点结构typedefstructDualNode(ElemTypedata;structDualNode*prior;前驱结点structDualNode*next;后继结点DualNode,*DuLinkList;2 .双向链表的插入操作代码实现：s->next=p;s->prior

22、=p->prior;p->prior->next=s;p->prior=s;3 .双向链表的删除操作代码实现：p->prior->next=p->next;p->next->prior=p->prior;free(p);prior指针4 .总结双向链表相对于单链表来说，多了一个双向链表可以有效提高算法的时间性能，说白了就是用空间来换取时间第二十三讲栈和队列一、栈(stack)的定义1 .栈是一个后进先出的线性表，它要求只在表尾进行删除和插入操作。2 .总结：栈的元素必“须后进先出”栈的操作只能在这个线性表的表尾进行表尾栈顶(top)表

23、头栈底(bottom)二、栈的插入和删除操作1 .栈的插入操作(push),叫做进栈，也称为压栈，入栈。2 .栈的删除操作(pop),叫做出栈，也称为弹栈。三、栈的顺序存储结构1 .typedefstruct(ElemType*base;指向栈底的指针变量ElemType*top;指向栈顶的指针变量intstackSize;/指示栈的当前可使用的最大容量sqStack;2 .创建一个栈#defineSTACK_INIT_SIZE100initStack(sqStack*s)(s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType

24、);if(!s->base)exit(0);s->top=s->base;s->stackSize=STACK_INIT_SIZE;)3 .入栈操作入栈操作又叫压栈操作，就是向栈存放数据入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1,直到栈满为止实现代码：Push(sqStack*s,ElemTypee)if(s->top-s->base>=s->stackSize)s->base=(ElemType*)realloc(s->base,(s->stackSize+10)*sizeof(ElemType);s-&

25、gt;top=s->base+s->stackSize;)*(s->top)=e;s->top+;)4 .出栈操作出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作每当从栈内弹出一个数据，栈的当前容量就-1代码实现：Pop(sqStack*s,ElemType*e)if(s->top=s->base)return;*e=*-(s->top);)5 .清空一个栈所谓清空一个栈，就是将栈中的元素全部作废，但栈本身物理空间并不发生改变因此只需将s->top的内容赋值为s->base即可，这样s->base等于s->top,就表明这个栈

26、是空的了代码实现：ClearStack(sqStack*s)(s->top=s->base;)6 .销毁一个栈销毁一个栈与清空一个栈不同销毁一个栈是要释放该栈所占据的物理内存空间DestroyStack(sqStack*s)(inti,len;len=s->stackSize;for(i=0;I<len;i+)(free(s->base);s->base+;)s->base=s->top=NULL;s->stackSize=0;)7 .计算栈的当前容量计算栈的当前容量也是计算栈中元素的个数，因此只需返回s->top-s->bas

27、e即可栈的最大容量是指该栈占据内存空间的大小代码实现：intStackLen(sqStacks)return(s.top-s.base);8 .利用栈的特点，将二进制转为十进制四、栈的链式存储结构(26讲)栈顶指针和单1 .栈只是在栈顶做插入和删除操作，因此，通常将栈顶放在单链表的头部,链表的头指针合二为一2 .栈的链式存储结构typedefstructStackNode(ElemTypedata;存放栈的数据structStackNode*next;StackNode,*LinkStackPtr;teypedefstructLinkStack(LinkStackPtrtop;/top指针in

28、tcount;栈元素计算器3 .入栈StatusPush(LinkStack*s,ElemTypee)(LinkStackPtrp=(LinkStackPtr)malloc(sizeof(StackNode);p->data=e;p->next=s->top;s->top=p;s->count+;returnOK;4 .出栈StatusPop(LinkStack*s,ElemType*e)(LinkStackPtrp;if(StackEmpty(*s)returnERROR;*e=s->top->data;p=s->top;s->top=s

29、->top->next;free(p);s->count-;returnOK;)5 .逆波兰表达式（RPN）不需要括号的后缀表达式。（操作符在后）队列(30讲)一、队列的定义1 .队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。2 .队列是一种先进先出的线性表二、队列的链式存储结构1. typedefstructQnode(ElemTypedata;structQnode*next;Qnode,*QueuePtr;typedefstruct(QueuePrtfront,rear;队头、尾指针LinkQueue;2. 队头指针指向链队列的头结点，而队尾指针指向终

30、端结点3. 空队列时，front和rear都指向头节点三、创建一个队列在内存中创建一个头节点将队列的头指针和尾指针都指向这个生成的头节点voidinitQueue(LinkQueue*q)(q->front=q->rear=(QueuePtr)malloc(sizeof(Qnode);if(!q->front)exit(0);q->front->next=NULL;四、入队列操作1.InsertQueue(LinkQueue*q,ElemTypee)(QueuePtrp;p=(QueuePtr)malloc(sizeof(Qnode);if(p=NULL)exit

31、(0);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;五、出队列操作DeleteQueue(LinkQueue*q,ElemType*e)(QueuePtrp;if(q->front=q->rear)return;p=q->front->next;*e=p->data;q->front->next=p->next;if(q->rear=p)q->rear=q->front;free(p);六、销毁一个队列1.DestroyQueue(LinkQue

32、ue*q)while(q->front)q->rear=q->front->next;free(q->front);q->front=q->rear;循环队列（31讲）一、循环队列1 .#defineMAXSIZE100typedefstruct(ElemType*base;intfront;intrear;cycleQueue;2 .初始化一个循环队列InitQueue(cycleQueue*q)(q->base=(ElemType*)malloc(MAXSIZ*sizeof(ElemType);if(!q->base)exit(0);q

33、->front=q->rear=NULL;3 .入列操作InsertQueue(cycleQueue*q,ElemTypee)(if(q->rear+1)%MAXSIZE=q->front)return;/队列为满q->baseq->rear=e;q->rear=(q->rear+1)%MAXSIZE;4 .出队列操作DeleteQueue(cycleQueue*q,ElemType*e)if(q->front=q->rear)return;队列为空*e=q->baseq->front;q->front=(q->

34、;front+1)%MAXSIZE;)递归（32讲）一、斐波那契数列的递归实现1.递归：就是函数调用自己。字符串一、字符串的存储结构1 .字符串的存储结构与线性表相同，也分为顺序存储结构和链式存储结构。2 .字符串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的3 .按照预定的大小，为每个定义的字符串变量分配一个固定长度的存储区，一般用定长数组来定义。4 .BF算法：模式匹配算法核心思想：有两个字符串S和T,长度为N和M.首先S1和T1比较，若相等，则再比较S2和T2,一直到TM为止；若S1和T1不相等，则T向右移动一个字符的位置，再依次进行比较。5 .S是主串，T是子串，这种字

35、串的定位操作通常称作串的模式匹配。树(41讲)一、树的定义1 .树是n个结点的有限集。当n=0时成为空树，在任意一棵非空树中：有且仅有一个特定的称为根(Root)的结点当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、Tm,其中每一个集合本身又是一棵树，并且称为根的子树。n>0时，根结点是唯一的，坚决不可能存在多个根结点。m>0时，子树的个数是没有限制的，但它们互相是一定不会相交的。二、结点分类：2 .结点：每一个圈圈我们就称为树的一个结点3 .度：结点拥有的子树数称为结点的度4 .树的度取树内各结点的度的最大值。5 .度为0的结点称为叶结点或终端结点

36、6 .度不为0的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点三、结点的层次1 .根为第一层，根的孩子为第二层2 .树中结点的最大层次称为树的深度或高度。二叉树（44讲）一、二叉树的定义1.二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二、二叉树的特点1.每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。三、二叉树的五种基本形态1 .空二叉树2 .只有一个根结点3 .根结点只有左子树4 .根结点只有右子树5 .根结点既有左子树又有右子树四、特殊二叉树1 .斜树2 .满二叉树所有分支结点都存在左子树和右子树所有叶子都在同一层上，3 .满二叉树特点叶子只能出现在最下一层非叶子结点的度一定是2在同样深度的二叉树中，满二叉树的结点个数一定最多，同时叶子也是最多4 .完全二叉树特点：叶子结点只能出现在最下两层最下层的叶子一定集中在左部连续位置倒数第二层，若有叶子结点，一定都在右部连续位置如果结点度为1,则该结点只有左孩子同样结点树的二叉树，完全二叉树的深度最小5 .满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树五、二叉树的性质1 .在二叉机勺第i层上至多有