第二章线性表

线性表

线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列。其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n )

PS:整数递增不能算是线性表（不满足有限）；

特点：除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继；

基本操作

InitList(&L):初始化表。构造一个空的线性表
DestoryList(&L):销毁操作
ListInsert(&L,i,e):插入操作
ListDelete(&L,i,&e):删除操作，并用e返回删除元素的值
LocateElem(L,e):按值查找操作，L表中给定关键字值的元素
GetElem(L,i):按位查找操作。L表中的第i个位置的元素值
Length(L):求表长
PrintList(L):输出操作
Empty(L):判断操作

Tips:对参数修改需要“带回来”时需要引用“&”

顺序表（顺序存储）重点

静态分配

#define MaxSize 10				//定义线性表的最大长度
typedef struct{
	ElemType data[MaxSize];		 //顺序表的元素静态的数组
	int length;					//顺序表的当前长度
}SqList;						//顺序表的类型定义

动态分配

#define InitSize 10			//表长度的初始定义
typedef struct{				
	ElemType *data;				//指示动态分配数组的指针
	int MaxSize,length;			//数组的最大容量和当前个数
}SqList;						//动态分配数组顺序表的类型定义
//C的初始动态分配语句
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
free(L);
//C++的初始动态分配语句
L.data = new ElemType[InitSize];
delete L;

顺序表特点：

1.随机访问2.存储密度高3.拓展容量不方便4.插删数据元素不方便；

单链表（带头节点和不带头节点）

typedef struct LNode{		//定义单链表结点类型
	ElemType data;			//数据域 每个节点放一个数据元素
    struct LNode *next;		//指针域  指针指向下一个节点
}LNode, *LinkList;		//LinkList为指向结构体LNODE的指针类型

Tips: 1、LinkList等价于LNode *；2、带头结点的空表定义 L->next==NULL写代码更方便；3注意考试时判断是否是有头节点；

创建单链表

LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));//创建头结点
    L->next = NULL;					//初始为空链表
    scanf("%d",&x);
    while(x!=9999){             //表示输入9999结束
        s = (LNode*)malloc(sizeof(LNode));//创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;//将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

头插法逆置（重点考点）

LNode *p,*q;
p=L->next;
L->next=NULL;    //断链
while(p){
q=p->next;    
p->next=L->next;
L->next=p;
p=q;}
return L

双链表（带头结点）

插入

s->next=p->next;
if(p->next)
p->next->prior=s;
s->prior=p;
p->next=s;

循环链表

头结点的next指向头结点L->next=L

静态链表

分配一整片连续的存储空间，各个结点集中安置（其中0号结点为头结点不放数据），游标充当指针（当游标为-1表示已经达到表尾）

#define MaxSize 10       //静态链表的最大长度
typedef struct{          //数据类型的定义
	ElemType data;      //存储数据元素
    int next;           //下一个元素的数组下标
}SLinkList[MaxSize];
void testSLinkList(){
    SLinkList a;
    //。。。。。后续代码
}

或者还可以

#define MaxSize 10       //静态链表的最大长度
struct Node{          //数据类型的定义
	ElemType data;      //存储数据元素
    int next;           //下一个元素的数组下标
};

vode testSLinkList(){
    struct Node a[MaxSize];
    //。。。。后续代码
}

静态链表优缺点

优点：增删改查不需要大量移动元素;

缺点：不能随机存储,只能从头结点开始依次往后查，容量固定不可变;

顺序表和链表总结

逻辑结构：都属于线性表，都是线性结构；

存储结构：顺序存储VS链式存储；

基本操作：创销、增删改查