线性表

线性表的抽象数据定义

ADT List{
数据对象：D={ai|ai∈ElemSet,i-1,2,....n,n≥0}
数据关系：R={<ai-1,ai>ai-1,ai∈D,i=2,...n}
基本操作：
InitList(&L);
构造一个空的线性表
Destroy(&L);
销毁线性表
ClearList(&L);
清除线性表
ListEmpty(L);
线性表是否为空
ListLength(L);
线性表的长度
GetElem(L,i,&e);
用e来返回线性表L第i个元素的值
LocateElem(L,e)
返回线性表L中第一个值与e相同的元素位置
ListInsert(&L,i,e)
在线性表L的第i个位置插入值为e的元素
ListDelete(&L,int i)
删除顺序表L中第i个元素
ListTraverse(L)
遍历输出数组
}ADT LIST

顺序表的基本操作的实现

顺序表的初始化

①为顺序表L静态/动态分配一个预定义大小的数组，使elem指向这段空间的基地址
②当前的长度设置为0

typedef struct{
ElemType data[MAXSIZE]
int length;
}

#define int ElemType 
typedef struct{
	ElemType *elem;
	int length;
}
typedef struct{
	L.elem=(ElemType *)malloc(sizeof(ElemType));
	if(!L.elem)
		exit(OVERFLOW);
	l.Length=0;
	return OK;
}

取值

①判断位置是否合理标准i(1≤i≤L.length)
②若i的值合理，将第i个的元素值L.data[i-1]赋值给e,通过e返回第i个数据元素的值

Status GetElem(L,i,&e){
	if(i<1||i>L.length||L.length==0)
		return error;
	e=L.data[i-1];
	return OK;

}

空间复杂度O(1)

查找

从第一个元素开始。即从元素下标从0开始，依次与之作比较

Status LocateElem(SqList L,ElemType e){
	for(int i=0;i<L.length;i++){
		if(L.data[i]==e)
			return i+1;
	return 0;
}}

空间复杂度O(n)

顺序表的插入

①首先判断插入的元素i的值是否是符合标准的值，这里符合标准的元素值i∈[1,n+1]
②判断元素的空间是否已满
③将第n个至第i个元素的值皆往后挪，空出第i个卫视
④将要插入的元素e放置在第i个元素下
⑤表长＋1

Status ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1||L.length==MAXSIZE）
			return error;
	for(int k=L.length-1;k>=n;k--)
	 		L.data[k+1]=L.data[k};
	 L.data[i-1]=e;
	 L.length++;
	 return OK;
}

空间复杂度O(n)

顺序表的删除

①首先判断要删除的元素的位置i是否合法，i∈[1,n]
②将i+1到n的位置都向前挪
③用e返回要删除的元素的值

Status Delete(SqList &L,int i,ElemType &e){
		if(i<1||i>L.length||L.length==0){
		 		return ERROR;
		}
		for(k=i;k<L.length;k++)
				L.data[k-1]=L.data[k];
		e=L.data[i-1];
		L.length--;
		return OK;

}

顺序表的代码实现

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int ElemType;


//顺序表的结构
typedef struct{
	ElemType data[MAXSIZE];
	int length;
}SqList;
//顺序表的初始化
Status InitList(SqList &L){
	L.length=0;
	return OK;
} 
//顺序表的判空
Status isEmpty(SqList L){
	if(L.length==0)
	return TRUE;
	else
	return FALSE;
}
//顺序表的清除
Status isClear(SqList &L){
	L.length=0;
	return OK;
} 
//求顺序表的长度
int ListLength(SqList L){
	return L.length;
} 
//返回第i个位置上的数据
int GetElem(SqList L,int i ,ElemType *e){
	if(i<1||i>L.length||L.length==0)
	return ERROR;
	*e=L.data[i-1];
	return OK;
	 
} 
//返回L中第1个与e满足关系的数据元素的位序。
int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
            return 0;
    for(i=0;i<L.length;i++)
    {
            if (L.data[i]==e)
                    break;
    }
    if(i>=L.length)
            return 0;
 
    return i+1;
}
 
Status ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1||L.length==MAXSIZE){
		return ERROR;
	}
  int k;
 		for(k=L.length-1;k>=i-1;k--)  /* 将要插入位置之后的数据元素向后移动一位 */
			L.data[k+1]=L.data[k];
  L.data[i-1]=e;
  L.length++;
  return OK;
} 
//顺序表删除数据
Status ListDelete(SqList &L,int i,ElemType *e){
	if(i<1||i>L.length||L.length==0)
	return ERROR;
	*e=L.data[i-1];
	if(i<=L.length){
		for(int k=i;k<L.length;k++){
					L.data[k-1]=L.data[k];
		}
	}
	L.length--;
	return OK;
} 
 

void displayTable(SqList L) {
    int i;
    for (i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");
}
void unionL(SqList &La,SqList Lb){
	int La_len,Lb_len,i;
	ElemType e;
	La_len=ListLength(La);
	Lb_len=ListLength(Lb);
	for(i=1;i<Lb_len;i++){
		GetElem(Lb,i,&e);
				if (!LocateElem(La,e))
			ListInsert(La,++La_len,e);
	}
} 

int main(){
	SqList L;
		SqList Lb;
	int i;
	ElemType e;
	int j;
	//初始化链表
	i=InitList(L);
	printf("%d\n",L.length);
    for (i = 1; i <= 5; i++) {
        L.data[i-1] = i;
         L.length++;
    }
    printf("顺序表中存储的元素分别是：\n");
    displayTable(L);
    ListInsert(L,1,8);
        printf("在顺序表中第一个插入数字8：\n");
    displayTable(L);
      ListInsert(L,2,9);
        printf("在顺序表中第二个插入数字9：\n");
    displayTable(L);
    ListDelete(L,2,&e);
       printf("在顺序表中第2个删除数字：\n");
    displayTable(L);
//        i=isEmpty(L);
//    printf("L是否空：i=%d(1:是 0:否)\n",i);
//        i=isClear(L);
//    printf("清空L后：L.length=%d\n",L.length);
    //有点类似于尾插法 
//       for(j=1;j<=5;j++)
//            i=ListInsert(&L,1,j);
//    printf("在L的表头依次插入1～5后：L.data=");
//有点类似于尾插法 
//        for(j=1;j<=10;j++)
//            ListInsert(L,j,j);
//    printf("在L的表尾依次插入1～10后：L.data=");
//     displayTable(L);
    //构造一个有10个数的Lb
	i=InitList(Lb);
    for(j=6;j<=15;j++)
            i=ListInsert(Lb,1,j);
  displayTable(Lb);
   displayTable(L);
	unionL(L,Lb); 
	printf("依次输出合并了Lb的L的元素：");
      displayTable(L);
    return 0;
}