数据结构算法c实现.docx

数据结构算法实现计算机科学与技术系算法一学会简单开发与程序调式1算法二线性表操作3算法三单链表操作7算法四栈基本操作13算法五表达式求值18算法六队列操作24算法七稀疏矩阵运算27算法八广义表操作30算法九二叉树操作33算法十二叉排序树的操作39算法H图的操作45算法十二排序操作63算法十三查找操作67算法十四哈希表操作69算法一学会简单开发与程序调式1、目的 熟悉C或C+集成开发环境的基本命令及功能键，熟悉常用功能菜单命令 理解C或C+程序结构 理解函数声明、定义和调用方法 理解标准库函数、自定义函数 掌握参数的不同传送方式及作用2、要求 学习如何根据编译信息，定位语法错误 将警告与错误一律看作错误 学习C或C+程序书写风格 写出上机调试后的体会3、内容(1)编程实现输出一组数的最大值(或最小值)参考程序如下：#include<iostream.h> const int n=10;void main() int i,x,an;cout«ninput in 10 num:*;fbr(i=0;ivn;i+)cin»ai;x=a0;i=l；while(i<n) if(ai>x)x=ai;i+；cout«M 10 num max is:"«x«endl;(2)阅读下列程序，体会参数传递的变化，并上机调试。#include<iostream.h>#include<iomanip.h>void fiinl(int a,int b);void fun2(int &a,int &b);void fun3(int *a,int *b);void main()int x=5,y=10;cout«nan zhi chuan song :"«endl;cout«,'main:H«setw( 10)«,x=,«setw(3)«x«setw( 10)<<My=M«setw(3)«y«endl;funl(x,y);cout«Hmain:H«setw( 10)<<Hx=,«setw(3)«x«setw( 10)«My=M«setw(3)«y«endl; cout«endl;cout«ny yong :H«endl;cout«"main:H«setw( 10)«nx=H«setw(3)«x«setw( 10)«My=n«setw(3)«y«endl;fim2(x,y);cout«"main:M«setw( 10)<<nx="«setw(3)«x«setw( 10)«My=M«setw(3)«y«endl; cout«endl;cout«nzhi zhen:M«endl;cout«nmain:H«setw( 10)«,'x=,«setw(3)«x«setw( 10)«Hy=,'«setw(3)«y«endl;fiin3(&x,&y);cout«Hmain:H«setw( 10)«Hx=,«setw(3)«x«setw( 10)<<Hy=M«setw(3)«y«endl; cout«endl;)void fun 1 (int a,int b)a=a+b;b=2*a+3*b;cout«Mfun l:M«setw(l 0)«na=,«setw(3)«a«setw( 10 )«Mb=M«setw( 3 )«b«endl; void fiin2(int &a,int &b)a=a+b;b=2*a+3*b;cout«Hfun2:n«setw( 10)<<na="«setw(3)«a«setw( 10)«Mb=M«set w(3 )«b«endl; void fun3(int *pa,int *pb)pa+=*pb;*pb-=l;cout«Hfun3:M«setw( 10)«n*Pa=,«setw(3)«*pa«setw(l 0)<<H*pb=H«setw(3)«*pb«e ndl;算法二顺性表操作1、目的 会定义线性表的顺序存储类型 掌握线性表的基本运算和具体函数的定义2、要求 编写对线性表的建立、插入、删除、查找等算法，并判断插入、删除的位置是否合 法。 认真编写源程序，并进行调试，写出输入、输出和溢出判断结果 写出上机调试后的体会3、内容编写线性表的顺序存储结构上的：初始化线性表、清空线性表、求线性表的长度、判 空、判满、查找、插入、删除、线性表的有序输出等算法。参考程序如下：#include<iostream.h> #include<stdlib.h> typedef int elemtype; struct listelemtype *list;intlen;int maxsize;);void initlist(list &l,int ms) l.list=new elemtypems; if(!l.list) cerr«Mmemory allocation failure!M«endl; 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;i<l.Ien;i+4-) coutvvl.listivv-; cout«endl;)int findlist(list &l,elemtype x) fbr(int i=O;i<l.len;i-H-) ifi(l.listi=x) x=Llisti;return 1;return 0;int insertlist(list &l,elemtype x,int k) if(listfull(l) return 0;ififk>0) fbr(int i=l.len-l;i>=0;i-) l.listi+l=Llisti;l.list0=x;)else if(k<0) l.listl.len=x;else for(int i=0;i<l.len;i+) if(x<l.listi) break; fbr(intj=l.len-l;j>=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(k>0) x=l.list0;fbr(int i=l;i<l.len;i-H-) l.listi-l=l.listi;else if(k<0) x=l.listl.len-l;else fbr(int i=0;i<I.len;i+) if(l.listi=x) break; if(i>=l.len)return 0;else x=Llisti;fbr(int j=i+l;j<Llen;j+)l.len;return 1;void outputlist(list &l,int m)int *b=new intl.len;int i,k;fbr(i=O;i<l.len;i-H-) bi=i;fbr(i=l;i<l.len;i-l-+)k=i-l;fbr(int j=i;j<l.len;j-H-)if(m=l&&l.listbj<l.listbk) k=j;if(m!=l&&l.listb|j>l.listbk)k=j;ifi(k!=i-l)int x=bi-l;bi-l=bk;bk=x;fbr(i=O;i<LIen;i-H-) cout«l.listbi«'t cout«endl;)void main()const int ml=20;list a;initlist(a,ml);int i;elemtype x;cout«ninput 5 int num:"；for(i=0;i<5;i+) cin»x;insertlist(a,x,-l)；cout«ninput 2 int num:"cin»x;insertlist(a,x, 1);cin»x;insertlist(a,x, 1);looklist(a);cout«nuporder sort:"； outputlist(a,l);cout«ndownorder sort:"；outputlist(a,0);list b;initlist(b,ml);for(i=O;i<a.len;i-H-)insertlist(b,a.listi,O);looklist(b);if(deletelist(a,x,l)cout«'*delete front!M«endl;elsecout«Hdelete fale!"«endl;looklist(a);ifdeletelist(a,x,-l)cout«"delete rear!H«endl;elsecout«Hdelete fale!*'«endl;looklist(a);cout«"input a del num:"； cin»x;if|deletelist(a,x,O)cout«'*delete success!M«endl;elsecout«"delete fale!H«endl;looklist(a);算法三单链表操作1、目的 会定义单链表的结点类型 掌握对单链表的一些基本操作和具体函数的定义 充分利用C或C+语言的特点，提高程序的可移植性2、要求 编写对单链表的初始化、插入、删除、查找等算法。 认真编写源程序，并进行调试，写出输入、输出结果 写出上机调试运行分析及功能。3、内容编写单链表：初始化单链表、清空单链表、求单链表的长度、判空、查找、插入、 删除、线性表的有序输出等算法。参考程序如下：#include<iostream.h>#include<stdlib.h>typedef 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=hl->next;while(p!=NULL)i"；p=p->next;return i;int listempty(lnode *hl) return hl->next=NULL;)elemtype getelem(Inode *hl,int i) cerr«"pos 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) cerr«npos is out range!H«endl; exit(l);)return (p->data);)void insertrear(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) cout«p->data«n p=p->next;)cout«endl;)int findlist(lnode *hl,elemtype &x) Inode *p=hl->next;while(p!=NULL) if(p->data=x) x=p->data;return 1;)elsep=p->next;return 0;void insertlist(lnode *hl,elemtype x,int i) cerr«npos is out range!M«endl; 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 cerr«Hpos is out range!H«endl; exit(l);void deletelist(lnode *hl,int i) Inode *p=hl;intj=O;while(p->next !=NULL&&j<i-1) p=p->next;j+；if(j>i-l|p->next=N ULL) cerr«,'error! M«endl;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->data;Inode *cp=head;Inode *ap=NULL;while(cp) if(k=l)ifl(q->data<cp->data) break;else ap=cp; cp=cp->next;else ifi(q->data>cp->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;initlist(hl);int i;elemtype x;cout«ninput in 5 num:"；fbr(i=O；i<5;i+) cin»x; insertrear(hl,x);)cout«Hinput 2 num:"cin»x;insertlist(hl,x, 1); cin»x;insertlist(hl,x,l); looklist(hl);sortlist(hl,l);sortlist(hl,0);算法四栈基本操作1、目的：掌握栈的存储表示方式和栈基本操作的实现方法2、要求：栈的基本操作实现方法，栈的应用3、内容：栈的实现栈的顺序存储。#include<stdio.h>#include<malloc.h>#include<con io.h># define 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 stacksize;)；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 Pop(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;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.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 *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.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);strcpy(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"" Let's see the left of Stack's elem:nn);StackTraverse(*Sa,StackPrintElem);getch();printf(nnnnWelcom to visit nnH);算法五表达式求值1、目的 熟悉栈的定义和栈的基本操作 熟悉每一种栈操作的函数实现 熟悉把中缀算术表达式转换为后缀表达式的算法 熟悉进行后缀表达式求值的算法2、要求 编写对栈操作的函数(栈初始化、清空栈、入栈、出栈等)算法，若采用的是顺序 栈存储结构入栈时要对栈满进行处理。注意类型定义。 认真编写源程序，并进行调试，写出输入、输出结果 写出上机调试后的体会3、内容输入一个以结尾的中缀算术表达式，转换成后缀算术表达式，进行计算并显示结果。参考程序如下：#include<iostream.h>#inc lude<std lib.h>#include<ctype.h>#include<PROCESS.H>#include<STRSTREAM.H>typedef 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!M«endl;exit(l);)s.top=-l;s.stackmaxsize=ms;static void clearstack(stack &s) s.top=-l;static 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) cerr«"stack empty !*'«endl; exit(l);)return s.stacks.top;static void push(stack &s,elemtype itim) ifi(s.top=s.stackmaxsize-1)cerr«Hstack ovflw!H«endI;exit( 1);)s.top+;s.stacks.top=itim;static elemtype pop(stack &s)ifs.top=-l) cerr«Mstack empty!M«endl; 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*:default: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;ins»ch;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;elsecerr«"divide by 0!M«endl;exit(l);)break;default:ins.putback(ch);ins»x;push(s,x);ins»ch;)/x=pop(s);/return x;ifi( !stackempty(s) X=pop(s);iR! stackempty(s) cerr«Hexpression error!n«endl; exit(l);)else cerr«Hstack is empty!H«endl; exit(l);)return x;static void change(char *s 1 ,char *s2) typedef char elemtype;int ms=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);push(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=©cerr«Mexpression error!n«endl;exit( 1);elses2j-H-=ch;ch=pop(r);)S2Lj+=''s2U+=W;void main()char a50,b50;cout«Minput in end :H«endl;cin.getline(a,sizeofi(a);change(a,b);cout«Hdui ying de hou zhui biao da shi:H«endl;cout«b«endl;cout«nqiu zhi jie guo shi:H«compute(b)«endl;算法六队列操作1、目的 熟悉队列的定义和队列的基本操作 熟悉队列的顺序存储结构和链式存储结构函数实现，以便在实际问题背景下的灵活 运用。 掌握各种存储结构的队列类型定义2、要求 编写对队列操作的函数（队列初始化、清空队列、入队、出队等）算法，若采用的 是顺序存储结构入队时要对队满进行处理，注意链队操作处理（带附加表头结点还 是不带附加表头结点）。 认真编写源程序，并进行调试，写出输入、输出结果 写出上机调试后的体会3、内容建立一个队列，对该队列进行一系列（入队、出队等）操作后，体现出该队列的变化, 注意循环队列的输出。参考程序如下：#include<iostream.h>#include<stdlib.h>const 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(q.front=q.rear) cerr«Mqueue is empty!n«en(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) cerr«nqueue 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);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!n«endl;exit(l);)int k=(q.front+l)%maxsize;while(l) cout«q.queuek«M ”； if(k=q.rear)break;k=(k+1 )%maxsize;cout«endl;void main()queue q;initqueue(q);for(int i=0;i<6;i+)iint x=rand()%100;int y=rand()%100;if(!queuefull(q) qinsert(q,x)；cout«x«M in queue, ” ；if(!queuefull(q) qinsert(q,y);cout«y«M in queue1,;)cout«endl;cout«"queuesize is: n«queuesize(q)«endl;cout«qdelete(q)«n out queuen«endl;cout«"queuesize is: "«queuesize(q)«endl;cout«endl;lookqueue(q);while(! queueempty(q)cout«qdelete(q)«endl;cout«Hqueuesize is:"«queuesize(q)«end