数据结构C代码汇总【1-线性表】

along the way7

838人浏览 · 2025-05-02 16:07:04

along the way7 · 2025-05-02 16:07:04 发布

下面直接往下看源代码及注释即可，注意，每一种数据结构都是按照数据结构定义+基本运算算法代码实现汇总在一起（包含常见算法的代码实现），这样在回顾数据结构的同时，掌握基本运算算法的代码实现，掌握住这些基础算法，就不用担心考研题目没思路了！

一、线性表

1、顺序表

//顺序表运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef char ElemType; 
typedef struct 
{	ElemType data[MaxSize];		//存放顺序表元素
   	int length;					//存放顺序表的长度
} SqList;						//声明顺序表的类型
void CreateList(SqList *&L,ElemType a[],int n) //整体建立顺序表
{
	L=(SqList *)malloc(sizeof(SqList));
	for (int i=0;i<n;i++)
		L->data[i]=a[i];
	L->length=n;
}
void InitList(SqList *&L)	//初始化线性表
{
	L=(SqList *)malloc(sizeof(SqList));	//分配存放线性表的空间
	L->length=0;
}
void DestroyList(SqList *&L)  //销毁线性表
{
	free(L);
}
bool ListEmpty(SqList *L)	//判线性表是否为空表
{
	return(L->length==0);
}
int ListLength(SqList *L)	//求线性表的长度
{
	return(L->length);
}
void DispList(SqList *L)	//输出线性表
{
	for (int i=0;i<L->length;i++)
		printf("%c ",L->data[i]); //若是int类型，就改为%d即可，注意细节
	printf("\n");
}
bool GetElem(SqList *L,int i,ElemType &e)	//求线性表中第i个元素值
{
	if (i<1 || i>L->length)
		return false;
	e=L->data[i-1];
	return true;
}
int LocateElem(SqList *L, ElemType e)	//查找第一个值域为e的元素序号
{
	int i=0;
	while (i<L->length && L->data[i]!=e) i++;
	if (i>=L->length)
		return 0;
	else
		return i+1;
}
bool ListInsert(SqList *&L,int i,ElemType e)	//插入第i个元素
{
	int j;
	if (i<1 || i>L->length+1)
		return false;
	i--;						//将顺序表位序转化为elem下标
	for (j=L->length;j>i;j--) 	//将data[i]及后面元素后移一个位置
		L->data[j]=L->data[j-1];
	L->data[i]=e;
	L->length++;				//顺序表长度增1
	return true;
}
bool ListDelete(SqList *&L,int i,ElemType &e)	//删除第i个元素
{
	int j;
	if (i<1 || i>L->length)
		return false;
	i--;						//将顺序表位序转化为elem下标
	e=L->data[i];
	for (j=i;j<L->length-1;j++)	//将data[i]之后的元素前移一个位置
		L->data[j]=L->data[j+1];
	L->length--;				//顺序表长度减1
	return true;
}

2、单链表

//单链表运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode 
{
	ElemType data;
	struct LNode *next;		//指向后继结点
} LinkNode;		 			//单链表结点类型
void CreateListF(LinkNode *&L,ElemType a[],int n)
//头插法建立单链表
{
	LinkNode *s;
	L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
	L->next=NULL;
	for (int i=0;i<n;i++)
	{	
		s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
		s->data=a[i];
		s->next=L->next;			//将结点s插在原开始结点之前,头结点之后
		L->next=s;
	}
}
void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立单链表
{
	LinkNode *s,*r;
	L=(LinkNode *)malloc(sizeof(LinkNode));  	//创建头结点
	L->next=NULL;
	r=L;						//r始终指向尾结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
		s->data=a[i];
		r->next=s;				//将结点s插入r结点之后
		r=s;
	}
	r->next=NULL;				//尾结点next域置为NULL
}
void InitList(LinkNode *&L)		//初始化线性表
{
	L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
	L->next=NULL;				//单链表置为空表
}
void DestroyList(LinkNode *&L)	//销毁线性表
{
	LinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{	free(pre);
		pre=p;					//pre、p同步后移一个结点					
		p=pre->next;
	}
	free(pre);					//此时p为NULL,pre指向尾结点,释放它
}
bool ListEmpty(LinkNode *L)		//判线性表是否为空表
{
	return(L->next==NULL);
}
int ListLength(LinkNode *L)		//求线性表的长度
{	int i=0;
	LinkNode *p=L;				//p指向头结点,n置为0(即头结点的序号为0)
	while (p->next!=NULL)
	{	i++;
		p=p->next;
	}
	return(i);					//循环结束,p指向尾结点,其序号i为结点个数
}

void DispList(LinkNode *L)	//输出线性表
{	LinkNode *p=L->next;	//p指向首结点
	while (p!=NULL)			//p不为NULL,输出p结点的data域
	{	printf("%c ",p->data); //若是int类型，改为%d即可，注意细节
		p=p->next;			//p移向下一个结点
	}
	printf("\n");
}

bool GetElem(LinkNode *L,int i,ElemType &e)	//求线性表中第i个元素值
{	int j=0;
	if (i<=0) return false;		//i错误返回假
	LinkNode *p=L;				//p指向头结点,j置为0(即头结点的序号为0)
	while (j<i && p!=NULL)		//找第i个结点p
	{	j++;
		p=p->next;
	}
	if (p==NULL)				//不存在第i个数据结点,返回false
		return false;
	else						//存在第i个数据结点,返回true
	{	e=p->data;
		return true;
	}
}

int LocateElem(LinkNode *L,ElemType e)	//查找第一个值域为e的元素序号
{	int i=1;
	LinkNode *p=L->next;			//p指向首结点,i置为1(即首结点的序号为1)
	while (p!=NULL && p->data!=e)	//查找data值为e的结点,其序号为i
	{	p=p->next;
		i++;
	}
	if (p==NULL)					//不存在值为e的结点,返回0
		return(0);
	else							//存在值为e的结点,返回其逻辑序号i
		return(i);
}

bool ListInsert(LinkNode *&L,int i,ElemType e)	//插入第i个元素
{	int j=0;
	if (i<=0) return false;		//i错误返回假
	LinkNode *p=L,*s;			//p指向头结点,j置为0(即头结点的序号为0)
	while (j<i-1 && p!=NULL)	//查找第i-1个结点p
	{	j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点,返回false
		return false;
	else						//找到第i-1个结点p,插入新结点并返回true
	{	s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=e;				//创建新结点s,其data域置为e
		s->next=p->next;		//将结点s插入到结点p之后
		p->next=s;
		return true;
	}
}

bool ListDelete(LinkNode *&L,int i,ElemType &e)	//删除第i个元素
{	int j=0;
	if (i<=0) return false;		//i错误返回假
	LinkNode *p=L,*q;			//p指向头结点,j置为0(即头结点的序号为0)
	while (j<i-1 && p!=NULL)	//查找第i-1个结点
	{	j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点,返回false
		return false;
	else						//找到第i-1个结点p
	{	q=p->next;				//q指向第i个结点
		if (q==NULL)			//若不存在第i个结点,返回false
			return false;
		e=q->data;
		p->next=q->next;		//从单链表中删除q结点
		free(q);				//释放q结点
		return true;			//返回true表示成功删除第i个结点
	}
}

3、循环单链表

//循环单链表运算算法
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode		//定义单链表结点类型
{
	ElemType data;
    struct LNode *next;
} LinkNode;
void CreateListF(LinkNode *&L,ElemType a[],int n) //头插法建立循环单链表
{
	LinkNode *s;int i;
	L=(LinkNode *)malloc(sizeof(LinkNode));  	//创建头结点
	L->next=NULL;
	for (i=0;i<n;i++)
	{	
		s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
		s->data=a[i];
		s->next=L->next;			//将结点s插在原开始结点之前,头结点之后
		L->next=s;
	}
	s=L->next;	
	while (s->next!=NULL)			//查找尾结点,由s指向它
		s=s->next;
	s->next=L;						//尾结点next域指向头结点

}
void CreateListR(LinkNode *&L,ElemType a[],int n) //尾插法建立循环单链表
{
	LinkNode *s,*r;int i;
	L=(LinkNode *)malloc(sizeof(LinkNode));  	//创建头结点
	L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (i=0;i<n;i++)
	{	
		s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点
		s->data=a[i];
		r->next=s;			//将结点s插入结点r之后
		r=s;
	}
	r->next=L;				//尾结点next域指向头结点
}
void InitList(LinkNode *&L)	//初始化线性表
{
	L=(LinkNode *)malloc(sizeof(LinkNode));	//创建头结点
	L->next=L;
}
void DestroyList(LinkNode *&L)	//销毁线性表
{
	LinkNode *pre=L,*p=pre->next;
	while (p!=L)
	{
		free(pre);
		pre=p;					//pre、p同步后移一个结点
		p=pre->next;
	}
	free(pre);					//此时p=L,pre指向尾结点,释放它
}
bool ListEmpty(LinkNode *L)		//判线性表是否为空表
{
	return(L->next==L);
}
int ListLength(LinkNode *L)		//求线性表的长度
{
	LinkNode *p=L;int i=0;		//p指向头结点,n置为0(即头结点的序号为0)
	while (p->next!=L)
	{
		i++;
		p=p->next;
	}
	return(i);					//循环结束,p指向尾结点,其序号n为结点个数
}
void DispList(LinkNode *L)		//输出线性表
{
	LinkNode *p=L->next;
	while (p!=L)				//p不为L,输出p结点的data域
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
bool GetElem(LinkNode *L,int i,ElemType &e)	//求线性表中第i个元素值
{	int j=1;
	LinkNode *p=L->next;
	if (i<=0 || L->next==L)		//i错误或者空表返回假
		return false;
	if (i==1)					//求第1个结点值，作为特殊情况处理
	{
		e=L->next->data;
		return true;
	}
	else						//i不为1时
	{
		while (j<=i-1 && p!=L)	//找第i个结点p
		{
			j++;
			p=p->next;
		}
		if (p==L)				//没有找到返回假
			return false;
		else					//找到了提取它的值并返回整
		{				
			e=p->data;
			return true;
		}
	}
}

int LocateElem(LinkNode *L,ElemType e)  //查找第一个值域为e的元素序号
{
	LinkNode *p=L->next;
	int i=1;
	while (p!=L && p->data!=e)	//查找第一个值域为e的结点p
	{
		p=p->next;
		i++;					//i对应结点p的序号
	}
	if (p==L)
		return(0);				//没有找到返回0
	else
		return(i);				//找到了返回其序号
}
bool ListInsert(LinkNode *&L,int i,ElemType e)	//插入第i个元素
{
	int j=1;
	LinkNode *p=L,*s;
	if (i<=0) return false;		//i错误返回假
	if (p->next==L || i==1)		//原单链表为空表或i=1作为特殊情况处理
	{
		s=(LinkNode *)malloc(sizeof(LinkNode));	//创建新结点s
		s->data=e;								
		s->next=p->next;		//将结点s插入到结点p之后
		p->next=s;
		return true;
	}
	else
	{
		p=L->next;
		while (j<=i-2 && p!=L)	//找第i-1个结点p
		{
			j++;
			p=p->next;
		}
		if (p==L)				//未找到第i-1个结点
			return false;
		else					//找到第i-1个结点p
		{
			s=(LinkNode *)malloc(sizeof(LinkNode));	//创建新结点s
			s->data=e;								
			s->next=p->next;						//将结点s插入到结点p之后
			p->next=s;
			return true;
		}
	}
}
bool ListDelete(LinkNode *&L,int i,ElemType &e)	//删除第i个元素
{
	int j=1;
	LinkNode *p=L,*q;
	if (i<=0 || L->next==L) 
		return false;			//i错误或者空表返回假
	if (i==1)					//i=1作为特殊情况处理
	{
		q=L->next;				//删除第1个结点
		e=q->data;
		L->next=q->next;
		free(q);
		return true;
	}
	else						//i不为1时
	{
		p=L->next;
		while (j<=i-2 && p!=L)	//找第i-1个结点p
		{
			j++;
			p=p->next;
		}
		if (p==L)				//未找到第i-1个结点
			return false;
		else					//找到第i-1个结点p
		{
			q=p->next;			//q指向要删除的结点
			e=q->data;
			p->next=q->next;	//从单链表中删除q结点
			free(q);			//释放q结点
			return true;
		}
	}
}

4、双链表

//双链表运算算法
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct DNode
{
	ElemType data;
	struct DNode *prior;	//指向前驱结点
	struct DNode *next;		//指向后继结点
} DLinkNode;				//声明双链表结点类型
void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建双链表
{
	DLinkNode *s;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		s->next=L->next;			//将结点s插在原开始结点之前,头结点之后
		if (L->next!=NULL) L->next->prior=s;
		L->next=s;s->prior=L;
	}
}
void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建双链表
{
	DLinkNode *s,*r;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		r->next=s;s->prior=r;	//将结点s插入结点r之后
		r=s;
	}
	r->next=NULL;				//尾结点next域置为NULL
}
void InitList(DLinkNode *&L)	//初始化线性表
{
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
}
void DestroyList(DLinkNode *&L)	//销毁线性表
{
	DLinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{
		free(pre);
		pre=p;					//pre、p同步后移一个结点
		p=pre->next;
	}
	free(p);
}
bool ListEmpty(DLinkNode *L)	//判线性表是否为空表
{
	return(L->next==NULL);
}
int ListLength(DLinkNode *L)	//求线性表的长度
{
	DLinkNode *p=L;
	int i=0;					//p指向头结点,i设置为0
	while (p->next!=NULL)		//找尾结点p
	{
		i++;					//i对应结点p的序号
		p=p->next;
	}
	return(i);
}
void DispList(DLinkNode *L)		//输出线性表
{
	DLinkNode *p=L->next;
	while (p!=NULL)
	{
		printf("%c ",p->data);
		p=p->next;
	}
	printf("\n");
}
bool GetElem(DLinkNode *L,int i,ElemType &e)	//求线性表中第i个元素值
{
	int j=0;
	DLinkNode *p=L;
	if (i<=0) return false;		//i错误返回假
	while (j<i && p!=NULL)		//查找第i个结点p
	{
		j++;
		p=p->next;
	}
	if (p==NULL)				//没有找到返回假			
		return false;
	else						//找到了提取值并返回真
	{
		e=p->data;
		return true;
	}
}
int LocateElem(DLinkNode *L,ElemType e)	//查找第一个值域为e的元素序号
{
	int i=1;
	DLinkNode *p=L->next;
	while (p!=NULL && p->data!=e)	//查找第一个值域为e的结点p
	{
		i++;						//i对应结点p的序号
		p=p->next;
	}
	if (p==NULL)					//没有找到返回0
		return(0);
	else							//找到了返回其序号
		return(i);
}
bool ListInsert(DLinkNode *&L,int i,ElemType e)	//插入第i个元素
{
	int j=0;
	DLinkNode *p=L,*s;			//p指向头结点,j设置为0
	if (i<=0) return false;		//i错误返回假
	while (j<i-1 && p!=NULL)	//查找第i-1个结点p
	{
		j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个结点p
	{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建新结点s
		s->data=e;	
		s->next=p->next;		//将结点s插入到结点p之后
		if (p->next!=NULL) 
			p->next->prior=s;
		s->prior=p;
		p->next=s;
		return true;
	}
}
bool ListDelete(DLinkNode *&L,int i,ElemType &e)  //删除第i个元素
{	int j=0;
	DLinkNode *p=L,*q;			//p指向头结点,j设置为0
	if (i<=0) return false;		//i错误返回假
	while (j<i-1 && p!=NULL)	//查找第i-1个结点p
	{	j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个节p
	{	q=p->next;				//q指向第i个结点
		if (q==NULL)			//当不存在第i个结点时返回false
			return false;
		e=q->data;
		p->next=q->next;		//从双链表中删除结点q
		if (p->next!=NULL)		//若p结点存在后继结点,修改其前驱指针
			p->next->prior=p;
		free(q);				//释放q结点
		return true;
	}
}

5、循环双链表

//循环双链表运算算法
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct DNode		//定义双链表结点类型
{
	ElemType data;
	struct DNode *prior;	//指向前驱结点
	struct DNode *next;		//指向后继结点
} DLinkNode;
void CreateListF(DLinkNode *&L,ElemType a[],int n) //头插法建立循环双链表
{
	DLinkNode *s;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->next=NULL;
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		s->next=L->next;			//将结点s插在原开始结点之前,头结点之后
		if (L->next!=NULL) L->next->prior=s;
		L->next=s;s->prior=L;
	}
	s=L->next;	
	while (s->next!=NULL)			//查找尾结点,由s指向它
		s=s->next;
	s->next=L;						//尾结点next域指向头结点
	L->prior=s;						//头结点的prior域指向尾结点

}
void CreateListR(DLinkNode *&L,ElemType a[],int n) //尾插法建立循环双链表
{
	DLinkNode *s,*r;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  //创建头结点
	L->next=NULL;
	r=L;					//r始终指向尾结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		r->next=s;s->prior=r;	//将结点s插入结点r之后
		r=s;
	}
	r->next=L;				//尾结点next域指向头结点
	L->prior=r;				//头结点的prior域指向尾结点
}
void InitList(DLinkNode *&L)	//初始化线性表
{
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=L;
}
void DestroyList(DLinkNode *&L)	//销毁线性表
{
	DLinkNode *pre=L,*p=pre->next;
	while (p!=L)
	{
		free(pre);
		pre=p;			//pre、p同步后移一个结点
		p=pre->next;
	}
	free(pre);			//此时p=L,pre指向尾结点,释放它
}
bool ListEmpty(DLinkNode *L)	//判线性表是否为空表
{
	return(L->next==L);
}
int ListLength(DLinkNode *L)	//求线性表的长度
{
	DLinkNode *p=L;
	int i=0;
	while (p->next!=L)
	{
		i++;
		p=p->next;
	}
	return(i);				//循环结束,p指向尾结点,其序号i为结点个数
}
void DispList(DLinkNode *L)	//输出线性表
{
	DLinkNode *p=L->next;
	while (p!=L)
	{
		printf("%c ",p->data);
		p=p->next;
	}
	printf("\n");
}
bool GetElem(DLinkNode *L,int i,ElemType &e)	//求线性表中第i个元素值
{
	int j=1;
	DLinkNode *p=L->next;
	if (i<=0 || L->next==L) 
		return false;			//i错误或者L为空表返回假
	if (i==1)					//i=1作为特殊情况处理
	{
		e=L->next->data;
		return true;
	}
	else						//i不为1时
	{
		while (j<=i-1 && p!=L)	//查找第i个结点p
		{
			j++;
			p=p->next;
		}
		if (p==L)				//没有找到第i个节，返回假
			return false;
		else					//找到了第i个节，返回真
		{
			e=p->data;
			return true;
		}
	}
}
int LocateElem(DLinkNode *L,ElemType e)	//查找第一个值域为e的元素序号
{
	int i=1;
	DLinkNode *p=L->next;
	while (p!=NULL && p->data!=e)
	{
		i++;
		p=p->next;
	}
	if (p==NULL)			//不存在值为e的结点,返回0
		return(0);
	else					//存在值为e的结点,返回其逻辑序号i
		return(i);
}
bool ListInsert(DLinkNode *&L,int i,ElemType e)	//插入第i个元素
{
	int j=1;
	DLinkNode *p=L,*s;
	if (i<=0) return false;				//i错误返回假
	if (p->next==L)						//原双链表为空表时
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建新结点s
		s->data=e;
		p->next=s;s->next=p;
		p->prior=s;s->prior=p;
		return true;
	}
	else if (i==1)						//L不为空，i=1作为特殊情况处理
	{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建新结点s
		s->data=e;
		s->next=p->next;p->next=s;		//将结点s插入到结点p之后
		s->next->prior=s;s->prior=p;
		return true;
	}
	else								//i不为1时
	{	
		p=L->next;
		while (j<=i-2 && p!=L)			//查找第i-1个结点p
		{	j++;
			p=p->next;
		}
		if (p==L)						//未找到第i-1个结点
			return false;
		else							//找到第i-1个结点*p
		{
			s=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建新结点s
			s->data=e;	
			s->next=p->next;			//将结点s插入到结点p之后
			if (p->next!=NULL) p->next->prior=s;
			s->prior=p;
			p->next=s;
			return true;
		}
	}
}
bool ListDelete(DLinkNode *&L,int i,ElemType &e) //删除第i个元素
{
	int j=1;
	DLinkNode *p=L,*q;
	if (i<=0 || L->next==L) 
		return false;				//i错误或者为空表返回假
	if (i==1)						//i==1作为特殊情况处理
	{
		q=L->next;					//删除第1个结点
		e=q->data;
		L->next=q->next;
		q->next->prior=L;
		free(q);
		return true;
	}
	else							//i不为1时
	{	
		p=L->next;
		while (j<=i-2 && p!=NULL)	//查找到第i-1个结点p	
		{
			j++;
			p=p->next;
		}
		if (p==NULL)				//未找到第i-1个结点
			return false;
		else						//找到第i-1个结点p
		{
			q=p->next;				//q指向要删除的结点
			if (q==NULL) return 0;	//不存在第i个结点
			e=q->data;
			p->next=q->next;		//从单链表中删除q结点
			if (p->next!=NULL) p->next->prior=p;
			free(q);				//释放q结点
			return true;
		}
	}
}

6、一些常见算法的代码实现

【1】删除[x,y]区间内的值

#include "sqlist_int.cpp" 
  
//一种更高效的算法删除[x,y]区间内的值（即把不在此区间内的值放在一个新建的顺序表中） 
void fun(SqList *&L,ElemType x,ElemType y) 
{ int k=0;   //新建的顺序表的下标变量 
  for (int i=0;i<L->length;i++)
 	if (!(L->data[i]>=x && L->data[i]<=y))
	      L->data[k++]=L->data[i]; 
  L->length=k;
}

int main()
{
	SqList *L;
	ElemType a[]={-1,-9,0,8,-7,11,5,-6};
	CreateList(L,a,8);
	printf("L:");DispList(L);
	printf("执行删除运算\n");
	fun(L,-6,5);
	printf("L:");DispList(L);
	DestroyList(L);
	return 1;
}

→代码执行结果如下：

【2】使顺序表内所有小于0的值移到大于或等于0的值前面

#include "sqlist.cpp" 

//用高效的算法使顺序表内所有小于0的值移到大于或等于0的值前面  
void move2(SqList *&L)  //快速排序的思想 
{	int i=0,j=L->length-1;
	ElemType pivot=L->data[0];	//以data[0]为基准
	while (i<j)  				//从顺序表两端交替向中间扫描,直至i=j为止
	{	while (j>i && L->data[j]>=0)
			j--;				//从右向左扫描,找一个小于等于pivot的data[j]
		L->data[i]=L->data[j];	//找到这样的data[j],放入data[i]处
		while (i<j && L->data[i]<0)
			i++;				//从左向右扫描,找一个大于pivot的记录data[i]
		L->data[j]=L->data[i];	//找到这样的data[i],放入data[j]处
	}
	L->data[i]=pivot;  //最后将基准归位 
}

int main()
{
	SqList *L;
	ElemType a[]={-1,-9,0,8,-7,0,5,-6};
	CreateList(L,a,8);
	printf("L:");DispList(L);
	printf("执行移动运算\n");
	move2(L);
	printf("L:");DispList(L);
	DestroyList(L);
	return 1;
}

【3】找到下标为n/2的元素

#include "linklist.cpp"

//找到下标为n/2的元素 
ElemType Midnode(LinkNode *L) //此算法采用双指针法，通过移动不同的步数最终找到中间的元素位置 
{ LinkNode *q,*p;
for (q=p=L->next; p->next!=NULL && p->next->next!=NULL; q=q->next,p=p->next->next)
    ;
return q->data;
} 
     
int main()
{
	LinkNode *L;
	ElemType a[]="12345678";
	int n=(sizeof(a)-1)/sizeof(ElemType);  
	CreateListR(L,a,n);	//创建表 
    printf("输出顺序表L:\n");
    DispList(L);  
	printf("中间元素为：%c\n", Midnode(L));  
	DestroyList(L);
	return 1;
}

【4】循环单链表实现两个单链表的合并

#include "clinklist.cpp"

//循环单链表实现两个单链表的合并 
void Merge(LinkNode *ha, LinkNode *hb, LinkNode *&hc) 
{ 	LinkNode *p;
	hc=ha;
	for (p=ha;p->next!=ha;p=p->next) 					
		;  //找到ha的尾结点p
	p->next=hb->next; //将结点p的next指向hb的首结点
	for ( ;p->next!=hb;p=p->next) 
		;  //找到hb的尾结点p
	p->next=hc; //构成循环单链表
	free(hb); //释放hb单链表的头结点
}
int main()
{
	LinkNode *ha,*hb,*hc;
	ElemType a[]={1,2,3,4,5},b[]={6,7,8,9,10};
	int n=5;
	CreateListR(ha,a,n);
	CreateListR(hb,b,n);
	printf("ha:");DispList(ha);
	printf("hb:");DispList(hb);
	Merge(ha,hb,hc);
    printf("hc:");DispList(hc);
	printf("\n释放链表hc。");
	DestroyList(hc);
	return 1;
}

【5】将L中所有数据结点按x进行划分，尾插法新建L表

#include "linklist.cpp"				//包含单链表的基本运算算法

void Split(LinkNode *&L,ElemType x)	//将L中所有数据结点按x进行划分，尾插法新建L表 
{
	LinkNode *p=L->next,*t,*r;
	L->next=NULL;				//L变为空链表
	r=L;
	while (p!=NULL)  //等价于while (p)
	{
		if (p->data<x)			//若p结点值小于x，将其插入在开头
		{
			t=p->next; //t帮p临时站岗
			p->next=L->next;//将结点p插入到L的开头 
			L->next=p;
			if (p->next==NULL)	//若p结点是第一个在开头插入的结点
				r=p;			//则它是尾结点
			p=t;    //t还给p
		}
		else					//若p结点值大于或等于x，将其插入到末尾
		{
			r->next=p;
			r=p;
			p=p->next;
		}
	}
	r->next=NULL;
}
int main()
{
	LinkNode *L;
	ElemType a[]="adbacbchfdeg";
	int n=(sizeof(a)-1)/sizeof(ElemType); 
	CreateListR(L,a,n);
	printf("L："); DispList(L);
	ElemType x='d';
	printf("以%c进行划分\n",x);
	Split(L,x);
	printf("L："); DispList(L);
	DestroyList(L);
	return 1;
}