數(shù)據(jù)結(jié)構(gòu)常用算法實(shí)現(xiàn)print

1、線性表的順序表示程序2_1.c提供了順序存儲結(jié)構(gòu)下線性表的實(shí)現(xiàn)。第1行定義了一個常數(shù)值MAXSIZE。它是一個常數(shù)，表示線性表的最大長度。第2行把ELEMTYPE設(shè)置為int的一個別名。這樣，這個例子就可以使用一組整數(shù)了。第3行到第7行包含了線性表的說明。接下來從第8行到第46行線性表運(yùn)算函數(shù)的定義。第8到第11行將線性表置成空表，只需簡單地將線性表元素個數(shù)置成0即可。由于線性表的長度已經(jīng)記錄在結(jié)構(gòu)成員length中，因此求線性表的長度（第35行到第38行）只是返回 length的值。第20到第24行是追加函數(shù)，函數(shù)append在線性表的表尾插入一個元素。第12行到第19行是插入函數(shù)。在表中第

2、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行的函數(shù)find在線性表中查找第一個出現(xiàn)的值為item的元素。如果值item找到了，函數(shù)返回元素item所在位置1，否則返回-1。第54行到第67行是main函數(shù)的一個例子，說明了線性表的使用。57行調(diào)用clear 函數(shù)將線性表清空，第58，59，60三行調(diào)用ap

3、pend函數(shù)追加三個元素，第62行在位置2插入一個元素15，第65行調(diào)用delete函數(shù)刪除位置3的元素。第47行到53行的print函數(shù)是為了顯示線性表中的數(shù)據(jù)而設(shè)置的。程序2_1.c1#define MAXSIZE 9992typedef int ELEMTYPE;3struct list 4ELEMTYPE listarrayMAXSIZE;5int length;6;7struct list l;8void clear()910l.length = 0;1112void insert(int pos ,ELEMTYPE item)1314int i;15for(i = l.length

4、;i>pos;i-)16l.listarrayi = l.listarrayi-1;17l.listarraypos = item;18l.length+;1920void append(ELEMTYPE item)2122l.listarrayl.length+ = item;2425ELEMTYPE delete(int pos)2627int i;28ELEMTYPE temp;29temp = l.listarraypos;30for(i = pos;i<l.length-1;i+)31l.listarrayi = l.listarrayi+1;32l.length-;33

5、return temp;35int length()37return l.length;39int find(ELEMTYPE item)40int i;42for (i=0;i<l.length;i+)43if (l.listarrayi = item)44return i;45return -1; 47void print()48int i;50 for (i=0;i<l.length;i+)51printf("%d ",l.listarrayi);52printf("n");54void main()55clrscr();57clear

6、();58append(10);/* L is 10 */59append(20);/* L is (10,20) */60append(30); /* L is (10,20,30) */61print();62insert(2,15);/* L is (10,20,15,30) */63print();64printf("n%d",find(100);65printf("n%dn",delete(3); /* L is (10,20,15) */66 print();線性表的鏈?zhǔn)奖硎境绦?_2.c提供了鏈?zhǔn)酱鎯Y(jié)構(gòu)下線性表的實(shí)現(xiàn)。第3行到第8行包含了

7、線性表中結(jié)點(diǎn)的說明，其中element表示數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息，next為指針域，指明該結(jié)點(diǎn)的唯一后繼結(jié)點(diǎn)在內(nèi)存中的存放地址，或是在該結(jié)點(diǎn)序列中所在的物理位置。線性鏈表由head和tail表示。接下來從第9行到第76行線性表運(yùn)算函數(shù)的定義。第9行到第14行初始化單鏈表。head指針與tail指針指向表頭結(jié)點(diǎn)。在單鏈表的最后一個結(jié)點(diǎn)后插入一個結(jié)點(diǎn)只要將單鏈表尾指針tail指向新插入結(jié)點(diǎn)，新插入結(jié)點(diǎn)成為最后一個結(jié)點(diǎn)即可。第15行到第20行函數(shù)append實(shí)現(xiàn)追加一個新結(jié)點(diǎn)到單鏈表的最后，新結(jié)點(diǎn)的元素值為item。malloc是C語言提供的標(biāo)準(zhǔn)函數(shù)，其功能是申請存儲空間。設(shè)p是指向單鏈表中一

8、個結(jié)點(diǎn)的指針，在p指向的結(jié)點(diǎn)后面插入一個結(jié)點(diǎn)包括三個步驟。首先，要創(chuàng)建一個新的結(jié)點(diǎn)，并且賦給它一個新的值。其次，新結(jié)點(diǎn)的next指向指針p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)。第三，指針p指向的結(jié)點(diǎn)的next要指向新插入的結(jié)點(diǎn)。第21行到第38行函數(shù)insert實(shí)現(xiàn)在單鏈表的第i個結(jié)點(diǎn)前面插入一個新結(jié)點(diǎn)。新結(jié)點(diǎn)的元素值為item，s為指向新結(jié)點(diǎn)的指針。算法在實(shí)現(xiàn)時，首先查找新結(jié)點(diǎn)插入位置，然后根據(jù)上面所述修改相應(yīng)指針。從單鏈表刪去一個結(jié)點(diǎn)只需將被刪結(jié)點(diǎn)的前趨結(jié)點(diǎn)的next域指向被刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)即可。但必須注意，被刪結(jié)點(diǎn)占據(jù)的內(nèi)存空間應(yīng)該返回給存儲器。因此可設(shè)一個臨時指針指向要刪去的結(jié)點(diǎn)，而后調(diào)用C語言提供的標(biāo)

9、準(zhǔn)過程free將被刪去的結(jié)點(diǎn)占據(jù)的內(nèi)存空間返回給存儲器。第39行到第57行的函數(shù)delete實(shí)現(xiàn)刪除結(jié)點(diǎn)運(yùn)算。第58行到第65求單鏈表中所含結(jié)點(diǎn)的個數(shù)。為求單鏈表的結(jié)點(diǎn)個數(shù)，我們必須從單鏈表表頭開始，沿著每個結(jié)點(diǎn)的鏈指針，依次向后訪問并計(jì)數(shù)，直到最后一個結(jié)點(diǎn)位置。程序2_2.c1#include <alloc.h>2typedef int ELEMTYPE;3struct list 4ELEMTYPE element;5struct list *next;6;7struct list *head;8struct list *tail;9void init()1011head = m

10、alloc(sizeof(struct list);12head->next = NULL;13tail = head;1415void append(ELEMTYPE item)1617tail=tail->next=(structlist *)malloc(sizeof(struct list);18tail->element = item;19tail->next = NULL;2021int insert(int pos,ELEMTYPE item)2223struct list *p,*s;24int j;25s = (struct list *)malloc

11、(sizeof(struct list);26s->element = item;27p = head;28j = 1;29while (p!=NULL) && (j<pos) 30p = p->next;31j+;3233if(!p)|(j>pos) return 0;34s->next = p->next;35p->next = s;36if (tail = p) tail = s;37return 1;3839ELEMTYPE delete(int pos)4041struct list *p,*q;42ELEMTYPE temp

12、;43int j;44q = p;p = head->next;45j = 1;46while (p!=NULL) && (j<pos) 47q = p; p = p->next;48j+;4950if(!p)|(j>pos)51return 052q->next = p->next;53temp = p->element;54if (tail = p) tail = q;55free(p);56return temp;5758int length()5960struct list *p;61int cnt = 0;62for (p =

13、 head->next;p != NULL;p = p->next)63cnt+;64return cnt;6566int find(ELEMTYPE item)6768struct list *p = head->next;69while (p!=NULL) 70if (p->element = item)71return 1;72else73p = p->next;7475return 0;7677void print()7879struct list *p;80printf("n");81for (p = head->next;p!

14、=NULL;p=p->next)82printf("%d ",p->element);8384void main()8586clrscr();87init();88append(10); /* list is (10) */89append(20);/* list is (10,20) */90append(30);/* list is (10,20,30) */91append(40);/* list is (10,20,30,40) */92insert(3,35);/* list is (10,20,30,35,40) */93print();94prin

15、tf("n%dn",delete(4);/* list is (10,20,30,35) */95print();96棧程序2_3.c是棧數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，第3行到第6行包含棧類型的說明， top被定義為表示棧中最上面那個元素的位置。push（第13行到第17行）和pop（第18行到第22行）只是從top指示的數(shù)組中的位置插入和刪去一個元素，因?yàn)閠op表示棧頂元素的位置，所以push首先把一個值插入到棧頂位置，然后把top加1。同樣，pop首先把top減1，然后刪去棧頂元素。函數(shù)topValue（第23行到27行）只是將棧頂元素返回。如果棧中沒有元素，函數(shù)isEmpty（第2

16、8行到第31行）返回1，否則返回0。程序2_3.c#include <assert.h>#include<stdio.h>#define MAXSIZE 100typedef int ELEMTYPE;struct stack ELEMTYPE listarrayMAXSIZE;int top;struct stack s;void init()s.top = 0;void push(ELEMTYPE item)assert(s.top<MAXSIZE);s.listarrays.top+ = item;ELEMTYPE pop()int isEmpty();as

17、sert(!isEmpty();return s.listarray-s.top;ELEMTYPE topValue()int isEmpty();assert(!isEmpty();return s.listarrays.top-1;int isEmpty()return s.top = 0;void main()init();push(10);/* s is (10) */push(20); /* s is (20,10) */printf("%d",topValue();/*return top element 20*/printf("n");pr

18、intf("%d",pop();/* s is (10) */程序2_4.c給出了鏈?zhǔn)綏１硎竞透鞣N運(yùn)算的算法。其中top是指向鏈?zhǔn)綏５谝粋€結(jié)點(diǎn)（棧頂）的指針。進(jìn)棧操作（第13行到第21行）首先申請一個新結(jié)點(diǎn)，并初始化該結(jié)點(diǎn)，然后修改新產(chǎn)生的結(jié)點(diǎn)的next域指向棧頂，并設(shè)置top指向新的鏈表結(jié)點(diǎn)。第22行到第32行是出棧操作。變量temp用來存儲棧頂結(jié)點(diǎn)的值，ltemp用于在刪去棧頂結(jié)點(diǎn)時保持與棧的鏈接，它指向當(dāng)前棧頂鏈接到的結(jié)點(diǎn)。此時把原來的棧頂結(jié)點(diǎn)釋放回內(nèi)存，恢復(fù)top等于ltemp。也就是指向原來?xiàng)ｍ旀溄拥慕Y(jié)點(diǎn)，原來?xiàng)ｍ數(shù)闹祎emp作為pop函數(shù)的返回值。程序2_4.c

19、 #include <malloc.h> #include<stdio.h>#include <assert.h>typedef int ELEMTYPE;struct node ELEMTYPE elem;struct node *next;struct node *top;void init()top = NULL;void push(ELEMTYPE item)struct node *p;if (p=(struct node *)malloc(sizeof(struct node)!=NULL)p->elem = item;p->next

20、 = top;top = p;ELEMTYPE pop()intisEmpty();ELEMTYPE temp;struct node *ltemp;assert(!isEmpty();temp = top->elem;ltemp = top->next;free(top);top = ltemp;return temp;ELEMTYPE topValue()intisEmpty();assert(!isEmpty();return top->elem;intisEmpty()return top = NULL;void main()init();push(10);/* s

21、is (10) */push(20); /* s is (20,10) */push(30); /* s is (30,20,10) */printf("%dn",topValue();printf("%dn",pop();/* s is (20,10)*/隊(duì)列在程序2_5.c中，q表示循環(huán)隊(duì)列（第3行到第9行），其隊(duì)頭與隊(duì)尾指示變量分別為front和rear。隊(duì)列中的元素類型為int（第3行）。函數(shù)enqueue（第14行到第19行）執(zhí)行隊(duì)列的插入操作，參數(shù)item是插入隊(duì)列的元素。當(dāng)隊(duì)列不滿時，enqueue首先移動隊(duì)尾指針，然后將item置入rea

22、r所指位置。函數(shù)dequeue(第20行到25行)執(zhí)行隊(duì)列的刪除操作，返回從隊(duì)列中取出的元素。函數(shù)firstValue（第26行到第30行）返回隊(duì)列頭元素。程序2_5.c#include <assert.h>#include<stdio.h>#define MAXSIZE 100typedef int ELEMTYPE;struct queue int front;int rear;ELEMTYPE elemMAXSIZE;struct queue q;void init() q.front = q.rear = 0;void enqueue(ELEMTYPE item

23、)assert(q.rear+1) % MAXSIZE) != q.front); q.rear = (q.rear + 1) % MAXSIZE; /* increment rear */q.elemq.rear = item;ELEMTYPE dequeue()/* dequeue element fro front of queue */int isEmpty();assert(!isEmpty();/* there must be somethingtodequeue */q.front = (q.front + 1) % MAXSIZE;/* increment front */re

24、turn q.elemq.front; /* return value */ELEMTYPE firstValue() /* get value of front element */int isEmpty();assert(!isEmpty();return q.elem(q.front+1) % MAXSIZE;int isEmpty()/* TRUE is queue is empty */return q.front = q.rear;void main()init();enqueue(10); /* q is (10)*/enqueue(20); /* q is (10,20)*/e

25、nqueue(30);/* q is (10,20,30)*/printf("%dn",firstValue();/* will display 10 */printf("%dn",dequeue();/* will displa 10 */程序2_6.c給出了鏈?zhǔn)疥?duì)列的說明和函數(shù)的實(shí)現(xiàn)。front和rear分別是指向隊(duì)首和隊(duì)尾元素的指針。鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)不需要表頭結(jié)點(diǎn)，當(dāng)隊(duì)列為空時，指針front和rear的值均為空（NULL）。當(dāng)在隊(duì)列中插入一個結(jié)點(diǎn)時(第14行到27行)，新結(jié)點(diǎn)鏈入rear所指結(jié)點(diǎn)的next域，并使rear指向新的結(jié)點(diǎn)。如果在插入之前

26、隊(duì)列為空，則指針front指向新插入的結(jié)點(diǎn)。當(dāng)從隊(duì)列中刪除一個結(jié)點(diǎn)時（第28行到37行），要把front所指結(jié)點(diǎn)的next域的值賦給front，并且釋放這個結(jié)點(diǎn)。如果刪除之后隊(duì)列為空，則置指針rear為空（NULL）。程序2_6.c#include <malloc.h>#include<stdio.h>#include <assert.h>typedef int ELEMTYPE;struct node ELEMTYPE elem;struct node *next;struct node *front;struct node *rear;void init

27、()rear = front = NULL;void enqueue(ELEMTYPE item)if (rear != NULL) rear->next=(struct node *)malloc(sizeof(struct node);rear->next->elem = item;rear->next->next = NULL;rear = rear->next;else front=rear=(struct node *)malloc(sizeof(struct node);front->elem = item;front->next =

28、 NULL;ELEMTYPE dequeue()int isEmpty();ELEMTYPE temp = front->elem;struct node *ltemp = front;assert(!isEmpty();front = front->next;free(ltemp);if (front=NULL) rear = NULL;return temp;ELEMTYPE firstValue()int isEmpty();assert(!isEmpty();return front->elem;int isEmpty()return front = NULL;voi

29、d main()init();enqueue(10);enqueue(20);enqueue(30);printf("%dn",firstValue();printf("%dn",dequeue();稀疏矩陣程序3_1.c是按照快速轉(zhuǎn)置算法求矩陣的轉(zhuǎn)置。程序第2行給出稀疏矩陣a的三元組表表示。函數(shù)FastTranspose按照快速轉(zhuǎn)置算法思想將稀疏矩陣a轉(zhuǎn)置為稀疏矩陣b，b也表示為三元組表形式。第11行到第13行計(jì)算矩陣a的每一列的非零元素個數(shù)。第15行計(jì)算a中每一列第一個非零元素在b中的起始位置。第16行第22行對a中的元素依此進(jìn)行轉(zhuǎn)置。程序3_1.c

30、1#define MAXCOL 1002int a3 = 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;3int b93;4FastTranspose(int a3,int b3)56int m,n,tn,i,j;7int sMAXCOL,tMAXCOL;8m = a00;n = a01;tn = a02;9b00 = n;b01 = m;b02 = tn;10if (tn<=0) return;11for (i = 0;i < n;i+) si = 0;12for (i = 1;i <= tn;i+)13sai

31、1 = sai1 + 1;14t0 = 1;15for (i = 1;i < n;i+)ti=ti-1+si-1;16for (i = 1;i <= tn;i+) 17j = ai1;18btj0 = ai1;19btj1 = ai0;20btj2 = ai2;21tj = tj + 1;222324main()2526int i;27clrscr();28for (i=0;i<=8;i+)29printf("%d %d %dn",ai0,ai1,ai2);30FastTranspose(a,b);31printf("n");32for

32、 (i=0;i<=8;i+)33printf("%d %d %dn",bi0,bi1,bi2);34程序3_2.c是求矩陣的乘積。程序第1行給出稀疏矩陣a的行數(shù)，程序第2行給出稀疏矩陣a的列數(shù)（b的行數(shù)），程序第3行給出稀疏矩陣的列數(shù)。第4行和第5行給出矩陣a與b的三元組表。第6行定義存放a與b相乘的結(jié)果c(二維數(shù)組)。第7行到第27行的MatrixMultiply函數(shù)實(shí)現(xiàn)稀疏矩陣相乘。此算法中數(shù)組S和T的意義與矩陣轉(zhuǎn)置中相同，分別表示矩陣B中各行非零元素個數(shù)和各行第一個非零元素在數(shù)組b中的位置。在找B中某行的所有非零元素時，只要知道此行第一個非零元素在b中的位置和下

33、一行第一個非零元素在b中的位置即可。例如，在B中行號為i所有非零元素，就是在b中從Ti到Ti+1-1的這些元素。對于在B中最后一行n，實(shí)際上它沒有“下一行”了，只是為了求Tn+1，又虛設(shè)了第n+1行，且Tn+1 的值為 t2+1。程序3_2.c1#define M 32#define P 43#define N 24int a3 =3,4,4,0,0,3,0,3,2,1,1,1,2,0,2;5int b3 =4,2,3,0,1,2,2,0,2,3,1,1;6int cMN;7MatrixMultiply()89int m,n,t1,t2,i,j,p,k;10int sP,tP;11m = a0

34、0;n = a01;t1 = a02;12if (n = b00) 13p = b01;14t2 = b02;1516if (t1*t2 = 0) return;17for (i = 0;i < n;i+) si = 0;18for (i = 1;i <= t2;i+)19sbi0 = sbi0 + 1;20t0 = 1;21for (i = 1;i < n+1;i+)ti=ti-1+si-1;22for (i = 1;i <= t1;i+) 23k = ai1;24for(j = tk;j <= tk+1-1;j+)25cai0bj1 += ai2*bj2;26

35、2728main()2930int i,j;31clrscr();32MatrixMultiply();33二叉樹遍歷在程序4_1.c中，函數(shù)inorder實(shí)現(xiàn)中序周游二叉樹的遞歸算法，周游時輸出所訪問結(jié)點(diǎn)的值。程序中第2行定義二叉樹結(jié)點(diǎn)元素類型為字符型，第3行到第7行定義二叉樹結(jié)點(diǎn)類型，第8行定義root為二叉樹的根結(jié)點(diǎn)指針。第24行到第31行的inorder函數(shù)首先檢查樹是否為空（如果為空，則周游完成；并且函數(shù)直接返回），否則對左子樹遞歸調(diào)用本函數(shù)，當(dāng)左子樹周游完成后，對根結(jié)點(diǎn)調(diào)用printf函數(shù)打印結(jié)點(diǎn)的值（或者按照需要完成某些運(yùn)算）。最后，對右子樹進(jìn)行同樣的操作。setup函數(shù)利用前序

36、結(jié)果序列建立二叉樹。Setup掃描一個字符串，若當(dāng)前字符不為.，則申請一個結(jié)點(diǎn)，存入當(dāng)前字符，并置該結(jié)點(diǎn)的左、右指針為空。然后用該結(jié)點(diǎn)的左鏈和右鏈存放子樹根結(jié)點(diǎn)的指針，遞歸調(diào)用函數(shù)setup，建立當(dāng)前結(jié)點(diǎn)的左子樹和右子樹。當(dāng)?shù)竭_(dá)字符串的末尾時，建立二叉樹的過程結(jié)束。第32行到第37行是main函數(shù)的一個例子，首先調(diào)用函數(shù)setup建立一棵二叉樹。然后調(diào)用inorder函數(shù)對二叉樹進(jìn)行中序周游。程序4_1.c1#include <alloc.h>2typedef char ELEMTYPE;3struct BinNode 4ELEMTYPE element;5struct BinNo

37、de *left;6struct BinNode *right;7;8struct BinNode *root;9void setup(struct BinNode *t)1011ELEMTYPE ch;12struct BinNode *p;13scanf("%c",&ch);14if (ch = '.')15*t = NULL;16else 17p = (struct BinNode *)malloc(sizeof(struct BinNode);18p->element = ch;19*t = p;20setup(&(p->

38、left);21setup(&(p->right);222324void inorder(struct BinNode *t)2526if (t != NULL) 27inorder(t->left);28printf("%c ",t->element);29inorder(t->right);303132void main()3334 clrscr();35 setup(&root);36 inorder(root);37程序4_2.c實(shí)現(xiàn)二叉樹周游的非遞歸算法。為了實(shí)現(xiàn)非遞歸算法，要在程序中設(shè)置一個棧結(jié)構(gòu)，用以保存指向結(jié)點(diǎn)的指針，

39、以便能夠繼續(xù)周游。第16行到第33是第3章中順序棧的實(shí)現(xiàn)。第34行到第48行的函數(shù)setup與程序4_1.c功能相同。第49行到第63的inorder函數(shù)實(shí)現(xiàn)二叉樹中序周游。對于inorder函數(shù)來說，首先從二叉樹的根結(jié)點(diǎn)開始周游，令指針變量p指向當(dāng)前訪問結(jié)點(diǎn)，只是在訪問結(jié)點(diǎn)之前，若p所指結(jié)點(diǎn)的左鏈不空，則沿著其左鏈前進(jìn)，在前進(jìn)過程中，把經(jīng)過的結(jié)點(diǎn)指針值逐一壓棧。這個過程一直重復(fù)到p為空，從而實(shí)現(xiàn)周游左子樹。然后，如果棧不空，則從棧中彈出一個結(jié)點(diǎn)的指針值，訪問這個結(jié)點(diǎn)。接下來，p取其右鏈的值，實(shí)現(xiàn)周游右子樹。整個周游過程是在一個do-while循環(huán)中進(jìn)行。只有當(dāng)p為空，而且棧也為空時，do-w

40、hile循環(huán)結(jié)束，周游結(jié)束。程序4_2.c1#include <alloc.h>2#include <assert.h>3#define MAXSIZE 1004typedef char ELEMTYPE;5struct BinNode 6ELEMTYPE element;7struct BinNode *left;8struct BinNode *right;9;10struct stack 11struct BinNode *listarrayMAXSIZE;12int top;13;14struct BinNode *root;15struct stack s;1

41、6void init()1718s.top = 0;1920void push(struct BinNode *item)2122assert(s.top<MAXSIZE);23s.listarrays.top+ = item;2425struct BinNode *pop()2627assert(!isEmpty();28return s.listarray-s.top;2930int isEmpty()3132return s.top = 0;3334void setup(struct BinNode *t)3536ELEMTYPE ch;37struct BinNode *p;38

42、scanf("%c",&ch);39if (ch = '.')40*t = NULL;41else 42p = (struct BinNode *)malloc(sizeof(struct BinNode);43p->element = ch;44*t = p;45setup(&(p->left);46setup(&(p->right);474849void inorder(struct BinNode *t)5051struct BinNode *p = t;52do 53while (p != NULL) 54p

43、ush(p);55p = p->left;5657if (!isEmpty() 58p = pop();59printf("%c ",p->element);60p = p->right;6162while (!(p = NULL && isEmpty();6364void main()6566 clrscr();67 init();68 setup(&root);69 inorder(root);70Huffman樹程序4_3.c按照Huffman算法由已知的權(quán)集構(gòu)造Huffman樹并求Huffman編碼。第2行定義權(quán)集元素個數(shù)。

44、第3行定義Huffamn樹結(jié)點(diǎn)個數(shù)。第4行到第9行定義Huffamn樹結(jié)點(diǎn)類型，結(jié)點(diǎn)類型由權(quán)值、雙親、左子樹和右子樹組成。第10行到第13行定義Huffamn編碼結(jié)構(gòu)，由存放編碼的數(shù)組和編碼的開始位置組成。第14行的數(shù)組weight存放權(quán)值，第15行數(shù)組 HT用來存放Huffman樹，第16行數(shù)組HC用于存放Huffman編碼。第17行到26行的init函數(shù)用于初始化Huffman樹。將由n個權(quán)值作為葉結(jié)點(diǎn)存放到數(shù)組HT的前n個分量中。第27行到38行函數(shù)minimum從數(shù)組weight中求出當(dāng)前最小的元素，并用一個大數(shù)HUGE把weight中的最小元素沖掉，返回最小元素所在位置。函數(shù)huff

45、mantree按照huffman算法的基本思想，不斷將兩個子樹合并為一個較大的子樹，每次構(gòu)成的新子樹的根結(jié)點(diǎn)順序存放到數(shù)組HT中的前n個分量的后面。函數(shù)huffmancode求每個葉結(jié)點(diǎn)的huffman編碼。從該葉結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親域回退到根結(jié)點(diǎn)，每回退一步，就走過了huffman樹中的一個分支，從而得到一位huffman編碼值。對于第i個葉結(jié)點(diǎn)，其huffman編碼存放在HCi.bit中從HTi.start到n的分量上。程序4_3.c1#define HUGE 9992#define N 83#define M 2*N-14struct HuffmanNode 5int weight;6

46、int parent;7int left;8int right;9;10struct HuffmanCode 11int bit10;12int start;13;14int weight = 5,29,7,8,14,23,3,11,0,0,0,0,0,0,0;15struct HuffmanNode HTM;16struct HuffmanCode HCN;17void init()1819int i;20for (i=0;i<M;i+) 21HTi.parent = 0;22HTi.weight = weighti;23HTi.left = 0;24HTi.right = 0;252

47、627int minimum()2829int i,k;30int min = HUGE;31for(i=0;i<M;i+)32if (min>weighti && weighti != 0) 33min = weighti;34k = i;3536weightk = HUGE;37return k;3839void huffmantree()4041int i,l,r;42for (i=N;i<M;i+) 43l = minimum();44r = minimum();45HTl.parent = i;46HTr.parent = i;47HTi.left

48、= l;48HTi.right = r;49HTi.weight = HTl.weight + HTr.weight;50weighti = HTi.weight;515253void huffmancode()5455int i,p,j,c;56struct HuffmanCode cd;57for(i=0;i<N;i+) 58cd.start = N-1;59c = i;60p = HTc.parent;61while (p != 0) 62if (HTp.left = c)63cd.bitcd.start = 0;64else cd.bitcd.start = 1;65cd.sta

49、rt-;66c = p;67p = HTc.parent;6869for(j=cd.start+1;j<N;j+) HCi.bitj = cd.bitj;70HCi.start = cd.start;717273void main()7475int i,j;76clrscr();77init();78huffmantree();79for (i=0;i<M;i+)80printf("%d%d%d%dn",HTi.weight,HTi.parent,HTi.left,HTi.right);81printf("n");82huffmancode(

50、);83for (i=0;i<N;i+) 84printf("%5d: ",HTi.weight);85for (j=HCi.start+1;j<N;j+)86printf("%d ",HCi.bitj);87printf("n");8889深度優(yōu)先遍歷在程序5_1.c，我們用鄰接表表示圖。用一維數(shù)組visitedw標(biāo)記頂點(diǎn)w是否被訪問過。程序第3行到第7行定義圖的鄰接表存儲結(jié)構(gòu)。函數(shù)setup建立n個頂點(diǎn)的鄰接表，該函數(shù)首先將鄰接表的頭結(jié)點(diǎn)初始化為空（第14行），然后依次輸入相鄰頂點(diǎn)（vi vj），并將vj鏈入vi的鏈表

51、中。輸入過程直到出現(xiàn)（vi=0 vj=0)結(jié)束。第24行到第37行的函數(shù)print用于打印鄰接表的全部內(nèi)容。在打印的結(jié)果中，第一列整數(shù)為圖中各頂點(diǎn)的序號，同一行的是該頂點(diǎn)的相鄰頂點(diǎn)。第38行到第52行的dfs函數(shù)實(shí)現(xiàn)以參數(shù)v為起點(diǎn)的深度優(yōu)先搜索。指針p指向頂點(diǎn)v的第一個相鄰頂點(diǎn)，在執(zhí)行函數(shù)dfs時沿著v的鄰接表前進(jìn)。程序5_1.c1#include <alloc.h>2#define MAXVERTEX 1003struct EdgeNode 4int vertex;5struct EdgeNode *next;6;7struct EdgeNode *aMAXVERTEX;8int visitedMAXVERTEX;9void setup(int n)1011int vi,vj;12int i;13struct EdgeNode *p;14for (i=0;i<n;i+)ai = NULL;15scanf("%d%d",&vi,&vj);16while