数组模拟链表.docVIP

数组模拟链表首先，什么是数组模拟链表.摘自维基百科(/wiki/%E9%93%BE%E8%A1%A8):一个链表或者多个链表使用独立的存储空间，一般用数组或者类似结构实现，优点是可以自动获得一个附加数据：唯一的编号，并且方便调试；缺点是不能动态的分配内存。当然，另外的在上面加一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法有时候被叫做数组模拟链表，但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种下标索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的（但是可以说成是用数组实现的链表）。 用图形象的说明一下：见图 开始指向arr[0],输出arr[0].data.又因arr[0].num为1，则指向arr[1],输出arr[1].data……这样输出arr[8].data之后则指向arr[9],而arr[9].data为先前指定的结束值0，则输出结束。链表好处在于不用事先指定数据量。虽然数组不行，但要指定的长度也只是初始长度，可以轻松向其中插入数据。我在以下c程序里，数组最后多设定一个空闲的元素，纯属偷懒，也可以新建立一个结构数据。 下面用实际程序说明一下，以下程序均原创，TURBO C 2.0上通过： （一）/*简单的程序，利用数组模拟链表输出a-h*/#includestdio.hvoid main(){struct{int data;int num;}arr[10]={{a,1},{b,2},{c,3},{d,4},{e,5},{f,6},{g,7},{h,8},{0,0},{0,0}};int pos; pos=0;while(arr[pos].data!=0){printf(%c,,arr[pos].data);pos=arr[pos].num;}printf(\n);} 输出：a,b,c,d,e,f,g,h, （二）/*在上面程序基础上改进，现要在编号为K,K+1的两个结构体数据之间插入数据x，x存在空闲的arr[9]里，K=3时即在de之间插入x*/ #includestdio.h#define K 3 void main(){struct{int data;int num;}arr[10]={{a,1},{b,2},{c,3},{d,4},{e,5},{f,6},{g,7},{h,8},{0,0},{0,0}};int pos=0; arr[K].num=9;arr[9].data=x;arr[9].num=(K+1); while(arr[pos].data!=0){printf(%c,,arr[pos].data);pos=arr[pos].num;}printf(\n);} 输出:a,b,c,d,x,e,f,g,h, （三）/*有26个人组成一个环，1，2，3循环报数，数到3的出列arr[0]到arr[25]是26个人，arr[26]是空数据，arr[27]是要插入的人这次先不插入人*/ #includestdio.h#define STEP 3 void main(){/*定义*/struct{int data;int num;}arr[28];int i;int pos;int count; /*赋值*/for(i=0;i=25;i++){arr[i].data=97+i;arr[i].num=i+1;}arr[26].data=0; /*输出每个人*/pos=0;while(arr[pos].data!=0){printf(%c,,arr[pos].data);pos=arr[pos].num;}printf(\n); /*输出报到STEP的人*/pos=0;count=0;while(arr[pos].data!=0){count++;if(count==STEP)?? {printf(%c,,arr[pos].data);?? count=0;?? } pos=arr[pos].num;}printf(\n);} 输出：a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,c,f,i,l,o,r,u,x, （四）/*有26个人组成一个环，1，2，3循环报数，数到3的出列arr[0]到arr[25]是26个人，arr[26]是空数据，arr[27]是插入的人这次向数组编号K和K+1两人之间插入名为A的人数组模拟链表就是方便插入新人*/ #includestdio.h#define STEP 3#define K 10 void m