Pressidian

Appearance

第二章 线性表 ​

线性表 ​

定义：大于等于零个具有相同数据类型的数据元素的有限序列，表示为L=（a1，a2，a3...an），数据元素的个数n为零的时候表示空表，a1表示表头元素，除其外的其他元素有且仅有一个（直接）前驱，an表示最后一个元素，除其外的其他元素有且仅有一个（直接）后继。线性表是一种逻辑结构，顺序表和链表是其物理实现（物理结构），数据元素的位序从“1”开始

  • 特点：
    • 表中的元素个数有限
    • 元素间具有逻辑上的顺序性
    • 元素都是数据元素
    • 表中的数据元素的类型都相同，占据相同的空间大小
  • 分类：
    • 顺序存储：顺序表
    • 链式存储：
      • 单链表
      • 双链表
      • 循环链表：
        • 循环单链表
        • 循环双链表
      • 静态链表

线性表基本操作 ​

定义：一个数据结构的基本操作是其最基本最核心的操作，其他的操作可以由其的组合构建，常见的基本操作包括创建、销毁、增删改查

  • 分类：
    • 初始化：InitList(&L)使用引用类型将数据返回
    • 删除：DestroyList(&L)
    • 插入元素：ListInsert(&L,i,e)
    • 删除元素：ListDelete(&L,i,&e)返回被删除的数据
    • 求表长：Length(L)
    • 判空：Empty(L)

顺序表 ​

定义：线性表的顺序存储，将逻辑上连续的存储单元在物理上也连续的存储，由于数据元素的大小相同能够实现随机存储，在高级语言中常采用数组来表述顺序表。线性表中的数据从“1”开始编号，数组从“0”开始。

  • 分配：
    • 静态分配：数组的大小空间固定，如果空间满，加入数据会存在数据溢出，导致程序崩溃
    • 动态分配：一旦数据的空间占满，就会动态的分配新的空间。重新开辟的空间将旧的空间的数据复制过来，使用free()来释放空间。其本质还是顺序存储，不是链式，只是动态的分配空间的大小
//静态分配
#define MaxSize 50 //使用宏定义最大值
typedef struct{
	ElemType data[MaxSize]; //假定数据元素的类型为ElemType，最好设置默认值防止内存脏数据
	int Length; //初识值为0
}SqList;
//动态分配
#define InitSize 100 //初始化时的大小
typedef struct{
	ElemType *data; 
	int Length,MaxSize; //最大值和当前的值
}SeqList;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize) //旧的
L.data=(ElemType*)malloc(sizeof(ElemType)*(InitSize+扩展数)) //新的空间

顺序表基本操作 ​

插入操作：首先进行健壮性判断，通过后将要插入的位置后的元素依次后移一位

bool ListInsert(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1) //判断i的范围是否有效
		return false;
	if(L.Length>=MaxSize) //判断是否有空间
		return false;
	for(int j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1]; //从后向前移动数据
	L.data[i-1]=e;
	L.length++; //表长加1
	return ture;
}//平均的时间复杂度为O(n)

删除操作：使用&e将删除的数值返回。顺序表的插入和删除操作的时间主要浪费在数据的移动上

bool ListDelet(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length+1) //判断i的范围是否有效
		return false;
	e=L.data[i-1]; //数组下标从零开始
	for(int j=i;j<Length;j++)
		L.data[j-1]=L.data[j]; //从前向后移动数据
	L.data[i-1]=e;
	L.length--; //表长减1
	return ture;
}//平均的时间复杂度为O(n)

按值查找：寻找L中的第一个与e相等的元素，并返回其位序

int LocateElem(SqList L,ElemType e){
	for(int i=0;i<Length;i++){
		if(L.data[i]==e){
			return i+1; //是位序，并不是数组下标
		}
	}
	return 0; //返回0表示失败
}//平均的时间复杂度为O(n)

单链表 ​

定义：线性表的链式存储，每个节点除了数据还有指向下一个节点的指针，每个节点只有一个指针，故称单链表

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
//LNode为struct LNode的别名，LinkList是一个指向LNode节点的指针，代表了一个链表

使用单链表能够解决需要连续内存空间的缺点，但是其中的指针会浪费空间，不能够实现随机存取，只能进行顺序存取，查找某个结点时必须从头查询。通常会使用头指针来表示一个链表，头指针为NULL时为空链表，通常在第一个节点前附加头结点位序为0，用于统一化操作并且无论表是否是空表，头指针都是非空的。头指针始终指向最前面的结点，由malloc()申请的空间必由free()释放，而顺序表的释放由系统自动完成

bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));
	if(L==NULL) //如果L申请失败
		return false;
	L->next=NULL; //表示空链表
	return ture;
}

单链表基本操作 ​

尾插法建表：正向建立单链表

LinkList List_TailInsert(LinkList &L){
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	scanf('%d',&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s;
		scanf('%d',&x);
	}
	r->next=NULL;
	return L;
}//O(n)

头插法建表：反向建立

LinkList List_TailInsert(LinkList &L){
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	LNode *s;
	L->next=NULL;
	scanf('%d',&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=r->next;
		L->next=s;
		scanf('%d',&x);
	}
	return L;
}//O(n)

按序号查找：寻找i号结点，并返回节点指针

LNode *GetElem(LinkList L,int i){
	if(i<0) //如果为头结点返回NULL
		return NULL;
	int j=0;
	LNode *p=L
	while(p!=NULL&&j<i){
		p=p->next;
		j++;
	}
	return p;
}//O(n)

按值查找：寻找第一个e值结点，并返回节点指针

LNode *LocateElem(LinkList L,ElemType e){
	LNode *p=L->next;
	while(p!=NULL&&p->data!=e){
		p=p->next;
	}
	return p;
}//O(n)

插入结点：将结点插入i号位置

bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
	LNode *p=L; //使用p指针来指向目标位置i前的结点
	int j=0;
	while(p!=NULL&&j<i-1){ //找到i前的位置，也可以使用GetElem()
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	LNode *s=(LNode*)malloc(sizeof(LNode)); //使用s来指向要插入的结点
	s->data=e;
	s->next=p->next; //必须先执行
	p->next=s; //必须后执行
	return ture;
}//O(n)

结点前插：在某个结点的前面插入

bool InsertPriorNode(LNode *p,ElemType e){
	if(p==NULL)
		return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->next=p->next; //在p的后面插入s
	p->next=s;
	s->data=p->data; //再将p和s的值交换，通过这种方法避免了访问p的前驱结点
	p->data=e;
	return ture;
}

结点后插：在某个结点的后面插入

bool InsertPriorNode(LNode *p,ElemType e){
	if(p==NULL)
		return false;
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->data=e;
	s->next=p->next;
	p->next=s;
	return ture;
}

删除结点：将i号结点删除

bool ListInsert(LinkList &L,int i,ElemType e){ //使用头指针
	if(i<1)
		return false;
	LNode *p=L; //使用p指针来指向目标位置i前的结点
	int j=0;
	while(p!=NULL&&j<i-1){ //找到i前的位置，也可以使用GetElem()
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	LNode *q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return ture;
}//O(n)
//将指定指针指向的结点删除
bool InsertPriorNode(LNode *p,ElemType &e){
	if(p==NULL)
		return false;
	LNode *q=(LNode*)malloc(sizeof(LNode));
	if(q==NULL)
		return false;
	e=p->data;
	q=p->next;
	p->data=q->next->data;
	p->nest=q->next;
	free(q);
	return ture;
}//O(n)

求表长：求表的长度（不包括头结点）

int Length(LinkList L){
	int len=0;
	LNode *p=L
	while(p->next!=NULL){
		p=p->next;
		len++;
	}
	return len;
}//O(n)

双链表 ​

定义：由于单链表只有指向后继结点的指针只能实现单方向的访问，双链表额外添加指向前驱结点的指针

typedef struct DNode{
	ElemType data;
	struct LNode *next,*prior;
}DNode,*DLinkList;

bool InitDLinkList(DLinkList &L){
	L=(DNode*)malloc(sizeof(DNode));
	if(L==NULL)
		return false;
	L->prior=NULL;
	L->next=NULL;
	return ture;
}

双链表基本操作 ​

插入操作：在p所指结点后插入s所指结点

bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL||s==NULL)
		return false;
	s->next=p->next; //代码的顺序不是唯一的，但是推荐这样写
	if(p->next!=NULL)
		p->next->prior=s;
	s->prior=p;
	p->next=s;
	return ture;
}

删除操作：删除p所指的结点的后继结点

bool DeleteNextDNode(DNode *p){
	if(p==NULL||s==NULL)
		return false;
	DNode *q=p->next;
	if(q==NULL)
		return false;
	p->next=q->next;
	q->next->prior=p;
	free(q);
	return ture;
}

循环单链表 ​

定义：在单链表的基础上将最后一个结点的next由NULL改为了头结点，也可以专门设置一个r专门指向尾结点。当L->next=L时循环单链表为空

bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));
	if(L==NULL) //如果L申请失败
		return false;
	L->next=L; //头结点指向头结点
	return ture;
}

循环双链表 ​

定义：头结点的prior指针还要指向尾节点，p->next为L时循环双链表为空，此时头结点的next和prior都指向L

静态链表 ​

定义：使用数组来描述链式存储的结构，具有data和next域，但是next中存的是结点在数组中的下标，静态链表也是事先分配一段连续的空间，尾节点的next为-1，空结点的next为-2。

#define MaxSize 50
typedef struct{
	ElemType data;
	int next;
}SLinkList[MaxSize];//这里SLinkList表示一个最大长度为MaxSize的数组，而不是一个节点