数据结构之:线性表的顺序表示和实现

一、线性表的顺序表示

用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。

2000:0001

2000:0003

2000:0005

2000:0007

2000:0009

2000:0011

2000:0013

2000:0015

2000:0017

...

2000:1001

2000:1003

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1
0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1
0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1
0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	0
0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1
0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1

a[9]

1

2

3

4

5

6

7

8

9

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：

LOC(ai+1)=LOC(ai)+l

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

式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。

线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。

称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。

二、顺序存储结构的线性表类C语言表示：

线性表的动态分配顺序存储结构
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct{

ElemType *elem; //存储空间基址

int length; //当前长度

int listsize; //当前分配的存储容量以一数据元素存储长度为单位

}SqList;
 

三、顺序存储结构的线性表操作及C语言实现：

顺序表的插入与删除操作：

序号	数据元素		序号	数据元素		序号	数据元素		序号	数据元素
1 2 3 4 5 6 7 8 9	12 13 21 24 28 30 42 77	<-25	1 2 3 4 5 6 7 8 9	12 13 21 24 25 28 30 42 77		1 2 3 4 5 6 7 8 9	12 13 21 24 28 30 42 77	->24	1 2 3 4 5 6 7 8 9	12 13 21 28 30 42 77
插入前n=8;插入后n=9;						删除前n=8;删除后n=7;

顺序表的插入算法
status ListInsert(List *L,int i,ElemType e) {

struct STU *p,*q;

if (i<1||i>L->length+1) return ERROR;

q=&(L->elem[i-1]);

for(p=&L->elem[L->length-1];p>=q;--p)

*(p+1)=*p;

*q=e;

++L->length;

return OK;

}/*ListInsert Before i */
 
顺序表的合并算法
void MergeList(List *La,List *Lb,List *Lc) {

ElemType *pa,*pb,*pc,*pa_last,*pb_last;

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(Less_EqualList(pa,pb)) *pc++=*pa++;

else *pc++=*pb++;

}

while(pa<=pa_last) *pc++=*pa++;

while(pb<=pb_last) *pc++=*pb++;

}
 
顺序表的查找算法
int LocateElem(List *La,ElemType e,int type) {

int i;

switch (type) {

case EQUAL:

for(i=0;i

if(EqualList(&La->elem[i],&e))

return 1;

break;

default:

break;

}

return 0;

}
 
顺序表的联合算法
void UnionList(List *La, List *Lb) {

int La_len,Lb_len; int i; ElemType e;

La_len=ListLength(La); Lb_len=ListLength(Lb);

for(i=0;i

GetElem(*Lb,i,&e);

if(!LocateElem(La,e,EQUAL))

ListInsert(La,++La_len,e);

}

}
 
三、C语言源程序范例

#include
#include
#include

#define ERROR 0
#define OK 1
#define EQUAL 1
#define OVERFLOW -1
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

struct STU{
 char name[20];
 char stuno[10];
 int age;
 int score;
}stu[50];
typedef struct STU ElemType;

struct LIST
{
 ElemType *elem;
 int length;
 int listsize;
};

typedef struct LIST List;

int init(List *L)
{
 L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
 if(!L->elem) exit(OVERFLOW);
 L->length=0;
 L->listsize=LIST_INIT_SIZE;
 return OK;
}/*init */

int ListLength(List *L)
{
 return L->length;
}

void GetElem(List L,int i,ElemType *e)
{
 *e=L.elem[i];
}

int EqualList(ElemType *e1,ElemType *e2)
{
 if (strcmp(e1->name,e2->name)==0)
  return 1;
 else
  return 0;
}

int Less_EqualList(ElemType *e1,ElemType *e2)
{
 if (strcmp(e1->name,e2->name)<=0)
  return 1;
 else
  return 0;
}

/* 顺序表的查找算法 */
int LocateElem(List *La,ElemType e,int type)
{
 int i;
 switch (type)
    {
 case EQUAL:
  for(i=0;ilength;i++)
   if(EqualList(&La->elem[i],&e))
    return 1;
   break;
 default:
  break;
    }
 return 0;
}

/* 顺序表的合并算法 */
void MergeList(List *La,List *Lb,List *Lc)
{
 ElemType *pa,*pb,*pc,*pa_last,*pb_last;
 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(Less_EqualList(pa,pb))   *pc++=*pa++;
  else *pc++=*pb++;
    }
 while(pa<=pa_last) *pc++=*pa++;
 while(pb<=pb_last) *pc++=*pb++;
}

/* 顺序表的联合算法 */
void UnionList(List *La, List *Lb)
{
 int La_len,Lb_len;
 int i;
 ElemType e;
 
 La_len=ListLength(La);  Lb_len=ListLength(Lb);
 for(i=0;i    {
  GetElem(*Lb,i,&e);
  if(!LocateElem(La,e,EQUAL))
   ListInsert(La,++La_len,e);
    }
 
}

int printlist(List L)
{
 int i;
 printf("name       stuno        age     score\n");
 for(i=0;i  printf("%-10s %s\t%d\t%d\n",  L.elem[i].name,  L.elem[i].stuno,
  L.elem[i].age,  L.elem[i].score);
 printf("\n");
}

/* 顺序表的插入算法 */
int ListInsert(List *L,int i,struct STU e)
{
 struct STU *p,*q;
 if (i<1||i>L->length+1) return ERROR;
 q=&(L->elem[i-1]);
 for(p=&L->elem[L->length-1];p>=q;--p)
  *(p+1)=*p;
 *q=e;
 ++L->length;
 return OK;
}/*ListInsert Before i */

main()
{
 struct STU e;
 List La,Lb,Lc;
 
 clrscr();
 
 printf("\n\n-------------------List Demo is running...----------------\n\n");
 printf("First is InsertList function.\n");
 init(&La);
 
 strcpy(e.name,"stu1");
 strcpy(e.stuno,"100001");
 e.age=80;
 e.score=1000;
 ListInsert(&La,1,e);
 strcpy(e.name,"stu3");
 strcpy(e.stuno,"100002");
 e.age=80;
 e.score=1000;
 ListInsert(&La,2,e);
 
 printlist(La);
 printf("List A length now is  %d.\n\n",La.length);
 getch();
 
 strcpy(e.name,"stu5");
 strcpy(e.stuno,"100003");
 e.age=80;
 e.score=1000;
 ListInsert(&La,3,e);
 
 printlist(La);
 printf("List A length now is  %d.\n\n",La.length);
 getch();
 
 init(&Lb);
 
 strcpy(e.name,"stu2");
 strcpy(e.stuno,"100001");
 e.age=80;
 e.score=1000;
 ListInsert(&Lb,1,e);
 strcpy(e.name,"stu4");
 strcpy(e.stuno,"100002");
 e.age=80;
 e.score=1000;
 ListInsert(&Lb,2,e);
 
 strcpy(e.name,"stu6");
 strcpy(e.stuno,"100001");
 e.age=80;
 e.score=1000;
 ListInsert(&Lb,3,e);
 
 printlist(Lb);
 printf("List B length now is  %d.\n\n",Lb.length);
 getch();
 
 MergeList(&La,&Lb,&Lc);
 printlist(Lc);
 getch();
 
 printf("Second is UnionList function.\n");
 printf("Now union List A and List B.....\n");
 UnionList(&La,&Lb);
 printlist(La);
 printf("List A length now is  %d.\n\n",La.length);
 getch();
 
 
 printf("\n\n\n\n\n\nWelcome to visit !\n\n\n\n\n\n\n");
 
}

数据结构教程: