你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

C语言数据结构

作者：你好赵伟 | 2024-04-09 09:22:24

踩

c语言数据结构

一、数据结构概述

1.1数据结构的概念

数据结构是计算机存储，管理数据的方式。数据必须依据某种逻辑联系组织在一起存储在计算机里，数据结构研究的是这种数据的存储结构和数据的逻辑结构。

1.2数据的逻辑结构的4种分类

二、线性表

2.1线性表概述

线性结构是简单且常用的数据结构，而线性表则是一种典型的线性结构。

存储数据，最简单最有效的方法是把它们存储在一个线性表中。

一个线性表是n个元素的有限排列。每个元素在不同情况下有不同的含义，可以是整数，也可以是字符。

线性表的存储方式有两种：顺序存储方式和链表存储方式。

线性表示例：


color={red,orange,yellow,green,blue,white};
score={90,84,38,29,90}

2.2、顺序表

就是把线性表中的所有元素按照其逻辑顺序依次存储到指定位置开始的一块连续的存储区域。
线性表中的第1个元素的存储位置就是指定的存储位置，第i个元素的存储位置紧接第i-1个元素的存储位置的后面。
顺序表的特点：

在顺序表中，各元素的逻辑顺序跟物理顺序一致，第i项就存在第i个位置。
对顺序表中的所有元素，既可以顺序访问，也可以随机访问。


#include "stdio.h"
#include "stdlib.h"
#define MAXLISTSIZE 1024
/*typedef struct的作用
1.简化较复杂的声明
2.typedef并没有创建一个新的类型，而是为了某个已经存在的类型增加一个新的名字，如示例汇总的linearlist是struct的别名
typedef struct 
{
    int id;
    char name;
}linearlisr
使用和不使用tepedef的区别
1.使用tepedef声明结构体，可以忽略struct这个关键字
struct linearlist list[3];
*/
 
tepedef struct  //结构体
{
    int data [MAXLISTSIZE];//顺序表
    int last;      //顺序表元素个数
}linearlist     //linearlisr结构体别名
void Listlist(linearlist *list)  //打印线性顺序表  声明一个指针 list指向结构体linearlist首地址
{
    int i;
    printf("当前线性表状态\n");
    if(list -> last==0)
    printf("当前线性表为空\n");
    else 
        for(i=0;i<(list->last);i++)
        {
            printf("[%4d]",list -> data[i]);
            
        }
        printf("\n");
}
 
void output(linearlist *list )
{
    system("cls");
    printf("    顺序表    ");
    printf("    a:增加一个字节 i:插入一个字节 \n");
    printf("    d:删除一个节点：e:退出     \n");
    Listlist(lsit);
}
 
Linearlist *Createlist()     //创建线性顺序表
{    
    Linearlist *list= (Linearlist *)malloc(sizeof(Linearlist));  //分配空间
    list -> last=0;     //初始化节点值
    return listl        //返回初始化节点指针
}
 
void AppendNode(Linearlist *list ,int n)
{    
    if(list -> last<MAXLISTSIZE>)
    {
        list -> data [list->list->last]=n;  //初始化节点值
        list -》last+=1;
    }
}
 
void insertNode (Linearlist *lsit,int n,int pos)
{
    int j;
    if(pos,0||pos>list->last)
    printf("所插入的位置超出顺序表的范围\n");
    else
    {
        for(j=list->last;j=pos;j--)
        {
            list ->data[j+1]=list->data[j];
            list ->data [pos]=n;
            list ->last++;
        }
    }
}
void DeleteNode(Linearlist*list,int pos)  // 删除节点
 {
    int j;
	if((pos<0)|| (pos>list->last))       // 删除位置超出顺序表的范围
		printf("所要删除的位置超出顺序表的范围\n");
	else
	{
	   for(j=pos;j<list->last;j++)         //  遍历顺序表
		   list->data[j]=list->data[j+1];  //  元素前移
	   list->last--;                       //  顺序长度减一
	}
 }
 
 int main()   // 主函数
 { 
    int key,pos; // 整型变量
	char ch;     // 字符型变量
Linearlist *list; // 
	list = CreateList();  // 创建顺序列表
	while(1)
	{
	Output(list);
	printf("请选择："); 
	ch=getchar();        // 接受选项
	fflush(stdin);       // 清除缓存  
	if(ch=='a')          // 追加
	{
	  printf("请输入要追加的数据");
	  scanf("%d",&key);
	  AppendNode(list,key);
 
	}
	  else if(ch=='i')    // 插入
	  { 
	   printf("请输入要插入的数据的位置：");
	   scanf("%d",&pos);
	   printf("请输入要插入的数据");
	   scanf("%d",&key);
	   insertNode(list,key,pos);
	  }
	  else if(ch=='d')       // 删除
	  {
	  printf("请输入要删除的数据的位置");
	  scanf("%d",&pos);
	  DeleteNode(list,pos);
 
	  }
	  else if(ch=='e')  // 退出
		  exit(0);
	  Output(list);
	  fflush(stdin);   // 清除缓存
	}
	return 0;

2.3、链表

单链表是一种简单的链表表示，也叫做线性链表，用它来表示线性表时，用指针表示结点间的逻辑关系，因此单链表的一个存储结点包含两部分

data部分称为数据域，用于存储线性表的一个数据元素；
link部分称为指针域，用于存放一个指针，该指针指示链表下一个结点的开始存储地址

单链表的第一个结点也称为首结点，它的地址可以通过链表的头指针head找到，其他结点的地址通过前驱结点的link域名找到，链表的最后一个结点没有后继，则在link域放一个空指针NULL，图中用“^”表示

线性表中的数据元素的顺序与器链表表示中的物理顺序可能不一致，一般通过但链表的指针将各个数据元素按照线性表的逻辑顺序链接起来。当head为空时，则单链表为空，否则为非空表。

2.3.1、链表节点的创建

链表是一种动态的数据结构，在程序中需要使用malloc()和free()函数创建链表。

为有效的地存储节点数据，并且实现链表的链式功能，可建立linknode结构体


struct linknode
 
{
 
int data;   // 结点数据
 
linknode *next; // 结点指针，指向下一个结点
 
}；

运行上面的结构体声明后，linknode就成为一个动态指针结构。建立了结点的结构后，接下来定义一个结构体指针变量，该指针变量在使用前必须分配存储空间，然后以用户键入初值初始化结点数据，同时初始化该结点指向的下一个结点为空


linknode *ptr;
 
ptr=(linknode *)malloc(sizeof(linknode)); // 获取linknode在内存中所占的字节的长度，用malloc函数开辟出保存linknode所占内存的一段地址，并强制转换为linknode类型指针
 
//sizeof函数计算数据（包括数组、变量、类型、结构体等）所占内存空间，用字节数表示
 
/*malloc函数用于在内存开辟了一段地址，而这段地址的首地址存在返回的那个指针变量里，由于不知道到底这段地址有多长，可以存什么变量，所以它的类型是空的*/

输入到数据的结构中


scanf("%d",&ptr->data)
 
pro->next=unll

2.3.2、链表结点遍历

链表的遍历和数组的遍历相似，数组的使用下标，而链表则是通过指针处理每一个结点的遍历。不同的是，数组可以随机访问数组元素，链表结构不一定要用遍历的方式访问其结点，如果要访问第n个结点的内容，就一定要遍历到n-1个结点才能够知道结果在哪里

2.3.3、链表结点删除

链表结点删除的三种情况

从动态的内存操作理论来说，应该在删除第一个结点后，立即将删除的结点内存释放给系统，如果ptr是指向删除结点的指针，那么释放命令如下

free(ptr);

如果是整个链表结构，除了使用上述命令，还需要借助于链表的遍历方法。

2.3.4、链表的插入


#include <stdio.h>  // 头文件  stdio 就是指 “standard input & output"（标准输入输出）
#include <stdlib.h> /* stdlib.h里面定义了五种类型、一些宏和通用工具函数,常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()*/
struct linknode      // 链表结构声明
{           
  int data;           // 存储结点数据
  struct linknode *next;  // 指向下一个结点
};
typedef struct linknode LinkNode;  // 为结构体定义新类型
 
 
 
/*链表函数*/
LinkNode *CreatLinkNode()          // 创建链表函数
{
    int i;                // 整型变量i
	LinkNode *head,*ptr,*p;   // 链表结点  head指向链表的首地址 head=null或head=0时 链表为空
	head = (LinkNode *)malloc(sizeof(LinkNode));  // 分配内存
	if(!head)                     // 判断条件
	{
	printf("内存分配失败!\n");    // 打印提示语句  
	exit(1);                      // 退出
	}
   printf("请输入第1个数据:");
   scanf("%d",&head->data);      // 创建结点内容
   head ->next=NULL;
   ptr=head;                     // ptr指向链表开始
   for(i=1;i<5;i++)              // 循环创建结点
   {
       p=(LinkNode *)malloc(sizeof(LinkNode));
	   if(!p)
	   {
	      printf("内存分配失败!\n");
		  exit(1);
	   }
	   printf("请输入第%d个数据:",i+1);
	   scanf("%d",&p->data);
	   p->next=NULL;
	   ptr->next=p;      // 链接结点
	   ptr=ptr->next;    // 指向下一个结点
   }
    return head;
}
 
 
 
 
 
/*链表的遍历*/
 LinkNode *FindNode(LinkNode *head,int num)  // 
 {
     LinkNode *ptr;
	 ptr=head;             // 指向链表起始
	 while(ptr!=NULL)      // 遍历链表
     {
	    if(ptr->data==num) return ptr;  // 查找编号
		ptr=ptr->next;
	 }
	 return ptr;
 }
 
 
 
 
/*链表结点的插入模块*/
 LinkNode *insertNode(LinkNode *head,LinkNode *ptr,int value) // 
 {
      LinkNode * newnode=(LinkNode *)malloc(sizeof(LinkNode));  // 分配内存
	  if(!newnode) return NULL;
	  newnode->data=value; // 创建结点内容
	  newnode->next=NULL;  // 设置指针初值
	  if(ptr==NULL)
	  {
	    newnode->next=head;
		return newnode;
	  }else
	  {
	  if(ptr->next == NULL) ptr->next=newnode;// 是否是链表结束
	  else
	  {
	    newnode ->next=ptr->next;  // 新结点指向下一个结点
		ptr->next=newnode;
	  }
	  }
	  return head;
 }
 
 
 
 
 
/* 链表结点删除*/
 LinkNode *DeleteNode(LinkNode *head,LinkNode *ptr) //  定义自定义类型LinkNode的两个形参指针head,ptr 指向 LinkNode结构体
 {
    LinkNode *pre;   // 指向前一个结点
	if(ptr=head)     // 是否用链表的开始
		return head->next;  // 输出第2个结点
	else
	{
	   pre=head;
	   while(pre->next!=ptr)
		   pre=pre->next;
	   if(ptr->next=NULL)       // 是否是链表结束
		   pre->next=NULL;      // 最后一个结点
	   else
		   pre->next=ptr->next;  // 中间结点
 
	}
	free(ptr);             // 释放结点内存
	return head;
 }
 
 
 
 
 
 
/*链表输出模块*/
 void PrintNode(LinkNode *ptr)   
 
	{
    while(ptr!=NULL)   // 指针ptr非空
	{
	   printf("%d\t",ptr->data);  // 输出当前指针指向结点的数据
	   ptr=ptr->next;             // 指针向后移动指向下一个结点
	}
	printf("\n"); // 打印一个换行符
 }
 
 /*链表的内存释放*/
 void FreeLinkNode(LinkNode *head) // 定义LinkNode类型的head指针指向结构体LinkNode的首地址
 {
      LinkNode *ptr;
	  while(head!=NULL)
	  {
	     ptr=head;
		 head=head->next;
		 free(ptr);
	  }
 }
 
 
 int main()
 {
     int num,value;
	 LinkNode *head,*ptr;      // 定义结构体自定义数据类型LinkNode的指针 head ptr 
	 head = CreatLinkNode();
	 PrintNode(head);
	 printf("输入要查找的数据：\n");
	 scanf("%d",&num);
	 ptr=FindNode(head,num); // 查询数据
	 if(!ptr)
		 printf("没有找到\n");
	 else
	 {
	    printf("找到啦！\n请输入要插入的数据：\n");
		scanf("%d",&value);
		head=insertNode(head,ptr,value);// 插入数据
		PrintNode(head);
	 }
	 printf("请输入要查找并删除的数据：\n");
	 scanf("%d",&num);
	 ptr=FindNode(head,num);
	 if(!ptr)
     printf("没有找到\n");
	 else
	 {
	 printf("找到了！\n");
	 head=DeleteNode(head,ptr);  // 删除
     PrintNode(head);
	 }
	FreeLinkNode(head);
	return 0;
 }

三、栈和队列

3.1、栈概述

栈是一种重要的线性结构，它是受限的线性表，它仅能在表的一端进行插入和删除运算的线性表，栈被广泛地应用到各种系统的程序设计中。

通常的插入，删除的这一端为栈顶(Top)，另外一端为栈底(Bottom)
当表中没有元素时称为空栈
栈为后进先出(Last In First Out)的线性表，简称为LIFO表
栈的修改是按照先进先出的原则，每次删除的总是当前栈中“最新”的元素，即最后插入(进栈)的元素，而最先插入的原则是被放在栈的底部，要到最后才能删除。

3.2、栈的基本运算

InitStack(s);构造一个空栈s。
StackEmpty(s):判断空。若s为空栈，则返回TRUE。
StackFull(s); 判断满。如s为满栈，则返回TRUE。
Push(S，x):进栈，如栈s不满，则将元素x插入s的栈顶。
Pop(s):退栈。若栈s非空，则将s的栈顶元素删去，并返回该元素。
StackTop(s);取栈顶元素，若栈s非空，则返回栈顶元素，但不改变栈的状态。

3.3、顺序栈的类型定义

顺序栈的定义和顺序表的定义一样，通常我们使用结构体定义顺序栈，记录栈顶坐标从而实现各种操作。


#define StackSize 100   // 假定预分配的栈空间最多为100个元素
typedef char DataType;  // 假定栈元素的数据类型为字符
typedef struct
{
   DataType data[StackSize];     // 定义栈数组
   int top;                      // 栈顶
} seqstack;                      // 结构体别名

栈底位置是固定不变的，可设置在向量两端的任意一个端点。

栈顶位置是随着进栈和退栈的操作而变化的，用一个整型量top(通常称为top)

3.4、链式栈的类型定义

栈的链式存储结构称为链栈。链栈是没有附加结点的运算受限的单链表。栈顶指针就是链表的头指针。跟单链表一样，通常我们使用结构体实现链式栈的功能，结构体内一个量存储结点值，一个量存储指针，实现链式结构，就像单链表有指针一样，我们也为链式栈定义头结点，以便对链式栈进行操作。


#include "stdio.h"
typedef struct stacknode     // 链式栈结构
{
    DataType data            // 栈元素
	Struct stacknode *next   // 结构体自用
 
}StackNode;
typedef struct
{
     StackNode *top;   // 栈顶指针
}LinkStack;
 
/* 注意
	 LinkStack结构体类型的定义为了在方便函数体中修改top指针本身；
	 若要记录栈中元素的个数，可将元素的属性放在LinkStack类型中定义。
  */

3.5、队列

队列（Queue）是一种线性结构，它是一种受限的线性表，它只允许在一端进行插入，而在另外一端进行删除的运算。受限的线性队列的修改也是依先进先出的原则进行的。

3.5.1、队列的常用运算

InitQueue(Q);置空队。构造一个空队列Q。
QueueEmpty(Q);判队空。若队列Q空，则返回真值，否则返回假值。
QueueFull(Q);判队满。若队列Q为满，则返回真值，否则返回假值。
EnQueue(Q,x);若队列Q非满，则将元素x插入Q的队尾。此操作简称入队。
DeQueue(Q);若对列Q非空，则删去Q的对头元素，并返回该元素，此操作简称出队。
QueueFront(Q);若队列Q非空，则返回对头元素，但不改变队列Q的状态。

3.5.2、顺序队列类型定义

队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
同顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。
由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示对头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置0,

入队时：将新元素插入rear所指的位置，然后加1
出队时:删去front所指的元素，然后将front加1并返回被删除的元素
注意:当头尾指针相等时，队列为空；在非空队列里，队头指针始终指向队头元素，尾指针始终指向对尾元素的下一个位置。

3.5.3、链队列类型定义

队列的链式存储结构简称为链队列。

它是限制仅在表头删除和表尾插入的单链表。

注意：增加指向链表上的最后一个结点的尾指针，便于在表尾进行插入操作，图中的Q为LinKQueue型的指针

四、二叉树

树形结构是一类重要的非线性结构。
树形结构的结点之间有分支，并具有层次关系的结构。
在程序中，用树来表示源程序的语法结构
在数据库系统中，可以用树来组织信息
二叉树是树形结构的一个重要类型。
二叉树(BinaryTree)是N(N>=0)个结点的有限集，它或者是空集(N=0)，或者由一个根结点及两颗互不橡胶的分别称作这个根的左子树和右子树的二叉树组成，二叉树可以是空集；根可以有空的左子树或右子树，或者左，右子树皆为空。

由上图可知，一颗非空的二叉树由根结点及左，右子树等3个部分组成。
因此，在任一结点上，可以按某种次序进行3个操作
访问结点本身(N);
遍历该结点的左子树(L)
遍历该结点的右子树(R)
该三种操作有6种执行次序:NLR、LNR、LRN、NRL、RNL、RLN
前三种和后三种的执行次序是对称的，常用的为前序遍历(NLR),中序遍历(LNR),后序遍历(LRN)
举例

前序遍历：A-B-D-Y-E-C-F-X-Z
中序遍历: D-Y-B-E-A-F-C-Z-X
后序遍历: Y-D-E-B-F-Z-X-C-A

五、查找方法

5.1、顺序查找

核心思想：同数组遍历一样，就是从数组的第一元素开始，检查数组的每一个元素，以便确定是否有查找的数据。

注意：因为从头检查到尾，因此数组数据是否排序就不再重要。


#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define MAX 100    // 宏定义   最大数组容量
 
struct element{    // 记录结构声明
	int key;
};
typedef struct element record;  // 结构体别名
record data[MAX+1];             // 结构体别名2
 
 
// 顺序查找
int seqseqrch(int key)
{
   int pos;                  // 数组索引
   data[MAX].key=key;        // 将seqseqrch函数的形参key传递给结构体element中的key
   pos=0;                    //  数组索引从0开始(数组从头开始找)
   /*
   while(1)的作用
     while(1);   
	 while(1){}    条件成立时，通过break跳出死循环    写在单片机中防止程序跑飞
   两者都是定义死循环(无限循环)
   */
   while(1)                  // 定义死循环
   {
      if(key==data[pos].key) // 是否找到
		  break;             // 上面条件满足时，跳出死循环
	  pos++;                 // 条件不满足时 继续查找下一个元素
   }
   if(pos==MAX)              // 数组从头开始找==数组容量最大   说明在最后   
	   /*
	   
   return 1,return 0 ,return -1
   0与1   0表示假  1表示真
   -1与0   -1表示语句执行不成共        0表示语句执行成功
		   
			 
	*/
   return -1;                // 一般的return -1;表示出错    return 0;表示正确
   else
	   return pos;           // 返回pos的值
}
 
/*主程序*/
int main()
{
 int checked[300];   // 检查数组
 int i,temp;         // 定义整型变量
 long temptime;      //  长整型变量
 srand(time(&temptime)%60);  // 使用时间初始随机数
 for(i=0;i<300;i++)
	 checked[i]=0;           // 清除检查数组
 i=0;
 while(i!=MAX)      // 生成数组值的循环
 {
   temp =rand()%300;// 随机数范围0~299
   if(checked[temp]==0)  // 是否已有的值
   {
      data[i].key=temp;
	  checked[temp]=1;  // 设置此值生成过
	  i++;
   }
 }
  while(1)  // 定义为死循环可以一直查找数据
  {
    printf("请输入查找的值0~299\n"); // 提示语句
	scanf("%d",&temp);  // 导入查找的值
	if(temp!=-1)        // temp =rand()%300;  键入的数值不能为负数
	{
	    i=seqseqrch(temp);  // 调用顺序查找
		if(i!=-1)           // 数值索引没有赋值
			printf("找到查找值%d\n",temp);
		else
			printf("没有找到查找值%d\n",temp);
	}
	else
		exit(1);  // 结束程序
 
  }
  return 0;
}

5.2、折半查找

如果查找的数据已经排序，可以使顺序查找的方式进行查找，但更好的查找方法是折半查找法

折半查找的核心思想：将数据分区，首先折半查找检查中间元素，如果中间元素小于查找的关键值，可以确定数据是存储在前半段，否则就在后半段。然后继续在可能存在的半段数据内重复上述操作，直到找到或已经没有数据可以分区，表示没有找到。

将数组分为上、下范围，用low和high分别表示，则中间元素为(low+high)/2。在进行查找时，可以分为以下3种情况。

如果查找关键值小于数组的中间元素，关键值在数据数组的前半部分。、
如果查找的关键值小于数组的中间元素，关键值在数据数组的后半部分。
如果查找关键值等于数组的中间元素，中间元素就是查找的值。


#include "stdio.h"
#include "stdlib.h"
#define MAX 21   // 最大
 
struct element{    
    int key;
};
 
typedef struct element record; // 结构体别名
 
record data[MAX]={
	1,3,5,7,9,21,25,33,46,89,100,121,127,144,234,432,500,509,689,700,890};
	// 折半查找
	int binarysearch(int key)   // 定义折半查找函数binarysearch 形参key 为要查找的元素
	{
	  int low,high,mid;         // 数组开始、结束，中间变量
	  low=0;                    // 数组从0开始，标记查找下限
	  high=MAX-1;               //数组结束，标记查找上限  下标从0开始  所以数组下标最大值为MAX-1
 
	  while(low<=high)          //因为数组已经排序 所以前半段中的数组元素必须小于等于后半段中的数组元素 low<=hign
	  {
	   mid=(low+high)/2;        // 折半查找中间值
	   if(key<data[mid].key)    // 当待查找的数据小于折半中间值
		   high=mid-1;          // 在折半的前一半重新查找
	   else
		   if(key>data[mid].key) // 当带查找数据大于折半中间值
			   low=mid+1;        // 在折半的后一半重新查找
		return  mid;             // 找到了返回下标
	  }
	  return -1;                   // 没有找到返回-1	
}
 
	int main()
	{
	    int found;     // 是否找到变量
		int value;     // 查找值
		while(1)       // 死循环
		{
		  printf("请输入查找值0~1000\n");  // 提示语句
		  scanf("%d",&value);            // 键盘输入要查找的值
		  if(value!=-1)                  // 查找的值不为负数
		  {
		      found=binarysearch(value);  // 调用折半查找
			  if(found!=-1)
				  printf("找到查找值：%d[%d]\n",value,found);
			  else
				  printf("没有找到查找值：%d\n",value);
		  }
		  else
			  exit(1); // 结束程序
		
		}
		return 0;
	}

六、排序方法

6.1、冒泡排序

冒泡排序的核心思想：将较小的元素搬到数组的开始，将较大的元素慢慢地浮到数组的最后。冒泡排序法使用交换方式进行排序。


#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAX 20
 
void bubble(char *arr,int count)  // 定义一个冒泡函数  有两个形参  char类型的指针 arr 整型count
{
    int i,j;
	char temp;
	for(j=count;j>1;j--)  // 外循环控制比较轮数
	{
		for(i=0;i<j-1;i++) // 内循环控制每轮比较的次数
		{
		if(arr[i+1]<arr[i]) // 比较相邻元素
		{
		   temp =arr[i+1];
		   arr[i+1]= arr[i];
		   arr[i]=temp;
		}
		}
		printf("输出结果[%s]\n",arr); // 交换后输出字符串
	}
}
int main()
{
   char array[MAX];  // 定义一个char类型的数组 数组长度为20
   int count;
   printf("请输入排序的字符串：\n");
   gets(array);             // 存储字符数组
   count=strlen(array);     // 测试字符数组
   bubble(array,count);
   return 0;
}

6.2、选择排序

核心思想：选择排序法是从排序的元素中宣传最小的一个元素和第一元素交换位置，然后从剩下的元素中选出最小的元素和第二个元素交换，重复这种处理的方法，直到最后一个元素为止。


#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAX 20
// 选择排序法
void select(char *arr,int count)
{
  int pos;
  int i,j;
  char temp;
  for(i=0;i<count-1;i++) // 数组
  {
     pos=i;
	 temp=arr[pos];
	 for(j=i+1;j<count;j++)
	 {
	  if(arr[j]<temp)
	  {
	    pos=j;
		temp=arr[j];
	  }
	 
	 }
	 arr[pos]=arr[i]; /*交换当前字符和最小字符两个元素和小标*/
	 arr[i]=temp;
	 printf("输出结果：[%s]\n",arr); // 交换后输出
  }
}
 
int main()
{
  char array[MAX];
  int count;
  printf("输入将排序的字符串：\n");
  gets(array);
  count=strlen(array);
  select(array,count);
  return 0;
}

6.3、插入排序法

插入排序法是对排序元素的前两个元素的排序，然后将第三个元素插入已经排好序的两个元素中，所以这三个元素任然是从小到大排序，接着第四个元素插入，重复操作直到所有的元素都排好序。


#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAX 10    // 宏定义
// 插入排序法
void insert(char *arr,int count)  // 插入排序函数  两个形参   指向char类型数组的指针   数组长度
{
  int i,j;      // 定义变量i循环次数，j数组长度
  char temp;     // 定义变量temp
  for(i=1;i<count;i++)  // 遍历数组
  {             
    temp=arr[i];        // 创建初值   当前数组值存入临时变量temp
	j=i-1;              // 开始位置
	while(j>=0 && temp<arr[j])  // 循环元素后移
	{
	  arr[j+1]=arr[j];
	  j--;
	}
    arr[j+1]=temp;     // 插入字符 
    printf("输出结果：[%s]\n",arr);
 
  }
 
}
 
int main()
{
 
 char array[MAX];
 int count;
 printf("输入将排序的字符串");
 gets(array);
 /*strlen所作的是一个计数器的工作，它从内存的某个位置（可以是字符串开头
 ，中间某个位置，甚至是某个不确定的内存区域）开始扫描，
 直到碰到第一个字符串结束符'\0'为止，然后返回计数器值(长度不包含'\0')*/
 count=strlen(array); // 返回array的数组长度
 insert(array,count); // 调用函数
 return 0;
}

七、综合应用 -- 反转链表


#include "stdio.h"
#include "stdlib.h"
// 链表结构声明
struct linknode{
int data;
struct linknode *next; // 结构体自用
};
// 定义新类型
typedef struct linknode LinkNode;
// 创建链表
LinkNode *CreatLinkNode(int *array,int len)
{
   LinkNode *head;  // 链表首结点
   LinkNode *ptr,*p;
   int i;
   head=(LinkNode*)malloc(sizeof(LinkNode)); // 分配内存
   if(!head)                                 // 检查指针
/*if(head)printf("xxxx");这里是判断head是否为真，如果是真，则执行printf("xxxx");head不等于0为真，head等于0为假。
if(!head)printf("xxxx");这里是判断head是否为假，如果是假，则执行printf("xxxx");head不等于0，
!head为假，head等于0，!head为真。*/
	   return NULL;
   head->data=array[0];
   head->next=NULL;    // 设置指针初值
   ptr=head;           //ptr指向链表开始
   for(i=1;i<len;i++)
   {
     p=(LinkNode*)malloc(sizeof(LinkNode));
	 if(!p)
		 return NULL;
	 p->data=array[i];
	 p->data=NULL;
     ptr->next=p;  // 连接结点 p与ptr关联
	 ptr=ptr->next;//指向下一个结点
 
   }
   return head;   // 返回首地址
}
 
// 链表反转
LinkNode *invertNode(LinkNode *head)
{
   LinkNode *mid,*last;
   mid=NULL;
   while(head!=NULL)
   {
	   last = mid;       // last 是head的后结点
	   mid=head;
	   head=head->next; // 下一个结点
	   mid->next=last;  // mid指向后结点last
   
   }
   return mid;
}
 
// 链表输出
void PrintNode(LinkNode *ptr)
{
  while(ptr!=NULL)                // 链表遍历循环
  {
     printf("%d\t",ptr->data);    // 输出结点数据
	 ptr=ptr->next;               // 指向下一个结点
  }
  printf("\n");
}
 
 
// 链表的内存释放
void FreeLinkNode(LinkNode *head)
{
  LinkNode *ptr;
  while(head!=NULL)
  {
     ptr =head;
	 head=head->next;
	 free(ptr);
  }
}
 
int main()
{
	int list[6] = {1,2,3,4,5,6};
	LinkNode *head;
	head=CreatLinkNode(list,6);
	if(!head)
	{
	  printf("内存分配失败");
	  exit(1);
	}
	printf("原来的链表是:\n");
	PrintNode(head);
	head=invertNode(head);
	printf("反转后的链表是:\n");
	PrintNode(head);
	FreeLinkNode(head);
	return 0;
 
}

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】