数据结构C语言版讲义

第一章绪论

第一节什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。信息模型：信息处理领域中的数学模型。数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。忽略数据的具体含义，研究信息模型的结构特性、处理方法。第二节概念、术语一、有关数据结构的概念数据：对客观事物的符号表示。例：生活中还有什么信息没有被数字化？身份证，汽车牌号，电话号码，条形代码 数据元素：数据的基本单位。相当于〃记录一个数据元素由若干个数据项组成，相当于“域数据对象：性质相同的数据元素的集合。数据结构：相互之间存在特定关系的数据集合。四种结构形式：集合、线性、树形、图（网）状形式定义：（D,S,P）D:数据元素的集合（数据对象）S:D上关系的有限集P:D上的基本操作集逻辑结构：关系S描述的是数据元素之间的逻辑关系。存储结构：数据结构在计算机中的存储形式。顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系：逻辑结构：描述、理解问题，面向问题。存储结构：便于机器运算，面向机器。程序设计中的基本问题：逻楫结构如何转换为存储结构？二、有关数据类型的概念数据类型：值的集合和定义在该值集上的一组操作的总称。包括：原子类型、结构类型。抽象数据类型(ADT):一个数学模型及该模型上的一组操作。核心：是逻辑特性，而非具体表示、实现。课程任务：学习ADT、实践ADT。如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……实践指导：为了代码的复用性，采用模块结构。如:C中的头文件、C++中的类第三节ADT的表示与实现本教材中，算法书写习惯的约定。数据元素类型ElemType:int,float,char,chart] 引用参数&算法：voidadd(inta,intb,int&c) {c=a+b;}程序：voidadd(inta,intb,int*p_c){*p_c=a+b;}第四节算法的描述及分析一、有关算法的概念算法：特定问题求解步骤的一种描述。1)有穷性2)确定性3)可行性二、算法设计的要求好算法：1)正确性2)可读性3)健壮性4)高效，低存储三、时间复杂度事箭估算：问题的规模，语言的效率，机器的速度时间复杂度：在指定的规模下，基本操作重复执行的次数。n:问题的规模。f(n):基本操作执行的次数T(n)=0(f(n))渐进时间复杂度(时间复杂度)例：求两个方阵的乘积C=A*BvoidMatrixMul(floata[][n],floatb[][n],floatc[][n]){inti,j,k;for(i=0;i<n;i++) // n+1for(j=0;j<n;j++) // n(n+l){c[i][j]=0; // n*nfor(k=0;k<n;k++) // n*n*(n+1)c[i][j]+=a[i][k]*b[k][j]; // n*n*n)J时间复杂度：T(〃)=2〃3+3/+2〃+l=。(〃3)一般情况下，对循环语句只需考虑循环体中语句的执行次数，可以忽略循环体中步长加1、终值判断、控制转移等成分。最好/最差/平均时间复杂度的示例：例：在数组A[n]中查找值为k的元素。for(i=0;i<n-l;i++)if(A[i]==k)returni;四、常见时间复杂度按数量级递增排序：0(1)<O(log2n)<0(〃)<O(nlog2n)<O(n2)<0(/)<0(2n)<0(及!)<0(nn)将指数时间算法改进为多项式时间算法：伟大的成就。五、空间复杂度实现算法所需的辅助存储空间的大小。S(n)=O(f(n))按最坏情况分析。六、算法举例例1:以下程序在数组中找出最大值和最小值voidMaxMin(intA[],intn){intmax,min,i;max=min=A[0];for(i=l;i<n;i++)if(A[i]>max)max=A[i];elseif(A[iJ<min)min=A[i];

printf(，，max=%d,min=%d\n”,max,min);}若数组为递减排列，比较次数是多少？if(A[i]>max):nT次if(A[i]<min):nT次若数组为递增排列，比较次数是多少？if(A[i]>max):nT次if(A[i]<min):0次例2:计算f(x)=a0+aix+a2x2+....+anxn解法一：先将x的赛存于power口，再分别乘以相应系数。floateval(floatcoef[],intn,floatx){floatpower[MAX],f;inti;for(power[0]=l,i=l;i〈=n;i++)power[i]=x*power[i-l];for(f=0,i=0;i〈=n;i++)f+=coef[i]*power[i];return(f);}解法二：f(x)=ao+(ai+(a2+ +(an-i+anx)x)x)xf(x)=a0+(ai+(a2+(a3+(a4+a5x)x)x)x)xfloateval(floatcoef[],intn,floatx){inti;floatf;for(f=coef[n],i=n-l;i>=0;i一)f=f*x+coef[i];return(f);}五、思考题1、问："s=s+i*j;"的执行次数？时间复杂度？for(i=l;i<=n;i++)if(5*i<=n)for(j=5*i;j<=n;j++)s=s+i*j;2、问:的执行次数？时间复杂度？for(i=0;i<n;i++)for(j=0;j<=i;j++)a[i][j]=x;第二章线性表线性结构：在数据元素的非空集中，①存在唯一的一个首元素，②存在唯一的一个末元素，③除首元素外每个元素均只有一个直接前驱，④除末元素外每个元素均只有一个直接后继。第一节逻辑结构形式定义：Linear_list=(D,S,P)D={ai|ai€ElemSet, i=0,1,2,…，nT}S={<aii,a；>|a1,ai£D,i=l,2,…，nT}<ap,a〉为序偶，表示前后关系基本操作P：①插入、删除、修改，存取、遍历、查找。voidListAppend(ListL,Eleme);voidListDelete(ListL,inti);intSetElem(ListL,inti,Eleme);intGetElem(ListL,inti,Elem&e);intListLength(ListL);voidListPrint(ListL);intLocateElem(ListL,Eleme);②合并、分解、排序基本操作的用途：集合的并、交、差运算有序线性表的合并、多项式的运算

例：利用线性表LA和LB分别表示集合A和B,<A=AUBOvoidunion(List&La,ListLb){intLa_len,Lb_len;//计算表长//取//计算表长//取Lb的第i个元素//在La中查找e//在La中插入eLblen=ListLength(Lb);for(i=l;i<=Lblen;i++){GetElem(Lb,i,e);if(!LocateElem(La,e))ListAppend(La,e);第二节顺序存储结构一、概念逻辑结构中的“前后关系”：物理结构中的“相邻关系”loc(aj=loc(a0)+i*sizeof(单个数据元素)静态顺序存储结构：一维数组。注意：第i个元素的下标是i-1动态顺序存储结构：ttdefineLIST_INIT_SIZE100ttdefineLIST_INCREMENT10 //存储空间的分配增量typedefstruct{ElemType*elem;intlength; 〃当前表长intlistsize; 〃当前已分配的存储空间}SqList;二、基本操作：1、在ai之前插入x:3o3i・・・Hi-i3.i・・••••Hn-l如何移动元素？ai•••a1XHi・・・•••a»nTvoidSqListlnsert(SqListA,inti,ElemTypee)

{for(j=A.length-1;j>=i;j)A.elem[j+l]=A.elem[j];A.elem[i]=e;A.length++;2、删除ajdoai•••a1aiai+i・・・•••an-i如何移动元素？HoHi・・•Hi-i@i+i・♦・・♦•Hn-lvoidSqListDelete(SqListA,inti){for(j=i+l;j<A.length;j++)A.elem[j-l]=A.elem[j];A.length―;}三、效率分析插入、删除时，大量时间用在移动元素上。设插入位置为等概率事件，时间复杂度？例1:增序顺序表的合并，设其中无相同元素StatusSqListMerge(SqListLa,SqListLb,SqList&Lc){ElemType*pa,*pb,*pc,*palast,*pblast;Lc.listsize=Lc.length=La.length+Lb.length;Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)returnERROR;pa=La.elem;pb=Lb.elem;pc=Lc.elem;palast=La.elem+La.length-1;pblast=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last)if(*pa〈=*pb){else{while(pa<=pa_last)while(pb<=pb_last)returnOK;*pc=*pa;pc++;pa++if(*pa〈=*pb){else{while(pa<=pa_last)while(pb<=pb_last)returnOK;*pc=*pb;pc++;pb++;}{*pc=*pa;pc++;pa++;}{*pc=*pb;pc++;pb++;}时间复杂度？现实意义：数据库与日志文件的合并。例2:无序顺序表的并集AUB例3:无序顺序表的交集AAB例4:无序顺序表的逆序例5:剔除顺序表中的某种元素剔除顺序表中的所有0元素，要求较高效率。120340005670089=>123456789voiddel(intA口，intn){inti,k;//k是0元素的个数for(k=0,i=0;i<n;i++)if(A[i]==0){k++;n—;}elseA[i-k]=A[i];I第三节线性动态链表一、概念每个元素除存储自身信息外，还需存储其后继元素的信息。结点、指针域、指针(链)链表、线性链表、头指针二、动态链表结构typedefstructLNode{ElemTypedata;structLNode*next;}LNODE;申请结点空间：LNODE*p;p=(LNODE*)malloc(sizeof(LNODE));释放结点空间：free(p);1、插入结点在*p之后插入新结点*q:q->next=p->next;p->next=q;在*p之前插入？时间复杂度？各种插入方法：①首插：插入在首结点前；②尾插：入在尾结点后。③有序插：保持结点的顺序，插在表中间；编程细节：①首插：修改头指针②尾插：链表为空时，修改头指针。③有序插：链表为空时，修改头指针。链表不空时，可能修改头指针//首插LNODE*LinkList_InsertBeforeHead(LNODE*head,LNODE*newp){newp->next=head;return(newp);}//遍历打印voidLinkListPrint(LNODE*head){LNODE*p;for(p=head;p;p=p->next)printfp->data);I//尾插LNODE*LinkList_InsertAfterTail(LNODE*head,LNODE*newp){LNODE*p;if(head==NULL){newp->next=NULL;return(newp);}for(p=head->next;p->next;p=p->next);newp->next=NULL;p->next=p;return(head);)简化程序细节的方法：特殊头结点//首插(有特殊头结点)voidLinkListlnsertBeforeHead(LNODE*head,LNODE*newp){newp->next=head->next;head->next=newp;//尾插(有特殊头结点)voidLinkListlnsertAfterTail(LNODE*head,LNODE*newp){LNODE*p;for(p=head;p->next;p=p->next);newp->next=NULL;p-〉next=p;}2、删除结点删除*p的后继结点：q=p->next;p->next=q->next;free(q);删除*p?时间复杂度？各种删除方法：①首删除：②尾删除：思考③查找删除：思考//首删除(有特殊头结点)voidLinkListDeleteHead(LNODE*head){LNODE*p;if(head->next==NULL)return;p=head->next;head->next=p-〉next;free(q);}三、单个链表的例程(设以下链表有特殊头结点)例1、按序号查找：取链表第i个结点的数据元素。i€[l.n]//注意计数次数的边界条件StatusLinkListGetElemBySID(LNODE*head,inti,ElemType&e){LNODE*p;intj;for(p=head->next,j=l;p&&j<i;j++) p=p->next;if(p==NULL)returnERROR;e=p->data;returnOK;}例2、按值查找：取链表中值为e的结点的地址。LNODE*LinkListGetElemByValue(LNODE*head,ElemTypee){LNODE*p;for(p=head->next;p;p=p->next)if(p->data~e)break;return(p);}例3、释放链表中所有结点。voidLinkListDeleteAll(LNODE*head){LNODE*p;while(head){p=head->next;free(head);head=p;}}例4、复制线性链表的结点//适合有/无特殊头结点的链表LNODE*LinkList_Copy(LNODE*L){LNODE*head=NULL,*p,*newp,*tail;if(!L)return(NULL);for(p=L;p;p=p->next){newp=(LNODE*)malloc(sizeof(LNODE));if(head==NULL)head=tai1=newp;else{tail->next=newp;tail=newp;}newp->data=p->data;}tail->next=NULL;return(head);}例5、线性链表的逆序LNODE*LinkListReverse(LNODE*head){LNODE*newhead,*p;newhead=(LNODE*)malloc(sizeof(LNODE));newhead->next=NULL;while(head->next!=NULL){p=head->next; head->next=p->next;〃卸下p->next=newhead->next;newhead->next=p;〃安装}free(Head);return(newhead);)例6、利用线性表的基本运算，实现清除L中多余的重复节点。352555356=>3526voidLinkListPurge(LNODE*head){LNODE*p,*q,*prev_q;for(p=head->next;p;p=p->next)for(prev_q=p,q=p->next;q;)if(p->data==q->data){prev_q=q->next;free(q);q=prev_q->next;}else{prev_q=q;q=q->next;}四、多个链表之间的例程(设以下链表有特殊头结点)例1、增序线性链表的合并，设其中无相同元素。〃破坏La和Lb,用La和Lb的结点组合LcLNODE*LinkList_Merge(LNODE*La,LNODE*Lb){LNode*pa,*pb,*pctai1,*Lc;Lc=pctail=La;//Lc的头结点是原La的头结点pa=La->next;pb=Lb->next;free(Lb);while(pa!=NULL&&pb!=NULL)if(pa->data<=pb->data){pctail->next=pa;pctail=pa;pa=pa->next;}else{pctail->next=pb;pctail=pb;pb=pb->next;}if(pa!=NULL)pctail->next=pa;elsepctail->next=pb;return(Lc);}例2、无序线性链表的交集AflB〃不破坏La和Lb,〃新链表Lc的形成方法：向尾结点后添加结点LNODE*LinkList_Intersection(LNODE*La,LNODE*Lb){LNode*pa,*pb,*Lc,*newp,*pctail;Lc=pctail=(LNODE*)malloc(sizeof(LNODE));for(pa=La->next;pa;pa=pa->next){for(pb=Lb->next;pb;pb=pb->next)if(pb->data==pa->data)break;if(pb){newp=(LNODE*)malloc(sizeof(LNODE));newp->data=pa->data;pctail->next=newp;pctail=newp;pctail->next=NULL;return(Lc);作业与上机：(选一)1、A-B2、AUB3、AAB4、(A-B)U(B-A)第五节循环链表尾结点的指针域指向首结点。实际应用：手机菜单遍历的终止条件？例：La、Lb链表的合并//将Lb链表中的数据结点接在La链表末尾voidConnect(LNODE*La,LNODE*Lb){LNODE*pa,*pb;for(pa=La->next;pa->next!=La;pa=pa->next);for(pb=Lb->next;pb->next!=Lb;pb=pb->next);pa->next=Lb->next;pb->next=La;free(Lb);第六节双向链表typedefstructDuLNode{ElemTypedata;structDuLNode*lLink,*rLink;}DuLinkNode;

1、*p-^lLink在*1、*p-^lLink在*p之后插入结点*qq->rLink=p->rLink;p->rLink=q;在*p之前插入结点*qq->lLink=p;q->rLink->lLink=qILink2、删除*p(p->lLink)->rLink=p->rLink;(p->rLink)->lLink=p->lLink;free(p);删除*p的前驱结点？删除*p的后继结点？第七节实例：一元多项式的存储、运算

一、多项式的存储结构f(x)-anxn+ +a2X2 +aiX+a。1、顺序结构intcoef[MAX];f(x)=14x10l+5x50-32、链式结构typedefstructpolynode{intcoef;intindex;structnode*next;}PolyNode;3、示例输入数据(指数无序)输出多项式(指数降序)多项式1多项式2count=2coef=5,index=3coef=l,index=5count=3coef=2,index=7coef=7,index=2count=4coef=2,index=7coef=l,index=5

coef=6,index=3coef=ll,index=3coef=7,index=24、结构细节设计带特殊头结点的单向链表；结点按指数降序排列；特殊头结点的index域：多项式的项数。5、程序框架设计main(){PolyNode*L1,*L2;PolyNodePrint(LI);PolyNodePrint(L2);PolyNodePrint(LI);PolyNodePrint(L2);//L1+L2=>L1L2=PolyNode_Create();PolyNode_Add(Ll,L2);PolyNodePrint(LI);voidPolyNodePrint(PolyNode*head){PolyNode*p;printf("count=%d\n”,head->index);〃打印项数for(p=head->next;p;p=p->next)printf(，zcoef=%d,index=%d\n”,p->coef,p->index);二、以插入为基础的算法1、将*newp插入到降序链表*head中voidPolyNodeinsert(PolyNode*head,PolyNode*newp);{PolyNode*p,*pre;//定位for(pre=head,p=pre->next;p;pre=p,p=p->next)if(p->index<=newp->index)break;if(p==NULL||p->index<newp->index)〃在*pre之后插入{newp->next=p;pre->next=newp;head->index++;}else{p->coef+=newp->coef;〃合并同类项free(newp);if(p->coef==0)〃删除{pre->next=p->next;free(p);head->index一;})I2、利用PolyNode_Insert函数，建立有序链表PolyNode*PolyNode_Create(){inti,count;PolyNode*head,*newp;scanf("%d\n”,&count);head=(PolyNode*)malloc(sizeof(PolyNode));head->coef=0;head->next=NULL;for(i=0;i<count;i++){newp=(PolyNode*)malloc(sizeof(PolyNode));scanf(线d,%d\n”,&newp->coef,&newp->index);PolyNodeinsert(head,newp);}return(head);I3、利用PolyNode_Insert函数，实现多项式加法//L1+L2=>L1不破坏L2链表voidPolyNodeAdd(PolyNode礼1,PolyNode*L2){NODE*p,*newp;for(p=L2-〉next;p;p=p->next){newp=(PolyNode*)malloc(sizeof(PolyNode));newp->coef=p->coef;newp->index=p->index;PolyNodeinsert(LI,newp);)时间复杂度？设LI长度为M,L2长度为N,则0(M*N)。

三、两表合并算法voidPolyNode_Add(PolyNode*L1,PolyNode*L2){PolyNode*pl,*plpre; //*plpre是*pl的直接前驱PolyNode*p2,*p2next;//*p2next是*p2的直接后继plpre=Ll;pl=Ll->next;//pl指向LI中第一个数据结点p2=L2->next;free(L2);//p2指向L2中第一个数据结点while(pl&&p2){switch(compare(pl->index,p2->index)){case' : //*pl指数大于*p2指数plpre=pl;pl=pl->next;break;case'<'： //*pl指数小于*p2指数p2next=p2->next;//小心①：准备在*plpre后插入*p2p2->next=pl;plpre->next=p2;plpre=p2; //小心②：保持plpre和pl的关系p2=p2next; 〃p2指向下一个待合并的结点break;case' : //*pl和*p2是同类项pl->coef+=p2->coef;//系数合并p2next=p2->next;free(p2); //删除*p2p2=p2next; 〃p2指向下一个待合并的结点if(pa->coef==0) //合并后系数为0{plpre->next=pl->next;free(pl);//删除*pl

pl=plpre->next;//保持plpre和pl的关系}}//switch} //whileif(p2)plpre->next=p2;//链上p2的剩余结点时间复杂度？设L1长度为M,L2长度为N,则O(M+N)。作业与上机：(选一)一、多项式加法、减法二、多项式乘法:a*b=>c(建立新表c)三、任意整数的加法、乘法第三章栈与队列栈与队列：限定操作的线性表。第一节栈一、逻辑结构1、栈的定义限定只能在表的一端进行插入、删除的线性表。栈顶top,栈底bottom。后进先出LIFO表(LastInFirstOut)实例：“进制数转换”、“表达式求值”、“函数调用关系”、“括号匹配问题”、“汉诺塔问题”、“迷宫问题”……2、基本操作进栈Push/出栈Pop取栈顶元素GetTop判别栈空StackEmpty/栈满StackFull3、栈的应用背景许多问题的求解分为若干步骤，而当前步骤的解答，是建立在后继步骤的解答基础上的。=»问题分解的步骤和求解的步骤次序恰好相反。二、顺序存储结构动态顺序存储结构：存储空间随栈的大小而变化。#defineSTACK_INIT_SIZE100〃初始化时分配的空间typedefstruct 〃定义栈类型{ElemType*base,*top; 〃栈底、栈顶指针intstacksize; 〃栈的存储空间大小}SqStack;SqStackS; 〃定义一个栈结构1、初始化栈StatusSqStacklnit(SqStack&S){S.base=malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)return(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);栈空：S.top==S.base栈满：S.top==S.base+S.stacksize2、进栈StatusSqStackPush(SqStack&S,ElemTypee){if(S.top==S.base+S.stacksize)return(OVERFLOW);S.top=e;S.top++;return(OK);}3、出栈算法StatusSqStackPop(SqStack&S,ElemType&e){if(S.top==S.base)return(UNDERFLOW);S.top-;e=S.top;return(OK);缺点：空间浪费思考：二栈合用同一顺序空间？0 max^izei////////////A“〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃〃%&tTt6[0] "0]"1] 6[1]#definemaxsize=100intstack[maxsize],topO=0,topl=maxsize-l;intpushO(inte){if(topO>topi)return(0);stack[topO]=e;topO++;return(1);}intpushl(inte){if(topO>topi)return(0);stack[topl]=e;topi—;return(1);)intpopO(int*e){if(top0==0)return(0);intpopl(int*e){if(top0==0)return(0);topO-;*e=stack[topO];return(1);topO++;*e=stack[topl];return(1);三、链栈typedefstructlinknode//栈中结点类型{ElemTypedata;structlinknode*link;}LinkNode;typedefstruct{typedefstruct{LinkNode*top;intstacksize;//定义栈类型//栈顶指针//栈的大小（可选）}LinkStack;LinkStackS;初始化：S.top==NULL;S.stacksize==O栈空：S.top==NULL栈满：系统内存不够1、进栈StatusLinkStackPush(LinkStack&S,ElemTypee){LinkNode*p;p=(LinkNode*)malloc(sizeof(LinkNode));if(p==NULL)return(OVERFLOW);〃上溢p->data=e;p->link=S.top;S.top=p;return(OK);2、出栈StatusLinkStackPop(LinkStack&S,ElemType&e){LinkNode*p;if(S.top==NULL)return(UNDERFLOW);p=S.top;e=S.top->data;S.top=S.top->link;free(p);return(OK);3、特殊头结点的讨论进栈、出栈是最常用的操作=»链栈的头指针频繁变更=»参数传递的负担=》应约定链栈具有特殊头结点。第二节栈的应用1、函数调用栈f(n)=f(n-l)+f(n-2)intf(intn){intx,y;if(n==l||n==2)return(1);x=f(n-1);y=f(n-2);return(x+y);}mainO{printf0%d\n”,f(5));}2、将十进制数转换为八进制数。例如(1348)|。=(2504)8,除8取余的过程：nn/8nmod8134816841682102125202voidConversion(intdec,intoct[]){InitStack(S);for(;dec!=0;dec=dec/8)push(S,dec%8);/*进栈次序是个位、十位...*/for(i=0;IStackEmpty(S);i++)oct[i]=pop(S); /*先出栈者是高位，最后是个位*/3、括号匹配的检验Equal("((a)(b))”):0Equal("(((a)(b))”):1Equal(〃((a)(b)))”):-1intEqual(chars[]){inti=0;for(i=0;s[i];i++)switch(s[i]){case'C:push(s[i]);break;case')':if(StackEmpty(S))return(-1);//)多pop();break;)if(!StackEmpty(S))return(1);//(多return(0); //完全匹配4、进栈出栈的组合问题已知操作次序：push(l);pop();push(2);push(3);pop();pop();push(4);pop();请写出出栈序列。5、中缀表达式求值的算法如：1+2*(3+4*(5+6))分析：先乘除，后加减；从左到右；先括号内，再括号外。前算符+—X/()#+>><<<>>—>><<<>>X>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=①一个运算是否立即执行？必须和“上一个运算符”比较优先级。3*5+2

②“上一个运算符”存于何处？运算符栈③对应的运算数存于何处？运算数栈④为保证第一个运算符有“上一个运算符"：Push(OPTR,'#')为保证最后一个运算符能被执行："3*5+2#"#:优先级最低的运算符。⑤运算结果：运算数栈最后的元素。跟踪示例：3*(7-2)##件3OPTR7：3OPNDOPTROPNDOPTROPND

c='3'OPTROPND

C='*'OPTROPNDc=c='7'23*OPTR*件53件OPTRIfOPTROPNDc='#'OPNDc=OPTROPND

c='2'OPNDOPTROPNDC=，)，c=y#件3OPTR7：3OPNDOPTROPNDOPTROPND

c='3'OPTROPND

C='*'OPTROPNDc=c='7'23*OPTR*件53件OPTRIfOPTROPNDc='#'OPNDc=OPTROPND

c='2'OPNDOPTROPNDC=，)，c=ycharStack:类型定义：基本函数：InitStackl(charStack*);charGetTopl(charStack*);voidPushl(charStack*,char);charPopl(charStack*);intStack:类型定义：基本函数：InitStack2(intStack*);intGetTop2(intStack*);voidPush2(intStack*,int);intPop2(intStack*);floatMidExpressionEval(charExpress[])//Express□:“3*5+2#“{inti=0;charc,pre_op;charStackOPTR;intStackOPND;

InitStackl(&OPTR);Pushl(&OPTR,' ;/*运算符栈*/InitStack2(&OPND); /*运算数栈*/while(Express[i] #)||GetTopl(&OPTR)!='#'){c=Express[i];if(!InOPTR(c))/*getnum(Express,&i)*/{Push2(&OPND,c」0');i++;}else/*getnum(Express,&i)*/{pre_op=GetTopl(&OPTR);switch(Precede(pre_op,c)){case'〈'： //pre_op<cPushl(&OPTR,c);i++;break;case'=':Popl(&OPTR); i++;break;case' : //pre_op>c执行pre_opb=Pop2(&OPND);a=Pop2(&OPND);Popl(&OPTR);Push2(&0PND,Operate(a,preop,b));)}return(GetTop2(&OPND));优先级的处理技巧+一*/()#intpriority[7JL7J={{,intpriority[7JL7J={{,X,',”,",{<,<,}intOpID(charop){switch(op)，，，，//)//#{case'+':return(0);case' :return(1);case' :return(2);case'/':return(3);case'(":return(4);case')':return(5);case'#':return(6);})charPrecede(charopl,charop2){return(priority[OpID(opl)][0pID(op2)]);}测试案例：〃3#","3+5#","3+5+2#""3*5+2#","3+5*2#","(3+5)*2#",”(3+5)*(2+l)#〃，"((3+5)/2+l)*2tf•…，作业与上机：1、表达式求值第三节队列、逻辑结构aoaiazan-iaoaiazan-irearrearfront只能在一端（队尾rear）插入，在另一端（队头front）删除的线性表。先进先出表FIFO（FirstInFirstOut）基本操作：进/出队列判别队列满/空队列的应用背景：排队模型。排队问题无处不在，各种服务行业、甚至生产管理中都存在排队问题。二、链式存储结构rearfront―»|C~D-~E »|G|八Typedefstructqueuenode〃队列中的结点类型{ElemTypedata;structNode*link;}QueueNode;typedefstruct 〃队列类型{QueueNode*front,*rear;}LinkQueue;LinkQueueQ;初始化空队列：Q.front==NULLQ.rear==NULL1、入队列StatusLinkQueueEnter(LinkQueue&Q,ElemTypee){QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));if(!p)return(OVERFLOW);p->data=e; p->link=NULL;if(Q.front==NULL)Q.front=Q.rear=p;else{Q.rear->link=p;Q.rear=p;}return(OK);)2、出队列StatusLinkQueueLeave(LinkQueue&Q,ElemType&e){QueueNode*p;if(Q.front==NULL)return(UNDERFLOW);p=Q.front;Q.front=p->link;if(Q.rear==p)Q.rear=NULL;e=p->data;free(p);return(OK);3、销毁队列voidLinkQueueDestroy(LinkQueue&Q){QueueNode*p;while(Q.front){p=Q.front;Q.front=p->link;free(p);}Q.rear=NULL;}三、顺序存储结构动态顺序存储结构：#defineQUEUE_SIZE100 〃初始化时分配的空间typedefstruct{ElemType*base; 〃存储空间的起始地址intfront,rear;}SqQueue;SqQueueQ; 〃定义一个队列结构rear为下一个进队列元素的位置。front在队列不空时，指向首元素；在队列为空时，等于rear。1、初始化队列StatusSqQueuelnit(SqQueue&Q){Q.base=malloc(QUEUE_SIZE*sizeof(ElemType));if(!Q.base)return(OVERFLOW);Q.front=Q.rear=0;return(OK);队列空：Q.front==Q.rear进队列：*(Q.base+Q.rear)=e;Q.rear++;出队列：e=*(Q.base+Q.front);Q.front++;54321rear—>qfront—>5rear—>4321front-0rear—>54front—>32]0rear—>front—>543210队列满：Q.rear==QUEUE_SIZE=»假溢出QUEUE_SIZEQUEUE_SIZE进队列：Q.rear=(Q.rear+1)%出队列：Q.fronts(Q.front+1)QUEUE_SIZEQUEUE_SIZE队列空：Q.front-Q.rear当队列中有QUEUE_SIZE个元素时:Q.front==Q.rear=》必须浪费一个结点空间队列满：(Q.rear+1)%QUEUE_SIZE==Q.frontrearffront5432105432front—>1

rear—>Q543front—>2rear—>102、入队列StatusSqQueueEnter(SqQueue&Q,ElemTypee){if((Q.rear+1)%QUEUE_SIZE=Q.front)return(OVERFLOW);*(Q.base+Q.rear)=e;Q.rear=(Q.rear+1)%QUEUE_SIZE;return(OK);3、出队列StatusSqQueueLeave(SqQueue&Q,ElemType&e){if(Q.rear~Q.front)return(UNDERFLOW);e=*(Q.base+Q.front);Q.front-(Q.front+1)%QUEUE_SIZE;return(OK);4、元素计数(Q.rear-Q.front+QUEUE_SIZE)%QUEUE_SIZE值的范围0 QUEUE_SIZE-1思考：一定要浪费一个结点空间？利用一个标志变量Q.flag(0:非满，1:非空)。typedefstructdata[M];intfront,rear;intflag;}SqQueue;{ElemTypeintEmpty(SqQueueQ){if(Q.front~Q.rear&&Q.flag==0)return(1);return(0);]intFull(SqQueueQ){if(Q.front-Q.rear&&Q.flag-l)return(1);return(0);1、初始化队列StatusSqQueue_Init(SqQueue&Q){Q.front=Q.rear=0;Q.flag=0;}2、入队列StatusSqQueueEnter(SqQueue&Q,ElemTypee){if(Full(Q))return(OVERFLOW);Q.flag=l; 〃非空return(OK);}3、出队列StatusSqQueueLeave(SqQueue&Q,ElemType&e){if(Empty(Q))return(UNDERFLOW);Q.flag=O;return(OK);〃非满第四节队列的实例：离散事件的模拟一、排队问题加油站的问题：一个加油站只有一台加油机,平均为每辆车加油需要5分钟,假定一个小时内，有20辆车随机进入加油站加油，计算每辆车的平均等待时间.银行营业所应设置几个柜台？1、设置N柜台时，计算顾客的平均等待时间；2、选择合适的N值。二、两个栈组合出一个队列制定两个栈与一个队列的对应规则:/ aoQiaz a»-i <-rearfrontS2SIa0,…ai进队列1 J%•♦♦aoa0出队列1-..一一，--ai+b...an-i进队列♦♦♦ai,——・♦♦ai+lab…ai出队列tL一・♦♦ai+lai+1出队列ai+2 ♦♦♦dn~istacksi,s2;voidEnter(ElemTypee){Push(si,e);}ElemTypeLeave(){ElemTypee;if(!Empty(s2))return(Pop(s2));while(!Empty(si))Push(s2,Pop(si));return(Pop(s2));第四章串串：限定数据元素类型的线性表。应用实例：编辑软件（本质上是字符串处理）信息检索、病毒查找（字符串比较）

第一节逻辑结构一、定义串是由字符组成的线性表。STRING=（D,S,P）D={a»|ai£CHARACTER（字符集），i=0,1,2,…,nT}ASCII码串:CHARACTER为ASCII码字符集。位串:CHARACTER={0,1}S={<a；i,a；>|ai-i,a；€D,i=l,2,n-l}"a()ai a0/的长度为no空串：长度为0。子串：串中任意个连续字符组成的子序列。两串相等：两串长度相等，对应的每个字符相等。例：根据字符串比较运算的定义，完善该函数：intstrcmp(chars[],chart[]){inti;for(i=0;s[i]&&t[i];i++)if(s[i]!=t[i]);二、基本运算线性表注重单个元素的操作串注重整体或部分整体的操作赋值 StrAssign(&S,T)判断 StrEmpty(S) StrComp(S,T)求长度 StrLen(S)联接 Concat(&T,S1,S2)求子串SubStr(&Sub,S,pos,len)子串定位 Index(S,T,pos)替换 Replace(&S,T,V)插入 Strinsert(&S,pos,T)删除 StrDelete(&S,pos,len)释放 DestroyString(&S)第二节存储结构一、顺序存储串中相邻的字符存放在内存的相邻单元中。静态顺序结构：typedefcharString[MAXSIZE+1];动态顺序结构之一:typedefstruct{char*ch; 〃起始地址intlength;〃串长}String;动态顺序结构之二：typedefstruct//C语言的约定{char*ch;〃起始地址，结束标记符}String;优点：访问子串方便，缺点：空间大小不灵活，插入、删除费时。二、链式存储如何设置结点的大小？一个结点存储1个字符：非紧缩格式。空间浪费，操作简单。一个结点存储多个字符：紧缩格式。空间效率高，操作复杂。//紧缩格式的块结构ttdefineCHUNKSIZE80typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}CHUNK;typedefstruct{CHUNK*head,*tail;intlength;〃串的长度}LString;如何在紧缩格式的链串中插入、删除？第四章串第三节模式匹配模式匹配Index(S,T,pos)主串S中寻找模式串T的起始位置。pos是主串中进行模式匹配的起始位置。Index("abcdef","cde"):2Index("abcdef","ab"):0Index("abcdef","ad"):-1一、BF算法(Brute-Force)主串S=SoSl...Sm-1模式串T="totl...tn/匹配过程：Si==tj时：i++;j++;Si<>tj时：如何回溯？t()t]・・・"tj-1tj・・・=二=<>...Si-jSi-j+i...Si-iSi... =》i=i-j+l;j=0;匹配结果：tL,]=='\o'：成功，返回s中的起始位置。to...tj-2tj-itj "匕时j==n.•Si-j...St-2Si-is,... 起始位置=》i-jtLi]!='\0'：失败，返回-LintindexBF(chars[],chart口){inti=0,j=0;while(s[i]&&t[j])if(s[i]==t[j]) { i++; j++;}else{i=i-j+l;j=0;}if(t[j]==O)return(i-j);elsereturn(-1);问题分析：S="aaaaaaaaaaaaaaab”长度为m

T="aaaab” 长度为n回溯次数=m-n最差时间复杂度：0((m-n)*n)«0(n*m)再例：S="abcabcabcde”T="abcabcd”二、KMP算法(Knuth等3人)在算法分析和编程语言设计方面有杰出贡献，著作有artofcomputerprogramming。获1974年图灵奖。1、推导琢磨模式串的内在规律，使得:在s〈>tj时，i不回溯，j适当回溯，再重新比较。当s〈》tj时，i不变，j=k。求k=? (k<j)此时有：“toti...〃-j.・・Si-itoti.・・tj-ktj-k+1・・・tj-1tj==...==.,=<>•*•Si-jSi-j+1•.・Si-kSi-k+1•・・Si-iSi=二二?totl…tk-ltk显然，k应具有性质:tot1.・,tk-i=Si-k.・・Si-i=tj-ktj-k+i.・・tj-i即：toti...tk-l-tj-ktj-k+l•••tj-1即：当，与Si失配时，由于tj的前k个字符等于模式串的开头k个字符,所以可将S1与加比较。为达到更高效率，k越大越好。(k<j)2、next每个tj与对应一个k值，所以设立next□存储所有k值。计算方法：1、j=0时:next[j]=-l;2、存在toti...tk-i=tj-ktj-k+i...tj-i»(k〈j):1列或□:to二tj-1tot1=tj-2tj-1totit2=tj-atj-2tj-1next[j]=max(k)»3、否则：next[j]=0;3、KMP程序〃预先求出next[]intindexkmp(chars[],chart[],intnext口){inti=0,j=0;while(s[i]&&t[j])if(j==-l||s[i]==t[j]){i++;j++;}elsej=next[j];if(t[j]-O)return(i-j);elsereturn(-1);}体会j==-l体会j=next[j]例1:abcabcd-1000123abcabcabcde<>匹配过程i=6i=61=7i=8i=9i=10abcabcdj=6j=3j=4j=5j=6j=7例2:aaaab-10123aaabaaaab<>aaaab匹配过程i=3i=3i=3i=3i=3i=4j=3j=2j=lj=oj=-lj=o例：设主串s="abcabcabd",模式串p="abcabd”,按KMP算法进行模式匹配,当“SoSlS2s3s/J'poPlP2P3P且S5rp5时，应进行比较。A、S5和P2B、S5和P3 C、Si和PoD、S8和P5第四章串

第四节串操作实例一、文本编辑软件的数据结构1、文本编辑软件数据对象：字符串。max(inta,intb){if(a>b)return(a);elsereturn(b);)maX(intaintb)z(if(a>1))return(a)!/e1sereturn(a)»/}基本操作：插入、删除字符。简易文本编辑器的功能菜单：①末尾添加/在某行前插入一行;②删除指定行；③在某行中插入字符串；④在某行中删除某子串；⑤查找/替换子串；⑥打开/保存文件；⑦显示文件内容（可以简化）2、数据结构的设计如何减少时间/空间复杂度？方案①：整个文件是一个顺序/链式字符串。方案②：每行作为一个顺序/链式字符串，行表：所有行结构的头结点组成的线性表。行表的存储结构：顺序/链式顺序结构：字符数/行、行数有上限链式结构：存储空间浪费严重。紧缩格式？二、多模式匹配问题：网络搜索引擎、病毒搜索查找对象：一个大字符串S若干模式串：一个字符串集合KeywordsS中存在多个包含Keywords中所有关键字的匹配子串。目标：求出包含所有匹配子串的最短匹配子串。上机：1、模式匹配例1、子串替换main(){chars[M]="abcdeabcdef”,t[M]="bcde";charv[M]="12";//"1234””123456"""substr(s,t,v);puts(s);}将s口中的t口用V口替换voidsubstr(chars[],chart[],charv[]){ints_len,t_len,vlen,s_i,t_i,v_i,gap,i,j;s_len=strlen(s);t_len=strlen(t);v_len=strlen(v);gap=v_len-t_len;s_i=0;while(s[s_i]){for(t_i=0;s[s_i]&&t[t_i];)//定位if(s[s_i]==t[t一i]){s_i++; t_i++;}else {s_i=s_i-t_i+l;t_i=0;}if(t[t_i]==\0')〃替换{if(gap>0) 〃扩充s串for(i=s_len-l;i>=s_i;i-)s[i+gap]=s[i];if(gap<0) //缩减s串for(i=s_i;i<=s_len-l;i++)s[i+gap]=s[i];for(i=s_i-t_len,j=0;j<v_len;i++,j++)s[i]=v[j];s_len=s_len+gap;s_i=s_i+gap;s[s」en]='\0';例2、在结点大小为1的链串上，实现子串定位算法。若匹配成功，则返回起始结点地址，否则返回空指针。typedefstructIstring{chardata;structIstring*next;}LString;LString*indexBF(LString*s,LString*t){LString*sp,*tp,*sstart;sp=s;tp=t;sstart=s;while(sp&&tp){if(sp->data-tp->data){sp=sp->next;tp=tp->next;}else{sstart=sstart->next;sp=sstart;tp=t;}}if(!tp)return(sstart);elsereturn(NULL);第五章数组和广义表继续增加线性表结构的内涵。数组结构每个子结构是由基本元素组成的大小均等的线性表。广义表每个子结构或是基本元素，或是由基本元素组成的大小不等结构的线性表结构。第一节数组的逻辑结构l_Array=(D,S,P)定长线性表D={a』ai€ElemSet,i=0,1,2, n-1}S={<aii,a(>|a1,ai£D,i=l,2,…，nT}2_Array=(D,S,P)定长线性表，每个元素又是定长线性表。

“0,0 “0/2-1A —“1,0 a\A "1/2-1an\-\A an\-\,n2-\_D={ai,jai.j€ElemSet,i=0,1,…，n「l;j=0,1,…，n2-l}S={ROW,COL}R0W={<ai,j-bai,j>|i=O,1,…，n「l;j=l,••,n2-l}C0L={<ai-i,j,a”i=l,…,mT;j=0,1,•••,n2-l}3_Array=（D,S,P）增加层的关系二维数组：分量为一维数组的一维数组。三维数组：分量为二维数组的一维数组。数组一旦被定义，它的维数和维界就不再改变。基本操作：取值、赋值。第二节数组结构的顺序存储结构数组结构是多维的，内存地址是一维的O二维数组a[nl][n2]的存储方式：行主序a（）,oa。jHo,n2-lQ-1,0…0-l,n2-l•••anl-l,n2-2列主序a（）,o3.1,0•••anl-1,0a。,]•••Q-nl-1,1•••an1-2,n2-l3n1-l,n2-l示例行主序列主序123412 3 41ABCD1ABCD2EFGH2EFGH3口JK|L3|1|J|K|L多维数组的存储方式:行主序先排最右下标，从右到左；列主序先排最左下标，从左向右。以行主序为例，计算数组元素的地址:一维LOC3)=base+i二维(MxN)LOC(a、。=base+i*N+j三维(MxNxP)LOC(3i,j.k)=base+i*N*P+j*P+k四维(MxNxPxQ)LOC(ai.j,k,i)=base+i*N*P*Q+j*P*Q+k*Q+1数组结构定义Typedefstruct{ElemType*base;intdim; 维数int*bounds;各维的维界int*constants;各维成员的大小}Array;例：数组A[3,4]的存储结构A.dim=2A.bounds[] ={3,4}A.constants[]={4,1}A[i,j]的地址:A.base+(i*4+j)例：数组A[3,4,5,6]的存储结构A.dim=4A.bounds[] ={3, 4,5,6}A.constants[]={120,30,6,1}A[i,j,k,1]的地址：A.base+(i*120+j*30+k*6+l)1、初始化数组结构StatusArraylnit(Array&A,intdim,intbounds[]){A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));A.constants=(int*)malloc(dim*sizeof(int));if(!A.bounds||!A.constants)return(OVERFLOW);for(i=0;i<dim;i++)A.bounds[i]=bounds[i];for(A.constants[dim-l]=l,i=dim-2;i>=0;i)A.constants[il=A.bounds[i+l]*A.constants[i+l];〃开辟数组空间elemtotal=A.bounds[0]*A.constants[0];A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)return(OVERFLOW);return(OK);2、取值ElemTypeArrayGetValue(ArrayA,intdim_i口){intoffset;for(offset=0,i=0;i<A.dim;i++)offset+=A.constants[i]*dimi[i];return(*(A.base+offset));Imain(){ArrayA;ElemTypee;intbounds[4]={3,4,5,6};intdim[4]={2,1,3,4};Array_Init(A,4,bounds);e=ArrayGetValue(A,dim);}第三节矩阵的压缩存储矩阵的用途：大型方程组求解、高次方程求解真正有用的计算是矩阵的计算。从空间/时间复杂度出发，讨论矩阵的存储结构。一、特殊矩阵利用矩阵的特征，尽量减少数据的存储量。1、对称矩阵dij-HjiLn-1,n-1「15137、Ln-1,n-1TOC\o"1-5"\h\z5 0 8 0 01 8 9 2 63 0 2 5 1C0613,NxN矩阵的存储结构:S[N(N+1)/2]O以行主序的方式存储下三角元素：3.0,031,0ai,i32,0 Hn-1,0a«n-l,n-1若i>=j:k=i*(i+l)/2+j若i<j:k=j*(j+l)/2+i/*取值*/intgetValue(inti,intj){if(i>=j)return(s[i*(i+1)/2+j])elsereturn(s[j*(j+l)/2+i]);I/*赋值*/voidSetValue(inti,intj,inte){if(i>=j)s[i*(i+l)/2+j]-e;elses[j*(j+l)/2+i]=e;I2、上/下三角矩阵类似对称矩阵。只是某个三角区域的所有元素为0,或某个固定值。例：设N阶对称矩阵A存储为一维数组S[N(N+l)/2],以行主序的方式存储A的下三角，则元素A[3][5]的存储位置是？3、小结练习的意义：培养摸索数据规律的感觉。二、稀疏矩阵之三元组表稀疏因子=t/(m*n)稀疏矩阵：稀疏因子<=0.05的大型矩阵。(非。数很少，且无规律)1、三元组的顺序表#defineMAXSIZE1000typedefstruct〃三元组结构{inti,j;ElemTypee;）Triple;typedefstruct〃三元组顺序表{intmu,nu,tu;Tripledata[MAXSIZE];〃静态顺序表//Triple*data;动态顺序表}TSMatrix;约定：①三元组中的e必须不等于0。②非0元素按行主序排列。优点：节省空间。缺点：按行号、列号存取元素，费时。2、转置运算M=>T（以T为中心，按需点菜）1000、「030000、300-5010