《数据结构课件.docx》由会员分享，可在线阅读，更多相关《数据结构课件.docx（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章 绪论例： 计算fM! +2! +3! +n!,用C语言描述。 void factorsum (n)int n；int i, j；int f, w；f=0；for (i=l； i (=n； i+)w=l ；for (j=l ； j=i； j+)w=w*j ；return ；第二章线性表P161算法2.1顺序表的插入】int lnsert(Elemtype List,int *num,int i,Elemtype x)/*在顺序表List中，*num为表尾元素下标位置，在第i个元素前插入数据元素x,若成功，返回 TRUE,否则返回 FALSE。/intj;/*插入位置出错*/*表-满*/*
2、数据元素后移*/*插入x*Z/*长度加1*/if(i*num+l)prin 国“Error!”);return FALSE;if(*num=MAXNUM-l)primfCoverflow!);return FALSE; fbr g=*numj=i;j-) ListU+l=Listj;Listi=x;(*num)-H-;return TRUE;P18【算法2.2顺序表的删除】int Delete(Elemtype List,int *num,int i)/*在线性表List中，*num为表尾元素下标位置，删除第i个长度，线性表的长度减1,若成功, 则返回TRUE；否则返回FALSE。/intj;
3、ifi(i*num)printfCError!)；return FALSE;/*删除位置出错！ /fbr(j=i+1Listj-l=Listj;/* 数据元素前移 */(num)-;/* 长度减 1*/return TRUE; P19 例：将有序线性表 La=2,4,6,7,9, Lb= 1,5,7,8,合并为 Lc= 1,2,4,5,6,7,7,8,9。void merge(Elemtype La,Elemtype Lb,Elemtype *Lc) int ij,k;int La_length,Lb_length;i=j=O;k=O;La_length=Length(La);Lb_lengt
4、h=Length(Lb); /*取表 La,Lb 的长度*/Initiate(Lc);/*初始化表 Lc*/While (i=La_length&j=Lb_length) a=get(La,i)；b=get(Lbj);if(ab) insert(Lc,+k,a);-H-i;else insert(Lc,+k,b);-H-j;/*将La和Lb的元素插入到Lc中*/while (i=La_length) a=get(La,i)；insert(Lc,-H-k,a);while (jnext=NULL; return TRUE; P22【算法2.4单链表的后插入】 s=(slnodetype*)mal
5、loc(sizeof(slnodetype);s-data=x;s-next=p-next;p-next=s;P22【算法2.5单链表的结点插入】q=head;whi le(q-next! =p) q=q-next;s=(slnodetype*)malloc(sizeof(slnodetype);s-data=x;s-next=p;q-next=s;P23【算法2.6单链表的前插入】int insert(slnodetype *h,int i,Elemtype x)/*在链表h中，在第i个数据元素前插入一个数据元素x*/ slnodetype *p,*q,*s;int j=0;P=h;whil
6、e(p!=NULL&jnext;j+;/*寻找第 i-1 个结点*/if(j!=i-l) printfCError!);retum FALSE;/*插入位置错误*/if (s=(s!nodetype*)malloc(sizeof(slnodetype)=NULL) return FALSE; s-data=x;s-next=p-next;q-next=s;return TRUE;P23例：下面C程序中的功能是，首先建立一个线性链表head=3, 5, 7, 9,其元素值依 次为从键盘输入正整数(以输入一个非正整数为结束)；在线性表中值为x的元素前插入一 个值为y的数据元素。若值为x的结点不存在
7、，则将y插在表尾。#include stdlib.h#include sldio.h struct slnode int data;struct slnode *next;/*定义结点类型*/main()int x,y,d;struct slnode *head,*p,*q,*s;head=NULL;/* 置链表空*/q=NULL; scanf(d”,&d); /*输入链表数据元素*/ while(d0)p=(struct slnode*)malloc(sizeof|struct slnode); /*中请一个新结点*/ p-data=d;p-next=NULL;if(head=NULL) h
8、ead=p; /*若链表为空，则将头指针指向当前结点p*/ else q-next=p;/*链表不为空时，则将新结点链接在最后*/q=p； /*将指针q指向链表的最后一个结点*/scanfr%d”,&d);scanfT%d,%d”,&x,&y);s=(struct slnode*)malloc(sizeof(struct slnode);s-data=y;q=head;p=q-next;while(p!=NULL)&(p-data!=x) q=p;p=p-next; /*查找元素为 x 的指针*/s-next=p;q-next=s; /*插入元素 y*/)P24【算法2.7单链表的删除】int
9、 Delet(slnodetype *h,int i) /*在链表h中删除第i个结点*/slnodetype *p,*s;intj;p=hJ=O;while(p-next !=NU LL&jnext;j=j+l;/*寻找第i-1个结点,p指向其前驱*/printfCError!); /*删除位置错误!*/return FALSE; s=p-next;p-next=p-next-next; /*删除第 i 个结点*/Gee；/*释放被删除结点空间*/return TRUE;P25例：假设已有线性链表La,编制算法将该链表逆置。void converse(slnodetype *head)slno
10、detype *p,*q;p=head-next;head-next=N ULL;whi!e(p!=NULL) q=p-next;p-next=head-next;head-next=p;p=q;)P27例：将两个循环链表首尾相接。La为第一个循环链表表尾指针，Lb为第二个循环链表 表尾指针。合并后Lb为新链表的尾指针。Void merge( slnodetype * La,slnodetype *Lb) slnodetype *p;p=La-next;Lb-next= La-next;La-next=p-next;free;P29【算法2.8双向链表的插入】int insert_dul(dl
11、nodetype *head,int i,EIemtype x)/*在带实结点的双向链表中第i个位置之前插入元素x*/dlnodetype *p,*s;intj;p=head;j=0；while (p!=NULL&jnext;j+；if(j!=i|idata=x;sprior=p-prior; /*图中步骤*/p-prior-next=s; /图中步骤*/s-next=p; /*图中步骤*/p-prior=s; /图中步骤*/return TRUE;P30【算法2.9双向链表的删除】int Delete_dl(dlnodetype *head,int i) dlnodetype *p,*s;i
12、ntj；p=head;j=0；while (p!=NULL&jnext; j+；if(j!=i|iprior-next=p-next;/* 图中步骤*/p-next-prior=p-prior;/* 图中步骤*/free(s);return TRUE;P32【算法2.1()多项式相加】struct poly *add_poly (struct poly * Ah, struct poly *Bh)struct poly *qa?*qb,*s,*r,*Ch;qa=Ah-next;qb=Bh-next; /*qa和qb分别指向两个链表的第一结点*/ i-qa;Ch=Ah;六将链表Ah作为相加后的和
13、链表*/while(qa!=NULL&qb!=NULL)产两链表均非空*/if (qa-exp=qb-exp)/*两者指数值相等*/x=qa-coefi-qb-coe f; if(x!=0) qa-coef=x;r-next=qa;r=qa; s=qb +十;free(s);qa-H-; 产相加后系数不为零时*/else s=qa-H-;free(s);s=qb-H-;free(s);/*相加后系数为零时*/ else ilqa-expexp) r-next=qa;r=qa;qa十十; /*多项式 Ah 的指数值小， else r-next=qb;r=qb;qb-H-;/*多项式 Bh 的指数
14、值小*/ if(qa=NULL) r-next=qb; else r-next=qa;/*链接多项式Ah或Bh中的剩余结点*/return (Ch); )第三章栈和队列P35相应的C语言函数是： float factfint n) float s; if(n=0|n=l) s=l; else s=n*fact(n-l ); return (s); P38用C语言定义的顺序存储结构的栈如下：# define MAXNUM v最大元素数, typedef struct Elemtype stack MAXNUM; int top; sqstack;P39【算法3.1栈的初始化】int initSt
15、ack(sqstack *s)/*创建一个空栈由指针S指出列if (s=(sqstack*)malloc(sizeof|sqstack)= =NULL) return FALSE;s-top= -1; return TRUE; )P39【算法3.2入栈操作】int push(sqstack *s, Elemtype x)/*将元素x插入到栈s中，作为s的新栈顶*/i s-top=M AXN UM-1) return FALSE;/* 栈满*/s-top-H-;s-stacks-top=x;return TRUE; )P39【算法3.3出栈操作】Elemtype pop(sqstack *s)/
16、*若栈s不为空，则删除栈顶元素*/Elemtype x;if(s-topstacks-top;s-top;return x;P39【算法3.4取栈顶元素】Elemtype getTop(sqstack *s)/*若栈s不为空，则返回栈顶元素*/ifl：s-topstacks-top);P40【算法3.5判栈空操作】int Empty(sqstack *s)/*栈s为空时，返回为TRUE：非空时，返回为FALSE*/ ifls-toptop= -1;)P40 C语言定义的这种两栈共享邻接空间的结构如下：Typedef struct Elemtype stackMAXNUM;int lefttop
17、;/*左栈栈顶位置指示器*/int righttop;/*右栈栈顶位置指示器*/ dupsqstack;P41【算法3.7共享栈的初始化】int initDupStack(dupsqstack *s)/*创建两个共享邻接空间的空栈由指针S指出*/if (s=(dupsqstack*)malloc(sizeof(dupsqstack)= =NULL) return FALSE;s-lefttop= -1;s-righttop=MAXN U M;return TRUE;P41【算法3.8共享栈的入栈操作】int pushDupStack(dupsqstack *s,char status,Elem
18、type x)广把数据元素x压入左栈(status=1D或右栈(status=，RD / ifl；s-lefttop+l= =s-righttop) return FALSE;/*栈满*/iWstatus=L) s-stack-H-s-lefttop=x;/* 左栈进栈else if(status=,R,) s-stacks-righttop=x;/*右栈进栈*/else return FALSE;/* 参数错误*/return TRUE;P42【算法3.9共享栈的出栈操作】Elemtype popDupStack(dupsqstack *s,char status)/*从左栈(status=
19、，U)或右栈(status=,R)退出栈顶元素*/ ifistatus= =L)if (s-lefttopstacks-lefttop-);/*左栈出栈*/else if|status= =R)if (s-righttopMAXNUM-1)return NULL;/*右栈为空*/else return (s-stacks-righttop-H-);/*右栈出栈*/)else return NULL;/*参数错误*/P42链栈的C语言定义为:typedef struct Stacknode Elemtype data;Struct Stacknode *next;sIStacktype;P43【
20、算法3.10单个链栈的入栈操作】int pushLstack(sIStacktype *top,Elemtype x)/*将元素x压入链栈top中*/slStacktype *p;iR(p=(slStacktype *)malloc(sizeof(slStacktype)= =NULL) return FALSE; /* 申请一个结 点*/p-data=x; p-next=top; top=p; return TRUE;P43【算法3.11单个链栈的出栈操作】Elemtype popLstack(slStacktype *top)/*从链栈top中删除栈顶元素*/slStacktype *p;
21、Elemtype x;if(top= =NULL) return NULL;/*空栈*/p=top; top=top-next;x=p-data;free(p);retum x;P44【算法3.12多个链栈的入栈操作】int pushDupLs(slStacktype *topM,int i,Elemtype x)/*将元素x压入链栈topi + */slStacktype *p;iR(p=(slStacktype *)malloc(sizeof|slStacktype)= =NULL) return FALSE; /*申请一个结点*/ p-data=x; p-next=topi; topi=
22、p; return TRUE;P44【算法3.13多个链栈的出栈操作】Elemtype popDupLs(slStacktype *topM,int i)/*从链栈topi中删除栈顶元素*/slStacktype *p;Elemtype x;if(topi= =NULL) return NULL;/*空栈*/p=topi; topi=topi-next;x=p-data;free(p);retum x;P47【算法3.14中缀表达式变为后缀表达式】# define MAXNUM 40# define FALSE 0# define TRUE 1#include stdio.h”#include
23、 ”stdlib.h#include string.htypedef struct char stackMAXNUM;int top; sqstack;int initStack(sqstack *s)/*初始化栈*/s-top=-1;return TRUE;)int push(sqstack *s,char x)/*将元素x插入到栈s中，作为s的新栈顶*/ifs-top=MAXNUM-l) return FALSE; /*栈满*/S-top-H-；s-stacks-top=x;return TRUE;char pop(sqstack *s)/*若栈s不为空，则删除栈顶元素*/char x;i
24、fs-topstacks-top; s-top; return x; ) char gettop(sqstack *s) /*若栈s不为空，则返回栈顶元素*/if(s-topstacks-top); ) char precede(char x 1 ,char x2) /*比较运算符xl与x2的优先*/ char result-*;char sting2;sting0=x2;stingl=MT;if(xl=,+,|xl=-,)&(strstr(,+-)#,sting)!=NULL)| (xl=,*,|xl=7,)&strstr(,+-*/)#,sting)!=NULL)| (xl=7&strst
25、r(,+-*/)#sting)!=NULL) result*;else ix 1 =,(,&x2=,),|x 1 =,#,&x2=,#) result-;else if(xl =)&x2=,(l|x 1 =,#&x2=,)1) result- *;)return result; main()sqstack *optr;char s80,c,y; int i=0;optr=(sqstack *)malloc(sizeof(sqstack);gets(s);initStack(optr); push(optr,#);c=si;while(c !=*#| Igettop(optr) !=,#*)in
26、c!=+&c!=&c!=&c!=/&c!=C&c!=)&c!=#) printf(M%cw,c);c=s-H-i;ififcTO) break; ) else switch (precede(gettop(optr),c)case *:y=pop(optr);printf(M%cM,y); break; printfT%c”W);)P51用C语言定义的顺序存储结构的队列如下：# define MAXNUM front= -1;q-rear=-l;return TRUE;)P52【算法3.16顺序队列的入队列操作】 int append(sqqueue *q,Elemtype x)/*将元素x插
27、入到队列q中，作为q的新队尾*/ ifrear=MAXNUM-l) return FALSE; /*队列满*/ q-rearH;q-queueq-rear=x;return TRUE;P52【算法3.17顺序队列的出队列操作】Elemtype delete(sqqueue *q)/*若队列q不为空，则返回队头元素*/Elemtype x;iRq-rear= =q-front) return NULL;/* 队列空*/x=q-queue-H-q-front;return x;P52【算法3.18顺序队列的取头元素操作】Elemtype getHead(sqqueue *q)/*若队列q不为空，则
28、返回队头元素*/ifq-rear= =q-front) return NULL;/队列空*/return (q-queues-front+1 );)P52【算法3.19顺序队列的非空判断操作】int Empty(sqqueue *q)/*队列q为空时，返回TRUE；否则返回FALSE*/if (q-rear= =q-front) return TRUE;return FALSE;)P53【算法3.20顺序队列的求长度操作】int length(sqqueue *q)/*返回队列q的元素个数*/re tum(q-rear-q- front);)P54用C语言定义循环队列结构如下：typedef
29、structElemtype queueMAXNUM;int fhmt; /*队头指示器*/int rear; /*队尾指示器*/int s; /*队列标志位*/qqueue;P54【算法3.21循环队列的初始化】int initQueue(qqueue *q)/*创建一个空队列由指针q指出*/if (q=(qqueue*)malloc(sizeof(qqueue)= =NULL) return FALSE;q-front= MAXNUM;q-rear=MAXNUM;q-s=0;/*置队列空*/return TRUE;)P55【算法3.22循环队列的入队列操作】int append(qqueu
30、e *q,Elemtype x)/*将元素x插入到队列q中，作为q的新队尾*/if ( q-s= =l)&(q-front= =q-rear) return FALSE;/*队列满*/q-rearH-;if (q-rear= =MAXNUM) q-rear=0;q-queueq-rear=x;q-s=l;/*置队列非空*/return TRUE;P55【算法3.23循环队列的出队列操作】Elemtype delete(qqueue *q)/*若队列q不为空，则返回队头元素*/Elemtype x;if(q-s= =0) retrun NULL;/*队列为空*/q-front-H-;if (q-
31、front= =MAXNUM) q-front=0; x=q-queueq- front;if (q-front = =q-rear) q-s=0;/* 置队列空*/return x;P56用C语言定义链队列结构如下： typedef struct Qnode Elemtype data;struct Qnode *next;JQnodetype; /*定义队列的结点/ typedef struct Qnodetype 头指针*/ Qnodetype *rear; /* 尾指针*/ Lqueue;P56【算法3.24链队列的初始化】int initLqueue(Lqueue *q) /*创建一
32、个空链队列q*/if (q-front=(Qnodetype*)malloc(sizeonQnodetype)= =NULL) return FALSE; q-rear=q-front;q- front-next=N U LL; return TRUE;P561算法3.25链队列的入队列操作】 int Lappend(Lqueue *q,Elemtype x) /*将元素x插入到链队列q中，作为q的新队尾*/ Qnodetype *p;if (p=(Qnodetype*)malloc(sizeof(Qnodetype)= =NULL) return FALSE; p-data=x;p-next
33、=NULL;/*置新结点的指针为空*/q-rear-next=p;/*将链队列中最后一个结点的指针指向新结点*/q-rear=p;/*将队尾指向新结点*/return TRUE; P57【算法3.26链队列的出队列操作】Elemtype Ldelete(Lqueue *q)/*若链队列q不为空，则删除队头元素，返回其元素值*/ Elemtype x;Qnodetype *p;ifiq-front-next= =NULL) return NULL;/*空队列*/P=q-front-next;/* 取队头 */q-front-next=p-next;/* 删除队头结点*/x=p-data; fre
34、e(p); return x; 第四章串P62用字符数组存放字符串时;其结构用C语言定义如下：#define MAXNUM(允许的最大的字符数typedef struct char strfMAXNUM; int length; /* 串长度*/ stringtype; /串类型定义*/ P62用链表存放字符串时，其结构HC语言定义如下： typedef struct node char str;struct node *next; slstrtypeiP63用块链存放字符重时，其结构用C语言定义如下： typedef struct node ) char str4;struct node *
35、next; slstrtype;P63用堆存放字符串时，其结构用C语言定义如下：typedef structchar *str;int length; HSstrtype;P65 C语言中用字符数组存储字符串时，结构定义如下：#define MAXNUM 80typedef struct char strfMAXNUM;int length; /* 串长度*/ stringtype; /* 串类型定义*/P65【算法4.1在静态存储方式中求子串】int substr(stringtype s 1 ,stringtype * s2,int m,int n) int j,kj=sl.length;
36、ifmj|nk) (*s2).length=k;else (s2).length=n;/* 置子串的串长 */for(j=0next!=NULL;p=p-next) length 1-H-;if(mlengthl|n0) s2=NULL;retum FALSE;p=sl.next;fbr(j=O;jnext;s2=(slstrtype *)malloc(sizeof(slstrtype);v=s2;q=v;fbr(j=O;jnext!=NULLj-H-) q-str=p-str;p=p-next;q=(slstrtype )malloc(sizeo.slstrtype);v-next=q;v=
37、q；/*求主串和串长*/*参数错误*/*找到子串和起始位置*/*分配子串和第一个结点*/*建立子串*/P67P67q-str=,O,;q-next=NULL;/* 置子串和尾结点*/return TRUE; 堆存储结构用C语言定义为： typedet struct char *str; int length; HSstrtype;【算法4.3共享法求子串】int substr(HSstrtype sl,HSstrtype *s2,int m,int n) intj,k;j=sl.length;if(mj|nlength=0;retum FALSE;/*参数错误*/k=strlen(sl.str
38、+m);/*主串第m个位置开始之后的串长*/if (nk) s2-length=k; else s2-length=n;/* 置子串的串长*/s2-str=sl.stH-m;/*置子串的串首地址return TRUE; P67【算法4.4前新赋值法求子串】int substr(HSstrtype sl,HSstrtype *s2,int m,int n)intj,k;j=sl.length;ifi(mj|nIength=0;retum FALSE;/*参数错误*/k=strlen(sl .str+m);/*主串第m个位置开始之后的串长*/if (nk) s2-length=k;else s2-length=n;k=s2-length;/*置子串的串长*/fbr(j=Ojstrj=sl .strm+;/*复制字符*/s2-strj=,0,; return TRUE;/*置结束符*/P68例main()int a,b,c