C语言数据结构--线性表常用操作代码合集_数据结构线性表c语言代码

概述

为方便调试，接下来的代码中,ElemType类型只用 int类型来表示，大家可根据需要来进行替换。

一、顺序表

1.1顺序表初始化

（1）静态分配初始化

#include<stdio.h>
# define MaxSize 10
typedef struct{
	int data[MaxSize];            
	int length;
}SqList; 
 
void InitList(SqList &L)
{
	L.length = 0;
 } 

（2）动态分配初始化

 #include<stdio.h> 
#include<stdlib.h>
#define InitSize 10   //初始表长 
typedef struct{
	int *data;        //指示动态分配数组的指针 
	int length;       //数组当前长度 
	int MaxSize;      //数组最大容量 
}SeqList;             //动态分配数组顺序表的定义 
 
void InitList(SeqList &L)
{
	L.data =(int *)malloc(sizeof(int)*InitSize);  //分配存储空间 
	L.length = 0;                                 //初始长度为0 
	L.MaxSize = InitSize;                         //最大容量暂定为初始容量 
 } 

1.2顺序表的创建

 void CreateList(SqList &L)
 {
 	int x = 0;
 	int i = 0;
 	scanf("%d",&x);              
 	while(x!=9999)         //输入9999停止输入
 	{
 		L.data[i]=x;
 		i++;
 		L.length++;
 		scanf("%d",&x);
	 }
 }

1.3插入操作

在顺序表的第i个位置插入新元素e

bool ListInsert(SqList &L,int i,int e)
{
	if(i<1 || i>L.length+1)        //判断i的范围是否有效 
	   return false;
	if(L.length >= MaxSize)        //判断空间是否已满 
	   return false;
	int j = 0;
	for(j=L.length;j>=i;j--)       //将第i个元素及之后的元素后移 
	{
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;                //在第i个位置放入e 
	L.length++;                   //线性表长度加1 
	return true;
}

1.4删除操作

bool ListDelete(SqList &L,int i,int &e)
{
	if(i<1 || i>L.length)
	  return false;
	int j = 0;
	e=L.data[i-1];             //将被删除的元素赋给e 
	for(j=i;j<L.length;j++)     //将第i个位置处的元素前移 
	{
		L.data[j-1]=L.data[j];
	}
	L.length--;                //线性表长度减一 
	return true;
 } 

1.5按值查找

按值查找：在顺序表L中查找第一个元素值等于e的元素，并返回其位序。

 int LocateElem(SqList L,int e)
 {
 	int i = 0;
 	for(i=0;i<L.length;i++)
 	{
 		if(L.data[i]==e)
 		  return i+1;       //下标为i的元素值等于e，返回其位序i+1 
	 }
	 return 0;       //退出循环，说明查找失败 
  } 

1.6按位查找

 int GetElem(SqList L,int i)
  {
  	return L.data[i-1];    //返回第i个位置的元素值 
   } 

1.7输出操作

void PrintList(SqList L)
{
	int i = 0;
 	for(i=0;i<L.length ;i++)
 	{
 		printf("%d ",L.data[i]);
	 }
 } 

 二、单链表

2.1单链表结点类型及初始化

（1）带头结点

#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));  //创建头结点 
	L->next = NULL;   //此处亦可写为 （*L）.next = NULL ,头结点之后暂无元素结点 
	return true;
}

（2）不带头结点

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
 
 
bool InitList(LinkList &L)
{
	L=NULL;
	return true;
}

2.2求表长

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

2.3按序号查找结点

LNode* GetElem(LinkList L,int i)
{
	LNode *p = L;              //p指向当前扫描到的结点 
	int j = 0;                 //头结点是第0个结点 
	while(p!=NULL && j<i)      //循环找到第i个结点 
	{
		p=p->next ;
		j++;
	}
	return p;               //返回第i个结点的指针或NULL 
}

2.4按值查找结点

LNode * LocateElem(LinkList L,int e)
{
	LNode *p = L->next ;
	while(p!=NULL&&p->data!=e)
	{
		p=p->next;
	}
	return p;
 } 

2.5插入结点操作

在第i个结点处插入元素e,先找到第i-1个结点，再在其后插入

bool ListInsert(LinkList &L,int i, int e)
{
	LNode *p=L;
	int j = 0;
	while(p!=NULL && j<i-1)
	{
		p=p->next ;
		j++;
	}
	if(p==NULL)         //i值不合法 
	  return false;
	  
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data =e;
	s->next =p->next ;
	p->next = s;
	return true; 
}

2.6删除结点操作

删除第i个结点，并用e返回删除结点的值

bool ListDelete(LinkList &L,int i,int &e)
{
	LNode *p=L;
	int j = 0;
	while(p!=NULL&&j<i-1)       //循环找到第i-1个结点 
	{
		p=p->next ;
		j++;
	}
	if(p==NULL ||p->next == NULL)     //i值不合法 
	  return false;
	  
	LNode *q=p->next ;             //令q 指向被删除结点 
	e=q->data ;                    //用e存储被删除结点的值 
	p->next = q->next ;             
	free(q);                       //释放结点存储空间 
	return true;
}

2.7头插法建立单链表

LinkList List_HeadInsert(LinkList &L)
{
	LNode *s;
	int x = 0;
	L=(LNode*)malloc(sizeof(LNode));      //创建头结点
	L->next=NULL;                         //初始为空链表 
	scanf("%d",&x);
	while(x!=9999)                        //输入9999表示结束 
	{
		s=(LNode*)malloc(sizeof(LNode));   //创建新结点 
		s->data = x; 
		s->next =L->next ;
		L->next=s ;                       //将新结点插入表中,L为头指针 
		scanf("%d",&x);
	}
	return L;
 } 

2.8尾插法建立单链表

 LinkList List_TailInsert(LinkList &L)
{
	int x = 0;
	L=(LNode*)malloc(sizeof(LNode));      //创建头结点
	LNode *s; 
	LNode *r=L;                             //尾指针  
	scanf("%d",&x);
	while(x!=9999)                        //输入9999表示结束 
	{
		s=(LNode*)malloc(sizeof(LNode));   //创建新结点 
		s->data = x; 
		r->next =s ;
		r = s ;                       //将新结点插入表中,L为头指针 
		scanf("%d",&x);
	}
	r->next =NULL;        //尾结点指针置空 
	return L;
 } 

三、双链表

3.1双链表插入操作

#include<stdio.h>
#include<stdlib.h>
typedef struct DNode{
	int data;
	struct DNode *prior,*next;    //前驱和后继指针 
}DNode, *DLinkList; 
bool ListInsert(DLinkList &L,int i,int e)
{
	int j = 0;
	DNode *p = L;
	while(p!=NULL &&j<i-1)
	{
		p=p->next ;
		j++;
	}
	if(p==NULL)
	  return false;
	DNode *s=(DNode *)malloc(sizeof(DNode));
	s->data = e;
	s->next = p->next ;
	s->prior = p;
	p->next->prior = s;
	p->next=s;
	return true;
 } 

3.2双链表删除操作

bool ListDelete(DLinkList &L,int i,int &e)
{
	int j = 0;
	DNode *p = L;
	while(p!=NULL &&j<i-1)
	{
		p=p->next ;
		j++;
	}
	if(p==NULL ||p->next == NULL)
	  return false;
	 DNode *q=p->next ;
	 e=q->data ;
	 q->next->prior =p;
	 p->next = q->next ;
	 free(q);
	 return true;
 }