一、数据结构构造概述

1.1、什么是数据结构

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

二、线性表

2.1、线性表概述

2.2、顺序表

2.3、链表

2.3.1、链表节点的创建

2.3.2、链表结点遍历

2.3.3、链表结点删除

2.3.4、链表的插入

三、栈和队列

3.1、栈概述

3.2、栈的基本运算

3.3、顺序栈的类型定义

3.4、链式栈的类型定义

3.5、队列

3.5.1、队列的常用运算

3.5.2、顺序队列类型定义

3.5.3、链队列类型定义

四、二叉树

五、查找方法

5.1、顺序查找

5.2、折半查找

六、排序方法

6.1、冒泡排序

6.2、选择排序

6.3、插入排序法

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

一、数据结构构造概述

1.1、什么是数据结构

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

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

二、线性表

2.1、线性表概述

线性结构是简单而且常用的数据结构，而线性表则是一种典型的线性结构。
存储数据，最简单，最有效的方法是把它们存储在一个线性表中。
一个线性表是n个元素的有限序列。每个元素在不同的情况下有不同的含义，可以是整数，也可以是字符。
线性表的存储方式有两种：顺序存储方式和链表存储方式
线性表示例

color = {red,orange,yellow,green,blue,black,white}; // color线性表的组成

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    // 此处省略了结构的的名称 为匿名结构体   typedef struct line{int id;char name;}linearlist
使用与不使用typedef的区别
1、使用typedef声明结构体，可以省略struct这个关键字
linearlist list[3];2、不使用typedef声明结构，则不可以省略struct这个关键字
struct linearlist list[3];*/typedef struct            // 结构体        
{int data[MAXLISTSIZE]; // 顺序表int last;              // 顺序表元素个数
}Linearlist;             // linearlist 结构体别名void ListList(Linearlist *list)      // 打印线性顺序表    声明一个指针 list 指向结构体linearlist首地址
{int i;                             //   定义变量iprintf("当前线性表的状态\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("-       顺序表       -\n");printf("-      a:追加一个节点 i:插入一个节点       -\n");printf("-      d:删除一个节点 e:退出     -\n ");ListList(list);              // 打印线性顺序表
} Linearlist *CreateList()    // 创建线性顺序表
{
Linearlist *list = (Linearlist*)malloc(sizeof(Linearlist)); // 分配空间
list ->last =0;       // 初始化节点值
return list;          // 返回初始化头节点指针
}void AppendNode(Linearlist *list,int n)
{if(list->last<MAXLISTSIZE)  // 顺序表不溢出{list ->data[list->last] = n; // 初始化节点值list ->last += 1;}}void insertNode(Linearlist *list,int n,int pos)   //插入人节点{int j;
if(pos < 0 || pos > list -> last)  // || 逻辑或运算  | 位运算 或  只要一个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++;                      // 顺序表长度加1}}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;                // 整型变量iLinkNode *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;      // 最后一个结点elsepre->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中的keypos=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 -10与1   0表示假  1表示真-1与0   -1表示语句执行不成共        0表示语句执行成功*/return -1;                // 一般的return -1;表示出错    return 0;表示正确elsereturn 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~299if(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);elseprintf("没有找到查找值%d\n",temp);}elseexit(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-1while(low<=high)          //因为数组已经排序 所以前半段中的数组元素必须小于等于后半段中的数组元素 low<=hign{mid=(low+high)/2;        // 折半查找中间值if(key<data[mid].key)    // 当待查找的数据小于折半中间值high=mid-1;          // 在折半的前一半重新查找elseif(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);elseprintf("没有找到查找值：%d\n",value);}elseexit(1); // 结束程序}return 0;}

六、排序方法

6.1、冒泡排序

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

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAX 20void 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类型的数组 数组长度为20int 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;     // 定义变量tempfor(i=1;i<count;i++)  // 遍历数组{             temp=arr[i];        // 创建初值   当前数组值存入临时变量tempj=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;}