线性表-链式存储

一.单链表
- 1.定义一个单链表
- 2.初始化一个单链表：弄个头结点
- 3.链表的建立：给了很多数据元素
- - (1)尾插法
  - (2)头插法
- 4.求表的长度
- 5.判断单链表是否为空
- 6.查
- - (1)按位查找：找到第i个位置的元素
  - (2)按值查找
- 7.增
- - (1)在指定结点前插元素
  - (2)在指定结点后插元素
  - (3)在指定位置处插入元素，返回是否插入成功（链表的下标=位置，因为有头结点）
- 8.删
- - (1)指定结点的删除
  - (2)删除指定位置的元素，返回删除的元素
二.双链表
- 1.双链表的定义
- 2.双链表的初始化：创建头结点
- 3.判断双链表是否为空
- 4.双链表的遍历
- 5.增：往指定结点p后插元素s
- 6.删
- - (1)删除p结点后继结点q
  - (2)删除双链表
三.循环链表
- 1.循环单链表
- - (1)单链表的定义
  - (2)循环单链表的初始化
  - (3)判断循环单链表是否为空
  - (4)判断该结点是否是循环单链表的表尾结点
- 2.循环双链表
- - (1)双链表的定义
  - (2)循环双链表的初始化
  - (3)判断循环双链表是否为空
  - (4)判断某结点是否是循环双链表的表尾结点
四.静态链表
- 1.静态链表的定义

一.单链表

概念：带头结点，头结点不存储数据，下标为0，推荐使用。

1.定义一个单链表

struct LNode{//链表结点结构
	int data;//数据
	struct LNode *next;//指向下一个结点的指针
}
typedet struct LNode LNode;//单链表结点
typedef struct LNode *LinkList;//单链表

2.初始化一个单链表：弄个头结点

bool InieList(LinkList L){
	L=(LNode)malloc(sizeof(LNode));//给定义好的单链表分配一个头结点空间
	if(L==NULL)return false;//L还等于NULL的话，就代表上面分配内存失败
	L->next=NULL;//头结点之后暂时还没有结点
	return true;
}

3.链表的建立：给了很多数据元素 (1)尾插法

TailInsert：初始化单链表，length记录链表长度
while 循环{
  每次取一个数据元素e;
  利用length，在指定位置后插元素;
  length++;
}

(2)头插法

HeadInsert：初始化单链表
while 循环{
  每次取一个数据元素e;
  每次在头结点后插元素e;
}

4.求表的长度

int Length(LinkList L){
	int len=0;//该变量统计表长
	LNode p=L;//扫描链表的过程变量，初始值是头结点
	//头->1->2->3->NULL
	while(p->next!=NULL){//最后一个结点->next=NULL
		p=p->next;//p=1，2，3
		len++;//1个，2个，3个
	}
	return len;
}

5.判断单链表是否为空

bool Empty(LinkList L){
	return L->next==NULL;
}

6.查 (1)按位查找：找到第i个位置的元素

LNode GetElem(LinkList L,int i){
	if(i<1)return false;//i超出范围
	LNode p=L;int j=0;//p指向当前扫描到的结点,p初始指向头结点；j指第几个结点；过程变量
	while(p!=NULL&&j//p没有扫描到最后一个元素（这样所求i就是过界）并且会扫描到i位置前一个元素
		p=p->next;//p扫描链表不断往后，最后会指向第i个位置
		j++;
	}
	return p;//第i个位置
}

(2)按值查找

LNode LocateElem(LinkList L,int e){
	LNode p=L->next;//从第一个结点开始
	while(p!=NULL&&p->data!=e)//p没有扫描到最后一个元素（这样所求i就是过界）并且扫描过的元素值不是e
		p=p->next;//继续往下扫描
	return p;//会在=NULL时或者=e时退出循环
}

7.增 (1)在指定结点前插元素

bool InsertPrior(LNode p,int 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->p的后继
	s->data=p->data;p->data=e;//将p的数据存进s中，让p代替s做那个前插元素
	return true;
}

(2)在指定结点后插元素

bool InsertNext(LNode p,int 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;//p->s->p的后继
	return true;//插入成功
}

(3)在指定位置处插入元素，返回是否插入成功（链表的下标=位置，因为有头结点）

bool ListInsert(LinkList L,int i,int e){//顺序表L,位置i，元素e
	LNode p=GetElem(L,i-1);//找到第i-1个结点
	//if(i<1)return false;//位置超过范围
	//LNode p=L;int j=0;//p指向当前扫描到的结点,p初始指向头结点；j指第几个结点；过程变量
	//while(p!=NULL&&jnext;//p扫描链表不断往后，最后会指向第i-1个位置
		//j++;
	//}
	retrun InsertNext(LNode p,int e);//下面五行代码就代表后插：在i-1位置元素后插元素成为第i个
	//if(p==NULL)return false;//位置i超过范围
	//LNode s=(LNode)malloc(sizeof(LNode));//给新结点分配内存空间
	//s->data=e;
	//s->next=p->next;p->next=s;//第i-1个元素->s->第i个元素
	//return true;//插入成功
}

8.删 (1)指定结点的删除

bool Delete(LNode p){
	if(p==null)return false;//代码健壮性
	LNode q=p->next;//过程变量=p的后继
	p->data=q->data;p->next=q->next;//把p的后继前移到p，那么就是删除p
	free(q);//释放过程变量的空间
	return true;
}

(2)删除指定位置的元素，返回删除的元素

bool ListDelete(LinkList L,int i){//顺序表L,位置i
	LNode p=GetElem(L,i-1);//找到第i-1个结点
	//if(i<1)return false;
	//LNode p=L;int j=0;//p指向当前扫描到的结点,p初始指向头结点；j指第几个结点；过程变量
	//while(p!=NULL&&jnext;//p扫描链表不断往后，最后会指向第i-1个位置
		//j++;
	//}
	if(p==NULL||p->next==NULL)return false;//i-1上面没判断，i要删除不能是NULL
	LNode q=p->next;//q=i的位置
	int e=q->data;//返回删除元素的值
	p->next=q->next;//i-1->i+1
	free(q);//释放结点的存储空间
	return e;//返回删除元素的值
}

二.双链表

概念：可以逆向检索

1.双链表的定义

typedef struct DNode{
  int data;//数据域
  struct DNode prior,next;//前驱指针和后继指针
}DNode,Dlinklist;

2.双链表的初始化：创建头结点

bool InitDLinkList(DlinkList L){
  L=(DNode) malloc(sizeof(DNode));//头结点分配空间
  if(L==NULL) return false;//没分配成功
  L->prior=NULL;L->next=NULL;
  return true;
}

3.判断双链表是否为空

bool Empty{
   if(L->next==NULL)return true
   else return false;
}

4.双链表的遍历

//后向遍历
while(p!=NULL){
	p->next;
}
//前向遍历
while(p!=NULL){
	p->prior;
}

5.增：往指定结点p后插元素s

bool InsertNextDNode(DNodep,DNode s){
  if(P=NULL||s==NULL)return false;//非法参数
  s->next=p->next;//s->q
  if(p->next!=NULL)//如果p是最后一个元素，那么q=NULL没有前驱
    p->next->prior=s;//q->s
  s->prior=p;//s->p
  p->next=s;//p->s
  return true;
}

6.删 (1)删除p结点后继结点q

bool DeleteNextNode(DNode p){
	if(p==NULL)return false;//非法参数：没有p，那就不用删了
	DNode q=p->next;//q是p的后继
	if(q==NULL)return false;//非法参数：没有q，那就不用删了
	p->next=q->next;//p->s，跳过q
	if(q->next!=NULL)q->next->prior=p;//有s：s->p
	free(q);
	return true;
}

(2)删除双链表

void DestroyList(DLinkList L){
	while(L->next!=NULL)//从头结点开始逐渐往后循环删除元素
		DeleteNextDNode(L);
	free(L);//释放链表空间
	L=NULL;
}

三.循环链表 1.循环单链表

概念：表尾指针的next指针指向头结点，从任何一个结点出发可以找到其他结点

(1)单链表的定义 (2)循环单链表的初始化

bool InitList(LinkList L){
	L=(LNode) malloc(sizeof(LNode));//给定义好的单链表分配一个头结点空间
	if(L==NULL)return false;//L还等于NULL的话，就代表上面分配内存失败
	L->next=L;//头结点的next指向头结点
	return true;
}

(3)判断循环单链表是否为空

bool Empty(LinkList L){
	if(L->next==L)return true;//头->头
	else return false;
}

(4)判断该结点是否是循环单链表的表尾结点

bool isTail(LinkList L,LNode p){
	if(p->next==L)return true;//最后一个结点指向头结点
	else return false;
}

2.循环双链表

概念：表头prior指向表尾，表尾next指向表头

(1)双链表的定义 (2)循环双链表的初始化

bool InitDLinkList(DLinkList L){
	L=(DNode) malloc(sizeof(DNode));//给定义好的双链表分配一个头结点空间
	if(L==NULL)return false;//L还等于NULL的话，就代表上面分配内存失败
	L->prior=L;L->next=L;//头结点的prior指向头结点，头结点的next指向头结点
	return true;
}

(3)判断循环双链表是否为空

bool Empty(DLinklist L){
	if(L->next==L)return true;//和刚初始化没差别
	else return false;
}

(4)判断某结点是否是循环双链表的表尾结点

bool isTail(DLinkList L,DNode p){//循环双链表L，双链表结点p
	if(p->next==L)return true;//如果该结点的后继是头结点的话
	else return false;
}

四.静态链表

概念：分配一整片连续的内存空间

1.静态链表的定义

第一个结点是头结点[0]，next=-1的结点是末尾结点，next=-2的结点是空闲结点

#define MaxSize 10//定义常量：静态链表的最大长度
//struct Node{//静态链表结点的类型
	//int data;//数据域
	//int next;//下个元素的数组下标
//}
typedef struct{
	int data;
	int next;
}SLinkList[MaxSize];
void main(){
	//struct Node arr[MaxSize];//struct Node类型的数组
	SLinkList a;
}

线性表-链式存储

C/C++/C#相关栏目本月热门文章