数据结构常用算法实现print.docx
《数据结构常用算法实现print.docx》由会员分享,可在线阅读,更多相关《数据结构常用算法实现print.docx(44页珍藏版)》请在冰点文库上搜索。
数据结构常用算法实现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
1#define MAXSIZE999
2ﻩtypedefintELEMTYPE;
3structlist {
4ﻩﻩELEMTYPE listarray[MAXSIZE];
5int length;
6ﻩ};
7ﻩstructlistl;
8void clear()
9{
10ﻩﻩl.length= 0;
11}
12ﻩvoidinsert(intpos ,ELEMTYPE item)
13{
14ﻩinti;
15ﻩfor(i= l.length;i>pos;i——)
16ﻩl.listarray[i]= l.listarray[i—1];
17ﻩl。
listarray[pos]= item;
18l.length++;
19ﻩ}
20ﻩvoidappend(ELEMTYPEitem)
21ﻩ{
22ﻩl。
listarray[l.length++]=item;
24}
25ﻩELEMTYPE delete(intpos)
26ﻩ{
27ﻩinti;
28ELEMTYPE temp;
29ﻩtemp= l。
listarray[pos];
30ﻩﻩfor(i =pos;i<l。
length-1;i++)
31ﻩﻩl。
listarray[i]=l。
listarray[i+1];
32l.length--;
33ﻩreturntemp;}
35ﻩintlength()
{
37ﻩreturnl.length;}
39intfind(ELEMTYPEitem)
40{inti;
42for(i=0;i<l。
length;i++)
43ﻩﻩif(l.listarray[i] ==item)
44ﻩreturn i;
45ﻩﻩreturn -1; }
47ﻩvoidprint()
48ﻩ{inti;
50ﻩfor(i=0;i〈l.length;i++)
51ﻩﻩprintf(”%d”,l.listarray[i]);
52printf(”\n”);}
54voidmain()
55{clrscr();
57ﻩclear();
58append(10);ﻩ/*Lis 10*/
59ﻩﻩappend(20);/*Lis(10,20)*/
60append(30);/*Lis(10,20,30)*/
61ﻩprint();
62insert(2,15);/*Lis(10,20,15,30)*/
63ﻩprint();
64ﻩprintf(”\n%d”,find(100));
65ﻩﻩprintf(”\n%d\n”,delete(3));/*Lis(10,20,15)*/
66 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
1ﻩ#include〈alloc.h〉
2typedef intELEMTYPE;
3structlist{
4ELEMTYPE element;
5ﻩstructlist*next;
6};
7ﻩstructlist *head;
8ﻩstructlist*tail;
9ﻩvoidinit()
10ﻩ{
11ﻩﻩhead =malloc(sizeof(structlist));
12ﻩhead—〉next=NULL;
13ﻩtail=head;
14}
15void append(ELEMTYPEitem)
16ﻩ{
17ﻩtail=tail—〉next=(structlist *)malloc(sizeof(structlist));
18ﻩtail-〉element =item;
19ﻩtail—〉next =NULL;
20}
21intinsert(int pos,ELEMTYPE item)
22ﻩ{
23ﻩstructlist*p,*s;
24ﻩintj;
25ﻩﻩs = (structlist*)malloc(sizeof(struct list));
26ﻩﻩs->element=item;
27ﻩp =head;
28ﻩj = 1;
29ﻩwhile((p!
=NULL)&&(j〈pos)){
30ﻩﻩp=p->next;
31ﻩj++;
32ﻩ}
33ﻩﻩif((!
p)||(j〉pos))return0;
34ﻩs->next=p->next;
35p->next=s;
36ﻩﻩif(tail==p)tail=s;
37return 1;
38}
39ELEMTYPE delete(intpos)
40ﻩ{
41ﻩstructlist*p,*q;
42ﻩELEMTYPE temp;
43ﻩint j;
44ﻩq=p;p=head—>next;
45ﻩﻩj=1;
46ﻩwhile((p!
=NULL)&&(j<pos)) {
47q=p;p=p—>next;
48ﻩﻩj++;
49}
50ﻩﻩif((!
p)||(j>pos))
51ﻩreturn 0
52q—>next =p->next;
53ﻩtemp=p—>element;
54ﻩif(tail==p)tail=q;
55ﻩﻩfree(p);
56return temp;
57}
58intlength()
59ﻩ{
60struct list*p;
61ﻩint cnt = 0;
62ﻩfor (p=head-〉next;p!
= NULL;p =p->next)
63ﻩﻩcnt++;
64ﻩﻩreturncnt;
65}
66ﻩint find(ELEMTYPEitem)
67{
68ﻩstructlist*p=head—〉next;
69ﻩwhile(p!
=NULL){
70ﻩﻩif(p->element==item)
71ﻩreturn1;
72ﻩﻩelse
73ﻩﻩp=p-〉next;
74ﻩﻩ}
75ﻩreturn0;
76}
77ﻩvoidprint()
78ﻩ{
79ﻩstructlist *p;
80printf(”\n");
81ﻩfor(p =head-〉next;p!
=NULL;p=p->next)
82ﻩprintf(”%d ",p—〉element);
83ﻩ}
84void main()
85{
86ﻩclrscr();
87init();
88ﻩappend(10);/*listis(10)*/
89ﻩappend(20);/*listis(10,20)*/
90append(30);/*listis (10,20,30) */
91ﻩﻩappend(40);/*listis (10,20,30,40)*/
92insert(3,35);ﻩ/*list is(10,20,30,35,40)*/
93ﻩprint();
94ﻩﻩprintf("\n%d\n",delete(4));/*list is(10,20,30,35)*/
95ﻩﻩprint();
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(第28行到第31行)返回1,否则返回0。
程序2_3.c
#include #include<stdio.h>
#define MAXSIZE100
typedefintELEMTYPE;
structstack{
ﻩELEMTYPElistarray[MAXSIZE];
ﻩinttop;
};
struct stacks;
voidinit()
{
s.top=0;
}
voidpush(ELEMTYPEitem)
{
assert(s。
top<MAXSIZE);
s.listarray[s。
top++] =item;
}
ELEMTYPEpop()
{
ﻩintisEmpty();
assert(!
isEmpty());
returns.listarray[—-s.top];
}
ELEMTYPE topValue()
{
ﻩintisEmpty();
assert(!
isEmpty());
return s.listarray[s。
top-1];
}
intisEmpty()
{
returns.top==0;
}
voidmain()
{
init();
push(10);/*sis(10) */
ﻩpush(20);/*sis (20,10)*/
printf("%d",topValue());/*returntopelement 20*/
printf("\n");
printf("%d",pop());ﻩ/*s is(10) */
}
程序2_4.c给出了链式栈表示和各种运算的算法。
其中top是指向链式栈第一个结点(栈顶)的指针。
进栈操作(第13行到第21行)首先申请一个新结点,并初始化该结点,然后修改新产生的结点的next域指向栈顶,并设置top指向新的链表结点。
第22行到第32行是出栈操作.变量temp用来存储栈顶结点的值,ltemp用于在删去栈顶结点时保持与栈的链接,它指向当前栈顶链接到的结点。
此时把原来的栈顶结点释放回内存,恢复top等于ltemp.也就是指向原来栈顶链接的结点,原来栈顶的值temp作为pop函数的返回值.
程序2_4.c
#includeh>
#include〈stdio.h>
ﻩ#include〈assert.h>
ﻩtypedef intELEMTYPE;
ﻩstructnode{
ﻩﻩELEMTYPEelem;
struct node*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()
ﻩ{
ﻩﻩintﻩisEmpty();
ﻩﻩELEMTYPE temp;
structnode*ltemp;
assert(!
isEmpty());
ﻩtemp=top—〉elem;
ﻩﻩltemp=top—〉next;
ﻩﻩfree(top);
ﻩﻩtop=ltemp;
ﻩreturntemp;
}
ELEMTYPEtopValue()
{
ﻩﻩintisEmpty();
assert(!
isEmpty());
ﻩreturntop—〉elem;
ﻩ}
intisEmpty()
{
ﻩreturntop==NULL;
}
voidmain()
{
init();
ﻩpush(10);/*s is(10) */
ﻩpush(20);/*s is (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#defineMAXSIZE100
typedefintELEMTYPE;
structqueue{
intfront;
ﻩint rear;
ﻩELEMTYPEelem[MAXSIZE];
};
struct queue q;
voidinit()
{
q.front =q.rear=0;
}
void enqueue(ELEMTYPEitem)
{
assert(((q.rear+1) %MAXSIZE) !
=q.front);
ﻩq.rear=(q。
rear+ 1) %MAXSIZE;/*incrementrear*/
q。
elem[q.rear]=item;
}
ELEMTYPEdequeue()/*dequeueelementfro front ofqueue*/
{
ﻩintisEmpty();
ﻩassert(!
isEmpty());ﻩ/* there mustbesomethingtodequeue */
ﻩq.front =(q。
front+1)%MAXSIZE;/*increment front*/
returnq.elem[q。
front];/*return value*/
ﻩ}
ELEMTYPEfirstValue()/*getvalue offront element*/
ﻩ{
ﻩintisEmpty();
assert(!
isEmpty());
ﻩreturnq.elem[(q.front+1)% MAXSIZE];
}
ﻩint isEmpty()ﻩ/*TRUE isqueueis empty*/
{
ﻩﻩreturn q.front ==q.rear;
}
ﻩvoid main()
ﻩ{
ﻩinit();
ﻩﻩenqueue(10);ﻩ/*qis(10)*/
ﻩenqueue(20);ﻩ/*qis(10,20)*/
ﻩﻩenqueue(30);/*qis (10,20,30)*/
ﻩprintf("%d\n”,firstValue());ﻩ/*willdisplay 10 */
ﻩﻩ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;
struct node{
ﻩELEMTYPEelem;
ﻩstruct node*next;
};
ﻩstructnode *front;
structnode*rear;
ﻩvoidinit()
ﻩ{
ﻩﻩrear=front=NULL;
}
ﻩvoid enqueue(ELEMTYPEitem)
ﻩ{
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=(structnode *)malloc(sizeof(structnode));
front—>elem=item;
ﻩfront-〉next =NULL;
ﻩ}
}
ELEMTYPEdequeue()
ﻩ{
ﻩﻩint isEmpty();
ELEMTYPEtemp =front->elem;
ﻩstruct node*ltemp=front;
ﻩassert(!
isEmpty());
ﻩfront=front—〉next;
ﻩﻩfree(ltemp);
ﻩif (front==NULL)rear=NULL;
ﻩreturntemp;
}
ELEMTYPEfirstValue()
ﻩ{
intisEmpty();
ﻩﻩassert(!
isEmpty());
returnfront->elem;
}
ﻩintisEmpty()
{
returnfront==NULL;
ﻩ}
void main()
{
ﻩﻩ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
1#defineMAXCOL100
2ﻩinta[][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},