数据结构算法c实现.docx

《数据结构算法c实现.docx》由会员分享，可在线阅读，更多相关《数据结构算法c实现.docx（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构算法实现计算机科学与技术系算法一学会简单开发与程序调式1算法二线性表操作3算法三单链表操作7算法四栈基本操作13算法五表达式求值18算法六队列操作24算法七稀疏矩阵运算27算法八广义表操作30算法九二叉树操作33算法十二叉排序树的操作39算法H图的操作45算法十二排序操作63算法十三查找操作67算法十四哈希表操作69算法一学会简单开发与程序调式1、目的 熟悉C或C+集成开发环境的基本命令及功能键，熟悉常用功能菜单命令 理解C或C+程序结构 理解函数声明、定义和调用方法 理解标准库函数、自定义函数 掌握参数的不同传送方式及作用2、要求 学习如何根据编译信息，定位语法错误 将警告与错误一律

2、看作错误 学习C或C+程序书写风格 写出上机调试后的体会3、内容(1)编程实现输出一组数的最大值(或最小值)参考程序如下：#include const int n=10;void main() int i,x,an;coutninput in 10 num:*;fbr(i=0;ivn;i+)cinai;x=a0;i=l；while(ix)x=ai;i+；coutM 10 num max is:xendl;(2)阅读下列程序，体会参数传递的变化，并上机调试。#include#includevoid fiinl(int a,int b);void fun2(int &a,int &b);void

3、fun3(int *a,int *b);void main()int x=5,y=10;coutnan zhi chuan song :endl;cout,main:Hsetw( 10),x=,setw(3)xsetw( 10)My=Msetw(3)yendl;funl(x,y);coutHmain:Hsetw( 10)Hx=,setw(3)xsetw( 10)My=Msetw(3)yendl; coutendl;coutny yong :Hendl;coutmain:Hsetw( 10)nx=Hsetw(3)xsetw( 10)My=nsetw(3)yendl;fim2(x,y);coutm

4、ain:Msetw( 10)nx=setw(3)xsetw( 10)My=Msetw(3)yendl; coutendl;coutnzhi zhen:Mendl;coutnmain:Hsetw( 10),x=,setw(3)xsetw( 10)Hy=,setw(3)yendl;fiin3(&x,&y);coutHmain:Hsetw( 10)Hx=,setw(3)xsetw( 10)Hy=Msetw(3)yendl; coutendl;)void fun 1 (int a,int b)a=a+b;b=2*a+3*b;coutMfun l:Msetw(l 0)na=,setw(3)asetw(

5、10 )Mb=Msetw( 3 )bendl; void fiin2(int &a,int &b)a=a+b;b=2*a+3*b;coutHfun2:nsetw( 10)na=setw(3)asetw( 10)Mb=Mset w(3 )bendl; void fun3(int *pa,int *pb)pa+=*pb;*pb-=l;coutHfun3:Msetw( 10)n*Pa=,setw(3)*pasetw(l 0)H*pb=Hsetw(3)*pbe ndl;算法二顺性表操作1、目的 会定义线性表的顺序存储类型 掌握线性表的基本运算和具体函数的定义2、要求 编写对线性表的建立、插入、删除、查

6、找等算法，并判断插入、删除的位置是否合 法。 认真编写源程序，并进行调试，写出输入、输出和溢出判断结果 写出上机调试后的体会3、内容编写线性表的顺序存储结构上的：初始化线性表、清空线性表、求线性表的长度、判 空、判满、查找、插入、删除、线性表的有序输出等算法。参考程序如下：#include #include typedef int elemtype; struct listelemtype *list;intlen;int maxsize;);void initlist(list &l,int ms) l.list=new elemtypems; if(!l.list) cerrMmemory

7、 allocation failure!Mendl; exit(l);)l.len=0;Lmaxsize=ms;void clearlist(list &1)l.len=0;int length(list &1) return Lien; int listempty(list &1) return l.len=0;int listfull(list &1) return l.len=l.maxsize;void looklist(list &1) for(int i=0;il.Ien;i+4-) coutvvl.listivv-; coutendl;)int findlist(list &l,

8、elemtype x) fbr(int i=O;i0) fbr(int i=l.len-l;i=0;i-) l.listi+l=Llisti;l.list0=x;)else if(k0) l.listl.len=x;else for(int i=0;il.len;i+) if(x=ij-)l.Ustj+l=l.list|j;l.listi=x;)l.len+;return 1;)int deletelist(Iist &l,elemtype &x,int k) if(listempty(l) return 0;if(k0) x=l.list0;fbr(int i=l;il.len;i-H-)

9、l.listi-l=l.listi;else if(k0) x=l.listl.len-l;else fbr(int i=0;i=l.len)return 0;else x=Llisti;fbr(int j=i+l;jLlen;j+)l.len;return 1;void outputlist(list &l,int m)int *b=new intl.len;int i,k;fbr(i=O;il.len;i-H-) bi=i;fbr(i=l;il.len;i-l-+)k=i-l;fbr(int j=i;jl.len;j-H-)if(m=l&l.listbjl.listbk)k=j;ifi(k

10、!=i-l)int x=bi-l;bi-l=bk;bk=x;fbr(i=O;iLIen;i-H-) coutl.listbit coutendl;)void main()const int ml=20;list a;initlist(a,ml);int i;elemtype x;coutninput 5 int num:；for(i=0;i5;i+) cinx;insertlist(a,x,-l)；coutninput 2 int num:;cinx;insertlist(a,x, 1);cinx;insertlist(a,x, 1);looklist(a);coutnuporder sort

11、:； outputlist(a,l);coutndownorder sort:；outputlist(a,0);list b;initlist(b,ml);for(i=O;ia.len;i-H-)insertlist(b,a.listi,O);looklist(b);if(deletelist(a,x,l)cout*delete front!Mendl;elsecoutHdelete fale!endl;looklist(a);ifdeletelist(a,x,-l)coutdelete rear!Hendl;elsecoutHdelete fale!*endl;looklist(a);cou

12、tinput a del num:； cinx;if|deletelist(a,x,O)cout*delete success!Mendl;elsecoutdelete fale!Hendl;looklist(a);算法三单链表操作1、目的 会定义单链表的结点类型 掌握对单链表的一些基本操作和具体函数的定义 充分利用C或C+语言的特点，提高程序的可移植性2、要求 编写对单链表的初始化、插入、删除、查找等算法。 认真编写源程序，并进行调试，写出输入、输出结果 写出上机调试运行分析及功能。3、内容编写单链表：初始化单链表、清空单链表、求单链表的长度、判空、查找、插入、 删除、线性表的有序输出等算法

13、。参考程序如下：#include#includetypedef int elemtype;struct Inode elemtype data;Inode *next;)；void initlist(lnode *&hl) Inode *p=new Inode;p-next=NULL;hl=p;hl-next=NULL;void clearlist(Inode *&hl)Inode *p,*q;p=hl-next;while(p!=NULL) q=p-next;delete p;p=q;hl-next=NULL;int lissize(lnode *hl) int i=0;Inode *p=h

14、l-next;while(p!=NULL)i；p=p-next;return i;int listempty(lnode *hl) return hl-next=NULL;)elemtype getelem(Inode *hl,int i) cerrpos is out range !endl;exit( 1);)Inode *p=hl-next;intj=O;while(p!=NULL)j+；if(j=i)break;p=p-next;)ifi(p=NULL) cerrnpos is out range!Hendl; exit(l);)return (p-data);)void insert

15、rear(Inode *hl,elemtype x) Inode *q=new Inode;q-data=x;q-next=NULL;Inode *p=hl;while(p-next!=NULL)p=p-next;p-next=q;)void looklist(lnode *hl)Inode *p=hl-next;while(p!=NULL) coutp-datan p=p-next;)coutendl;)int findlist(lnode *hl,elemtype &x) Inode *p=hl-next;while(p!=NULL) if(p-data=x) x=p-data;retur

16、n 1;)elsep=p-next;return 0;void insertlist(lnode *hl,elemtype x,int i) cerrnpos is out range!Mendl; exit(l);)Inode *p,*q;intj=O;P=hl;while(p-next!=NULL)if(j=i) break;p=p-next;if(j=i) q=new Inode;q-data=x;q-next=p-next;p-next=q;else cerrHpos is out range!Hendl; exit(l);void deletelist(lnode *hl,int i

17、) Inode *p=hl;intj=O;while(p-next !=NULL&jnext;j+；if(ji-l|p-next=N ULL) cerr,error! Mendl;exit( 1);)Inode *q=p-next;p-next=q-next;delete q;void sortlist(Inode *hl,int k) Inode *head=new Inode;head-next=N ULL;head-data=hl-next-data;fbr(lnode *p=hl-next-next;p;p=p-next) Inode *q=new Inode;q-data=p-dat

18、a;Inode *cp=head;Inode *ap=NULL;while(cp) if(k=l)ifl(q-datadata) break;else ap=cp; cp=cp-next;else ifi(q-datacp-data) break;else ap=cp; cp=cp-next;)ifiap=NULL) q-next=head; head=q; else q-next=cp; ap-next=q; )Inode *r=new Inode;r-next=head;head=r;looklist(head);clearlist(head);)void main()Inode *hl;

19、initlist(hl);int i;elemtype x;coutninput in 5 num:；fbr(i=O；i5;i+) cinx; insertrear(hl,x);)coutHinput 2 num:;cinx;insertlist(hl,x, 1); cinx;insertlist(hl,x,l); looklist(hl);sortlist(hl,l);sortlist(hl,0);算法四栈基本操作1、目的：掌握栈的存储表示方式和栈基本操作的实现方法2、要求：栈的基本操作实现方法，栈的应用3、内容：栈的实现栈的顺序存储。#include#include#include# de

20、fine ERROR 0# define TRUE 1# define FALSE 0# define OK 1# define EQUAL 1/define OVERFLOW-1# define STACK_INIT_SIZE 100# define STACKINCREMENT 10typedef int Status ;struct STU char name 20;char stuno10;int age;int score;);typedef struct STU SElemType;struct STACK SElemType *base;SElemType *top;int st

21、acksize;)；typedef struct STACK SqStack;typedef struct STACK *pSqstack;Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);Status ClearStack(SqStack *S);Status StackEmpty(SqStack S);int StackLength(SqStack S);Status GetTop(SqStack S,SElemType *e);Status Push(SqStack *S,SElemType e);Status Po

22、p(SqStack *S,SElemType *e);Status StackTraverse(SqStack S,Status (*visit)();Status InitStack(SqStack *S)(*S)=(SqStack *) malloc(sizeof(SqStack);(*S)-base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!(*S)-base)exit(OVERFLOW);(*S)-top=( *S)-base;(*S)-stacksize=STACK_INIT_SIZE;return OK;

23、Status DestroyStack(SqStack *S) free(S-base);free(S);Status ClearStack(SqStack *S)S-top=S-base;Status StackEmpty(SqStack S)if(S.top=S.base) return TRUE;elsereturn FALSE;int StackLength(SqStack S)( 一int i;SElemType *p;i=0;p=S.top;while(p!=S.base)p+;i+；Status GetTop(SqStack S,SElemType *e) (if(S.top=S

24、.base) return ERROR;*e=*(S.top-l);return OK;ifl(S-top - S-base=S-stacksize)S-base=(SElemType *) realloc(S-base,(S-stacksize + STACKINCREMENT) * sizeof(SElemType);if(!S-base)exit(OVERFLOW);S-top=S-base+S-stacksize;S-stacksize += STACKINCREMENT;)*/*(S-top+)=e;return OK;)Status Pop(SqStack *S,SElemType

25、 *e)(if(S-top=S-base) return ERROR;*e=*-S-top;return OK;Status StackPrintElem(SElemType * e)printfin%s %s %d %dnM,e-name,e-stuno,e-age,e-score);Status StackTraverse(SqStack S,Status (*visit)()(while(S.top!=S.base)visit(S.top);main()SElemType e;SqStack *Sa;clrscr();printfifnnnSqStack Demo is running.

26、nnH);printf(nFirst is Push function.nn);InitStack(&Sa);strcpy(e.name,nstu 1 )；strcpy(e.stuno,nl 00001 )；e.age=80;e.score=1000;printff Now Stack is Empty.nM);StackTraverse(*Sa,StackPrintElem);Push(Sa,e);printR” Now Stack has one element.nM);StackTraverse(*Sa,StackPrintElem);strcpy(e.name,nstu3n);strc

27、py(e.stuno,nl 00002”)；e.age=80;e.score=1000;Push(Sa,e);printf(n Now Stack has another element.nn);StackTraverse(*Sa,StackPrintElem);prints Now Pop Stack,the top elem put into variable e.nn);Pop(Sa,&e);printftM%sn%sn%dn%dn,e.name,e.stuno,e.age,e.score);print Lets see the left of Stacks elem:nn);Stack

28、Traverse(*Sa,StackPrintElem);getch();printf(nnnnWelcom to visit nnH);算法五表达式求值1、目的 熟悉栈的定义和栈的基本操作 熟悉每一种栈操作的函数实现 熟悉把中缀算术表达式转换为后缀表达式的算法 熟悉进行后缀表达式求值的算法2、要求 编写对栈操作的函数(栈初始化、清空栈、入栈、出栈等)算法，若采用的是顺序 栈存储结构入栈时要对栈满进行处理。注意类型定义。 认真编写源程序，并进行调试，写出输入、输出结果 写出上机调试后的体会3、内容输入一个以结尾的中缀算术表达式，转换成后缀算术表达式，进行计算并显示结果。参考程序如下：#incl

29、ude#inc lude#include#include#includetypedef float elemtype;struct stack elemtype * stack;short top;short stackmaxsize;);static void initstack(stack &s,int ms)s.stack=new elemtypems;if(!s.stack) cerr,memory full!Mendl;exit(l);)s.top=-l;s.stackmaxsize=ms;static void clearstack(stack &s) s.top=-l;stati

30、c void deletestack(stack &s) delete s.stack;s.top=-l;s.stackmaxsize=O;static int stackempty(stack &s) return s.top=-l;static elemtype peek(stack &s) if(s.top=-l) cerrstack empty !*endl; exit(l);)return s.stacks.top;static void push(stack &s,elemtype itim) ifi(s.top=s.stackmaxsize-1)cerrHstack ovflw!

31、HendI;exit( 1);)s.top+;s.stacks.top=itim;static elemtype pop(stack &s)ifs.top=-l) cerrMstack empty!Mendl; exit(l);s.top;return s.stacks.top+l;static int stack full (stack &s) return s.top=s.stackmaxsize-1;int precedence(char op)switch(op)case+1:case*-*:return 1;case*:case/1:return 2;case。：case*:defa

32、ult:return 0;static float compute(char *str)typedef float elemtype;int sm=20;stack s;initstack(s,sm);istrstream ins(str);char ch;float x;insch;while(ch!=,) switch(ch)(case+:x=pop(s)+pop(s);break;case-1:x=pop(s);x=pop(s)-x;break;case*:x=pop(s)*pop(s);break;case/:x=pop(s);if(x!=0)x=pop(s)/x;elsecerrdi

33、vide by 0!Mendl;exit(l);)break;default:ins.putback(ch);insx;push(s,x);insch;)/x=pop(s);/return x;ifi( !stackempty(s) X=pop(s);iR! stackempty(s) cerrHexpression error!nendl; exit(l);)else cerrHstack is empty!Hendl; exit(l);)return x;static void change(char *s 1 ,char *s2) typedef char elemtype;int ms

34、=20;stack r;initstack(r,ms);push(r；);int ij;i=0;j=0；char ch=sli;while(ch!-*)if(ch=-)ch=sl-H-i;else if(ch(1) push(r,ch); ch=sl-H-i;else ifCch=7) while(peek(r)!= s2j+=pop(r);pop(r);ch=sl-H-i;elseif(ch=,+,|ch=,-,|ch=,*|ch=7,) char w=peek(r);while(precedence(w)=precedence(ch) s2j+=w;pop(r)；w=peek(r);pus

35、h(r,ch);ch=sl-H-i;)else while(isdigit(ch)|ch.*) s2j-H-=ch;ch=sl-H-i;)S2j+=r；)ch=pop(r);while(ch!=,) if(ch=cerrMexpression error!nendl;exit( 1);elses2j-H-=ch;ch=pop(r);)S2Lj+=;s2U+=W;void main()char a50,b50;coutMinput in end :Hendl;cin.getline(a,sizeofi(a);change(a,b);coutHdui ying de hou zhui biao d

36、a shi:Hendl;coutbendl;coutnqiu zhi jie guo shi:Hcompute(b)endl;算法六队列操作1、目的 熟悉队列的定义和队列的基本操作 熟悉队列的顺序存储结构和链式存储结构函数实现，以便在实际问题背景下的灵活 运用。 掌握各种存储结构的队列类型定义2、要求 编写对队列操作的函数（队列初始化、清空队列、入队、出队等）算法，若采用的 是顺序存储结构入队时要对队满进行处理，注意链队操作处理（带附加表头结点还 是不带附加表头结点）。 认真编写源程序，并进行调试，写出输入、输出结果 写出上机调试后的体会3、内容建立一个队列，对该队列进行一系列（入队、出队等）

37、操作后，体现出该队列的变化, 注意循环队列的输出。参考程序如下：#include#includeconst int maxsize=50;typedef int elemtype;struct queue elemtype queuemaxsize;int front,rear;；void initqueue（queue &q） q.front=q.rear=0;void clearqueue(queue &q) q.front=q.rear=0;int queueempty(queue &q)return q.front=q.rear;elemtype qfront(queue &q)ifi

38、(q.front=q.rear) cerrMqueue is empty!nen(il;exit(l);return q.queue(q.front+ l)%maxsize;void qinsert(queue &q,elemtype x) int k=(q.rear+1 )%maxsize;ifi(k=q.front) cerrnqueue overflowe! *endl; exit(l);q.rear=k;q.queuek=x;elemtype qdelete(queue &q)ifi(q.front=q.rear) cerr”queue is empty! ,endl; exit(l)

39、;q.front=(q.front+l )%maxsize;return q.queueq.front;int queuefull(queue &q)return (q.rear+-1 )%maxsize=q.front; )int queuesize(queue &q)return (q.rear-q.front)%maxsize;void lookqueue(queue &q)if(q.front=q.rear)cerr,queue is empty!nendl;exit(l);)int k=(q.front+l)%maxsize;while(l) coutq.queuekM ”； if(

40、k=q.rear)break;k=(k+1 )%maxsize;coutendl;void main()queue q;initqueue(q);for(int i=0;i6;i+)iint x=rand()%100;int y=rand()%100;if(!queuefull(q) qinsert(q,x)；coutxM in queue, ” ；if(!queuefull(q) qinsert(q,y);coutyM in queue1,;)coutendl;coutqueuesize is: nqueuesize(q)endl;coutqdelete(q)n out queuenendl;coutqueuesize is: queuesize(q)endl;coutendl;lookqueue(q);while(! queueempty(q)coutqdelete(q)endl;coutHqueuesize is:queuesize(q)end