数据结构——第二章 线性表

Posted on by hackdl

目录

前言

1 线性表

2 线性表的顺序存储——顺序表

3 线性表的链式存储

3.1 单链表

3.2 双链表

3.3 循环链表

3.4 静态链表

前言

逻辑结构：线性表

存储结构：顺序存储结构（简称顺序表）和链式存储结构（简称链表）

1 线性表

线性表中的位序从1开始

2 线性表的顺序存储——顺序表

顺序表用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

静态分配

#define MaxSize 50
typedef struct{
  //ElempType为元素类型，如int,float等
  ElempType data[MaxSize];//地址连续
  int length;
}SqList;

静态分配的初始化方法InitList(SqList &L)

void InitList(SqList &L){
    int length=0;//初始时顺序表的长度为0，没有元素
}

静态分配与动态分配的区别是动态分配可以增加顺序表的容量，以下对动态分配进行讲解： (ElemType为数据类型，Status为函数的类型)

动态分配

#define InitSize 100
typedef struct{
    ElemType *data;//引入指针，指向首地址
    int length;
    int MaxSize;
}SqList;

1、动态分配的初始化方法InitList(SqList &L)

//初始化
void InitList(SqList &L){
    L.data=malloc(Initsize*sizeof(ElemType));//将data指向开辟的空间
    L.length=0;
    L.MaxSize=InitSize;
}

2、动态分配增加顺序表容量IncreaseSize(SqList &L,int len)

//扩大顺序表的容量
void IncreaseList(SqList &L,int len){
    ElemType *p=L.data;//将p指针指向原来的顺序表
    L.data=malloc((MaxSize+len)*sizeof(ElemType));//data指针指向新开辟的更大的空间
    for(int i=0;i

3、查找元素的位置LocateElem(SqList L,int e)

//查找元素的位置
int LocateElem(SqList L,ElemType e){
	for(int i=0;i

4、查找位置i的元素GetElem(SqList L,int i)

Status GetElem(SqList L,int i){
	if(iL.length) return -1;
	return L.data[i-1];
}

5、在位置x插入元素e：IncreaseElem(SqList &L,int x,ElemType e)

//插入元素
bool IncreaseElem(SqList &L,int x,ElemType e){
	if(xL.length+1) return false;
	if(L.length==L.MaxSize) return false;
	for(int i=L.length-1;i>=x-1;i++){
		L.data[i+1]=L.data[i];
	}
	L.data[x-1]=e;
	L.length+=1;
	return true;
}

6、删除位置x的元素DeleteElem(SqList &L,int x,ElemType&e)

//删除元素
bool DeleteElem(SqList &L,int x,ElemType &e){
	e=L.data[x-1];
	if(xL.length) return false;
	for(int i=x;i

7、展示

//展示
void printList(SqList L){
	for(int i=0;i

8、判空

//判空
bool Empty(SqList L){
	if(L.length==0){
		return true;
	}else{
		return false;
	}
}

9、销毁

//销毁
void DestroyList(SqList &L){
	free(L.data);
}

10、当ElemType为int时，动态分配具体实现：

#include
#include
#define InitSize 100
typedef int ElemType;
typedef struct{
	int *data;
	int length;
	int MaxSize;
}SeqList;
//初始化 
void InitList(SeqList &L){
	L.data=(int *)malloc(InitSize*sizeof(ElemType));
	L.length=0;
	L.MaxSize=InitSize;
}
//扩大顺序表的容量 
void IncreaseSize(SeqList &L,int len){
	int *q=L.data;
	L.data=(ElemType *)malloc((InitSize+len)*sizeof(ElemType));
	for(int i=0;iL.length)
	return -1;
	return L.data[i-1];
}
//插入元素 
bool ListInsert(SeqList &L,int i,ElemType e){
	if(iL.length+1)
	return false;
	if(L.MaxSize=i-1;j--){
		L.data[j+1]=L.data[j];
	}
	L.data[i-1]=e;
	L.length++;
	return true;
}
//删除元素 
bool ListDelete(SeqList &L,int i,ElemType &e){
	if(iL.length)
	return false;
	e=L.data[i-1];
	for(int j=i;j

3 线性表的链式存储

3.1 单链表

带头结点

typedef struct LNode{
	ElemType data;
	struct node *next;
}LNode,*LinkList;
//初始化
void InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
}

带头结点的单链表具体实现：

#include
#include
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
//初始化（创建只有一个头结点的空链表） 
void InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NUL服务器托管网L;
}
//头插法建立单链表
void CreateList_H(LinkList &L){
	//初始化一个空链表，可以用InitList(LinkList &L)代替 
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
	//头插
	LNode *s;
	int x;
	printf("请输入单链表的数据域（输入9999表示结束）n");
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x; 
		s->next=L->next;
		L->next=s; 
		scanf("%d",&x);
	} 
} 
//尾插法建立单链表
void CreateList_R(LinkList &L){
	//初始化一个空链表
	L=(LNode *)malloc(sizeof(LNode));
	L->next=NULL;
	//尾插法
	LNode *s,*r;
	int x;
	r=L;//指向最后一个结点
	printf("请输入单链表的数据域（输入9999表示结束）n");
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x; 
		s->next=NULL;
		r->next=s;
服务器托管网		r=s; 
		scanf("%d",&x);
	} 
} 
//判空
bool Empty(LinkList L){
	return L->next==NULL;
} 
//输出单链表 
void print_LinkList(LinkList L){
	LNode *p=L->next;
	while(p){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("n");
}
//单链表的取值 
LNode *GetElem(LinkList L,int i){
	LNode *p=L->next;
	int j=1;
	if(i==0) return L;
	if(inext;
		j++;
	}
	return p;
} 
//按值查找
LNode *LocateElem(LinkList L,int e){
	LNode *p=L->next;
	while(p&&p->data!=e){
		p=p->next;
	}
	return p;
} 
//插入(在位置i上插) 
void ListInsert(LinkList &L,int i,int e){
	LNode *p=GetElem(L,i-1);
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
} 
//前插(给定结点，要进行前插，可以进行后插，然后交换数据域，时间复杂度仅为O(1)) 
void AfterInsert(LNode *p,int e){
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=p->data;
	s->next=p->next;
	p->next=s;
	p->data=e; 
}
//删除 (删除位置i上的结点)
void ListDelete(LinkList &L,int i,int &e){
	LNode *p=GetElem(L,i-1);
	LNode *q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
} 
//删除给定结点（和后继结点交换数据域，然后删除后继结点）注意：不能是尾结点 
void DeleteLNode(LNode *p){
	//q为下一个
	LNode *q=p->next;
	p->data=q->data; 
	p->next=q->next;
	free(q); 
} 
//求表长
int LinkLength(LinkList L){
	LNode *p=L->next;
	int count=0;
	while(p){
		count++;
		p=p->next;
	}
	return count;
} 
int main(){
	LinkList L;
	printf("------------------头插法创建单链表(与输入倒序)-------------------n");
	CreateList_H(L);
	printf("创建完成：");
	print_LinkList(L);
	printf("------------------插入-------------------n");
	printf("在位置2上插入，数据域为10:n");
	ListInsert(L,2,10);
	print_LinkList(L);
	printf("------------------删除-------------------n");
	printf("删除第1个：n");
	int e=0;
	ListDelete(L,1,e);
	print_LinkList(L);
	printf("删除的数是：%dn",e);
	printf("------------------取值-------------------n");
	printf("第一个结点的数据域是：n");
	LNode *p=GetElem(L,1);
	printf("%dn",p->data);
	printf("------------------按值查找-------------------n");
	printf("数据域为3的结点q地址:n");
	LNode *q=LocateElem(L,3);
	printf("%pn",q); 
	printf("------------------前插-------------------n");
	printf("在结点q前面插入数据域为20的结点：n");
	AfterInsert(q,20);
	print_LinkList(L);
	printf("------------------删除给定结点-------------------n");
	printf("删除给定的第一个结点:n");
	DeleteLNode(p);
	print_LinkList(L);
	printf("------------------求表长-------------------n");
	printf("链表长度：%dn",LinkLength(L));
	printf("------------------尾插法创建单链表(与输入相同)-------------------n");
	LinkList L2;
	CreateList_R(L2);
	printf("创建完成：");
	print_LinkList(L2);
	return 0; 
}

不带头结点

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
//初始化
void InitLinkList(LinkList &L){
	L=NULL;
}

不带头结点的单链表的具体实现：（给出了创建方法，其他基本方法与带头结点的类似）

#include
#include
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
//初始化
void InitLinkList(LinkList &L){
	L=NULL;
} 
//判空
bool Empty(LinkList L){
	return L==NULL;
} 
//头插法建立单链表
void CreateList_H(LinkList &L){
	L=NULL;
	//头插 
	LNode *s;
	int x;
	printf("请输入单链表的数据域（输入9999表示结束）n");
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		s->next=L;
		L=s;
		scanf("%d",&x);
	}
}
//尾插法建立单链表
void CreateList_R(LinkList &L){
	L=NULL;
	//尾插
	LNode *s,*r=L;
	int x;
	printf("请输入单链表的数据域（输入9999表示结束）n");
	scanf("%d",&x);
	while(x!=9999){
		if(L==NULL){
			s=(LNode *)malloc(sizeof(LNode)); 
			s->data=x;
			s->next=NULL;
			L=s;
			r=s; 
		}else{
			s=(LNode *)malloc(sizeof(LNode)); 
			s->data=x;
			s->next=NULL;
			r->next=s;
			r=s; 
		} 
		scanf("%d",&x);
	}
}
//输出
void printfList(LinkList L){
	LNode *p=L;
	while(p){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("n");
} 
int main(){
	LinkList L;
	printf("-----------------头插法建立单链表--------------------n");
	CreateList_H(L);
	printf("创建完成：n");
	printfList(L);
	printf("-----------------尾插法建立单链表--------------------n");
	LinkList L2;
	CreateList_R(L2);
	printf("创建完成：n");
	printfList(L2);
	return 0;
}

3.2 双链表

3.3 循环链表

3.4 静态链表

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: