数据结构C语言版讲义.doc

第一章 绪论第一节 什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。信息模型：信息处理领域中的数学模型。数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。忽略数据的具体含义，研究信息模型的结构特性、处理方法。第二节 概念、术语一、有关数据结构的概念 数据：对客观事物的符号表示。 例：生活中还有什么信息没有被数字化？ 身份证，汽车牌号，电话号码，条形代码 数据元素：数据的基本单位。相当于记录。 一个数据元素由若干个数据项组成，相当于域。 数据对象：性质相同的数据元素的集合。 数据结构：相互之间存在特定关系的数据集合。 四种结构形式：集合、线性、树形、图(网)状 形式定义：(D，S，P) D：数据元素的集合(数据对象) S：D上关系的有限集 P：D上的基本操作集 逻辑结构：关系S描述的是数据元素之间的逻辑关系。存储结构：数据结构在计算机中的存储形式。 顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系： 逻辑结构：描述、理解问题，面向问题。 存储结构：便于机器运算，面向机器。程序设计中的基本问题：逻辑结构如何转换为存储结构？二、有关数据类型的概念数据类型：值的集合和定义在该值集上的一组操作的总称。 包括：原子类型、结构类型。抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。 核心：是逻辑特性，而非具体表示、实现。课程任务：学习ADT、实践ADT。如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型实践指导：为了代码的复用性，采用模块结构。 如：C中的头文件、C+中的类第三节 ADT的表示与实现本教材中，算法书写习惯的约定。数据元素类型ElemType：int,float,char, char 引用参数 &算法：void add(int a,int b,int &c) c=a+b; 程序：void add(int a,int b,int *p_c) *p_c=a+b; 第四节 算法的描述及分析一、有关算法的概念 算法：特定问题求解步骤的一种描述。 1)有穷性 2)确定性 3)可行性二、算法设计的要求好算法：1)正确性2)可读性3)健壮性4)高效，低存储三、时间复杂度 事前估算：问题的规模，语言的效率，机器的速度 时间复杂度：在指定的规模下，基本操作重复执行的次数。 n：问题的规模。f(n)：基本操作执行的次数 T(n)=O(f(n) 渐进时间复杂度(时间复杂度)例：求两个方阵的乘积 CA*Bvoid MatrixMul(float an,float bn,float cn) int i,j,k; for(i=0; in; i+) / n+1 for(j=0; jn; j+) / n(n+1) cij=0; / n*n for(k=0; kn; k+) / n*n*(n+1) cij+ = aik * bkj; / n*n*n 时间复杂度： 一般情况下，对循环语句只需考虑循环体中语句的执行次数，可以忽略循环体中步长加1、终值判断、控制转移等成分。 最好/最差/平均时间复杂度的示例：例：在数组An中查找值为k的元素。 for(i=0; in-1; i+) if(Ai=k) return i; 四、常见时间复杂度 按数量级递增排序： 将指数时间算法改进为多项式时间算法：伟大的成就。五、空间复杂度实现算法所需的辅助存储空间的大小。S(n)=O(f(n) 按最坏情况分析。六、算法举例例1：以下程序在数组中找出最大值和最小值void MaxMin(int A, int n) int max, min, i; max=min=A0; for(i=1; imax) max=Ai; else if(Aimax)：n-1次 if(Aimax)：n-1次 if(Aimin): 0次例2：计算f(x)=a0+a1x+a2x2+.+anxn解法一：先将x的幂存于power，再分别乘以相应系数。float eval(float coef,int n,float x) float powerMAX, f; int i; for(power0=1,i=1;i=n;i+) poweri=x*poweri-1; for(f=0,i=0;i=0;i-) f=f*x+coefi; return(f);五、思考题1、问：“s=s+i*j;”的执行次数？时间复杂度？for(i=1;i=n;i+) if(5*i=n)for(j=5*i;j=n;j+) s=s+i*j;2、问：“aij=x;”的执行次数？时间复杂度？for(i=0; in; i+)for(j=0; j=i; j+) aij=x; 第二章 线性表 线性结构：在数据元素的非空集中，存在唯一的一个首元素，存在唯一的一个末元素，除首元素外每个元素均只有一个直接前驱，除末元素外每个元素均只有一个直接后继。第一节 逻辑结构 形式定义： Linear_list=(D，S，P) D = ai| aiElemSet, i=0,1,2,n-1 S = | ai-1,aiD, i=1,2,n-1为序偶，表示前后关系 基本操作P：插入、删除、修改，存取、遍历、查找。 void ListAppend(List L, Elem e) ; void ListDelete(List L, int i) ; int SetElem(List L, int i, Elem e); int GetElem(List L, int i, Elem &e); int ListLength(List L); void ListPrint(List L); int LocateElem(List L, Elem e);合并、分解、排序 基本操作的用途：集合的并、交、差运算 有序线性表的合并、多项式的运算 例：利用线性表LA和LB分别表示集合A和B，求A=AB。void union(List &La，List Lb) int La_len, Lb_len; La_len=ListLength(La); / 计算表长 Lb_len=ListLength(Lb); for(i=1; i=i; j-) A.elemj+1 = A.elemj; A.elemi=e; A.length+; 2、删除ai：a0a1ai-1aiai+1an-1 如何移动元素？a0a1ai-1ai+1an-1void SqList_Delete(SqList A, int i) for(j=i+1; jA.length; j+) A.elemj-1 = A.elemj; A.length-;三、效率分析 插入、删除时，大量时间用在移动元素上。 设插入位置为等概率事件，时间复杂度？例1：增序顺序表的合并，设其中无相同元素Status SqList_Merge(SqList La,SqList Lb,SqList &Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; Lc.listsize=Lc.length=La.length+Lb.length; Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem) return ERROR; pa=La.elem; pb=Lb.elem; pc=Lc.elem; pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last & pb=pb_last) if(*pa=*pb) *pc=*pa; pc+; pa+; else *pc=*pb; pc+; pb+; while(pa=pa_last) *pc=*pa; pc+; pa+; while(pb 1 2 3 4 5 6 7 8 9void del(int A,int n) int i,k; / k是0元素的个数 for(k=0,i=0; inext=p-next; p-next=q; 在*p之前插入？ 时间复杂度？ 各种插入方法：首插：插入在首结点前；尾插：入在尾结点后。有序插：保持结点的顺序，插在表中间； 编程细节：首插：修改头指针尾插：链表为空时，修改头指针。有序插：链表为空时，修改头指针。链表不空时，可能修改头指针/ 首插LNODE * LinkList_InsertBeforeHead(LNODE *head, LNODE *newp) newp-next=head; return(newp); / 遍历打印void LinkList_Print(LNODE *head) LNODE *p; for(p=head; p; p=p-next) printf(.,p-data);/ 尾插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); 简化程序细节的方法：特殊头结点/ 首插（有特殊头结点）void LinkList_InsertBeforeHead(LNODE *head, LNODE *newp) newp-next=head-next; head-next=newp;/ 尾插（有特殊头结点）void LinkList_InsertAfterTail(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？ 时间复杂度？ 各种删除方法：首删除： 尾删除： 思考查找删除：思考/ 首删除（有特殊头结点）void LinkList_DeleteHead(LNODE *head) LNODE *p; if(head-next=NULL) return; p=head-next; head-next=p-next; free(q);三、单个链表的例程（设以下链表有特殊头结点）例1、按序号查找：取链表第i个结点的数据元素。i1,n/ 注意计数次数的边界条件Status LinkList_GetElemBySID(LNODE *head,int i,ElemType &e) LNODE *p; int j;for(p=head-next,j=1; p & jnext; if(p=NULL) return ERROR; e=p-data; return OK;例2、按值查找：取链表中值为e的结点的地址。LNODE * LinkList_GetElemByValue(LNODE *head, ElemType e) LNODE *p; for(p=head-next; p; p=p-next)if(p-data=e) break; return(p);例3、释放链表中所有结点。void LinkList_DeleteAll(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=tail=newp; else tail-next=newp; tail=newp; newp-data=p-data; tail-next=NULL; return(head);例5、线性链表的逆序LNODE * LinkList_Reverse(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中多余的重复节点。 3 5 2 5 5 5 3 5 6= 3 5 2 6void LinkList_Purge(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,*pctail,*Lc;Lc=pctail=La; / Lc的头结点是原La的头结点pa=La-next; pb=Lb-next; free(Lb); while(pa!=NULL & pb!=NULL) if(pa-data data) pctail-next=pa; pctail=pa; pa=pa-next; else pctail-next=pb; pctail=pb; pb=pb-next; if(pa!=NULL) pctail-next=pa; else pctail-next=pb; return(Lc);例2、无序线性链表的交集AB/不破坏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、AB3、AB4、(A-B)(B-A)第五节 循环链表 尾结点的指针域指向首结点。 实际应用：手机菜单 遍历的终止条件？例：La、Lb链表的合并 / 将Lb链表中的数据结点接在La链表末尾void Connect(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);第六节 双向链表 非空表 空表 typedef struct DuLNode ElemType data; struct DuLNode *lLink, *rLink;DuLinkNode;1、在*p之后插入结点*q q-rLink=p-rLink; q-lLink=p; p-rLink=q; q-rLink-lLink=q 在*p之前插入结点*q ?2、删除*p (p-lLink)-rLink=p-rLink; (p-rLink)-lLink=p-lLink; free(p); 删除*p的前驱结点? 删除*p的后继结点?第七节 实例：一元多项式的存储、运算一、 多项式的存储结构 f(x) = anxn +.+a2x2 + a1x + a01、顺序结构 int coefMAX;f(x) = 14x101+ 5x50 - 32、链式结构typedef struct polynode int coef; int index; struct node *next;PolyNode;3、示例输入数据（指数无序）输出多项式(指数降序)多项式1多项式2count=2coef=5,index=3coef=1,index=5count=3coef=2,index=7coef=7,index=2coef=6,index=3count=4coef=2,index=7coef=1,index=5coef=11,index=3coef=7,index=24、结构细节设计带特殊头结点的单向链表； 结点按指数降序排列；特殊头结点的index域：多项式的项数。5、程序框架设计main() PolyNode *L1,*L2; L1=PolyNode_Create(); PolyNode_Print(L1); L2=PolyNode_Create(); PolyNode_Print(L2); PolyNode_Add(L1,L2); / L1+L2=L1 PolyNode_Print(L1);void PolyNode_Print(PolyNode *head) PolyNode *p; printf(count=%dn,head-index); /打印项数 for(p=head-next; p; p=p-next) printf(coef=%d,index=%dn,p-coef, p-index);二、以插入为基础的算法1、将*newp插入到降序链表*head中void PolyNode_Insert(PolyNode *head, PolyNode *newp); PolyNode *p,*pre;/ 定位for(pre=head,p=pre-next; p; pre=p,p=p-next) if(p-index index) break;if(p=NULL | p-index 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-; 2、利用PolyNode_Insert函数，建立有序链表PolyNode *PolyNode_Create() int i,count; PolyNode *head,*newp; scanf(%dn,&count); head=(PolyNode *)malloc(sizeof(PolyNode); head-coef=0; head-next=NULL; for(i=0; icoef,&newp-index); PolyNode_Insert(head, newp); return(head);3、利用PolyNode_Insert函数，实现多项式加法/ L1+L2=L1 不破坏L2链表 void PolyNode_Add(PolyNode *L1, 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; PolyNode_Insert(L1,newp); 时间复杂度？设L1长度为M，L2长度为N，则O(M*N)。三、两表合并算法L1+L2=L1 破坏L2链表 将L2中的每个结点卸下，合并到L1中void PolyNode_Add(PolyNode *L1, PolyNode *L2) PolyNode *p1, *p1pre; / *p1pre 是*p1的直接前驱 PolyNode *p2, *p2next; / *p2next是*p2的直接后继 p1pre=L1; p1=L1-next; / p1指向L1中第一个数据结点 p2=L2-next; free(L2); / p2指向L2中第一个数据结点 while(p1 & p2) switch(compare(p1-index, p2-index) case : / *p1指数大于*p2指数 p1pre=p1; p1=p1-next; break; case next; / 小心：准备在*p1pre后插入*p2 p2-next=p1; p1pre-next=p2; p1pre=p2; / 小心：保持p1pre和p1的关系 p2=p2next; / p2指向下一个待合并的结点 break; case =: / *p1和*p2是同类项 p1-coef+=p2-coef; / 系数合并 p2next=p2-next; free(p2); / 删除*p2 p2=p2next; / p2指向下一个待合并的结点 if(pa-coef=0) / 合并后系数为0 p1pre-next=p1-next; free(p1); / 删除*p1 p1=p1pre-next; / 保持p1pre和p1的关系 / switch / while if(p2) p1pre-next=p2; / 链上p2的剩余结点时间复杂度？设L1长度为M，L2长度为N，则O(M+N)。作业与上机：(选一) 一、多项式加法、减法 二、多项式乘法:a*b=c(建立新表c) 三、任意整数的加法、乘法第三章 栈与队列栈与队列：限定操作的线性表。第一节 栈一、逻辑结构1、栈的定义限定只能在表的一端进行插入、删除的线性表。栈顶top，栈底bottom。后进先出LIFO表(Last In First Out)实例：“进制数转换”、“表达式求值”、“函数调用关系”、“括号匹配问题”、“汉诺塔问题”、“迷宫问题” 2、基本操作进栈Push/出栈Pop取栈顶元素GetTop判别栈空StackEmpty/栈满StackFull3、栈的应用背景许多问题的求解分为若干步骤，而当前步骤的解答，是建立在后继步骤的解答基础上的。=问题分解的步骤和求解的步骤次序恰好相反。二、顺序存储结构动态顺序存储结构：存储空间随栈的大小而变化。#define STACK_INIT_SIZE 100 /初始化时分配的空间typedef struct /定义栈类型 ElemType *base,*top; /栈底、栈顶指针 int stacksize; /栈的存储空间大小SqStack; SqStack S; /定义一个栈结构1、初始化栈Status SqStack_Init(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、进栈Status SqStack_Push(SqStack &S,ElemType e) if(S.top=S.base+S.stacksize) return(OVERFLOW); S.top=e; S.top+; return(OK);3、出栈算法Status SqStack_Pop(SqStack &S,ElemType &e) if(S.top=S.base) return(UNDERFLOW); S.top-; e=S.top; return(OK);缺点：空间浪费思考：二栈合用同一顺序空间？ #define maxsize=100int stackmaxsize, top0=0, top1=maxsize-1;int push0(int e) if(top0 top1) return(0); stacktop0=e; top0+; return(1);int push1(int e) if(top0 top1) return(0); stacktop1=e; top1-; return(1);int pop0(int *e) if(top0=0) return(0); top0-; *e=stacktop0; return(1);int pop1(int *e) if(top0=0) return(0); top0+; *e=stacktop1; return(1);三、链栈typedef struct linknode / 栈中结点类型 ElemType data; struct linknode *link; LinkNode;typedef struct / 定义栈类型 LinkNode *top; / 栈顶指针 int stacksize; / 栈的大小(可选)LinkStack; LinkStack S; 初始化: S.top=NULL; S.stacksize=0栈 空：S.top=NULL栈 满：系统内存不够1、进栈Status LinkStack_Push(LinkStack &S，ElemType e) 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、出栈Status LinkStack_Pop(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-1)+f(n-2)int f(int n) int x,y; if(n=1 | n=2) return(1); x=f(n-1); y=f(n-2); return(x+y); main() printf(%dn,f(5); 2、将十进制数转换为八进制数。例如 (1348)10=(2504)8，除8取余的过程：nn / 8n mod 8134816841682102125202void Conversion(int dec,int oct) InitStack(S); for(; dec!=0; dec=dec/8) push(S, dec%8); /* 进栈次序是个位、十位. */ for(i=0; !StackEmpty(S); i+) octi=pop(S); /* 先出栈者是高位，最后是个位 */3、括号匹配的检验Equal( (a)(b) ) : 0Equal( (a)(b) ) : 1Equal( (a)(b) ) : -1int Equal(char s) int i=0; for(i=0; si; i+) switch(si) case (: push(si); break; case ): if(StackEmpty(S) return(-1); / )多 pop(); break; if(!StackEmpty(S) return(1); / (多 return(0); / 完全匹配4、进栈出栈的组合问题 已知操作次序：push(1); pop(); push(2); push(3); pop(); pop( ); push(4); pop( ); 请写出出栈序列。5、中缀表达式求值的算法如： 1 + 2 *（3 + 4 *（5 + 6）分析：先乘除，后加减；从左到右；先括号内，再括号外。后算符前算符()#(#=一个运算是否立即执行？必须和“上一个运算符”比较优先级。 3 * 5 + 2 3 - 5 * 2 + 8“上一个运算符”存于何处？ 运算符栈对应的运算数存于何处？ 运算数栈为保证第一个运算符有“上一个运算符”： Push(OPTR,#)为保证最后一个运算符能被执行： 3*5+2#：优先级最低的运算符。运算结果：运算数栈最后的元素。跟踪示例：3*(7-2)#c=3C=*c=(c=7c=-c=2C=)c=)c=#charStack： 类型定义： 基本函数：InitStack1(charStack *); char GetTop1(charStack *); void Push1(charStack *, char); char Pop1(charS