淘先锋技术网

首页 1 2 3 4 5 6 7

数据结构--线性表（顺序表、单链表、双链表、循环链表、静态链表）

前言

 学习所记录，如果能对你有帮助，那就泰裤辣。

目录

1.线性表概念

定义

基本操作

2.顺序表

定义

顺序表的实现--静态分配

动态分配

顺序表的特点

顺序表的插入和删除

顺序表的查找

按位查找

 按值查找

3.单链表

定义

单链表的初始化

不带头节点的单链表

带头节点的单链表

插入按位序插入

指定结点的后插操作

指定结点的前插操作

 按位序删除

指点结点的删除

单链表的查找

按位查找

按值查找

 表的长度

单链表的建立

尾插法

头插法

4.双链表

插入

删除

5.循环链表

循环单链表

循环双链表

初始化

与双链表基本操作的不同

6.静态链表

7.顺序表和链表的异同

逻辑结构

存储结构

基本操作

1.线性表概念

定义

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

注

1.Ai 是线性表中的 “ 第 i 个” 元素线性表中的位序( 位序从1开始,数组下标从0开始 )
2.A1 是表头元素 ; an 是表尾元素。
3.除第一个元素外，每个元素有且仅有一个直接前驱;除最后一个元素外，每个元素有且仅有一个直接后继

基本操作

         基本操作主要包括 ： 创建、销毁、增删改查

基本操作
lnitList(&L):初始化表。构造一个空的线性表L，分配内存空间。
DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e)ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
LocateElem(Le):按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作
Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。
PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):判空操作。若L为空表，则返回true，否则返回false。

2.顺序表

定义

 顺序表――用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表的实现--静态分配

#include <stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
	int data[MaxSize];	
	int length;			//当前长度
}SqList;
//	初始化顺序表
void InitList(SqList &L){
	for(int i=0; i<MaxSize ; i++)
		L.data[i] = 0 ; //设置默认值为0
	L.length = 0 ;
}

int main(){
	SqList L;	//声明顺序表
	InitList(L);
	return 0;
}

动态分配

C  malloc 、frree 函数

        

C++ new 、delete 关键字

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10 //定义默认最大长度
typedef struct{
	int *data;		//指示动态分配数组的指针	
	int MaxSize;	//顺序表的最大容量
	int length;		//当前长度
}SqList;
//	初始化顺序表
void InitList(SqList &L){
	//申请存储空间
	L.data = (int*)malloc(InitSize*sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}
//增加动态数组的长度
void IncreaseSize(SqList &L,int len){
	int *p = L.data ;
	L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
	for( int i=0 ; i<L.length ; i++ ){
		L.data[i] = p[i];	//将数据复制到新区域
	}
	L.MaxSize = L.MaxSize+len;//顺序表最大长度增加len
	free(p);					//释放原来的内存空间
}

int main(){
	SqList L;	//声明顺序表
	InitList(L);//初始化顺序表
	printf("%d\n",L.MaxSize);
	IncreaseSize(L,5);//增加数组长度
	printf("after:%d\n",L.MaxSize);

	system("pause");
	return 0;
}

顺序表的特点

  1. 随机访问，即可以在O（1)时间内找到第 i 个元素。
  2. 存储密度高，每个节点只存储数据元素
  3. 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高)
  4. 插入、删除操作不方便，需要移动大量元素

顺序表的插入和删除

 插入

#include <stdio.h>
#define MaxSize 10

//定义顺序表
typedef struct{
	int data[MaxSize];	//数据
	int length;			//当前长度
}SqList;
//将e插入到顺序表L的第i处
bool ListInsert(SqList &L,int i,int 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--)//将第i个以及之后的元素后移
		L.data[j] = L.data[j-1];
	L.data[i-1] = e;
	L.length++;
	return true;
}

 删除操作

//删除顺序表中的第i个元素
bool ListDelete(SqList &L,int i ,int &e){
	if(i<1 || i>L.length)	//判断i的范围是否合理
		return false;
	e = L.data[i-1];		//将被删除的值赋给e
	for(int j=i-1 ; j<L.length ;j++ ){					//元素前移
		L.data[j] = L.data[j+1];
	}
	L.length--;
	return true;
}

顺序表的查找

按位查找

//按位查找:获取表L中第i个位置的元素的值
int GetElem(SqList L,int i){
	return L.data[i-1];
}

 按值查找

//按值查找：在表L中查找具有给定关键字值的元素,并返回对应位序
int LocateElem(SqList L,int e){
	for(int i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;
		return 0;	//查找失败
}

3.单链表

定义

优点：不要求大片连续空间，改变容量方便。

缺点：不可随机存取，要耗费一定空间复杂度。

单链表的初始化

注意：如无特殊要求，一般视为带头结点的单链表来处理

不带头节点的单链表

#include <stdio.h>
#include <stdlib.h>
//不带头结点的单链表
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
	L = NULL;	//空表，无结点，防止脏数据
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L){
	if(L == NULL )
		return true;
	else
		return false;
}

void test(){
	LinkList L;
	InitList(L);
}

带头节点的单链表

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
	int data;
	//struct
		LNode *next;
}LNode,*LinkList;

//初始化单链表
bool InitList(LinkList &L){
	L = (LNode *) malloc(sizeof(LNode));//分配一个头结点
	if(L ==NULL)
		return false;
	L->next = NULL;
	return true;
}

int main(){
	LinkList L; //声明一个单链表指针
	InitList(L);

	system("pause");
	return 0;
}

 比较

不带头结点，写代码更麻烦
对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
对空表和非空表的处理需要用不同的代码逻辑

插入按位序插入

带头结点

//在第i个位置插入元素e
bool ListInsert(LinkList &L ,int i, int e){
	if(i<1)
		return false;
	LNode *p;	//指针指向当前扫描到的结点
	int j=0;	//当前p指向的是第几个结点
	p = L;
	while (p!=NULL && j<i<1){	//循环找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	//开始插入操作
	LNode *s = (LNode *)malloc(sizeof(LNode));//申请空间
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

 不带头结点

//在第i个位置插入元素e
bool ListInsert(LinkList &L ,int i, int e){
	if(i<1)
		return false;
	//插入第一个结点
	if(i==1){
		LNode *s=(LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}

	LNode *p;	//指针指向当前扫描到的结点
	int j=0;	//当前p指向的是第几个结点
	p = L;
	while (p!=NULL && j<i<1){	//循环找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	//开始插入操作
	LNode *s = (LNode *)malloc(sizeof(LNode));//申请空间
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

指定结点的后插操作

//后插操作:在p结点之后插入元素e
bool InsertNextNode (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;		//将结点s保存数据元素e
	return true;
}

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
	LNode *p;
	int j =0;
	p=L;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++;
	}
	InsertNextNode(p,e);
}

指定结点的前插操作

//前插操作：在p结点之前插入元素e
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->next = s;		//将新结点连到p之后
	s->data = p->data;  //将p中的元素复制到s中
	p->data = e;		//p中元素覆盖为e
	return true;
}

 按位序删除

//按位序删除（带头结点）
bool ListDelete(LinkList &L,int i,ElemType &e){
	if(i<1)
		return false;
	LNode *p;
	int j=0;
	p = L;
	while(p!=NULL && j<i-1){//将p指针定位到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)//i值不合法
		return false;
	if(p->next == NULL)
		return false;
	LNode *q = p->next;	//令q指向被删除结点
	e = q->data;		//用e返回元素的值
	p->next=q->next;	//将*q结点从链中“断开”
	free(p);			//释放结点的存储空间
	return true;
}

指点结点的删除

即将p后继结点的值赋给p，再将p的后继删除。 

//删除指点结点p
bool DeleteNode(LNode *p){
	if(p==NULL)
		return false;
	LNode *q=p->next;		//令q指向*p的后继结点
	p->data=p->next->data;	//和后继结点交换数据域
	p->next=q->next;		//将*q结点从链中“断开”
	free(q);				//释放后继结点的存储空间
	return true;
}

单链表的查找

按位查找

//按位查找，返回第i个元素(带头结点)
LNode * GetElem(LinkList L,int i){
	int j=1;
	LNode *p=p->next;
	if(i==0)//若获取的是第一个结点
		return L;
	if(i<1)//若链表L中没有结点
		return NULL;
	while(p!=NULL && j<i){
		p=p->next;
		j++;
	}
	return p;
}

按值查找

//按位查找，找到数据域==e的结点
LNode * LocateElem(LinkList L,ElemType e){
	LNode *p = L->next;
	//从第1个结点开始查找数据域为e的结点
	while(p!=NULL && p->data!=e)
		p=p->next;
	return p;		//若找到则返回结点指针，否则返回NULL
}

 表的长度

//表的长度
int length(LinkList L){
	int len=0;
	LNode *p =L;
	while(p->next!=NULL){
		p = p->next;
		len++;
	}
	return len;
}

单链表的建立

尾插法

//尾插法
bool List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;						//r为表尾指针
	scanf("%d",&x);						//输入结点的值
	while(x!=9999){						//输入9999则结束输入
		//在r结点之后插入元素x
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r=s;							//确保r为表尾指针
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}

头插法

即每次插入一个元素都插入到单链表头结点后面。

LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));//创建头结点
	scanf("%d",&x);						//输入结点的值
	while(x!=9999){						//输入9999则结束输入
		//在头结点之后插入元素x
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d",&x);
	}
	return L;
}

4.双链表

与单链表相比，多了个前驱指针，可以逆向检索

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

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

//初始化双链表(带头结点)
bool InitDLinkList(DLinklist &L){
	L = (DNode *)malloc(sizeof(DNode));
	if(L==NULL)			//内存不足，分配失败
		return false;
	L->prior = NULL;	//头结点的prior永远指向NULL
	L->next = NULL;		
	return true;
}

int main(){
	//初始化双链表
	DLinklist L;
	InitDLinkList(L);

	return 0;
}

插入

//在p结点后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL)
		return false;
	s->next = p->next;
	if(p->next != NULL)	//如果p结点有后继结点
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

删除

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
	if(p==NULL)
		return false;
	DNode *q = p->next;		//找到p的后继结点q
	if(q==NULL)				//p没有后继结点q
		return false;
	p->next = q->next;
	if(q->next!=NULL)		//q结点不是最后一个结点
		q->next->prior = p;
	free(q);				//释放结点空间
	return true;
}

5.循环链表

循环单链表

将表尾指针指向头结点

#include <stdio.h>
#include <stdlib.h>
#define ElemType int

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

//判断循环单链表是否为空
bool Empty( LinkList L) {
	if(L->next == L)
		return true;
	else
		return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail( LinkList L, LNode *p){
	if (p->next==L)
		return true;
	else
		return false;
}

//初始化一个循环单链表
bool InitList(LinkList &L) {
	L = (LNode *) malloc(sizeof( LNode) );//分配一个头结点
	if (L==NULL)			//内存不足，分配失败
		return false;
	L->next = L;			//头结点next指向头结点
	return true;
}

循环双链表

双链表:
表头结点的prior指向NULL;

表尾结点的next指向NULL
循环双链表:
表头结点的prior指向表尾结点;

表尾结点的next指向头结点

初始化

#include <stdio.h>
#include <stdlib.h>
#define ElemType int


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


//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
	L = ( DNode *) malloc(sizeof( DNode) );//分配一个头结点
	if (L==NULL)	//内存不足，分配失败
		return false;
	L->prior = L;	//头结点的prior指向头结点
	L->next = L;	//头结点的next指向头结点
	return true;
}
//判断循环双链表是否为空
bool Empty(DLinklist L) {
	if(L->next == L)
		return true;
	else
		return false;
}

//判断结点p是否为循环链表的表尾结点
bool isTail(DLinklist L,DNode *p){
	if( p->next==L)
		return true;
	else
		return false;
}

void testDLinkList() {
	//初始化循环双链表
	DLinklist L;
	InitDLinkList(L);
	// ...后续代码...
}

与双链表基本操作的不同

在p结点后插入新结点、删除p结点后面的结点时不用考虑p后继结点是否为空的问题

 删除

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
	if(p==NULL)
		return false;
	DNode *q = p->next;		//找到p的后继结点q
	//注释的内容为双链表所需进行的条件判断
	//if(q==NULL)				//p没有后继结点q
	//	return false;
	p->next = q->next;
	//if(q->next!=NULL)		//q结点不是最后一个结点
	//	q->next->prior = p;
	free(q);				//释放结点空间
	return true;
}

插入

//在p结点后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL)
		return false;
	s->next = p->next;
	//注释的内容为双链表所需进行的条件判断
	// if(p->next != NULL)	//如果p结点有后继结点
	//	 p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

6.静态链表

单链表:各个结点在内存中随机存储。
静态链表:分配一整片连续的内存空间，各个结点集中存储。用数组的方式实现的链表。

#define MaxSize		//静态链表的最大长度
typedef struct {	//静态链表结构类型的定义
	int data;	//存储数据元素
	int next;		//下一个元素的数组下标
}SLinkList[MaxSize];

基本操作的实现逻辑

初始化静态链表:
把a[o] 的next 设为1
把其他结点的next设为一个特殊值用来表示结点空闲，如-2
 

查找:
从头结点出发挨个往后遍历结点

插入位序为i的结点:
①找到一个空的结点，存入数据元素

②从头结点出发找到位序为i-1的结点

③修改新结点的next
④修改i-1号结点的next
 

删除某个结点:
①从头结点出发找到前驱结点

②修改前驱结点的游标
③被删除结点next设置一个特殊值以表示已经被删除

7.顺序表和链表的异同

逻辑结构

都属于线性表，都是线性结构

存储结构

顺序表（顺序存储）：

优点:支持随机存取、存储密度高
缺点:大片连续空间分配不方便,改变容量不方便

链表（链式存储）：

优点:离散的小空间分配方便、改变容量方便
缺点:不支持随机存取、存储密度低

基本操作

创销、增删改查

创建

顺序表：

需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量;若分配空间过大，则浪费内存资源
链表：

只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

销毁

顺序表：

静态分配:静态数组                         -->系统自动回收空间
动态分配:动态数组( malloc、 free)  -->  需要手动free
链表：

依次删除各个结点（ free)

增删

顺序表：

插入/删除元素要将后续元素都后移/前移
链表：

插入/删除元素只需修改指针即可

查

顺序表：

按位查找:O(1)
按值查找:O(n)若表内元素有序，可在O(\log_{2}n)时间内找到
链表：

按位查找:O(n)
按值查找:O(n)

综上所述

表长难以预估、经常要增加/删除元素—―链表
表长可预估、查询（搜索）操作较多――顺序表

开放式问题的答题思路:

问题:请描述顺序表和链表的bla bla bla....
交规线性表时,用顺序表还是链表好?(6分)
一一
顺序表和链表的逻辑结构都是线性结构，都属于线性表。
但是二者的存储结构不同，顺序表采用顺序存储...(特点，带来的优点缺点);链表采用链式存储...(特点、导致的优缺点）。
由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时...;当插入一个数据元素时...;当删除一个数据元素时...;当查找一个数需元素时...