数据结构常用算法实现print

资料范本本资料为word版本，可以直接编辑和打印，感谢您的下载数据结构常用算法实现print地点： 时间： 说明：本资料适用于约定双方经过谈判，协商而共同承认，共同遵守的责任与义务，仅供参考，文档可直接下载或修改，不需要的部分可直接删除，使用时请详细阅读内容线性表的顺序表示程序2_1.c提供了顺序存储结构下线性表的实现。第1行定义了一个常数值MAXSIZE。它是一个常数，表示线性表的最大长度。第2行把ELEMTYPE设置为int的一个别名。这样，这个例子就可以使用一组整数了。第3行到第7行包含了线性表的说明。接下来从第8行到第46行线性表运算函数的定义。第8到第11行将线性表置成空表，只需简单地将线性表元素个数置成0即可。由于线性表的长度已经记录在结构成员length中，因此求线性表的长度（第35行到第38行）只是返回length的值。第20到第24行是追加函数，函数append在线性表的表尾插入一个元素。第12行到第19行是插入函数。在表中第i位置插入一个新元素item时，需将i，i+1，…，n-1位置上的元素向后移，变成编号为i+1，i+2，…，n，然后将item插入到第i个位置，且线性表的长度加1。第25行到第34行是删除元素。要删去表中位置i上的元素，同样需要移动表中元素，使原编号为i+1，i+2，…，n-1的元素变成编号为i，i+1，…，n-2,并将表的长度减1。第39行到第46行的函数find在线性表中查找第一个出现的值为item的元素。如果值item找到了，函数返回元素item所在位置1，否则返回-1。第54行到第67行是main函数的一个例子，说明了线性表的使用。57行调用clear函数将线性表清空，第58，59，60三行调用append函数追加三个元素，第62行在位置2插入一个元素15,第65行调用delete函数删除位置3的元素。第47行到53行的print函数是为了显示线性表中的数据而设置的。程序2_1.c#defineMAXSIZE999typedefintELEMTYPE;structlist（ELEMTYPElistarray[MAXSIZE];

8 void9 {1011121314151617181920212224252627282930intlength;};structlistl;clear()l.length=0;}voidinsert(intpos,ELEMTYPEitem)(inti;for(i=l.length;i>pos;i--)l.listarray[i]=l.listarray[i-1];l.listarray[pos]=item;l.length++;}voidappend(ELEMTYPEitem)(l.listarray[l.length++]=item;}ELEMTYPEdelete(intpos)(inti;ELEMTYPEtemp;temp=l.listarray[pos];for(i=pos;i<l.length-1;i++)

31323335(3739404243444547485051525455575859606162l.listarray[i]=l.listarray[i+1];l.length--;returntemp;}intlength()returnl.length;}intfind(ELEMTYPEitem)(inti;for(i=0;i<l.length;i++)if(l.listarray[i]==item)returni;return-1;}voidprint()(inti;for(i=0;i<l.length;i++)printf("%d〃，l.listarray[i]);printf("\n");}voidmain()(clrscr();clear();append(10);/*Lis10*/append(20);/*Lis(10,20)*/append(30);/*Lis(10,20,30)*/print();insert(2,15); /*Lis(10,20,15,30)*/

print();printf("\n%d",find(100));printf("\n%d\n",delete(3));/*Lis(10,20,15)*/print();}线性表的链式表示程序2_2.c提供了链式存储结构下线性表的实现。第3行到第8行包含了线性表中结点的说明，其中element表示数据域，存放该结点的数据信息，next为指针域，指明该结点的唯一后继结点在内存中的存放地址，或是在该结点序列中所在的物理位置。线性链表由head和tail表示。接下来从第9行到第76行线性表运算函数的定义。第9行到第14行初始化单链表。head指针与tail指针指向表头结点。在单链表的最后一个结点后插入一个结点只要将单链表尾指针tail指向新插入结点，新插入结点成为最后一个结点即可。第15行到第20行函数append实现追加一个新结点到单链表的最后，新结点的元素值为item。malloc是C语言提供的标准函数，其功能是申请存储空间。设p是指向单链表中一个结点的指针，在p指向的结点后面插入一个结点包括三个步骤。首先，要创建一个新的结点，并且赋给它一个新的值。其次，新结点的next指向指针p指向结点的后继结点。第三，指针p指向的结点的next要指向新插入的结点。第21行到第38行函数insert实现在单链表的第i个结点前面插入一个新结点。新结点的元素值为item，s为指向新结点的指针。算法在实现时，首先查找新结点插入位置，然后根据上面所述修改相应指针。从单链表删去一个结点只需将被删结点的前趋结点的next域指向被删结点的后继结点即可。但必须注意，被删结点占据的内存空间应该返回给存储器。因此可设一个临时指针指向要删去的结点，而后调用C语言提供的标准过程free将被删去的结点占据的内存空间返回给存储器。第39行到第57行的函数delete实现删除结点运算。第58行到第65求单链表中所含结点的个数。为求单链表的结点个数，我们必须从单链表表头开始，沿着每个结点的链指针，依次向后访问并计数，直到最后一个结点位置。程序2_2.c#include<alloc.h>typedefintELEMTYPE;structlist(ELEMTYPEelement;structlist*next;TOC\o"1-5"\h\z);struct list *head;struct list *tail;voidinit()(head= malloc(sizeof(structlist));head->next= NULL;tail= head;}voidappend(ELEMTYPEitem)(tail二tail->next=(structlist *)malloc(sizeof(structlist));tail->element=item;tail->next=NULL;}

21222324252627282930313233343536373839404142434445intinsert(intpos,ELEMTYPEitem)(structlist*p,*s;intj;s=(structlist*)malloc(sizeof(structlist));s->element=item;p=head;j=1;while((p!=NULL)&&(j<pos))(p=p->next;j++;}if((!p)||(j>pos))return0;s->next=p->next;p->next=s;if(tail==p)tail=s;return1;}ELEMTYPEdelete(intpos)(structlist*p,*q;ELEMTYPEtemp;intj;q=p;p=head->next;j=1;

46474849505152535455565758596061626364656667686970while((p!=NULL)&&(j<pos))(q=p;p=p->next;j++;}if((!p)||(j>pos))return0q->next=p->next;temp=p->element;if(tail==p)tail=q;free(p);returntemp;}intlength()(structlist*p;intcnt=0;for(p=head->next;p!=NULL;p=p->next)cnt++;returncnt;}intfind(ELEMTYPEitem)(structlist*p=head->next;while(p!=NULL)(if(p->element==item)

717273747576777879808182838485868788899091929394(10,20,30,return1;elsep=p->next;}return0;}voidprint()(structlist*p;printf("\n");for(p=head->next;p!二NULL;p=p->next)printf("%d",p->element);}voidmain()(clrscr();init();append(10);/*listis(10)*/append(20);/*listis(10,20)*/append(30);/*listis(10,20,30)*/append(40);/*listis(10,20,30,40)*/insert(3,35); /*listis(10,20,30,35,40)*/print();printf("\n%d\n",delete(4));/*listis35)*/

95print();9596 }栈程序2_3.c是栈数据结构的实现，第3行到第6行包含栈类型的说明，top被定义为表示栈中最上面那个元素的位置。push（第13行到第17行）和pop（第18行到第22行）只是从top指示的数组中的位置插入和删去一个元素，因为top表示栈顶元素的位置，所以push首先把一个值插入到栈顶位置，然后把top加1。同样，pop首先把top减1，然后删去栈顶元素。函数topValue（第23行到27行）只是将栈顶元素返回。如果栈中没有元素，函数isEmpty（第28行到第31行）返回1，否则返回0。程序2_3.c#include<assert.h>#include<stdio.h>#defineMAXSIZE100typedefintELEMTYPE;structstack（ELEMTYPElistarray[MAXSIZE];inttop;};structstacks;voidinit（）（s.top=0;}

voidpush(ELEMTYPEitem)(assert(s.top<MAXSIZE);s.listarray[s.top++]=item;}ELEMTYPEpop()(intisEmpty();assert(!isEmpty());returns.listarray[--s.top];}ELEMTYPEtopValue()(intisEmpty();assert(!isEmpty());returns.listarray[s.top-1];}intisEmpty()(returns.top==0;}voidmain()(init();push(10);/*sis(10)*/push(10);/*sis(10)*/push(20); /*sis(20,10)*/printf(〃％d〃，topValue());/*returntopelement20*/printf(〃\n〃)；printf("%d",pop());/*sis(10)*/}程序2_4.c给出了链式栈表示和各种运算的算法。其中top是指向链式栈第一个结点(栈顶)的指针。进栈操作(第13行到第21行)首先申请一个新结点，并初始化该结点，然后修改新产生的结点的next域指向栈顶，并设置top指向新的链表结点。第22行到第32行是出栈操作。变量temp用来存储栈顶结点的值，ltemp用于在删去栈顶结点时保持与栈的链接，它指向当前栈顶链接到的结点。此时把原来的栈顶结点释放回内存，恢复top等于ltemp。也就是指向原来栈顶链接的结点，原来栈顶的值temp作为pop函数的返回值。程序2_4.c#include<malloc.h>#include<stdio.h>#include<assert.h>typedefintELEMTYPE;structnode(ELEMTYPEelem;structnode*next;};structnode*top;voidinit()(top=NULL;}voidpush(ELEMTYPEitem)(structnode*p;if((p=(structnode*)malloc(sizeof(structnode)))!=NULL)(p->elem=item;p->next=top;top=p;}}ELEMTYPEpop()(intisEmpty();ELEMTYPEtemp;structnode*ltemp;assert(!isEmpty());temp=top->elem;ltemp=top->next;free(top);top=ltemp;returntemp;}ELEMTYPEtopValue()

intisEmpty();intisEmpty();assert(!isEmpty());returntop->elem;}intisEmpty()(returntop==NULL;}voidmain()(init();push(10); /*sis(10)*/push(20); /*sis(20,10)*/push(30); /*sis(30,20,10)*/printf("%d\n",topValue());printf("%d\n",pop());/*sis(20,10)*/}队列在程序2_5.c中，q表示循环队列(第3行到第9行)，其队头与队尾指示变量分别为front和rear。队列中的元素类型为int(第3行)。函数enqueue(第14行到第19行)执行队列的插入操作，参数item是插入队列的元素。当队列不满时，enqueue首先移动队尾指针，然后将item置入rear所指位置。函数dequeue(第20行到25行)执行队列的删除操作，返回从队列中取出的元素。函数firstValue(第26行到第30行)返回队列头元素。程序2_5.c#include<assert.h>#include<stdio.h>#defineMAXSIZE100typedefintELEMTYPE;structqueue(intfront;intrear;ELEMTYPEelem[MAXSIZE];};structqueueq;voidinit()(q.front=q.rear=0;}voidenqueue(ELEMTYPEitem)(assert(((q.rear+1)%MAXSIZE)!=q.front);q.rear=(q.rear+1)%MAXSIZE;/*incrementrear*/q.elem[q.rear]=item;}ELEMTYPEdequeue()/*dequeueelementfrofrontofqueue*/(intisEmpty();assert(!isEmpty());/*theremustbesomethingtodequeue*/q.front=(q.front+1)%MAXSIZE;/*incrementfront*/q.front=returnq.elem[q.front];/*returnvalue*/}ELEMTYPEfirstValue()/*getvalueoffrontelement*/(intisEmpty();assert(!isEmpty());returnq.elem[(q.front+1)%MAXSIZE];}intisEmpty()/*TRUEisqueueisempty*/(returnq.front==q.rear;}voidmain()(init();enqueue(10); /* q is (10)*/enqueue(20); /* q is (10,20)*/enqueue(30); /* q is (10,20,30)*/printf("%d\n",firstValue());/*willdisplay10*/printf("%d\n",dequeue());/*willdispla10*/}程序2_6.c给出了链式队列的说明和函数的实现。front和rear分别是指向队首和队尾元素的指针。链式队列的实现不需要表头结点，当队列为空时，指针front和rear的值均为空（NULL）。当在队列中插入一个结点时(第14行到27行)，新结点链入rear所指结点的next域，并使rear指向新的结点。如果在插入之前队列为空，则指针front指向新插入的结点。当从队列中删除一个结点时(第28行到37行)，要把front所指结点的next域的值赋给front，并且释放这个结点。如果删除之后队列为空，则置指针rear为空(NULL)。程序2_6.c#include<malloc.h>#include<stdio.h>#include<assert.h>typedefintELEMTYPE;structnode(ELEMTYPEelem;structnode*next;};structnode*front;structnode*rear;voidinit()(rear=front=NULL;}voidenqueue(ELEMTYPEitem)(if(rear!=NULL)(rear->next=(structnode*)malloc(sizeof(structnode));rear->next->elem=item;rear->next->next=NULL;rear=rear->next;}else(front=rear=(structnode*)malloc(sizeof(structnode));front->elem=item;front->next=NULL;}}ELEMTYPEdequeue()(intisEmpty();ELEMTYPEtemp=front->elem;structnode*ltemp=front;assert(!isEmpty());front=front->next;free(ltemp);if(front==NULL)rear=NULL;returntemp;}ELEMTYPEfirstValue()(intisEmpty();assert(!isEmpty());returnfront->elem;}intisEmpty()(returnfront==NULL;}voidmain()(init();enqueue(10);enqueue(20);enqueue(30);printf("%d\n",firstValue());printf(〃％d\n〃，dequeue());}稀疏矩阵程序3_1.c是按照快速转置算法求矩阵的转置。程序第2行给出稀疏矩阵a的三元组表表示。函数FastTranspose按照快速转置算法思想将稀疏矩阵a转置为稀疏矩阵b，b也表示为三元组表形式。第11行到第13行计算矩阵a的每一列的非零元素个数。第15行计算a中每一列第一个非零元素在b中的起始位置。第16行第22行对a中的元素依此进行转置。程序3_1.c#defineMAXCOL100inta[][3]={{7,6,8},{0,0,5},{0,3,2},{0,5,8},{1,1,6},{1,2,9},{2,3,3},{4,0,9},{5,2,2}};intb[9][3];

5{678910111213141516171819202122232425262728FastTranspose(inta[][3],intb[][3])intm,n,tn,i,j;ints[MAXCOL],t[MAXCOL];m=a[0][0]; n=a[0][1]; tn=a[0][2];b[0][0]=n; b[0][1]=m; b[0][2]=tn;if(tn<=0)return;for(i=0;i<n;i++)s[i]=0;for(i=1;i<=tn;i++)s[a[i][1]]=s[a[i][1]]+1;t[0]=1;for(i=1;i<n;i++) t[i]=t[i-1]+s[i-1];for(i=1;i<=tn;i++)(j=a[i][1];b[t[j]][0]=a[i][1];b[t[j]][1]=a[i][0];b[t[j]][2]=a[i][2];t[j]=t[j]+1;}}main()(inti;clrscr();for(i=0;i<=8;i++)

29printf("%d%d%d\n”,a[i][0],a[i][1],a[i][2]);29FastTranspose(a,b);printf(〃\n〃)；for(i=0;i<=8;i++)printf("%d%d%d\n”,b[i][0],b[i][1],b[i][2]);}程序3_2.c是求矩阵的乘积。程序第1行给出稀疏矩阵a的行数，程序第2行给出稀疏矩阵a的列数(b的行数)，程序第3行给出稀疏矩阵的列数。第4行和第5行给出矩阵a与b的三元组表。第6行定义存放a与b相乘的结果c(二维数组)。第7行到第27行的MatrixMultiply函数实现稀疏矩阵相乘。此算法中数组S和T的意义与矩阵转置中相同，分别表示矩阵B中各行非零元素个数和各行第一个非零元素在数组b中的位置。在找B中某行的所有非零元素时，只要知道此行第一个非零元素在b中的位置和下一行第一个非零元素在b中的位置即可。例如，在B中行号为i所有非零元素，就是在b中从T[i]到T[i+1]-1的这些元素。对于在B中最后一行n，实际上它没有“下一行”了，只是为了求T[n+1]，又虚设了第n+1行，且T[n+1]的值为t2+1。程序3_2.c#defineM3#defineP4#defineN2inta[][3]={{3,4,4},{0,0,3},{0,3,2},{1,1,1},{2,0,2}};intb[][3]={{4,2,3},{0,1,2},{2,0,2},{3,1,1}};intc[M][N];MatrixMultiply(){

9101112131415161718192021222324252627282930313233intm,n,t1,t2,i,j,p,k;ints[P],t[P];m=a[0][0];n=a[0][1];t1=a[0][2];if(n==b[0][0])(p=b[0][1];t2=b[0][2];}if(t1*t2==0)return;for(i=0;i<n;i++)s[i]=0;for(i=1;i<=t2;i++)s[b[i][0]]=s[b[i][0]]+1;t[0]=1;for(i=1;i<n+1;i++)t[i]=t[i-1]+s[i-1];for(i=1;i<=t1;i++)(k=a[i][1];for(j=t[k];j<=t[k+1]-1;j++)c[a[i][0]][b[j][1]]+=a[i][2]*b[j][2];}}main()(inti,j;clrscr();MatrixMultiply();}

二叉树遍历在程序4_1.c中，函数inorder实现中序周游二叉树的递归算法，周游时输出所访问结点的值。程序中第2行定义二叉树结点元素类型为字符型，第3行到第7行定义二叉树结点类型，第8行定义root为二叉树的根结点指针。第24行到第31行的inorder函数首先检查树是否为空(如果为空，则周游完成；并且函数直接返回)，否则对左子树递归调用本函数，当左子树周游完成后，对根结点调用printf函数打印结点的值(或者按照需要完成某些运算)。最后，对右子树进行同样的操作。setup函数利用前序结果序列建立二叉树。Setup扫描一个字符串，若当前字符不为‘.’，则申请一个结点，存入当前字符，并置该结点的左、右指针为空。然后用该结点的左链和右链存放子树根结点的指针，递归调用函数setup，建立当前结点的左子树和右子树。当到达字符串的末尾时，建立二叉树的过程结束。第32行到第37行是main函数的一个例子，首先调用函数setup建立一棵二叉树。然后调用inorder函数对二叉树进行中序周游。程序4_1.c#include<alloc.h>typedefcharELEMTYPE;structBinNode(ELEMTYPEelement;structBinNode*left;structBinNode*right;);structBinNode*root;voidsetup(structBinNode**t)(

11121314151617BinNode));1819202122232425262728293031323334ELEMTYPEch;structBinNode*p;scanf(〃％c〃,&ch);if(ch=='.')*t=NULL;else(p=(structBinNode*)malloc(sizeof(structp->element=ch;*t=p;setup(&(p->left));setup(&(p->right));}}voidinorder(structBinNode*t)(if(t!=NULL)(inorder(t->left);printf("%c",t->element);inorder(t->right);}}voidmain()(clrscr();

35setup(&root);35setup(&root);inorder(root);}程序4_2.c实现二叉树周游的非递归算法。为了实现非递归算法，要在程序中设置一个栈结构，用以保存指向结点的指针，以便能够继续周游。第16行到第33是第3章中顺序栈的实现。第34行到第48行的函数setup与程序4_1.c功能相同。第49行到第63的inorder函数实现二叉树中序周游。对于inorder函数来说，首先从二叉树的根结点开始周游，令指针变量p指向当前访问结点，只是在访问结点之前，若p所指结点的左链不空，则沿着其左链前进，在前进过程中，把经过的结点指针值逐一压栈。这个过程一直重复到p为空，从而实现周游左子树。然后，如果栈不空，则从栈中弹出一个结点的指针值，访问这个结点。接下来，p取其右链的值，实现周游右子树。整个周游过程是在一个do-while循环中进行。只有当p为空，而且栈也为空时，do-while循环结束，周游结束。程序4_2.c#include<alloc.h>#include<assert.h>#defineMAXSIZE100typedefcharELEMTYPE;structBinNode(ELEMTYPEelement;struct BinNode *left;struct BinNode *right;};struct stack(

11121314151617181920212223242526272829303132333435structBinNode*listarray[MAXSIZE];inttop;};structBinNode*root;structstacks;voidinit()(s.top=0;}voidpush(structBinNode*item)(assert(s.top<MAXSIZE);s.listarray[s.top++]=item;}structBinNode*pop()(assert(!isEmpty());returns.listarray[--s.top];}intisEmpty()(returns.top==0;}voidsetup(structBinNode**t)(

36373839404142BinNode));4344454647484950515253545556575859ELEMTYPEch;structBinNode*p;scanf(〃％c〃,&ch);if(ch=='.')*t=NULL;else(p=(structBinNode*)malloc(sizeof(structp->element=ch;*t=p;setup(&(p->left));setup(&(p->right));}}voidinorder(structBinNode*t)(structBinNode*p=t;do(while(p!=NULL)(push(p);p=p->left;}if(!isEmpty())(p=pop();printf("%c",p->element);

60p=p->right;60TOC\o"1-5"\h\z}}while(!(p==NULL&&isEmpty()));}voidmain()(clrscr();init();setup(&root);inorder(root);}Huffman树程序4_3.c按照Huffman算法由已知的权集构造Huffman树并求Huffman编码。第2行定义权集元素个数。第3行定义Huffamn树结点个数。第4行到第9行定义Huffamn树结点类型，结点类型由权值、双亲、左子树和右子树组成。第10行到第13行定义Huffamn编码结构，由存放编码的数组和编码的开始位置组成。第14行的数组weight存放权值，第15行数组HT用来存放Huffman树，第16行数组HC用于存放Huffman编码。第17行到26行的init函数用于初始化Huffman树。将由n个权值作为叶结点存放到数组HT的前n个分量中。第27行到38行函数minimum从数组weight中求出当前最小的元素，并用一个大数HUGE把weight中的最小元素冲掉，返回最小元素所在位置。函数huffmantree按照huffman算法的基本思想，不断将两个子树合并为一个较大的子树，每次构成的新子树的根结点顺序存放到数组HT中的前n个分量的后面。函数huffmancode求每个叶结点的huffman编码。从该叶结点开始，沿结点的双亲域回退到根结点，每回退一步，就走过了huffman树中的一个分支，从而得到一位huffman编码值。对于第i个叶结点，其huffman编码存放在HC[i].bit中从HT[i].start到n的分量上。程序4_3.c#defineHUGE999#defineN8#defineM2*N-1structHuffmanNode(intweight;intparent;intleft;intright;TOC\o"1-5"\h\z);struct HuffmanCode (intbit[10];intstart;);intweight：]={5,29,7,8,14,23,3,11,0,0,0,0,0,0,0};struct HuffmanNode HT[M];struct HuffmanCode HC[N];voidinit(){inti;for(i=0;i<M;i++){HT[i].parent=0;HT[i].weight=weight[i];

23242526272829303132333435363738394041424344454647HT[i].left=0;HT[i].right=0;}}intminimum()(inti,k;intmin=HUGE;for(i=0;i<M;i++)if(min>weight[i]&&weight[i]!=0)(min=weight[i];k=i;}weight[k]=HUGE;returnk;}voidhuffmantree()(inti,l,r;for(i=N;i<M;i++)(=minimum();r=minimum();HT[l].parent=i;HT[r].parent=i;HT[i].left=l;

48495051525354555657585960616263646566676869cd.bit[j];7071HT[i].right=r;HT[i].weight=HT[l].weight+HT[r].weight;weight[i]=HT[i].weight;}}voidhuffmancode()(inti,p,j,c;structHuffmanCodecd;for(i=0;i<N;i++)(cd.start=N-1;c=i;p=HT[c].parent;while(p!=0)(if(HT[p].left==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HT[c].parent;}for(j=cd.start+1;j<N;j++)HC[i].bit[j]=HC[i].start=cd.start;

}voidmain()(inti,j;clrscr();init();huffmantree();for(i=0;i<M;i++)80printf(〃％d%d%d%d\n〃，HT[i].weight,HT[i].parent,HT[i].left,HT[i].right);81printf(〃\n〃)；82huffmancode();83for(i=0;i<N;i++)(84printf("%5d:〃,HT[i].weight);85for(j=HC[i].start+1;j<N;j++)86printf("%d〃，HC[i].bit[j])87printf(〃\n〃)；88}89}深度优先遍历在程序5_1.c，我们用邻接表表示图。用一维数组visited[w]标记顶点w是否被访问过。程序第3行到第7行定义图的邻接表存储结构。函数setup建立n个顶点的邻接表，该函数首先将邻接表的头结点初始化为空(第14行)，然后依次输入相邻顶点(vivj)，并将vj链入vi的链表中。输入过程直到出现(vi=0vj=0)结束。第24行到第37行的函数print用于打印邻接表的全部内容。在打印的结果中，第一列整数为图中各顶点的序号，同一行的是该顶点的相邻顶点。第38行到第52行的dfs函数实现以参数v为起点的深度优先搜索。指针p指向顶点v的第一个相邻顶点，在执行函数dfs时沿着v的邻接表前进。程序5_1.c#include<alloc.h>#defineMAXVERTEX100structEdgeNode(intvertex;structEdgeNode*next;);structEdgeNode*a[MAXVERTEX];intvisited[MAXVERTEX];voidsetup(intn)10(11intvi,vj;12inti;13structEdgeNode*p;14for(i=0;i<n;i++)a[i]=NULL;15scanf(〃％d%d〃，&vi,&vj);16while(vi>=0)(

17EdgeNode))1819202122232425262728293031323334353637383940(structEdgeNode*)malloc(sizeof(structp->vertex=vj;p->next=a[vi];a[vi]=p;scanf(〃％d%d〃，&vi,&vj);}}voidprint(intn)(structEdgeNode*p;inti;for(i=0;i<n;i++)(printf("%d",i);p=a[i];while(p!=NULL)(printf("%d",p->vertex);p=p->next;}printf("\n");}}voidDFS(intv)(structEdgeNode*p;

414243444546474849505152535455565758596061626364inti;visited[v]=1;p=a[v];while(p!=NULL)(=p->vertex;if(!visited[i])(printf("(%d,%d)",v,i);DFS(i);}p=p->next;}}voidmain()(intn,i;clrscr();printf("Pleaseinputvertexnumberofgraph:");scanf(〃%d〃,&n);for(i=0;i<n;i++)visited[i]=0;setup(n);print(n);printf("Orderintraversbydfs...”);DFS(0);}最小生成树

在程序5_2.c中，第1行定义常量HUGE为大于图中边的权最大值，第3行到第8行给出了加权图的邻接矩阵，其中N为图的顶点个数。第9行到第36行的函数prim实现Prim算法，在这个函数里，matrix表示带权图的邻接矩阵。为了便于选出权最小的边，我们引入两个数组CloseVertex和LowCost，CloseVertex[i]表示最小代价生成树中的一个顶点，该顶点和不是最小代价生成树中的一个顶点i构成的边（CloseVertex[i]，i）具有最小的权。LowCost[i]表示边（CloseVertex[i]，i）的权。起初（第14行到第17行）我们将顶点0作为生成树的顶点，所以，CloseVertex[i]的值为0，i=1，2，…，n-1。而LowCost[i]为边（0，i）的权，i=1，2，…，n-1。由于n个顶点的连通图共有n-1条边，所以，选择边的过程共需要重复n-1次。每次扫描数组LowCost，找出当前与生成树中顶点最近的顶点，令其为w，得到生成树的一条边（w，CloseVertex[w]）（第23行到第27行）。然后，令LowCost[w]=0（表示顶点w已在最小生成树中），由于顶点w加入最小生成树中后，可能引起其它顶点的LowCost发生变化，因此第30行到第34行修改数组LowCost和CloseVertex。第37到第45行的PrintMatrix函数输出加权图的邻接矩阵。程序5_2.c#defineHUGE999#defineN6intmatrix[N][N]={{0,60,10,50,HUGE,HUGE},{60,0,50,HUGE,30,HUGE},{10,50,0,50,60,40},{50,HUGE,50,0,HUGE,20},{HUGE,30,60,HUGE,0,60},{HUGE,HUGE,40,20,60,0}};intPrim（intmatrix[N][N],intn）

11121112131415161718192021222324LowCost[j]!=0)252627282930313233intLowCost[N];intCloseVertex[N];for(i=1;i<n;i++)(LowCost[i]=matrix[0][i];CloseVertex[i]=0;}LowCost[0]=0;CloseVertex[0]=0;for(i=1;i<n;i++)(MinCost=HUGE;k=i;for(j=1;j<n;j++)if(LowCost[j]<MinCost&&(MinCost=LowCost[j];k=j;}printf("(%d,%d)",k,CloseVertex[k]);LowCost[k]=0;for(j=1;j<n;j++)if(matrix[k][j]<LowCost[j])(LowCost[j]=matrix[k][j];CloseVertex[j]=k;

3536 }37 void38 (39404142434445 }46 void47 (48495051 }拓扑排序}PrintMatrix(intmatrix[N][N],intn)inti,j;for(i=0;i<n;i++)(for(j=0;j<n;j++)printf("%5d",matrix[i][j]);printf(〃\n〃)；}main()clrscr();PrintMatrix(matrix,N);Prim(matrix,N);程序5_3.c中第4行到第7行定义邻接表头结点类型，头结点中有两个字段count和link。Count字段存放该顶点的入度，link是一个指向该结点邻接表的第一个表结点的指针。第8行到第11行定义表结点类型。每个表结点有两个字段：vertex程序5_3.c中第13行到30行函数AdjList生成图邻接表。在该函数中利用头结点的count记录顶点的直接前驱数。

第45行到第71行函数TopOrder实现拓扑排序。首先将前驱为0的顶点入栈，栈通过count字段连接起来。第55行到第70行从栈中取出一个顶点并输出，然后将该顶点的邻接表上所有顶点的前驱计数递减，如果前驱计数为0则入栈，这个过程重复n次。程序5_3.c#include<alloc.h>#defineMAXVERTEX100#defineN7structEdgeNode(intvertex;structEdgeNode*next;TOC\o"1-5"\h\z)；structVertexNode(intcount;structEdgeNode*link;);structVertexNode AdjList[N];voidAdjList(struct VertexNodea[],intn){int vi,vj,i;structEdgeNode *p;for (i=0;i<n;i++) (a[i].count=0;a[i].link=NULL;}

212223EdgeNode))242526272829303132333435363738394041424344scanf("%d%d”,&vi,&vj);while(vi>=0)(p=(structEdgeNode*)malloc(sizeof(structp->vertex=vj;p->next=a[vi].link;a[vi].link=p;a[vj].count=a[vj].count+1;scanf("%d%d",&vi,&vj);}}voidPrintAdjList(structVertexNodea[],intn)(inti;structEdgeNode*p;for(i=0;i<n;i++)(printf("%d%d〃，i,a[i].count);p=a[i].link;while(p!=NULL)(printf("%d",p->vertex);p=p->next;}printf("\n");

45464748495051525354555657585960616263646566676869voidTopOrder(structVertexNodea[],intn)(inti,j,k,top;structEdgeNode*ptr;top=-1;for(i=0;i<n;i++)if(a[i].count==0)(a[i].count=top;top=i;}for(i=0;i<n;i++)(if(top==-1)return;j=top;top=a[top].count;printf("%d",j);ptr=a[j].link;while(ptr!=NULL)(k=ptr->vertex;a[k].count=a[k].count-1;if(a[k].count==0)(a[k].count=top;top=k;}ptr=ptr->next;

TOC\o"1-5"\h\z}}voidmain()(AdjList(AdjList,N);PrintAdjList(AdjList,N);TopOrder(AdjList,N);}最短路径Dijkstra算法的执行过程是：首先从S之外的顶点集合V-S中选出一个顶点u，使distance[u]值最小，我们把u加入到集合S中(S[u]=1)，顶点u也成为S中的一员。这时v0出发，中间只经过S中的顶点并以不在S中的一个顶点w为终点的最短路径长度可能会减小。就是说，distance*]的值可能发生变化。如果distance*]的值真的发生了变化(减小)，是因为有一条从v0到u，再到w的路径，而且v0到u的路径为最短的这种路径，自u到w的路径是边＜u,w＞的缘故。这条路径长度是distance[u]+matrix[u][w]。因此接下来要调整distance中记录的从源点到V-S中每个顶点v的最短路径长度：从原来的distance[v]和distance[u]+matrix[u][v]中选择较小值作为新的distance[v]，使distance[v]始终保持到目前为止最短的路径长度。重复上述过程，直到S中包含V中的全部顶点。结果数组distance记录了从源点到图中其余各顶点的最短路径长度。在程序5_4.c中，为了实现从“S之外的顶点集合V-S中选出一个顶点u，使distance[u]值最小”的目的，我们建立函数MinCost，选择当s[u]为0时，使distance[u]最小的w,并返回w的值。函数ShortPath按上述说明实现Dijkstra算法。函数PrintMatrix输出图邻接矩阵的值。程序5_4.c#defineHUGE9992#defineN53intmatrix[N][N]={{0,10,2,30,HUGE},4{HUGE,0,HUGE,15,HUGE},5{HUGE,3,0,HUGE,10},6{HUGE,HUGE,HUGE,0,6},7{HUGE,HUGE,HUGE,HUGE,0}};8intdistance[N];9voidShortPath(intmatrix[N][N],intv0,intn)10(11inti,u,dist,number;12ints[N];13for(i=0;i<n;i++)(14s[i]=0;15distance[i]=matrix[v0][i];16}17s[v0]=1;number=1;18while(number<n)(19u=MinCost(distance,s,n);20s[u]=1;21number++;22for(i=0;i<n;i++)(23if(s[i]==0)(2425dist=distance[u]+matrix[u][i]distance[i]=(distance[i]<dist)?distance[i]:dist;

26272829303132333435363738394041424344454647484950}}intMinCost(intdistance[],ints[],intn)(inti,k;intMinDistance=HUGE;for(i=0;i<n;i++)if(s[i]==0&&distance[i]<MinDistance)(MinDistance=distance[i];k=i;}returnk;}voidPrintMatrix(intmatrix[N][N],intn)(inti,j;for(i=0;i<n;i++)(for(j=0;j<n;j++)printf("%5d",matrix[i][j]);printf(〃\n〃)；}}voidmain()

51inti;clrscr();PrintMatrix(matrix,N);ShortPath(matrix,0,N);for(i=1;i<N;i++)printf("(0-%d):%d\n”,i,distance[i]);}顺序查找程序6_1.c实现顺序查找。第2行定义了一个常整数N表明查找表的大小。函数init随机产生N个数并将其置入查找表a中。程序6_1.c#include<stdlib.h>#defineN8inta[N];voidinit(inta[],intn){inti;for(i=0;i<n;i++)a[i]=random(100);}voidprint(inta[],intn)inti;for(i=0;i<n;i++)

1415161718192021222324252627282930313233343536printf("%d",a[i]);printf(〃\n〃)；}intsearch(inta[],intk,intn)(inti=0;for(i=0;i<n&&a[i]!=k;i++);if(i<n)returni;elsereturn-1;}voidmain()(intk;clrscr();init(a,N);print(a,N);printf("PleaseinputKEY:〃)；scanf(〃％d〃,&k);printf("\n%d",search(a,k,N));printf("\nPressanykeytoRETURN...");getche();}折半查找

程序6_2.c实现折半查找。第3行对查找表中元素赋值，且值有序。在函数search中，如果查找下限小于上限，则计算中间位置。并根据中间位置的元素值与k进行比较，根据比较结果决定下次查找的范围。程序6_2.c#include<stdlib.h>#defineN8inta[N]={15,17,30,46,56,82,90,95};voidprint(inta[],intn)5{6inti;7for(i=0;i<n;i++)8printf("%d",a[i]);9printf(〃\n〃)；10}11intsearch(inta[],intk,intn)12{13intlow=0;14inthigh=n-1;15intmid;16while(low<=high){17mid=(low+high)/2;18if(a[mid]==k)returnmid;19elseif(a[mid]>k)high=mid-1;20elselow=mid+1;21}return-1;}voidmain()(intk;clrscr();print(a,N);printf("PleaseinputKEY: 〃)；scanf(〃％d〃,&k);printf("\n%d",search(a,k,N));printf("\nPressanykeyto RETURN...");getche();}二叉排序树程序6_3.c实现二叉排序树的有关操作。第4行到第8行定义二叉排序树结点结构。第9行一维数组a存放用于构造二叉排序树的元素。函数search按3.1所述思想查找与参数item匹配的结点，若找到这个结点，则返回该结点的地址，否则返回空。第11行到第44行函数insert功能是将元素item插入二叉排序树中。若二叉排序树为空，则item作为根结点。若二叉排序树不空，则要根据item的值进行查找。程序6_3.c#include<alloc.h>#defineN8typedefintEL