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

前言

目录

1.线性表概念

定义

基本操作

2.顺序表

定义

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

动态分配

顺序表的特点

顺序表的插入和删除

顺序表的查找

按位查找

 按值查找

3.单链表

定义

单链表的初始化

不带头节点的单链表

带头节点的单链表

插入按位序插入

指定结点的后插操作

指定结点的前插操作

 按位序删除

指点结点的删除

单链表的查找

按位查找

按值查找

 表的长度

单链表的建立

尾插法

头插法

4.双链表

插入

删除

5.循环链表

循环单链表

循环双链表

初始化

与双链表基本操作的不同

6.静态链表

7.顺序表和链表的异同

逻辑结构

存储结构

基本操作

---

1.线性表概念

定义

注

基本操作

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

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;
}

动态分配

#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;
}

顺序表的特点

顺序表的插入和删除

 插入

#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
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;
}

循环双链表

初始化

#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结点的后继结点
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];

基本操作的实现逻辑

7.顺序表和链表的异同

逻辑结构

存储结构

基本操作

创建

销毁

增删

查

综上所述

开放式问题的答题思路: