数据结构常用算法实现print

1、线性表的顺序表示程序2_1.c提供了顺序存储结构下线性表的实现。第1行定义了一个常数值MAXSIZE。它是一个常数，表示线性表的最大长度。第2行把ELEMTYPE设置为int的一个别名。这样，这个例子就可以使用一组整数了。第3行到第7行包含了线性表的说明。接下来从第8行到第46行线性表运算函数的定义。第8到第11行将线性表置成空表，只需简单地将线性表元素个数置成0即可。由于线性表的长度已经记录在结构成员length中，因此求线性表的长度（第35行到第38行）只是返回 length的值。第20到第24行是追加函数，函数append在线性表的表尾插入一个元素。第12行到第19行是插入函数。在表中第

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行的函数find在线性表中查找第一个出现的值为item的元素。如果值item找到了，函数返回元素item所在位置1，否则返回-1。第54行到第67行是main函数的一个例子，说明了线性表的使用。57行调用clear 函数将线性表清空，第58，59，60三行调用ap

3、pend函数追加三个元素，第62行在位置2插入一个元素15，第65行调用delete函数删除位置3的元素。第47行到53行的print函数是为了显示线性表中的数据而设置的。程序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();线性表的链式表示程序2_2.c提供了链式存储结构下线性表的实现。第3行到第8行包含了

7、线性表中结点的说明，其中element表示数据域，存放该结点的数据信息，next为指针域，指明该结点的唯一后继结点在内存中的存放地址，或是在该结点序列中所在的物理位置。线性链表由head和tail表示。接下来从第9行到第76行线性表运算函数的定义。第9行到第14行初始化单链表。head指针与tail指针指向表头结点。在单链表的最后一个结点后插入一个结点只要将单链表尾指针tail指向新插入结点，新插入结点成为最后一个结点即可。第15行到第20行函数append实现追加一个新结点到单链表的最后，新结点的元素值为item。malloc是C语言提供的标准函数，其功能是申请存储空间。设p是指向单链表中一

8、个结点的指针，在p指向的结点后面插入一个结点包括三个步骤。首先，要创建一个新的结点，并且赋给它一个新的值。其次，新结点的next指向指针p指向结点的后继结点。第三，指针p指向的结点的next要指向新插入的结点。第21行到第38行函数insert实现在单链表的第i个结点前面插入一个新结点。新结点的元素值为item，s为指向新结点的指针。算法在实现时，首先查找新结点插入位置，然后根据上面所述修改相应指针。从单链表删去一个结点只需将被删结点的前趋结点的next域指向被删结点的后继结点即可。但必须注意，被删结点占据的内存空间应该返回给存储器。因此可设一个临时指针指向要删去的结点，而后调用C语言提供的标

9、准过程free将被删去的结点占据的内存空间返回给存储器。第39行到第57行的函数delete实现删除结点运算。第58行到第65求单链表中所含结点的个数。为求单链表的结点个数，我们必须从单链表表头开始，沿着每个结点的链指针，依次向后访问并计数，直到最后一个结点位置。程序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是栈数据结构的实现，第3行到第6行包含栈类型的说明， top被定义为表示栈中最上面那个元素的位置。push（第13行到第17行）和pop（第18行到第22行）只是从top指示的数组中的位置插入和删去一个元素，因为top表示栈顶元素的位置，所以push首先把一个值插入到栈顶位置，然后把top加1。同样，pop首先把top减1，然后删去栈顶元素。函数topValue（第23行到27行）只是将栈顶元素返回。如果栈中没有元素，函数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给出了链式栈表示和各种运算的算法。其中top是指向链式栈第一个结点（栈顶）的指针。进栈操作（第13行到第21行）首先申请一个新结点，并初始化该结点，然后修改新产生的结点的next域指向栈顶，并设置top指向新的链表结点。第22行到第32行是出栈操作。变量temp用来存储栈顶结点的值，ltemp用于在删去栈顶结点时保持与栈的链接，它指向当前栈顶链接到的结点。此时把原来的栈顶结点释放回内存，恢复top等于ltemp。也就是指向原来栈顶链接的结点，原来栈顶的值temp作为pop函数的返回值。程序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)*/队列在程序2_5.c中，q表示循环队列（第3行到第9行），其队头与队尾指示变量分别为front和rear。队列中的元素类型为int（第3行）。函数enqueue（第14行到第19行）执行队列的插入操作，参数item是插入队列的元素。当队列不满时，enqueue首先移动队尾指针，然后将item置入rea

22、r所指位置。函数dequeue(第20行到25行)执行队列的删除操作，返回从队列中取出的元素。函数firstValue（第26行到第30行）返回队列头元素。程序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给出了链式队列的说明和函数的实现。front和rear分别是指向队首和队尾元素的指针。链式队列的实现不需要表头结点，当队列为空时，指针front和rear的值均为空（NULL）。当在队列中插入一个结点时(第14行到27行)，新结点链入rear所指结点的next域，并使rear指向新的结点。如果在插入之前

26、队列为空，则指针front指向新插入的结点。当从队列中删除一个结点时（第28行到37行），要把front所指结点的next域的值赋给front，并且释放这个结点。如果删除之后队列为空，则置指针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是按照快速转置算法求矩阵的转置。程序第2行给出稀疏矩阵a的三元组表表示。函数FastTranspose按照快速转置算法思想将稀疏矩阵a转置为稀疏矩阵b，b也表示为三元组表形式。第11行到第13行计算矩阵a的每一列的非零元素个数。第15行计算a中每一列第一个非零元素在b中的起始位置。第16行第22行对a中的元素依此进行转置。程序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的行数，程序第2行给出稀疏矩阵a的列数（b的行数），程序第3行给出稀疏矩阵的列数。第4行和第5行给出矩阵a与b的三元组表。第6行定义存放a与b相乘的结果c(二维数组)。第7行到第27行的MatrixMultiply函数实现稀疏矩阵相乘。此算法中数组S和T的意义与矩阵转置中相同，分别表示矩阵B中各行非零元素个数和各行第一个非零元素在数组b中的位置。在找B中某行的所有非零元素时，只要知道此行第一个非零元素在b中的位置和下

33、一行第一个非零元素在b中的位置即可。例如，在B中行号为i所有非零元素，就是在b中从Ti到Ti+1-1的这些元素。对于在B中最后一行n，实际上它没有“下一行”了，只是为了求Tn+1，又虚设了第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中，函数inorder实现中序周游二叉树的递归算法，周游时输出所访问结点的值。程序中第2行定义二叉树结点元素类型为字符型，第3行到第7行定义二叉树结点类型，第8行定义root为二叉树的根结点指针。第24行到第31行的inorder函数首先检查树是否为空（如果为空，则周游完成；并且函数直接返回），否则对左子树递归调用本函数，当左子树周游完成后，对根结点调用printf函数打印结点的值（或者按照需要完成某些运算）。最后，对右子树进行同样的操作。setup函数利用前序

36、结果序列建立二叉树。Setup扫描一个字符串，若当前字符不为.，则申请一个结点，存入当前字符，并置该结点的左、右指针为空。然后用该结点的左链和右链存放子树根结点的指针，递归调用函数setup，建立当前结点的左子树和右子树。当到达字符串的末尾时，建立二叉树的过程结束。第32行到第37行是main函数的一个例子，首先调用函数setup建立一棵二叉树。然后调用inorder函数对二叉树进行中序周游。程序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实现二叉树周游的非递归算法。为了实现非递归算法，要在程序中设置一个栈结构，用以保存指向结点的指针，

39、以便能够继续周游。第16行到第33是第3章中顺序栈的实现。第34行到第48行的函数setup与程序4_1.c功能相同。第49行到第63的inorder函数实现二叉树中序周游。对于inorder函数来说，首先从二叉树的根结点开始周游，令指针变量p指向当前访问结点，只是在访问结点之前，若p所指结点的左链不空，则沿着其左链前进，在前进过程中，把经过的结点指针值逐一压栈。这个过程一直重复到p为空，从而实现周游左子树。然后，如果栈不空，则从栈中弹出一个结点的指针值，访问这个结点。接下来，p取其右链的值，实现周游右子树。整个周游过程是在一个do-while循环中进行。只有当p为空，而且栈也为空时，do-w

40、hile循环结束，周游结束。程序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算法由已知的权集构造Huffman树并求Huffman编码。第2行定义权集元素个数。

44、第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中的最小元素冲掉，返回最小元素所在位置。函数huff

45、mantree按照huffman算法的基本思想，不断将两个子树合并为一个较大的子树，每次构成的新子树的根结点顺序存放到数组HT中的前n个分量的后面。函数huffmancode求每个叶结点的huffman编码。从该叶结点开始，沿结点的双亲域回退到根结点，每回退一步，就走过了huffman树中的一个分支，从而得到一位huffman编码值。对于第i个叶结点，其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深度优先遍历在程序5_1.c，我们用邻接表表示图。用一维数组visitedw标记顶点w是否被访问过。程序第3行到第7行定义图的邻接表存储结构。函数setup建立n个顶点的邻接表，该函数首先将邻接表的头结点初始化为空（第14行），然后依次输入相邻顶点（vi vj），并将vj链入vi的链表

51、中。输入过程直到出现（vi=0 vj=0)结束。第24行到第37行的函数print用于打印邻接表的全部内容。在打印的结果中，第一列整数为图中各顶点的序号，同一行的是该顶点的相邻顶点。第38行到第52行的dfs函数实现以参数v为起点的深度优先搜索。指针p指向顶点v的第一个相邻顶点，在执行函数dfs时沿着v的邻接表前进。程序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