数据结构常用算法实现print.doc

《数据结构常用算法实现print.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、一个元素。第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行是

3、main函数的一个例子，说明了线性表的使用。57行调用clear函数将线性表清空，第58，59，60三行调用append函数追加三个元素，第62行在位置2插入一个元素15，第65行调用delete函数删除位置3的元素。第47行到53行的print函数是为了显示线性表中的数据而设置的。程序2_1.c1#defineMAXSIZE9992typedefintELEMTYPE;3structlist{4ELEMTYPElistarray[MAXSIZE];5intlength;6};7structlistl;8voidclear()9{10l.len

4、gth=0;11}12voidinsert(intpos,ELEMTYPEitem)13{14inti;15for(i=l.length;i>pos;i--)16l.listarray[i]=l.listarray[i-1];17l.listarray[pos]=item;18l.length++;19}20voidappend(ELEMTYPEitem)21{22l.listarray[l.length++]=item;24}25ELEMTYPEdelete(intpos)26{27inti;28ELEMTYPEtemp;29temp=l.l

5、istarray[pos];30for(i=pos;i

6、length;i++)51printf("%d",l.listarray[i]);52printf("");}54voidmain()55{clrscr();57clear();58append(10);/*Lis10*/59append(20);/*Lis(10,20)*/60append(30);/*Lis(10,20,30)*/61print();62insert(2,15);/*Lis(10,20,15,30)*/63print();64printf("%d",find(100));65printf("%d",delet

7、e(3));/*Lis(10,20,15)*/66print();}线性表的链式表示程序2_2.c提供了链式存储结构下线性表的实现。第3行到第8行包含了线性表中结点的说明，其中element表示数据域，存放该结点的数据信息，next为指针域，指明该结点的唯一后继结点在内存中的存放地址，或是在该结点序列中所在的物理位置。线性链表由head和tail表示。接下来从第9行到第76行线性表运算函数的定义。第9行到第14行初始化单链表。head指针与tail指针指向表头结点。在单链表的最后一个结点后插入一个结点只要将单链表尾指针tail指向新插入结点，新

8、插入结点成为最后一个结点即可。第15行到第20行函数append实现追加一个新结点到单链表的最后，新结点的元素值为item。malloc是C语言提供的