精品数据结构数据结构

1、第一章 绪论例： 计算f=1！+2！+3！+n！，用c语言描述。void factorsum（n）int n；int i，j；int f，w；f=0；for （i=1；i=n；i+）w=1；for （j=1；j=i；j+）w=w*j；f=f+w；return；第二章 线性表p16【算法2.1 顺序表的插入】int insert(elemtype list,int *num,int i,elemtype x)/*在顺序表list中，*num为表尾元素下标位置，在第i个元素前插入数据元素x，若成功，返回true，否则返回false。*/int j; if (i*num+1) printf(“err

2、or!”); /*插入位置出错*/ return false; if (*num=maxnum-1) printf(“overflow!”); return false; /*表已满*/for (j=*num;j=i;j-)listj+1=listj; /*数据元素后移*/listi=x; /*插入x*/(*num)+; /*长度加1*/return true;p18【算法2.2 顺序表的删除】int delete(elemtype list,int *num,int i)/*在线性表list中，*num为表尾元素下标位置，删除第i个长度，线性表的长度减1，若成功，则返回true；否则返回fa

3、lse。*/int j;if(i*num)printf(“error!”); return false; /*删除位置出错！*/ for(j=i+1;j=*num;j+) listj-1=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 i,j,k; int la_length,lb_length; i=j=0;k=0; la

4、_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(lb,j); if(ab) insert(lc,+k,a);+i; else insert(lc,+k,b);+j; /*将la和lb的元素插入到lc中*/while (i=la_length) a=get(la,i);insert(lc,+k,a);while (jnext=null; return true; p22 【算法2.4 单

5、链表的后插入】 s=(slnodetype*)malloc(sizeof(slnodetype); s-data=x; s-next=p-next;p-next=s;p22 【算法2.5 单链表的结点插入】q=head; while(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 */ s

6、lnodetype *p,*q,*s; int j=0; p=h; while(p!=null&jnext;j+; /*寻找第i-1个结点*/ if ( j!=i-1) printf(“error!”);return false; /*插入位置错误*/ if (s=(slnodetype*)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，其元素值依次为从键盘输入正整数（以输入一个非

7、正整数为结束）；在线性表中值为x的元素前插入一个值为y的数据元素。若值为x的结点不存在，则将y插在表尾。#include “stdlib.h”#include “stdio.h”struct slnodeint 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

8、); /*申请一个新结点*/ p-data=d; p-next=null; if(head=null) head=p; /*若链表为空，则将头指针指向当前结点p*/ else q-next=p; /*链表不为空时，则将新结点链接在最后*/ q=p; /*将指针q指向链表的最后一个结点*/ scanf(“%d”,&d); scanf(“%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; /

9、*查找元素为x的指针*/ s-next=p;q-next=s; /*插入元素y*/p24【算法2.7 单链表的删除】int delet(slnodetype *h,int i) /*在链表h中删除第i个结点*/ slnodetype *p,*s; int j; p=h;j=0; while(p-next!=null&jnext;j=j+1; /*寻找第i-1个结点,p指向其前驱*/ if(j!=i-1) printf(“error!”); /*删除位置错误!*/ return false; s=p-next; p-next=p-next-next; /*删除第i个结点*/ free(s); /

10、*释放被删除结点空间*/ return true;p25例：假设已有线性链表la，编制算法将该链表逆置。void converse(slnodetype *head)slnodetype *p,*q; p=head-next; head-next=null; while(p!=null) q=p-next; p-next=head-next; head-next=p; p=q; p27例：将两个循环链表首尾相接。la为第一个循环链表表尾指针，lb为第二个循环链表表尾指针。合并后lb为新链表的尾指针。void merge(slnodetype *la,slnodetype *lb) slnode

11、type *p; p=la-next; lb-next= la-next; la-next=p-next; free(p); p29【算法2.8 双向链表的插入】int insert_dul(dlnodetype *head,int i,elemtype x)/*在带头结点的双向链表中第i个位置之前插入元素x*/ dlnodetype *p,*s; int j; p=head; j=0; while (p!=null&jnext; j+; if(j!=i|idata=x;s-prior=p-prior; /*图中步骤*/p-prior-next=s; /*图中步骤*/s-next=p; /*图

12、中步骤*/p-prior=s; /*图中步骤*/return true;p30【算法2.9 双向链表的删除】int delete_dl(dlnodetype *head,int i) dlnodetype *p,*s; int j; 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.10 多项式相加】struct poly *add_poly(struct poly *ah,struc

13、t poly *bh)struct poly *qa,*qb,*s,*r,*ch;qa=ah-next;qb=bh-next;/*qa和qb分别指向两个链表的第一结点*/r=qa;ch=ah;/*将链表ah作为相加后的和链表*/while(qa!=null&qb!=null) /*两链表均非空*/ if (qa-exp=qb-exp) /*两者指数值相等*/ x=qa-coef+qb-coef; if(x!=0) qa-coef=x;r-next=qa;r=qa; s=qb+;free(s);qa+; /*相加后系数不为零时*/ else s=qa+;free(s);s=qb+;free(s)

14、; /*相加后系数为零时*/ else if(qa-expexp) r-next=qa;r=qa;qa+; /*多项式ah的指数值小*/ else r-next=qb;r=qb;qb+; /*多项式bh的指数值小*/if(qa=null) r-next=qb; else r-next=qa; /*链接多项式ah或bh中的剩余结点*/return (ch);第三章 栈和队列p35相应的c语言函数是：float fact(int n)float s; if (n= =0|n= =1) s=1; else s=n*fact(n-1); return (s); p38用c语言定义的顺序存储结构的栈如下

15、：# define maxnum typedef struct elemtype stackmaxnum;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的新栈顶*/ if(s-top=maxnum-1)

16、return false; /*栈满*/ s-top+; s-stacks-top=x;return true;p39【算法3.3 出栈操作】elemtype pop(sqstack *s)/*若栈s不为空，则删除栈顶元素*/elemtype x; if(s-topstacks-top; s-top-;return x;p39【算法3.4 取栈顶元素】elemtype gettop(sqstack *s)/*若栈s不为空，则返回栈顶元素*/ if(s-topstacks-top); p40【算法3.5 判栈空操作】int empty(sqstack *s)/*栈s为空时，返回为true；非空时

17、，返回为false*/ if(s-toptop= -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-l

18、efttop= -1;s-righttop=maxnum;return true;p41【算法3.8 共享栈的入栈操作】int pushdupstack(dupsqstack *s,char status,elemtype x)*把数据元素x压入左栈（status=l）或右栈（status=r）*/ if(s-lefttop+1= =s-righttop) return false; /*栈满*/ if(status=l) s-stack+s-lefttop=x; /*左栈进栈*/ else if(status=r) s-stack-s-righttop=x; /*右栈进栈*/ else re

19、turn false; /*参数错误*/return true;p42【算法3.9 共享栈的出栈操作】elemtype popdupstack(dupsqstack *s,char status)/*从左栈（status=l）或右栈（status=r）退出栈顶元素*/ if(status= =l) if (s-lefttopstacks-lefttop-); /*左栈出栈*/ else if(status= =r) if (s-righttopmaxnum-1) return null; /*右栈为空*/else return (s-stacks-righttop+); /*右栈出栈*/ el

20、se return null; /*参数错误*/p42链栈的c语言定义为：typedef struct stacknode elemtype data;struct stacknode *next;slstacktype;p43【算法3.10 单个链栈的入栈操作】int pushlstack(slstacktype *top,elemtype x)/*将元素x压入链栈top中*/slstacktype *p;if(p=(slstacktype *)malloc(sizeof(slstacktype)= =null) return false;/*申请一个结点*/p-data=x; p-next

21、=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);return x;p44【算法3.12 多个链栈的入栈操作】int pushdupls(slstacktype *topm,int i,elemtype x)/*将元素x压入链栈topi中*/slstack

22、type *p;if(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

23、-data;free(p);return 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的新栈顶

24、*/ if(s-top=maxnum-1) return false; /*栈满*/ s-top+;s-stacks-top=x;return true;char pop(sqstack *s)/*若栈s不为空，则删除栈顶元素*/char x; if(s-topstacks-top;s-top-;return x;char gettop(sqstack *s)/*若栈s不为空，则返回栈顶元素*/ if(s-topstacks-top);char precede(char x1,char x2)/*比较运算符x1与x2的优先*/char result=;else if(x1=(&x2=)|x1=

25、#&x2=#) result=;else if (x1=)&x2=(|x1=#&x2=) 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!=#|gettop(optr)!=#) if(c!=+&c!=-&c!=*&c!=/&c!=(&c!=)&c!=#) printf(%c,c);c=s+i; if(c=0) brea

26、k; else switch (precede(gettop(optr),c) case :y=pop(optr); printf(%c,y); break; printf(%c,#);p51 用c语言定义的顺序存储结构的队列如下：# define maxnum typedef struct elemtype queuemaxnum; int front; /*队头指示器*/ int rear; /*队尾指示器*/ sqqueue;p51【算法3.15 顺序队列的初始化】int initqueue(sqqueue *q)/*创建一个空队列由指针q指出*/ if (q=(sqqueue*)mal

27、loc(sizeof(sqqueue)= =null) return false; q-front= -1; q-rear=-1;return true;p52【算法3.16 顺序队列的入队列操作】int append(sqqueue *q,elemtype x)/*将元素x插入到队列q中，作为q的新队尾*/ if(q-rear=maxnum-1) return false; /*队列满*/ q-rear+;q-queueq-rear=x;return true;p52【算法3.17 顺序队列的出队列操作】elemtype delete(sqqueue *q)/*若队列q不为空，则返回队头元素

28、*/elemtype x;if(q-rear= =q-front) return null; /*队列空*/x=q-queue+q-front; return x;p52【算法3.18 顺序队列的取头元素操作】elemtype gethead(sqqueue *q)/*若队列q不为空，则返回队头元素*/ if(q-rear= =q-front) return null; /*队列空*/return (q-queues-front+1); p52【算法3.19 顺序队列的非空判断操作】int empty(sqqueue *q)/*队列q为空时，返回true；否则返回false*/ if (q-r

29、ear= =q-front) return true; return false;p53【算法3.20 顺序队列的求长度操作】int length(sqqueue *q)/*返回队列q的元素个数*/ return(q-rear-q-front);p54用c语言定义循环队列结构如下：typedef structelemtype queuemaxnum;int front; /*队头指示器*/int rear; /*队尾指示器*/int s; /*队列标志位*/qqueue;p54【算法3.21 循环队列的初始化】int initqueue(qqueue *q)/*创建一个空队列由指针q指出*/

30、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= =1)&(q-front= =q-rear) return false;/*队列满*/ q-rear+; if (q-rear= =maxnum) q-rear=0; q-queueq-rear

31、=x; q-s=1; /*置队列非空*/return true;p55【算法3.23 循环队列的出队列操作】elemtype delete(qqueue *q)/*若队列q不为空，则返回队头元素*/elemtype x;if (q-s= =0) retrun null; /*队列为空*/q-front+;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 qnodeelemtype da

32、ta;struct qnode *next;qnodetype; /*定义队列的结点*/typedef struct qnodetype *front;/*头指针*/qnodetype *rear; /*尾指针*/lqueue;p56【算法3.24 链队列的初始化】int initlqueue(lqueue *q)/*创建一个空链队列q*/ if (q-front=(qnodetype*)malloc(sizeof(qnodetype)= =null) return false; q-rear=q-front;q-front-next=null; return true;p56【算法3.25

33、链队列的入队列操作】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)/

34、*若链队列q不为空，则删除队头元素，返回其元素值*/elemtype x;qnodetype *p;if(q-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 strmaxnum; int length; /*串长度*/ stringtype; /* 串类型定义*/p62 用

35、链表存放字符串时，其结构用c语言定义如下：typedef struct nodechar str;struct node *next; slstrtype;p63 用块链存放字符串时，其结构用c语言定义如下：typedef struct nodechar str4;struct node *next; slstrtype;p63 用堆存放字符串时，其结构用c语言定义如下：typedef structchar *str;int length; hsstrtype;p65 c语言中用字符数组存储字符串时，结构定义如下：#define maxnum 80typedef struct char str

36、maxnum; int length; /*串长度*/ stringtype; /* 串类型定义*/p65【算法4.1 在静态存储方式中求子串】int substr(stringtype s1,stringtype * s2,int m,int n)int j,k;j=s1.length;if(mj|nk) (*s2).length=k;else (*s2).length=n; /*置子串的串长*/for(j=0;jnext!=null;p=p-next) length1+;/*求主串和串长*/ if(mlength1|n0) s2=null;return false;/*参数错误*/ p=s

37、1.next; for(j=0;jnext;/*找到子串和起始位置*/ s2=(slstrtype *)malloc(sizeof(slstrtype);/*分配子串和第一个结点*/ v=s2;q=v; for(j=0;jnext!=null;j+) /*建立子串*/ q-str=p-str;p=p-next;q=(slstrtype *)malloc(sizeof(slstrtype);v-next=q;v=q;q-str=0;q-next=null; /*置子串和尾结点*/return true;p67 堆存储结构用c语言定义为：typedet structchar *str;int le

38、ngth; hsstrtype;p67【算法4.3 共享法求子串】int substr(hsstrtype s1,hsstrtype *s2,int m,int n) int j,k; j=s1.length; if(mj|nlength=0;return false;/*参数错误*/ k=strlen(s1.str+m);/*主串第m个位置开始之后的串长*/if (nk) s2-length=k;else s2-length=n;/*置子串的串长*/s2-str=s1.str+m;/*置子串的串首地址return true;p67【算法4.4 重新赋值法求子串】int substr(hsst

39、rtype s1,hsstrtype *s2,int m,int n) int j,k; j=s1.length; if(mj|nlength=0;return false;/*参数错误*/ k=strlen(s1.str+m);/*主串第m个位置开始之后的串长*/if (nk) s2-length=k;else s2-length=n; /*置子串的串长*/k=s2-length;for(j=0;jstrj=s1.strm+;/*复制字符*/s2-strj=0;/*置结束符*/return true;p68 例main()int a,b,c;scanf(%d,%d,&a,&b);c=a+b;

40、printf(“%d”,c);第五章 多维数组和广义表p77 三元组表#define maxsize 100/*定义非零元的最大数目*/struct node /*定义一个三元组*/ int i , j; /*非零元行、列号*/int v; /*非零元值*/; struct sparmatrix /*定义稀疏矩阵*/ int rows,cols ; /*稀疏矩阵行、列数*/int terms; /*稀疏矩阵非零元个数*/node data maxsize; /*三元组表*/;p79 十字链表的数据类型描述如下：struct linknode int i, j;struct linknode *

41、cptr, *rptr;union vnext /*定义一个共用体*/ int v; /*表结点使用v域,表示非零元值*/struct linknode next; /*表头结点使用next域*/ k; p81 （1）按照a的列序进行转置#define maxsize 100struct node int i,j; /*定义三元组的行、列号*/ int v; /*三元组的值*/ ; struct sparmatrix int rows,cols; /*稀疏矩阵的行、列数*/ int terms; /*稀疏矩阵的非零元个数*/ struct node datamaxsize; /*存放稀疏矩阵的

42、三元组表*/ ;void transpose(struct sparmatrix a) struct sparmatrix b; /*b为a的转置*/int ano,bno=0,col,i;b.rows=a.cols; b.cols=a.rows;b.terms=a.terms;if (b.terms0)for ( col=0; cola.cols; col+) /*按列号扫描*/ for( ano=0;anoa.terms;ano+) /*对三元组扫描*/if (a.dataano.j=col) /*进行转置*/ b.databno.j=a.dataano.i;b.databno.i=a.dataano.j;b.databno.v=a.dataano.v;bno+; for( i=0;ia.terms;i+) /*输出转置后的三元组结果*/ printf(%5d%5d%5dn,b.