作者在 2008-10-11 20:54:17 发布以下内容
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素.
线性表的顺序存储结构是一种随机存取的存储结构。
1.线性表的顺序存储结构
（1）//- - - - - -线性表的动态分配顺序存储结构- - - - -
typedef struct
typedef struct
{elemtype *elem; //存储空间的基地址
int length; //线性表的当前长度
int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
}Sqlist; //Sqlist指结构体的类型
（2）//- - - - - -线性表的静态分配顺序存储结构- - - - -
typedef struct
{elemtype elem[max];
int length;
}sqlist; //Sqlist指结构体的类型
2.线性表的实现（建立、插入、删除）
//- - - - -静态- - - - -
(1)在第i个元素前插入元素e
Insertlist（Sqlist &L int i,elemtype e）
{int j;
if(i<1||i>L.length+1) printf("ERROR"); // 位置不正确，出错
else{for(j=L.length-1;j>i;j--)
elem[j+1]=elem[j]; // 把第i个元素及后续元素向后移一位
l.elem[i-1]=e; // 在第i个元素加入e
L.length++;} //线性表长度加1
return L;
}
(2)删除第i个元素
delete(Sqlist &L,int i,elemtype &e)
{int j;
if(j<1||j>L.length)return ERROR;
else{for(j=i;j<L.length;j++) // 把第i+1个元素及后续元素向前移一位
L.elem[j-1]=L.elem[j];
L.length--;} //线性表长度减1
return L;
}
//- - - - -动态- - - - -
（1）建立空线性表
Initlist(Sqlist L)
{L.elem=(elemtype*)malloc(LIST_INIT_SIZE*sizeof(elemtype));//把分配的空间给基地址
if(！L.elem)exit(overflow); // 存储分配失败
L.length=0; // 空表长度为0
listsize=LIST_INIT_SIZE; // 初始存储容量
}
(2)在第i个元素前插入元素e
Insertlist（Sqlist &L int i,elemtype e）
{
if(i<1||i>L.length+1) printf("ERROR"); // 位置不正确，出错
q=&(L.elem[i-1]); //插入的位置
else{for(p=&(L.elem[L.length-1]);p>q;p--)
*(p+1)=*p; // 把插入位置的元素及后续元素向后移一位
*q=e; // 在第i个元素加入e
L.length++;} //线性表长度加1
return L;
}
(3)删除第i个元素
delete(Sqlist &L,int i,elemtype &e)
{
if(j<1||j>L.length)return ERROR;
p=&L.length[i-1];
e=*p; // 被删除元素的值赋给e
q=L.elem+L.length; //表尾元素的位置
else{for(++p;q<p;p++)
*(p-1)=*p; // 把删除位置的元素及后续元素向前移一位
L.length--;} //线性表长度减1
return L;
}
3.顺序表的合并
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
// 已知顺序线性表La和Lb的元素按值非递减排列
// 归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
pa=La.elem; pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem) exit(OVERFLOW); //存储分配失败
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last && pb<=pb_last){ //归并
if(*pa<=*pb) *pc++=*pa++;
else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++; // 插入La的剩余元素
while(pb<=pb_last) *pc++=*pb++; // 插入Lb的剩余元素
} // MergeList_Sq
// 已知顺序线性表La和Lb的元素按值非递减排列
// 归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
pa=La.elem; pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem) exit(OVERFLOW); //存储分配失败
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last && pb<=pb_last){ //归并
if(*pa<=*pb) *pc++=*pa++;
else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++; // 插入La的剩余元素
while(pb<=pb_last) *pc++=*pb++; // 插入Lb的剩余元素
} // MergeList_Sq