线性表(一)--顺序存储 (C语言实现)

线性结构是最简单、最直接的数据关系,数据元素之间一一对应。

抽象数据类型定义:
即包含(1) 数据元素(ADT)(2)结构关系 (3)基本操作

基本操作包含:1、InitList(初始化) 2、DestroyList(销毁)3、ClearList(置空)4、EmptyList(判空)5、ListLength(求长度)6、Localte(查找)7、GetDate(存取)8、InList(插入)9、DelList(删除)

抽象数据类型一经定义可多次使用

了解了线性表的基本信息,我们就从顺序存储类型开始。

顺序存储结构的定义:用一组地址连续的存储单元依此存储线性表中的各个元素逻辑上相邻的数据元素在物理上也相邻。

假设线性表中有n个元素,每个元素占k个单元格。那么第一个元素的地址为loc(a1)称为基地址,则第i个元素的地址loc(ai):loc(ai)=loc(a1)+(i-1)×k

顺序存储结构的C语言描述(使用结构体):

typedef struct
{
ElemType elem[maxsize];
int last;
}SeqList;

那么接下来我们来看看顺序存储结构的基本运算。

1、查找运算 2、插入运算 3、删除运算 4、顺序表合并运算。

首先是查找运算,查找运算有两种,一种是按序号查找,另一种是按内容查找。按序号查找非常简单,只需要对数组进行操作即可。我们重点来看按内容查找。

int  Locate(SeqList L,ElemType e) 
 {
 i=0;i 为扫描计数器,初值为 0,即从第一个元素开始比较
 while ((i<=L.last)&&(L.elem[i]!=e))顺序扫描表,直到找到值为key的元素
 i++;或扫描到表尾而没找到
 if (i<=L.last)
return(i+1);若找到值为e的元素,则返回其序号
 else
return(-1);若没找到,则返回空序号
}算法的时间复杂度为 O(n)。

然后是插入算法,因为插入算法需要将插入位置之后的元素移动,因而显得比查找难一些。下面列出代码:

#define OK   1
#define ERROR  0
int  InsList(SeqList *L,int i,ElemType e)
//在顺序表 L 中第 i 个数据元素之前插入一个元素 e。 插入前表长 n=L->last+1,i 的合法取值范围是 1≤i≤L->last+2 
{  
 int k; 
 if((i<1) || (i>L->last+2)) /首先判断插入位置是否合法/ 
 {
 printf(“插入位置 i 值不合法”); 
 return(ERROR); 
 } 
 if(L->last>= MAXSIZE-1) 
 {
printf(“表已满无法插入”); 
return(ERROR); 
 } 
 for(k=L->last;k>=i-1;k--)   /为插入元素而移动位置/ 
 L->elem[k+1]=L->elem[k]; 
 L->elem[i-1]=e;   /*在 C 语言数组中,第 i 个元素的下标为 i-1*/ 
 L->last++; 
 return(OK); 
} 

完成了插入运算之后,删除运算也就明白了

int  DelList(SeqList *L,int i,ElemType *e) 
/*在顺序表 L 中删除第 i 个数据元素,并用指针参数 e 返回其值。i 的合法取值为 1≤i≤L.last+1 */ 
{  
 int k; 
 if((i<1)||(i>L->last+1))
 {  
 printf(“删除位置不合法!”); 
 return(ERROR); 
 } 
*e= L->elem[i-1];  /* 将删除的元素存放到 e 所指向的变量中*/ 
for(k=i;i<=L->last;k++) 
 L->elem[k-1]= L->elem[k];  /*将后面的元素依次前移*/ 
 L->last--; 
 return(OK); 
} 

有了插入删除的基础,我们就可以实现两个表的合并操作了

void merge(SeqList *LA,  SeqList *LB,  SeqList *LC) 
{ 
   int i,j,k,l;
   i=0;j=0;k=0;
   while(i<=LA->last&&j<=LB->last) 
   if(LA->elem[i]<=LB->elem[j]) 
   {
  LC->elem[k]= LA->elem[i];
  i++;k++; 
   }
   else{ 
   LC->elem[k]=LB->elem[j]; 
   j++;k++; 
   } 
   while(i<=LA->last) /*当表 LA 有剩余元素时,则将表 LA 余下的元素赋给表 LC*/
   {
  LC->elem[k]= LA->elem[i];
  i++;k++;
   }
   while(j<=LB->last)  /*当表 LB 有剩余元素时,则将表 LB 余下的元素赋给表 LC*/
   {
  LC->elem[k]= LB->elem[j]; 
  j++;k++;
   }
   LC->last=LA->last+LB->last+1;
} 

学习完了顺序结构之后,我们来看看顺序结构的优缺点。
线性表顺序表示的优点是:
(1)无需为表示结点间的逻辑关系而增加额外的存储空间。
(2)可方便的随机存取表中的任一元素。
缺点:
(1) 插入或删除运算需要移动大量的结点,效率低下。
(2)由于顺序表存储分配静态分配。当表长变化较大难以确定合适的存储规模。

纯手打。。。累死我了。。。。慢慢来,还早着呢。

0%