二民院数据结构必会算法（C语言）

文章目录

• 1.用已有数组创建顺序表
• 2.用键盘输入的方式创建顺序表
• 3.输出顺序表各元素
• 4.在顺序表中某个位置插入一个元素
• 5.在顺序表中某个位置删除一个元素
• 6.在顺序表中查找某个位置上的元素值并输出
• 7.在顺序表中查找元素值为某个数所在的位置并输出
• 8.创建一个空单链表
• 9.用尾插法创建单链表
• 10.头插法创建单链表
• 11.输出单链表上各结点值
• 12.在单链表上查找第i个位置上的结点,并将结点值输出
• 13.在单链表head中第i个位置上插入元素值为x的新结点
• 14.判断单链表是否为空
• 15.删除单链表上第i个位置上的结点
• 16.删除整个单链表
• 17.定义链栈的结点结构,并写出入栈算法
• 18.定义链栈的结点结构,并写出出栈算法
• 19.定义循环队列(顺序结构),并写出入队算法
• 20.定义循环队列(顺序结构),并写出出队算法
• 21.定义链队列的结点结构,并写出链队列的入队算法
• 22.定义链队列的结点结构,并写出链队列的出队算法
• 23.以递归方式创建(构造) 二叉树
• 24.二叉树前序遍历算法(递归算法)
• 25.二叉树中序遍历算法(递归算法)
• 26.二叉树后序遍历算法(递归算法)
• 27.以广义表的形式输出二叉树
• 28.计算二叉树深度的递归算法
• 29.计算二叉树结点总数的递归算法
• 30.计算二叉树叶子结点总数的递归算法
• 31.删除整颗二叉树的递归算法
• 32.基于邻接矩阵创建图的算法
• 33.输出图的邻接矩阵的算法
• 34.基于邻接表创建图的算法
• 35.输出图的邻接表的算法
• 36.基于邻接矩阵存储结构的图的深度优先遍历算法(递归算法)
• 37.基于邻接表存储结构的图的深度优先遍历(递归算法)
• 38.直接插入算法
• 39.希尔排序算法
• 40.交换排序算法
• 41.快速排序算法
• 42.折半查找(二分查找)算法

1.用已有数组创建顺序表

typedef int datatype;

typedef struct list{
	datatype data[MaxSize];  //MaxSize 是线性表总长度-数组总元素个数 
	int length;  //  线性表的当前长度 
}sequenlist;     //顺序表定义


void Creatlist(sequenlist *sq,int data[],int n)
{
	int i;
	sq->length=0;
	for(i=0;i
		sq->data[i]=a[i];
		sq->length++;
	}		
}

2.用键盘输入的方式创建顺序表

void Creatlist(sequenlist *sq)
{
	datatype x;
	int i;
	char s;
	sq->length=0;
	for(i=0;i
		scanf("%d",&x);
		s=getchar();		
		sq->data[i]=x;
	    sq->length++;		
	}	
}

3.输出顺序表各元素

void Displaylist(sequenlist *sq)
{
	int i;
	for(i=0;ilength;i++)
	printf("%d ",sq->data[i]);
	printf("n");
}

4.在顺序表中某个位置插入一个元素

int Insert(sequenlist *sq, int index, datatype x)
{
	int j;
	if(sq->length>=MaxSize)   //表满无法插入
	return -1;   //插入失败返回-1
    if(index<1||index>sq->length+1)  //插入位置应该在1至(sq->length+1)，否则无法插入
	return -1;
	else
	{
		for(j=sq->length;j>=index;j--)//移动数组元素，空出index对应的sq->data[index-1]
		sq->data[j]=sq->data[j-1];
		sq->data[index-1]=x;
		sq->length++;			
	}      
}

5.在顺序表中某个位置删除一个元素

int Delete(sequenlist *sq, int index)
{
	int j;
	if(index<1||index>sq->length)//删除位置取值为1至(sq->length)
	return -1;                   //删除失败返回-1
	for(j=index;jlength;j++)//移动数组元素,补齐index对应的sq->data[index-1]
	sq->data[j-1]=sq->data[j];
	sq->length--;                //此处容易忘记
}

6.在顺序表中查找某个位置上的元素值并输出

void GetItem(sequenlist *sq, int index)//按位查找
{
	printf("%dn",sq->data[index-1]);
}

7.在顺序表中查找元素值为某个数所在的位置并输出

int Locate(sequenlist *sq, datatype x)
{
	int i=0;
    while(ilength&&sq->data[i]!=x)//表长为sq->length,下表i的最大值为(表长-1)
    i++;
    if(i>=sq->length)
    printf("未查到该值！n");
    else
    return i+1;
}

8.创建一个空单链表

typedef int datatype;
typedef struct node
{
  datatype data;
  struct node *next;
}linklist;             //单链表结点定义

linklist *CreatList()
{ 
   linklist *head;
   head=(linklist *)malloc(sizeof(linklist));
   head->next=NULL;
   return head;
}

9.用尾插法创建单链表

linklist *CreatList(int n)
{
	linklist *head,*rear,*s;
	datatype x;
	int i;
	head=(linklist *)malloc(sizeof(linklist));
    head->next=NULL;
	rear=head;
	for(i=0;i
		s=(linklist *)malloc(sizeof(linklist));
		scanf("%d",&x);
		s->data=x;
		rear->next=s;
		rear=s;
	}
	rear->next=NULL;
    return head;	
} 

10.头插法创建单链表

linklist *CreatList(int n)
{
	linklist *head,*s;
	datatype x;
	int i;
	head=(linklist *)malloc(sizeof(linklist));
    head->next=NULL;
	for(i=0;i
		s=(linklist *)malloc(sizeof(linklist));
		scanf("%d",&x);
		s->data=x;
		s->next=head->next;
		head=s;
	}
    return head;	
} 

11.输出单链表上各结点值

void Displaylist(linklist *head)
{
	linklist *p;
	p=head->next;
	while(p) //即while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("n");
}

12.在单链表上查找第i个位置上的结点,并将结点值输出

linklist *LocateItem(linklist *head,int index)
{	
    int j=0;
	linklist *p;
	p=head;
	if(index<=0)
	printf("位置有误！n");
	while(p!=NULL&&j
		p=p->next;
		j++;
	}
	if(p==NULL)
	printf("未找到该值！n");
	else
	return p->data;	 
}

13.在单链表head中第i个位置上插入元素值为x的新结点

linklist *Insert(linklist *head,int i, datatype x)
{
	linklist *p,*s;
	int j=0;
	p=head;
	while(p!=NULL&&j
	    p=p->next;
		j++;
	}
	if(!p)//if(p==NULL)
	printf("结点i不存在！");
	else
	{
		s=(linklist *)malloc(sizeof(linklist));
		s->data=x;
		s->next=p->next;
		p->next=s;	
	}
    return head;	
}

14.判断单链表是否为空

int Judge(linklist *head)
{
   if(head->next==NULL)
   return 1;
   else
   return 0;
}

15.删除单链表上第i个位置上的结点

linklist *Delete(linklist *head,int i)
{  
    linklist *p,*q; 
	int j=0;
	p=head;
	while(p!=NULL&&j
	    p=p->next;
		j++;
	}
	if(!p||!p->next)
	printf("结点不存在！");
	else
	{
		q=p->next;
		p->next=q->next;
		free(q);
	}
	return head;	
}

16.删除整个单链表

void DeleteList(linklist *head)
{
   linklist *p,*q;
   p=head->next;
   while(p)
   {
   	q=p;
   	p=p->next;
   	free(q);
   }
   free(head);
}

17.定义链栈的结点结构,并写出入栈算法

typedef int datatype;
typedef struct node
{
	datatype data;
	struct node *next;
}linkstack;
linkstack *Push(linkstack *top,datatype x)
{
	linkstack *s;
	s=(linkstack *)malloc(sizeof(linkstack));
	s->data=x;
	s->next=top;   //头插法
	top=s;
	return top;
}

18.定义链栈的结点结构,并写出出栈算法

typedef int datatype;
typedef struct node
{
	datatype data;
	struct node *next;
}linkstack;
linkstack *Pop(linkstack *top,datatype x)
{
	linkstack *p;
	if(top==NULL)
	printf("栈空n");
	else
	{
		p=top;
		x=p->data;
		top=p->next;
		free(p);
	}
	return top;
}

19.定义循环队列(顺序结构),并写出入队算法

typedef int datatype;
typedef struct
{
	datatype data[MaxSize];
	int front,rear;
}SeqQueue;
SeqQueue *Push(SeqQueue *sq,datatype x)
{
	if((sq->rear+1)%MaxSize==sq->front)
	printf("队满!n");
	else
	{
		sq->data[sq->rear]=x;
		sq->rear=(sq->rear+1)%MaxSize;		
	} 
	return sq;
}

20.定义循环队列(顺序结构),并写出出队算法

typedef int datatype;
typedef struct
{
	datatype data[MaxSize];
	int front,rear;
}SeqQueue;
SeqQueue *Pop(SeqQueue *sq,datatype x)
{
	if(sq->front==sq->rear)
	printf("队空!");
	else
	{
		x=sq->data[sq->front];
		sq->front=(sq->front+1)%MaxSize;
	}
	return sq;
}

21.定义链队列的结点结构,并写出链队列的入队算法

typedef int datatype;
typedef struct node
{
	datatype data;
	struct node *next;
}linkqueue;

typedef struct
{
	linkqueue *front,*rear;
}Squeue;
Squeue *Push(Squeue *head,datatype x)
{	
	linkqueue *s;
	s=(linkqueue *)malloc(sizeof(linkqueue));
	s->data=x;
	s->next=NULL;
	head->rear->next=s;
    head->rear=s;
	return head;	
}

22.定义链队列的结点结构,并写出链队列的出队算法

typedef int datatype;
typedef struct node
{
	datatype data;
	struct node *next;
}linkqueue;

typedef struct
{
	linkqueue *front,*rear;
}Squeue;
Squeue *Pop(Squeue *head)
{
	linkqueue *p;
	datatype x;
	if(head->front==head->rear)
	printf("队空!");
	else
	{
		p=head->front;
		head->front=head->front->next;
		free(p);
	}
	return head;	
}

23.以递归方式创建(构造) 二叉树

typedef struct BiNode
{
    datatype data;
    struct BiNode  *lchild, *rchild;
}bitree;       //二叉树结点定义


bitree *Creatbitree()
{
	bitree *root;
	char ch;
	ch=getchar();
	if(ch=='#')
	root=NULL;
	else
	{
		root=(bitree *)malloc(sizeof(bitree));
		root->data=ch;
		root->lchild=Creatbitree();
		root->rchild=Creatbitree();
	}
	return root;
}

24.二叉树前序遍历算法(递归算法)

void Preorder(bitree *root)
{
	if(root==NULL)
	return;
	else
	{
		printf("%c ",root->data);
		Preorder(root->lchild);
		Preorder(root->rchild);
	}
}

25.二叉树中序遍历算法(递归算法)

void Inorder(bitree *root)
{
	if(root==NULL)
	return;
	else
	{
		Inorder(root->lchild);
		printf("%c ",root->data);
		Inorder(root->rchild);
	}
}

26.二叉树后序遍历算法(递归算法)

void Postorder(bitree *root)
{
	if(root==NULL)
	return;
	else
	{
		Postorder(root->lchild);
		Postorder(root->rchild);
		printf("%c ",root->data);
	}
}

27.以广义表的形式输出二叉树

void Displaybitree(bitree *root)
{
	if(root==NULL)
	return;
	else
	{
		printf("%c",root->data);
		printf("(");
		Displaybitree(root->lchild);
		printf(",");
		Displaybitree(root->rchild);
		printf(")");
	}	
}

28.计算二叉树深度的递归算法

int CountDepth(bitree *T)
{
	int m,n;
	if(T==NULL)
	return 0;
	else
	{
		m=CountDepth(T->lchild);
		n=CountDepth(T->rchild);
		return (m>n)?(m+1):(n+1);
	}	
}

29.计算二叉树结点总数的递归算法

int Countnode(bitree *T)
{
	if(T==NULL)
	return 0;
	else
	return 1+Countnode(T->lchild)+Countnode(T->rchild);
}

30.计算二叉树叶子结点总数的递归算法

int Countleaf(bitree *T)
{
	if(T==NULL)
	return 0;
	else if(!T->lchild&&!T->rchild)
	return 1;
	else
	return Countleaf(T->lchild)+Countleaf(T->rchild);
}

31.删除整颗二叉树的递归算法

void DelBitree(bitree *T)
{  
  if(T!=NULL)
  {    
       DelBitree(T->lchild);
       DelBitree(T->rchild);
       free(T);
  }
}

32.基于邻接矩阵创建图的算法

#define N 10
struct { 
	datatype vertex[N];
	int arc[N][N];  
}mGraph;      


void CreatMGraph()//创建邻接矩阵 (基于有向图)
{
	int i,j,k;
	puts("请输入顶点值："); 
	for(i=0;i
    	scanf("%d%d",&i,&j);
    	mGraph.arc[--i][--j]=1;
    }
} 

33.输出图的邻接矩阵的算法

void Display()
{
	int i,j;
	puts("输出顶点的值：n");
	for(i=0;i
		for(j=0;j 
34.基于邻接表创建图的算法 
struct ArcNode
{    int adjvex; 
     struct ArcNode *next;
};               //边表结点
struct VertexNode 
{
      datatype  vertex;
      struct ArcNode *firstedge;
} adjlist[N];   //表头


void CreatALGraph()//创建邻接表(基于有向图)
{
	int i,j,k;
	struct ArcNode *s;
	puts("请输入顶点值:");
	for(i=0;iscanf("%d",&adjlist[i].vertex);
	 adjlist[i].firstedge=NULL;}
	puts("请创建边:");
	for(k=0;k
		scanf("%d%d",&i,&j);
		i=i-1;j=j-1;        //顶点1 2在数组中对应的位置是0 1
		s=(struct ArcNode *)malloc(sizeof(struct ArcNode));
		s->adjvex=j;
		s->next=adjlist[i].firstedge;    //头插法创建
		adjlist[i].firstedge=s;
	}
}
 
35.输出图的邻接表的算法 
void DisplayALgraph()
{
	int i,j;
	struct ArcNode *p;
	puts("输出顶点的值及其邻接边：");
	for(i=0;i
		p=adjlist[i].firstedge;
		printf("%d :",adjlist[i].vertex);
		while(p!=NULL)
		{
			printf("(%d,%d) ",adjlist[i].vertex,p->adjvex+1);
			p=p->next;
		}
		printf("n");
	} 
} 
 
36.基于邻接矩阵存储结构的图的深度优先遍历算法(递归算法) 
void DFSTraverse(int v)//深度优先遍历（基于邻接矩阵） 
{
    int i;
	printf("%d ",mGraph.vertex[v]);
	visited[v]=1;
	for(i=0;i 
37.基于邻接表存储结构的图的深度优先遍历(递归算法) 
void DFSTraverse(int v)//深度优先遍历（基于邻接表）
{
	struct ArcNode *p;
	int i;	
	printf("%d ",adjlist[v].vertex);
	visited[v]=1;
	p=adjlist[v].firstedge;
	while(p!=NULL)
	{
		i=p->adjvex;
		if(visited[i]==0)
		DFSTraverse1(i);
		p=p->next;
	}
	
}
 
38.直接插入算法 
void InsertSort(int r[],int n)//直接插入排序
{
	int i,j;
    for(i=2;i<=n;i++)//从第二数开始
    {
    	r[0]=r[i];   //r[0]做为监视器
    	j=i-1;
    	while(r[0]
	    	r[j+1]=r[j];
	    	j=j-1;
	    }
	    r[j+1]=r[0];
    } 
}
 
39.希尔排序算法 
void ShellSort(int r[],int n)//希尔排序 
{
	int i,j,d;
	for(d=n/2;d>=1;d=d/2)   //以d为增量进行划分
	{
		for(i=d+1;i<=n;i++) //从每组的第二个元素开始进行直接插入排序，而不是一组一组排
		{
			r[0]=r[i];
			j=i-d;
			while(j>0&&r[0]
				r[j+d]=r[j];
				j=j-d;
			}
			r[j+d]=r[0];
		}
	}
}
 
40.交换排序算法 
void BubbleSort(int r[],int n)//冒泡排序 
{
	int j,temp,exchange,bound;
	exchange=n;
	while(exchange)
	{
		bound=exchange; //bound位置的记录是无序区的最后一个记录
		exchange=0;   
		for(j=1;jr[j+1])
		{
			temp=r[j];
			r[j]=r[j+1];
			r[j+1]=temp;
			exchange=j;
		}
	}	
}
 
41.快速排序算法 
int Partition(int r[],int first,int end)//实现一次划分
{
	int i,j,temp;
	i=first;
	j=end;                 //初始化
	while(i
		while(i
			temp=r[i];
			r[i]=r[j];
			r[j]=temp;               //将较小记录交换到前面
			i++;
		} 
		while(i
			temp=r[j];
			r[j]=r[i];
			r[i]=temp;              //将较大记录交换到前面
			j--;
		} 
	}
	return i;                       //i为轴值记录的最终位置
}

void QuickSort(int r[],int first,int end)//快速排序 
{
	int pivotpos;
	if(first
		pivotpos=Partition(r,first,end);     //一次划分
		QuickSort(r,first,pivotpos-1);       //对前一个子序列进行快速排序
		QuickSort(r,pivotpos+1,end);         //对后一个子序列进行快速排序
	}
}
 
42.折半查找(二分查找)算法 
int Binsearch(int r[],int low,int high,int k)//折半查找递归算法
{
	int mid;
	if(low>high)             //递归出口
	return 0;
	else
	{
		mid=(low+high)/2;
		if(kr[mid])
	     return Binsearch(r,mid+1,high,k);
	    else return mid;
	}
}

int Binsearch(int r[],int n,int k) //折半查找非递归算法
{
    int low,high;
    low=1;
    high=n;
    while(low<=high)
    {
      mid=(low+high)/2;
      if(kr[mid])
      low=mid+1;
      else return mid;
     }
    return 0;
}