线性表是从数据元素的逻辑结构上定义的.
这种数据元素的逻辑结构的特征如下:
1.除开第一个和最后一个元素之外.所有元素都有一个前驱元素和后继元素.
2.第一个元素无前驱元素,但有后继元素.
3.最后一个元素有前驱元素,单无后继元素.
可以抽象为如下表述:
然而同一种逻辑结构在内存中却可以有两种存储方式:1.在内存中连续存储的线性表-----顺序表(如数组)
2.在内存中离散存储的线性表-----链表(如单链表,双链表)
对于顺序表有多重操作:初始化,赋值,插入新值,删除值等
下面的用C代码实现顺序表及其一些常用的操作：
1 #include<stdio.h> 2 3 #define ERROR 0 4 5 #define InitSize 20 //顺序表的初始大小 6 7 typedef int ElemType; 8 9 typedef struct{ 10ElemType data[InitSize]; 11int length; 12 }sqlist; 13 14 //顺序表初始化 15 void InitList(sqlist *L) 16 { 17L->length=0; 18return ; 19 } 20 21 //获取顺序表的长度 22 int GetLength(sqlist *L) 23 { 24return L->length; 25 } 26 27 //顺序表赋值 28 void GiveValue(sqlist *L) 29 { 30int value; 31int i=0; 32while(value!=0) 33{ 34 printf("Please input %d valueL-------(exit until value equal 0)\n",i+1); 35 scanf("%d",&value); 36 if(value!=0) 37 { 38 L->data[i++]=value; 39 L->length++; 40 } 41} 42 } 43 44 45 46 //获取顺序表某个位置的值 47 ElemType GetValue(sqlist *L,int i) 48 { 49ElemType e; 50if(i>L->length||i<1) 51 return ERROR; 52 53int k=0; 54for(k=0;k<L->length;k++) 55{ 56 if(k==i-1) 57 e=L->data[k]; 58} 59return e; 60 } 61 62 //获取顺序表某个值的位置 63 int GetPos(sqlist *L,ElemType value) 64 { 65int pos; 66int judeflag=1; 67int i; 68for(i=0;i<L->length;i++) 69{ 70 if(L->data[i]==value) 71 { 72 pos=i+1; 73 break; 74 } 75 judeflag++; 76} 77 78if(judeflag>=L->length) 79 return ERROR; 80 81return pos; 82 } 83 84 //在顺序表指定位置插入新的值 85 void InsertValue(sqlist *L,int pos,ElemType value) 86 { 87if(pos<1||pos>L->length) 88 return ERROR; 89 90int i; 91for(i=L->length-1;i>pos-2;i--) 92{ 93 L->data[i+1]=L->data[i]; 94} 95 96L->data[pos]=value; 97L->length++; 98 } 99 100 //在顺序表中指定位置删除值101 void DeleteValue(sqlist *L,int pos)102 {103if(pos<1||pos>L->length)104 return ERROR;105 106int i;107for(i=pos;i<L->length;i++)108{109 L->data[i-1]=L->data[i];110}111 112L->length--;113 }114 115 //显示顺序表116 void ShowList(sqlist *L)117 {118int i;119printf("The List show below:\n");120for(i=0;i<L->length;i++)121{122 printf("%d ",L->data[i]);123}124 }125 126 127 //主函数128 int main()129 {130sqlist L;131InitList(&L);//初始化顺序表132GiveValue(&L);//顺序表赋值133ShowList(&L);//显示线性表134 135printf("\n\n\n\n");136int flag;137printf("******************************************************\n");138printf("*************choose the operation of List*************\n");139printf("*****************1-指定位置插入值*********************\n");140printf("*****************2-指定位置删除值*********************\n");141printf("*****************3-获取顺序表某个值得位置*************\n");142printf("*****************4-获取顺序表某个位置上的值*********\n");143printf("*****************5-获取顺序表长度*********************\n");144printf("*****************0-退出*******************************\n");145printf("******************************************************\n");146printf("\n\n\n");147 148printf("Input the value Flag:\n");149scanf("%d",&flag);150 151printf("flag=%d\n",flag);152 153int pos,value,len;154switch(flag){155case 1:156 {157 printf("Please input the value and position:\n");158 scanf("%d %d",&value,&pos);159 printf("Insert value=%d in pos=%d\n",value,pos+1);160 InsertValue(&L,pos,value);161 ShowList(&L);162 break;163 }164case 2:165 {166 printf("Please input the position:\n");167 scanf("%d",&pos);168 printf("Delete value in pos=%d\n",pos);169 DeleteValue(&L,pos);170 ShowList(&L);171 break;172 }173case 3:174 {175 printf("Please input the value:\n");176 scanf("%d",&value);177 pos=GetPos(&L,value);178 printf("Get value=%d's position is %d\n",value,pos);179 ShowList(&L);180 break;181 }182case 4:183 {184 printf("Please input the position:\n");185 scanf("%d",&pos);186 value=GetValue(&L,pos);187 printf("Get value=%d from pos=%d\n",value,pos);188 ShowList(&L);189 break;190 }191case 5:192 {193 len=GetLength(&L);194 printf("the length of List is %d\n",len);195 ShowList(&L);196 break;197 }198case 0:199 printf("you choose to exit\nGoodbye!\n");200}201 202return 0;203 }
结果图:
