线性表是从数据元素的逻辑结构上定义的.
这种数据元素的逻辑结构的特征如下:
1.除开第一个和最后一个元素之外.所有元素都有一个前驱元素和后继元素.
2.第一个元素无前驱元素,但有后继元素.
3.最后一个元素有前驱元素,单无后继元素.
可以抽象为如下表述:
元素1 | 元素2 | 元素3 | 元素4 | 元素5 | 元素6 |
然而同一种逻辑结构在内存中却可以有两种存储方式:1.在内存中连续存储的线性表-----顺序表(如数组)
2.在内存中离散存储的线性表-----链表(如单链表,双链表)
对于顺序表有多重操作:初始化,赋值,插入新值,删除值等
下面的用C代码实现顺序表及其一些常用的操作:
#include<stdio.h> #define ERROR 0 #define InitSize 20 //顺序表的初始大小 typedef int ElemType; typedef struct{ ElemType data[InitSize]; int length; }sqlist; //顺序表初始化 void InitList(sqlist *L) { L->length=0; return ; } //获取顺序表的长度 int GetLength(sqlist *L) { return L->length; } //顺序表赋值 void GiveValue(sqlist *L) { int value; int i=0; while(value!=0) { printf("Please input %d valueL-------(exit until value equal 0)\n",i+1); scanf("%d",&value); if(value!=0) { L->data[i++]=value; L->length++; } } } //获取顺序表某个位置的值 ElemType GetValue(sqlist *L,int i) { ElemType e; if(i>L->length||i<1) return ERROR; int k=0; for(k=0;k<L->length;k++) { if(k==i-1) e=L->data[k]; } return e; } //获取顺序表某个值的位置 int GetPos(sqlist *L,ElemType value) { int pos; int judeflag=1; int i; for(i=0;i<L->length;i++) { if(L->data[i]==value) { pos=i+1; break; } judeflag++; } if(judeflag>=L->length) return ERROR; return pos; } //在顺序表指定位置插入新的值 void InsertValue(sqlist *L,int pos,ElemType value) { if(pos<1||pos>L->length) return ERROR; int i; for(i=L->length-1;i>pos-2;i--) { L->data[i+1]=L->data[i]; } L->data[pos]=value; L->length++; } //在顺序表中指定位置删除值 void DeleteValue(sqlist *L,int pos) { if(pos<1||pos>L->length) return ERROR; int i; for(i=pos;i<L->length;i++) { L->data[i-1]=L->data[i]; } L->length--; } //显示顺序表 void ShowList(sqlist *L) { int i; printf("The List show below:\n"); for(i=0;i<L->length;i++) { printf("%d ",L->data[i]); } } //主函数 int main() { sqlist L; InitList(&L);//初始化顺序表 GiveValue(&L);//顺序表赋值 ShowList(&L);//显示线性表 printf("\n\n\n\n"); int flag; printf("******************************************************\n"); printf("*************choose the operation of List*************\n"); printf("*****************1-指定位置插入值*********************\n"); printf("*****************2-指定位置删除值*********************\n"); printf("*****************3-获取顺序表某个值得位置*************\n"); printf("*****************4-获取顺序表某个位置上的值*********\n"); printf("*****************5-获取顺序表长度*********************\n"); printf("*****************0-退出*******************************\n"); printf("******************************************************\n"); printf("\n\n\n"); printf("Input the value Flag:\n"); scanf("%d",&flag); printf("flag=%d\n",flag); int pos,value,len; switch(flag){ case 1: { printf("Please input the value and position:\n"); scanf("%d %d",&value,&pos); printf("Insert value=%d in pos=%d\n",value,pos+1); InsertValue(&L,pos,value); ShowList(&L); break; } case 2: { printf("Please input the position:\n"); scanf("%d",&pos); printf("Delete value in pos=%d\n",pos); DeleteValue(&L,pos); ShowList(&L); break; } case 3: { printf("Please input the value:\n"); scanf("%d",&value); pos=GetPos(&L,value); printf("Get value=%d's position is %d\n",value,pos); ShowList(&L); break; } case 4: { printf("Please input the position:\n"); scanf("%d",&pos); value=GetValue(&L,pos); printf("Get value=%d from pos=%d\n",value,pos); ShowList(&L); break; } case 5: { len=GetLength(&L); printf("the length of List is %d\n",len); ShowList(&L); break; } case 0: printf("you choose to exit\nGoodbye!\n"); } return 0; }
结果图:
转载请注明作者:小刘