线性表：
（1） 存在惟一的一个被称做“第一个”的数据元素；
（2）存在惟一的一个被称做“最后一个”的数据元素；
（3）除第一个之外，集合中每个数据元素均只有一个前驱；
（4）除最后一个之外，集合中每个数据元素均只有一个后继。
2.1 线性表的类型定义
线性表是最常用也是最简单的一种数据结构。
线性表的操作
1) INITIATE(L)——初始化操作
2)LENGTH(l)——求长度函数
3)GET(L,i)———取元素函数
4)PRIOR（L，elm）——求前驱函数
5)NEXT(L,elm)——求后继函数
6)LOCATE(L,x) ——定位函数
7)INSERTE(L,i,b)——前插操作
8)DELETE（L,i）——删除操作
9)EMPTY(L)——判空表函数
10)CLEAR(L)——表置空操作
1 #include2 #include 3 #define MaxSize 50 4 typedef char ElemType; 5 typedef struct { 6 ElemType data[MaxSize]; 7 int length; 8 }SqList; 9 10 void InitList(SqList* &L) 11 { 12 L = (SqList *)malloc(sizeof(SqList)); 13 L->length=0; 14 } 15 16 void DestroyList(SqList *L) 17 { 18 free(L); 19 } 20 21 int ListEmpty(SqList *L) 22 { 23 return(L->length==0); 24 } 25 26 int ListLength(SqList *L) 27 { 28 return (L->length); 29 } 30 31 void DispList(SqList *L) 32 { 33 int i; 34 if (ListEmpty(L)) 35 { 36 return; 37 } 38 for (i=0;i length;i++) 39 { 40 printf("%c",L->data[i]); 41 42 } 43 printf("\n"); 44 } 45 46 int GetElem(SqList *L,int i,ElemType &e) 47 { 48 if(i<1 || i>L->length) 49 { 50 return 0; 51 } 52 e=L->data[i-1]; 53 return 1; 54 } 55 56 int LocateElem(SqList *L,ElemType e) 57 { 58 int i=0; 59 while(i length && L->data[i]!=e) 60 { 61 i++; 62 } 63 if (i>=L->length) 64 { 65 return 0; 66 } 67 else 68 return i+1; 69 } 70 71 int ListInsert(SqList * &L,int i,ElemType e) 72 { 73 int j; 74 if (i<1 || i>L->length+1) 75 { 76 return 0; 77 } 78 i--; 79 for (j=L->length;j>i;j--) 80 { 81 L->data[j]=L->data[j-1]; 82 } 83 L->data[i]=e; 84 L->length++; 85 return 1; 86 } 87 88 int ListDelete(SqList* &L,int i,ElemType &e) 89 { 90 int j; 91 if (i<1 || i>L->length) 92 { 93 return 0; 94 } 95 i--; 96 e=L->data[i]; 97 for (j=i;j length-1;j++) 98 { 99 L->data[j]=L->data[j+1];100 }101 L->length--;102 return 1;103 }
1 #include2 #include 3 4 #define MaxSize 50 5 typedef char ElemType; 6 typedef struct 7 { 8 ElemType data[MaxSize]; 9 int length;10 }SqList;11 12 extern void InitList(SqList* &L);13 extern void DestroyList(SqList *L);14 extern int ListEmpty(SqList *L);15 extern int ListLength(SqList *L);16 extern void DispList(SqList* L);17 extern int GetElem(SqList *L,int i,ElemType &e);18 extern int LocateElem(SqList *L,ElemType e);19 extern int ListInsert(SqList* &L,int i,ElemType e);20 extern int ListDelete(SqList *&L,int i,ElemType &e);21 22 void main()23 {24 SqList *L;25 ElemType e;26 printf("(1)初始化顺序表\n");27 InitList(L);28 printf("(2)依次采用尾插法插入a,b,c,d,e元素\n");29 ListInsert(L,1,'a');30 ListInsert(L,2,'b');31 ListInsert(L,3,'c');32 ListInsert(L,4,'d');33 ListInsert(L,5,'e');34 printf("(3)输出顺序表L:");35 DispList(L);36 37 printf("(4)顺序表长度 = %d\n",ListLength(L));38 39 printf("(5)顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));40 41 GetElem(L,3,e);42 printf("(6)顺序表L的第3个元素 =%c\n",e);43 44 printf("(7)元素a的位置=%d\n",LocateElem(L,'a'));45 46 printf("(8)在第4个元素位置上插入f元素\n");47 ListInsert(L,4,'f');48 49 printf("(9)输出顺序表L:");50 DispList(L);51 printf("(10)删除L的第3个元素\n");52 ListDelete(L,3,e);53 printf("(11)输出顺序表L:");54 DispList(L);55 printf("(12)释放顺序表L\n");56 DestroyList(L);57 }
1 void ListUnion(SqList *&La,SqList* Lb) 2 { 3 int La_len=ListLength(La); 4 int Lb_len=ListLength(Lb); 5 for (int i=1;i<=Lb_len;i++) 6 { 7 ElemType e; 8 GetElem(Lb,i,e); 9 10 int k=LocateElem(La,e);11 12 if (k==0)//不存在13 {14 ListInsert(La,La_len+1,e);15 }16 }17 } 1 #include2 #include 3 4 #define MaxSize 50 5 typedef char ElemType; 6 typedef struct 7 { 8 ElemType data[MaxSize]; 9 int length;10 }SqList;11 12 extern void InitList(SqList* &L);13 extern void DestroyList(SqList *L);14 extern int ListEmpty(SqList *L);15 extern int ListLength(SqList *L);16 extern void DispList(SqList* L);17 extern int GetElem(SqList *L,int i,ElemType &e);18 extern int LocateElem(SqList *L,ElemType e);19 extern int ListInsert(SqList* &L,int i,ElemType e);20 extern int ListDelete(SqList *&L,int i,ElemType &e);21 extern void ListUnion(SqList *&La,SqList* Lb);22 23 int main()24 {25 SqList *Linear_list_A,*Linear_list_B;26 //Initialize Linear list27 InitList(Linear_list_A);28 InitList(Linear_list_B);29 30 ListInsert(Linear_list_A,1,'a');31 ListInsert(Linear_list_A,2,'b');32 ListInsert(Linear_list_A,3,'c');33 ListInsert(Linear_list_A,4,'d');34 ListInsert(Linear_list_A,5,'e');35 36 ListInsert(Linear_list_B,1,'x');37 ListInsert(Linear_list_B,2,'y');38 ListInsert(Linear_list_B,3,'z');39 DispList(Linear_list_A);40 DispList(Linear_list_B);41 42 ListUnion(Linear_list_A,Linear_list_B);43 44 DispList(Linear_list_A);45 46 return 0;47 48 }
1 void MergeList(SqList *La,SqList *Lb,SqList *&Lc) 2 { 3 int La_len=ListLength(La); 4 int Lb_len=ListLength(Lb); 5 6 InitList(Lc); 7 8 int i=1,j=1,k=0; 9 ElemType e,f;10 11 while(i<=La_len && j<=Lb_len)12 {13 if (!ListEmpty(La) && !ListEmpty(Lb))14 {15 16 GetElem(La,i,e);17 GetElem(Lb,j,f);18 if (e<=f)19 {20 ListInsert(Lc,k+1,e);21 k++;22 i++;23 }24 else25 {26 ListInsert(Lc,k+1,f);27 k++;28 j++;29 }30 }31 32 }33 while(i<=La_len)34 {35 GetElem(La,i,e);36 ListInsert(Lc,k+1,e);37 k++;38 i++;39 }40 while(j<=Lb_len)41 {42 GetElem(Lb,j,f);43 ListInsert(Lc,k+1,f);44 k++;45 j++;46 }47 } 1 #include2 #include 3 4 #define MaxSize 50 5 typedef char ElemType; 6 typedef struct 7 { 8 ElemType data[MaxSize]; 9 int length;10 }SqList;11 12 extern void InitList(SqList* &L);13 extern void DestroyList(SqList *L);14 extern int ListEmpty(SqList *L);15 extern int ListLength(SqList *L);16 extern void DispList(SqList* L);17 extern int GetElem(SqList *L,int i,ElemType &e);18 extern int LocateElem(SqList *L,ElemType e);19 extern int ListInsert(SqList* &L,int i,ElemType e);20 extern int ListDelete(SqList *&L,int i,ElemType &e);21 extern void ListUnion(SqList *&La,SqList* Lb);22 extern void MergeList(SqList *La,SqList *Lb,SqList *&Lc);23 24 int main()25 {26 SqList *Linear_list_A,*Linear_list_B,*Linear_list_C;27 //Initialize Linear list28 InitList(Linear_list_A);29 InitList(Linear_list_B);30 31 ListInsert(Linear_list_A,1,'a');32 ListInsert(Linear_list_A,2,'b');33 ListInsert(Linear_list_A,3,'c');34 ListInsert(Linear_list_A,4,'d');35 ListInsert(Linear_list_A,5,'e');36 37 ListInsert(Linear_list_B,1,'a');38 ListInsert(Linear_list_B,2,'y');39 ListInsert(Linear_list_B,3,'z');40 DispList(Linear_list_A);41 DispList(Linear_list_B);42 43 //ListUnion(Linear_list_A,Linear_list_B);44 MergeList(Linear_list_A,Linear_list_B,Linear_list_C);45 46 DispList(Linear_list_C);47 48 return 0;49 50 }