表插入排序
一、目的
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。
二、需求分析
******
三、概要设计
1、本程序包括7个模块:
（1）主程序模块：
main(){
    定义及初始化；
    输出菜单，根据用户的输入调用对应的函数将要进行排序的数字保存至数组中；
    用数组对链表进行初始化，并输出初始化之后的表结构；
    修改next域形成有序的循环链表,并显示每一步具体执行过程；
    输出调整后的表结构最终结果，并将结果保存至文件。
}
（2）菜单模块；
（3）从键盘读取要进行排序的数字，并将其保存至数组的模块；
（4）从文件读取要进行排序的数字，并将其保存至数组的模块；
（5）对链表进行具体操作的模块；
（6）输出每一步执行情况的模块；
（7）将最终结果写入文件的模块。
2、函数定义:
menu()
操作结果：输出选项供用户选择.
manualInput(int n,int* values)
n数组的长度，values存储数据的整形数组
操作结果：手动输入需要进行排序的数字并保存至数组.
fileIuput(int n,int* values)
n数组的长度，values存储数据的整型数组
操作结果：从文件中读取数据并保存至数组.
Arrange(SqList* SL,int* values,int count)
linkList事先定义好，将被处理的链表，values存储数据的整型数组，count是数组的长度
操作结果：用数组对链表进行初始化，并用表插入算法对其进行排序，使SL中记录按关键字非递减有序顺序排列.
Print(SqList* SL)
SL已被定义好的链表
操作结果：输入每一步进行相应处理之后的表结构.
FileWrite(SqList* SL,int length)
SL已被定义好的链表，length进行排序的数字的个数
操作结果：将排序之后的最终结果写入文件.
四、详细设计
链表的定义
typedef int KeyType;
typedef int InfoType;
typedef struct
{    KeyType value;    //记录项
    InfoType next;  //指针项
}RedType;    //表结点类型
typedef struct
{    SLNode numbers[SIZE];  //0号节单元为表头结点
    int length;    //链表当前长度
}SqList;        //链表当前类型
定义的链表的最大长度
#define SIZE 100
全局变量
int len;  /链表的长度
局部变量
SLinkList sl;  //静态链表
int i ,num;    /*  i用于读取用户的选项，执行对应操作;num存放进行排序的数字的个数，也即数组的长度  */
int a[50];    /*存放被排序的数字的整型数组*/
字符串长度排序RedType temp;  //进行交换时的辅助节点
system("color 3E");    /*调整屏幕的背景和文字颜*/
定义文件指针
FILE *f,*fp; 
f=fopen("C:\\Users\\Administrator\\Desktop\\","at+"  //以“追加”方式将数据写入文件
fp=fopen("C:\\Users\\Administrator\\Desktop\\","r"  //以“读”方式打开文件
往文件中写入数据
fputs("\n",f);  //往文件中写入换行符
fprintf(f,"%4d",SL->numbers[j].value);  //往文件中写入value值
fscanf(fp,"%d",&values[j]);  //读取文件中的数字并保存至数组
关闭文件
fclose(f);    fclose(fp);   
//头节点指示第一个元素，并赋予整形最大值
SL->numbers[0].value = INT_MAX;    SL->numbers[0].next = 1; 
for(i=1;i<=count;i++)
{    //用数组对链表进行初始化
SL->numbers[i].value = values[i-1];         
SL->numbers[i].next = 0;  //指针项都初始化为0    }
q=0;          p = SL->numbers[0].next;
while( SL->numbers[i].value > SL->numbers[p].value )
{    //修改next域形成有序的循环链表
    q = p;  //若i的value值大于p的value值，链表后移
p = SL->numbers[p].next;      }
}
//将当前记录插入链表
SL->numbers[q].next = i;      SL->numbers[i].next = p;
// 根据next域调整数组，使链表中记录按关键字非递减有序顺序排列
p = SL->numbers[0].next;  //p指示第一个记录的当前位置
while (p<i)     //第i个记录在SL中的当前位置应不小于i
{    //到第i个记录，并用p指示其在链表中当前位置
    p = SL->numbers[p].next;          }
    q = SL->numbers[p].next; // q指示尚未调整的表尾
if (p!= i)
  {    //p与i不相等时，交换p节点与i节点的内容，使第i个记录到位
    temp=SL->numbers[p];
    SL->numbers[p]=SL->numbers[i];
    SL->numbers[i]=temp;
//指向被移走的记录，使得以后可由while循环回
SL->numbers[i].next=p;    }
    p=q;        //链表后移
整个程序的流程图如下：
五、调试分析
1、**************************************************************
六、 测试结果
七、 用户使用说明
1、本程序在DEV-C++5能运行。
2、*********************************
八、 课程设计总结
通过这个程序，对表插入排序算法有了更深刻的了解。**************************************************************************

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。