线性表

类型名称：线性表（list）

数据对象集：线性表是n（≥0)个元素构成的有序序列（a_1，a_2，...,a_n)

操作集：线性表 L €（属于） list，整数 i 表示位置，元素X € ElementType，

　　　　线性表基本操作主要有：

1、List MakeEmpty（）：初始化一个空线性表L；

2、ElementType FindKth（int K，List L）：根据位序K，返回相应元素；

3、int Find（ElementType X，List L）：在线性表L中查找X的第一次出现位置；

4、void Insert（ElementType X，int i，List L）：在位序 i 前面插入一个新元素X；

5、void Delete（int i，List L）：删除指定位序 i 的元素；

6、int Length（List L）：返回线性表L的长度n。

例：

 1 　typedef struct LNode *List;
 2 　　struct LNode{
 3 　　　　　　ElementType Data[MAXSIZE];
 4 　　　　　　int Last;
 5 　　};
 6 　　struct LNode L;
 7 　　List PtrL;
 8 　　
 9 
10 
11 //1.初始化（建立空的顺序表）
12 List MakeEmpty()
13 {
14     List PtrL;
15     PtrL = (List)malloc( sizeof(struct LNode));
16     PtrL->Last = -1;
17     return PtrL;
18 } 
19 
20 //2.查找
21 int Find(ElementType X, List PtrL)
22 {
23     int i=0;
24     while(i <= PtrL->Last && PtrL->Data[i]!=X)
25         i++;
26         if(i > PtrL->Last)  return -1; /*如果没找到，返回-1*/
27         else    return i;
28 }
29 
30 //3.插入(第i（1<=i && i<=n+1)个位置上插入一个值为X的新元素）
31 void Insert(ElementType X,int i,List PtrL)
32 {
33     int j;
34     if( PtrL->Last == MAXSIZE-1){   /*表空间已满，不能插入*/
35         printf(" 表满“ );
36         return ;
37     }
38     if(i<1 || i>Ptr->Last+2){
39         printf( " 位置不合法 " );
40         return ;
41     }
42     for(j=PtrL->Last;j>=i-1;j--)
43         PtrL->Data[j+1] = PtrL->Data[j];/*将a[i]~a[n]倒序向后移动*/
44     PtrL->Data[i-1] = X;                /*Last仍指向最后元素*/                /*新元素插入*/
45     PtrL->Last++;
46     return;
47 }
48 
49 
50 //4.删除（删除表的第i（1<=i && i<=n)个位置上的元素）
51 void Delete(int i,List PtrL)
52 {
53     int j;
54     if(i < 1 || i > PtrL->Last){    /*检查空表及删除位置的合法性*/
55         printf( "不存在第%d个元素",i);
56         return ;
57     }
58     for(j=i;j<=PtrL->Last;j++)
59         PtrL->Data[j-1] = PtrL->Data[j];    /*将a[i+1]~a[n]顺序向前移动*/
60     PtrL->Last--;                           /*Last仍指向最后元素*/
61     return ;
62 }
63 
64 
65