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

《数据结构C语言版讲义.docx》由会员分享，可在线阅读，更多相关《数据结构C语言版讲义.docx（134页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一章绪论第一节什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象 的行为、特性基本一致。信息模型：信息处理领域中的数学模型。数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。忽略数据的具体含义，研究信息模型的结构特性、处理方法。第二节概念、术语一、有关数据结构的概念数据：对客观事物的符号表示。例：生活中还有什么信息没有被数字化？身份证，汽车牌号，电话号码，条形代码数据元素：数据的基本单位。相当于记录一个数据元素由若干个数据项组成，相当于“域数据对象：性质相同的数据元素的集合。数据结构：相互之

2、间存在特定关系的数据集合。四种结构形式：集合、线性、树形、图（网）状形式定义：（D, S, P）D:数据元素的集合（数据对象）S: D上关系的有限集P: D上的基本操作集逻辑结构：关系S描述的是数据元素之间的逻辑关系。存储结构：数据结构在计算机中的存储形式。顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系：逻辑结构：描述、理解问题，面向问题。存储结构：便于机器运算，面向机器。程序设计中的基本问题：逻楫结构如何转换为存储结构？二、有关数据类型的概念数据类型：值的集合和定义在该值集上的一组操作的总称。包括：原子类型、结构类型。抽象数据类型(ADT): 一个数学模型及该模型上的一组操

3、作。核心：是逻辑特性，而非具体表示、实现。课程任务：学习ADT、实践ADT。如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型实践指导：为了代码的复用性，采用模块结构。如:C中的头文件、C+中的类第三节ADT的表示与实现本教材中，算法书写习惯的约定。数据元素类型 ElemType: int, float, char, chart引用参数&算法：void add (int a, int b, int &c) c=a+b; 程序：void add(int a, int b, int *p_c) *p_c=a+b; 第四节算法的描述及分析一、有关算法的概念算法：特定问

4、题求解步骤的一种描述。1)有穷性 2)确定性 3)可行性二、算法设计的要求好算法：1)正确性2)可读性3)健壮性4)高效，低存储三、时间复杂度事箭估算：问题的规模，语言的效率，机器的速度时间复杂度：在指定的规模下，基本操作重复执行的次数。n:问题的规模。f(n):基本操作执行的次数T (n) =0 (f (n)渐进时间复杂度(时间复杂度)例：求两个方阵的乘积C = A*Bvoid MatrixMul(float an, float bn,float cn) int i, j, k;for(i=0; in; i+)/n+1for(j=0; jn; j+)/n(n+l) cij=0;/n*nfor

5、(k=0; kn; k+)/n*n*(n+1)ci j+ = ai k * bk j;/n*n*n)J时间复杂度：T()= 23+3/+2 + l =。(3)一般情况下，对循环语句只需考虑循环体中语句的执行次数，可以忽略循 环体中步长加1、终值判断、控制转移等成分。最好/最差/平均时间复杂度的示例： 例：在数组A n中查找值为k的元素。for(i=0; in-l; i+)if (Ai=k) return i ;四、常见时间复杂度按数量级递增排序：0(1) O(log2n) 0() O(nlog2n) O(n2) 0(/) 0 (2n) 0(及!) 0(nn)将指数时间算法改进为多项式时间算法：

6、伟大的成就。五、空间复杂度实现算法所需的辅助存储空间的大小。S(n)=O(f(n)按最坏情况分析。六、算法举例例1:以下程序在数组中找出最大值和最小值void MaxMin(int A, int n) int max, min, i;max=min=A0;for(i=l; imax) max=Ai;else if (AiJmax): nT 次if (Aimax): nT 次if (Ai=0;i一) f=f*x+coefi;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

7、*j;2、问:的执行次数？时间复杂度？ for(i=0; in; i+)for(j=0; j=i; j+) ai j=x;第二章线性表 线性结构：在数据元素的非空集中， 存在唯一的一个首元素， 存在唯一的一个末元素，除首元素外每个元素均只有一个直接前驱， 除末元素外每个元素均只有一个直接后继。第一节逻辑结构 形式定义：Linear_list=(D, S, P)D = ai | ai ElemSet,i=0, 1, 2,，nTS = | a1, ai D, i=l,2,，nT ap, a为序偶，表示前后关系 基本操作P：插入、删除、修改，存取、遍历、查找。 void ListAppend(Lis

8、t 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=AUBO void union (List &La, List Lb) in

9、t La_len, Lb_len;/计算表长/取Lb的第i个元素/在La中查找e/在La中插入eLa_len=ListLength(La);Lb len=ListLength(Lb); for(i=l; i=i; j)A. elemj+l = A. elemj;A. elemi=e; A. length+;2、删除ajdoai a1aiai+i an-i如何移动元素？HoHiHi-ii+i Hn-lvoid SqListDelete(SqList A, int i) for(j=i+l; jA. length; j+)A. elemj-l = A. elemj;A. length;三、效率分析

10、插入、删除时，大量时间用在移动元素上。设插入位置为等概率事件，时间复杂度？例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=

11、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) else while(pa=pa_last) while(pb123456789void del (int A口，int n) int i, k; / k是0元素的个数for(k=0, i=0; inext=p-next; p-next=q;在*p之前插入？时间复杂度？各种插入方法：首插：插入在首结点前；尾插：入在尾结点后。有序插：保持结点的顺序，插

12、在表中间；编程细节：首插：修改头指针尾插：链表为空时，修改头指针。有序插：链表为空时，修改头指针。链表不空时，可能修改头指针/首插LNODE * LinkList_InsertBeforeHead(LNODE *head, LNODE *newp) newp-next=head; return(newp); /遍历打印void LinkListPrint(LNODE *head) LNODE *p;for(p=head; p; p=p-next)printf p-data);I/尾插LNODE * LinkList_InsertAfterTail(LNODE *head, LNODE *new

13、p) 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 LinkListlnsertBeforeHead(LNODE *head, LNODE *newp) newp-next=head-next; head-next=newp;/尾插(有特殊头结点)void LinkListlnsertAfterTail(LNODE *head

14、, 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);三、单个链表的例程(设以

15、下链表有特殊头结点)例1、按序号查找：取链表第i个结点的数据元素。i l.n/注意计数次数的边界条件Status LinkList GetElemBySID(LNODE *head, int i, ElemType &e) LNODE *p; int j;for(p=head-next, j=l; p & jnext;if(p=NULL) return ERROR;e=p-data; return OK;例2、按值查找：取链表中值为e的结点的地址。LNODE * LinkListGetElemByValue(LNODE *head, ElemType e) LNODE *p;for(p=hea

16、d-next; p; p=p-next)if (p-datae) break;return(p);例3、释放链表中所有结点。void LinkListDeleteAll(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

17、*)malloc(sizeof(LNODE);if(head=NULL) head=ta i1=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-

18、next; 卸下p-next=newhead-next; newhead-next=p; 安装free(Head);return(newhead);)例6、利用线性表的基本运算，实现清除L中多余的重复节点。 352555356= 3526void 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

19、; q=q-next; 四、多个链表之间的例程(设以下链表有特殊头结点) 例1、增序线性链表的合并，设其中无相同元素。破坏La和Lb,用La和Lb的结点组合LcLNODE *LinkList_Merge(LNODE *La, LNODE *Lb) LNode *pa, *pb, *pctai 1, *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;

20、else pctail-next=pb; pctail=pb; pb=pb-next; if(pa!=NULL) pctail-next=pa;else pctail-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

21、-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链表末尾 voi

22、d 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-lLink 在*p之后插入结点*q q-rLink=p-rLink; p-rL

23、ink=q;在*p之前插入结点*qq-lLink=p;q-rLink-lLink=qI Link2、删除*p(p-lLink)-rLink=p-rLink;(p-rLink)-lLink=p-lLink;free (p);删除*p的前驱结点？删除*p的后继结点？第七节实例：一元多项式的存储、运算一、多项式的存储结构f (x) - anxn +a2X2+ aiX + a。1、顺序结构int coefMAX;f (x) = 14x10l+ 5x50 - 3 2、链式结构 typedef struct polynode int coef;int index;struct node *next;Pol

24、yNode;3、示例输入数据(指数无序)输出多项式 (指数降序)多项式1多项式2count=2coef=5, index=3coef=l,index=5count=3coef=2,index=7coef=7, index=2count=4coef=2, index=7coef=l, index=5coef=6, index=3coef=ll, index=3 coef=7, index=24、结构细节设计带特殊头结点的单向链表；结点按指数降序排列；特殊头结点的index域：多项式的项数。5、程序框架设计main () PolyNode *L1, *L2;PolyNode Print(LI);P

25、olyNodePrint(L2);/ L1+L2=L1Ll=PolyNode_Create();L2=PolyNode_Create();PolyNode_Add(Ll, L2);PolyNode Print(LI);void PolyNodePrint(PolyNode *head) PolyNode *p;printf (count=%dn”, head-index); 打印项数for (p=head-next; p; p=p-next)printf (，zcoef=%d, index=%dn”, p-coef, p-index);二、以插入为基础的算法1、将*newp插入到降序链表*he

26、ad中void PolyNodeinsert(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

27、; free(p); head-index一; )I2、利用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); PolyNodeinsert(head, newp);return(head);I3、利用PolyNode_Insert函数，实

28、现多项式加法/ L1+L2=L1 不破坏L2链表void PolyNodeAdd(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; PolyNode insert(LI, newp);)时间复杂度？设LI长度为M, L2长度为N,则0(M*N)。三、两表合并算法void PolyNode_Add(PolyNode *L1, PolyNode *L2

29、) 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 next; / 小心：准备在*plpre 后插入*

30、p2 p2-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) ; / 删除*plpl=plpre-next; / 保持 plpre 和 pl 的关系 / switch/ while

31、if (p2) plpre-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取栈顶元素Get

32、Top判别栈空 StackEmpty/栈满 StackFull3、栈的应用背景许多问题的求解分为若干步骤，而当前步骤的解答，是建立在后继步骤的 解答基础上的。=问题分解的步骤和求解的步骤次序恰好相反。二、顺序存储结构动态顺序存储结构：存储空间随栈的大小而变化。#define STACK_INIT_SIZE 100 初始化时分配的空间typedef struct定义栈类型 ElemType *base, *top;栈底、栈顶指针int stacksize;栈的存储空间大小SqStack;SqStack S;定义一个栈结构1、初始化栈Status SqStack lnit(SqStack &S)

33、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+;re

34、turn (OK);3、出栈算法Status SqStack Pop(SqStack &S, ElemType &e) if (S. top=S. base) return(UNDERFLOW);S. top-; e=S. top;return(OK);缺点：空间浪费思考：二栈合用同一顺序空间？0maxizei/A“%&t Tt600 161#define maxsize=100int stackmaxsize, topO=0, topl=maxsize-l;int pushO(int e) if(topO topi) return(0);stacktopO=e; topO+;return(1

35、);int pushl(int e) if (topO topi) return(0); stacktopl=e; topi;return (1);)int popO(int *e) if(top0=0) return(0);int popl(int *e) if(top0=0) return(0);topO-; *e=stacktopO; return(1);topO+; *e=stacktopl;return(1);三、链栈typedef struct linknode / 栈中结点类型 ElemType data;struct linknode *link;LinkNode;typede

36、f struct LinkNode *top; int stacksize;/定义栈类型/栈顶指针/栈的大小（可选）LinkStack;LinkStack S;初始化：S. top=NULL; S. stacksize=O栈空：S. top=NULL栈满：系统内存不够1、进栈Status LinkStackPush(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

37、=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-l)+f (n-2)int f (int n) int x, y;if(n=l | n=2) return(1);x=f (n-1);y=f(n-2);return(x+y);mainO printf 0%dn”, f (5); 2、将十进制数转换为八进制数。例如(1348) |。= (2504)8,除8取余的过程：nn / 8n mod 8134816841682102125202void Conversion(int dec,int oct) InitStack(S);for(; dec!=0; dec=dec/8)push (S