数据结构课件.docx

第一章 绪论例： 计算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;/*插入位置出错*/*表-满*/*数据元素后移*/*插入x*Z/*长度加1*/if(i<O|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;ifi(i<O|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_length=Length(Lb); /*取表 La,Lb 的长度*/Initiate(Lc);/*初始化表 Lc*/While (i<=La_length&&j<=Lb_length) a=get(La,i)；b=get(Lbj);if(a<b) 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 (j<=lb_length) b=get(Laj);insert(Lc,-H-k,b); P21例如：下面定义的结点类型中，数据域包含三个数据项：学号、姓名、成绩。Struct student char num8;/*数据域*/har name8;/* 数据域*/int score;/*数据域*/struct student *next;/*指针域*/P21单链表结点结构定义为：Typedef struct slnode Elemtype data;struct slnode *next;Jslnodetype;slnodetype *p,*q,*s;P21【算法2.3单链表的初始化】int lnitiate(slnodetype * *h)if(*h=(slnodetype*)malIoc(sizeofslnodetype)=NlJLL) return FALSE;(*h)->next=NULL; return TRUE; P22【算法2.4单链表的后插入】 s=(slnodetype*)malloc(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;while(p!=NULL&&j<i-l) p=q->next;j+;/*寻找第 i-1 个结点*/if(j!=i-l) printfC'Error!");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的结点不存在，则将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(d>0)p=(struct slnode*)malloc(sizeof|struct slnode); /*中请一个新结点*/ p->data=d;p->next=NULL;if(head=NULL) head=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 Delet(slnodetype *h,int i) /*在链表h中删除第i个结点*/slnodetype *p,*s;intj;p=hJ=O;while(p->next !=NU LL&&j<i-1) p=p->next;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)slnodetype *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(dlnodetype *head,int i,EIemtype x)/*在带实结点的双向链表中第i个位置之前插入元素x*/dlnodetype *p,*s;intj;p=head;j=0；while (p!=NULL&&j<i) p=p->next;j+；if(j!=i|i<l) printf(k4Error!M);return FALSE;if(s=(dlnodetype *)malloc(sizeof(dlnodetype)=NLJLL) return FALSE;s->data=x;s>prior=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;intj；p=head;j=0；while (p!=NULL&&j<i) p=p->next; j+；if(j!=i|i<l)printfC'Error!");return FALSE; s=p； p->prior->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作为相加后的和链表*/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->exp<qb->exp) r->next=qa;r=qa;qa十十; /*多项式 Ah 的指数值小， else r->next=qb;r=qb;qb-H-;/*多项式 Bh 的指数值小*/ 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 initStack(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)/*若栈s不为空，则删除栈顶元素*/Elemtype x;if(s->top<0) return NULL;/*栈空曾x=s->stacks->top;s->top;return x;P39【算法3.4取栈顶元素】Elemtype getTop(sqstack *s)/*若栈s不为空，则返回栈顶元素*/ifl：s->top<0) return NULL;/*栈空曾return (s->stacks->top);P40【算法3.5判栈空操作】int Empty(sqstack *s)/*栈s为空时，返回为TRUE：非空时，返回为FALSE*/ ifls->top<0) return TRUE;return FALSE;)P40【算法3.6栈置空操作】void setEmpty(sqstack *s)/*将栈s的栈顶指针lop,置为“*/s->top= -1;)P40 C语言定义的这种两栈共享邻接空间的结构如下：Typedef struct Elemtype stackMAXNUM;int lefttop;/*左栈栈顶位置指示器*/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,Elemtype 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=，U)或右栈(status=,R')退出栈顶元素*/ ifistatus= ='L')if (s->lefttop<0)return NULL;/*左栈为空*/else return (s->stacks->lefttop-);/*左栈出栈*/else if|status= ='R')if (s->righttop>MAXNUM-1)return NULL;/*右栈为空*/else return (s->stacks->righttop-H-);/*右栈出栈*/)else return NULL;/*参数错误*/P42链栈的C语言定义为:typedef struct Stacknode Elemtype data;Struct Stacknode *next;sIStacktype;P43【算法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;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=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 ”stdlib.h"#include "string.h"typedef 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;ifs->top<0) return NULL;/*栈空*/x=s->stacks->top; s->top; return x; ) char gettop(sqstack *s) /*若栈s不为空，则返回栈顶元素*/if(s->top<0) return NULL;/*栈空*/return (s->stacks->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&&strstr(,'+-*/)#sting)!=NULL) result*;else i«x 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) !=,#*)inc!='+'&&c!=''&&c!="&&c!='/'&&c!='C&&c!=')'&&c!='#') printf(M%cw,c);c=s-H-i;ififcTO') break; ) else switch (precede(gettop(optr),c)case *<*: push(optr,c);c=s-H-i;break; case : pop(optr);c=s-H-i;break; case *>*:y=pop(optr);printf(M%cM,y); break; printfT%c”W);)P51用C语言定义的顺序存储结构的队列如下：# define MAXNUM <最大元素数, typedef struct Elemtype queueMAXNUM;int front; /*队头指示器*/ int rear; /*队尾指示器*/ sqqueue;P51【算法3.15顺序队列的初始化】int initQueue(sqqueue *q)/*创建一个空队列由指针q指出*/if (q=(sqqueue* )malloc(sizeofi(sqqueue)= =NULL) return FALSE; q->front= -1;q->rear=-l;return TRUE;)P52【算法3.16顺序队列的入队列操作】 int append(sqqueue *q,Elemtype x)/*将元素x插入到队列q中，作为q的新队尾*/ if<q->rear>=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不为空，则返回队头元素*/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 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(qqueue *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->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) /*创建一个空链队列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=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; free(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 *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;ifm<=0|m>j|n<0) (*s2).str0='0'(*s2).length=0;retum FALSE; /*参数错误*/k=strlen(&s 1 .strm-1 );/*求子串的长度*/if (n>k) (*s2).length=k;else (s2).length=n;/* 置子串的串长 */for(j=0<=(*s2).length(*s2).strj=sl.strm-l;(s2).strj=,0,;/* 置结束标记*/return TRUE; P66假设链表中每个结点仅存放一个字符，则单链表定义如下P66typedet struct nodechar str;struct node *next; slstrtype;【算法4.2在链式存储方式中求子串】int substr(slstrtype sl,slstrtype *s2,int m,int n)slstrtype *p»*q,*v;int lengthIj;p=&s 1;fbrflenghtl =0;p->next!=NULL;p=p->next) length 1-H-;if(m<=0|m>lengthl|n<0) s2=NULL;retum FALSE;p=sl.next;fbr(j=O;j<mj-H-) p=p->next;s2=(slstrtype *)malloc(sizeof(slstrtype);v=s2;q=v;fbr(j=O;j<n&&p->next!=NULLj-H-) q->str=p->str;p=p->next;q=(slstrtype )malloc(sizeo.slstrtype);v->next=q;v=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(m<=0|m>j|n<0) s2->length=0;retum FALSE;/*参数错误*/k=strlen(sl.str+m);/*主串第m个位置开始之后的串长*/if (n>k) 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(m<=0|m>j|n<0) s2->Iength=0;retum FALSE;/*参数错误*/k=strlen(sl .str+m);/*主串第m个位置开始之后的串长*/if (n>k) s2->length=k;else s2->length=n;k=s2->length;/*置子串的串长*/fbr(j=Oj<kj+) s2->strj=sl .strm+;/*复制字符*/s2->strj=,0,; return TRUE;/*置结束符*/P68例main()int a,b,c