1.1 线性表的顺序存储

1.1.0 绪论

预定义常量和类型

1 #define TRUE 1;
2 #define FALSE 0;
3 #define MAXSIZE 100;
4 #define OK 1;
5 #define ERROR 0;

1.1.1 顺序表

顺序存储是指在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素。采用顺序存储结构的线性表成为“顺序表”。

设第一个元素存放地址为LOC(a1)，每个元素占用的空间大小为d个字节，则元素ai的存放地址为：

LOC(ai)=LOC(a1)+d*(i-1)

只要确定了存储线性表的起始位置，线性表中任意元素都可随机存储，既线性表示一种可随机存储结构。

常用一维数组来描述顺序表的数据存储，表长可变，为了运算方便，用整型变量length记录当前线性表中元素的个数，线性顺序表的顺序存储结构可描述如下：

1 #include<stdio.h>
2 #define MAXSIZE<线性表可能达到的最大长度>
3 typedef int MlemType:
4 typedef struct{
5     ElemType elem[MAXSIZE];
6     int length;//线性表长度 
7 };

定义一个顺序表：

                                 SeqList *L;

顺序表的长度为 L->Length,数据元素是 L->elem[1] ~ L->elem[length]

 

1.1.2 顺序表的基本运算

顺序表的初始化既构造一个空表，将表长length设为0，表示表中没有数据。

1 //顺序表的初始化
2 void Init_SeqList(SeqList *L){
3     L->length=0;
4 } 

调用方法：

                               Init_SeqList(&L)

顺序表的插入操作如下：

• 将an ~ ai按从后向前的顺序向下移动，为新元素让出位置。
• x置入空出的第i个位置
• 修改表长

 1 //顺序表的插入
 2 int Insert_SeqList(SeqList *L,int i,ElemType x){
 3     int j;
 4     if(L->length==MAXSIZE-1){
 5         printf("表满");
 6         return OVERFLOW; 
 7     }
 8     if(i<i||L->Length<i){
 9         printf("位置满");
10         return ERROR; 
11     }
12     for(j=L->length;j>=i;j--)
13         L->elem[j+1] = L->elem[j];
14     L->elem[i] = x;
15     L->length++;
16     return TRUE;
17 } 

顺序表的删除

• 将a i+1 ~a n 依次向上移动
•  将length值减一

 1 //顺序表的删除 
 2 int Delete_SeqList(SeqList *L,int i,ElemType *e){
 3     int j;
 4     if(i<1||i>L->Length){
 5         printf("不存在第i个元素");
 6         return ERROR; 
 7     }
 8     *e = L->elem[i]; 
 9     for(j=i;j<=L->Length;j++)
10         L->elem[j] = L->elem[j+1];
11     L->length--;
12     return TRUE;
13 } 

顺序表中按值查找

1 //顺序表的按值查找 
2 int Location_SeqList(SeqList *L,ElemType x){
3     int i=1;
4     while(i<=L-Length&&L->elem[i]!=x){
5         i++;
6     }
7     if(i>L->length) return FALISE;
8     else return i;
9 } 

练习题

有两个顺序表A和B，其元素均按从小到大顺序排序，编写一个算法，将它们合并成一个顺序表，要求元素表C中的元素也按升序排序。

 1 //顺序表的按值查找 
 2 void merge(SeqList *A,SeqList *B,SeqList *C){
 3     int i=1,j=1,k=1;
 4     while(i<=A-Length&&j<B->Length){
 5         if(A->elem[i]<B->elem[j]){
 6             C->elem[k++] = A->elem[i++];
 7         }
 8         else C->elem[k++] = B->elem[j++];
 9     }
10     while(<=A->length){
11         C->elem[k++]=A->elem[i++];
12     }
13     while(j<=B->length){
14         C->elem[k++]=B->elem[j++];
15     }
16     C->length = A->length+B->length;
17 }