《《数据结构与算法分析》课程设计：顺序表、单链表、顺序栈、查找、排序算法》由会员分享，可在线阅读，更多相关《《数据结构与算法分析》课程设计：顺序表、单链表、顺序栈、查找、排序算法（51页珍藏版）》请在金锄头文库上搜索。
1、*大学数据结构与算法分析课程设计题 目：数据结构上机试题学生姓名： 学 号：专 业：信息管理与信息系统班 级：指导教师： 2014 年 04 月数据结构与算法分析课程设计1目录一、顺序表的操作.2【插入操作原理】2【删除操作原理】2【NO.1 代码】.3【运行截图演示】7二、单链表的操作.10【创建操作原理】10【插入操作原理】10【删除操作原理】10【NO.2 代码】.11【运行截图演示】20三、顺序栈的操作.25【数值转换原理】25【NO.3 代码】.26【运行截图演示】30四、查找算法32【顺序查找原理】32【折半查找原理】32【NO.4 代码】.33【运行截图演示】38五、排序算法40
2、【直接插入排序原理】40【快速排序原理】40【NO.5 代码】.41【运行截图演示】46数据结构与算法分析课程设计2一、顺序表的操作一、顺序表的操作（1）插入元素操作：将新元素 x 插入到顺序表 a 中第 i 个位置；（2）删除元素操作：删除顺序表 a 中第 i 个元素。【插入操作原理插入操作原理】线性表的插入操作是指在线性表的第 i-1 个数据元素和第 i 个数据元素之间插入一个新的数据元素，就是要是长度为 n 的线性表：11,iinaaaa 变成长度为 n+1 的线性表： 11, ,iinaab aa 数据元素和之间的逻辑关系发生了变化。1iaia（其【插入原理】在课本 P23 的算法 2
3、.3 有解释）【删除操作原理删除操作原理】反之，线性表的删除操作是使长度为 n 的线性表： 111,iiinaaa aa 变成长度为 n-1 的线性表： 111,iinaaaa 数据元素、和之间的逻辑关系发生变化，为了在存储1iaia1ia结构上放映这个变化，同样需要移动元素。数据结构与算法分析课程设计3（其【删除原理】在课本 P24 的算法 2.4 有解释）【NO.1【NO.1 代码代码】#include#define MAX 100typedef int datatype;typedef structdatatype dataMAX;int list; sequenlist; /*顺序表*
4、/int main()int insert( sequenlist *L, int x, int i );int deletee( sequenlist *L, int i );int input( sequenlist *L );int output( sequenlist *L );sequenlist s,*p=int indata,inlocate,deletedx;input(p);printf( “请输入要插入的数：“ ); 数据结构与算法分析课程设计4scanf( “%d“,printf( “请输入要插入的位置：“ );scanf( “%d“,insert( p,indata,i
5、nlocate );printf( “插入后的数据：“ );output(p);printf( “请输入要删除的位置：“ );scanf( “%d“,deletee( p, deletedx );printf( “删除后的数据：“ );output(p);return 0;int output( sequenlist *L ) int i;for( i=0; ilist; i+ ) printf( “%d “,L-datai );printf( “nn“ );return(1);int input( sequenlist *L ) 数据结构与算法分析课程设计5int i;printf( “请输
6、入原始数据个数：“ );scanf( “%d“,L-list-; printf( “请输入原始数据：“ );for( i=0; i list; i+ ) scanf( “%d“,printf( “原始数据为：“ );output(L);return (1);int insert( sequenlist *L, int x, int i ) int j;if ( ( (*L).list )=MAX-1 )printf( “overflow“ ); return 0;elseif ( (i ( (*L).list )+1 ) )数据结构与算法分析课程设计6printf( “errorn“ ); r
7、eturn 0;else for ( j=L-list;j=i-1;j- )L-dataj+1=L-dataj;L-datai-1=x; L-list+;return(1);int deletee( sequenlist *L,int i ) /*定义删除函数*/ int j;if ( (i(L-list)+1 ) ) printf( “errorn“ );return 0; else 数据结构与算法分析课程设计7for ( j=i;jlist;j+ )L-dataj-1=L-dataj;L-list-;return(1);【运行截图演示运行截图演示】、如下面的运行截图所示，当输入的线性表长度
8、设置为 12 的时候，该线性表最多能输入 12 位数的长度。输入要插入的数和插入数的位置下标，便可以进行插入操作；同理当输入要执行删除操作数的位置下标，可以将该数删除出线性表。数据结构与算法分析课程设计8、如下面的运行截图所示，当初始设置的线性表长度为 5 的时候，其 5 个数分别是-3、4、5、0、1。若是要执行程序中输入的插入数字“2” ，其插入数的位置在“-4”的时候，程序是不能执行插入操作的。此时的线性表能插入的下标范围为“15” ，明显“-4”数值上限“5”数值，所以程序执行“error” 。数据结构与算法分析课程设计9、如下面的运行截图所示，初始设置的线性表插入数字 2 之后，要删
9、除位置 7 已超过线性表的最大长度 n=6，所以程序执行“error” 。、如下面的运行截图所示，同理该线性表要删除数的位置数据结构与算法分析课程设计10“0”下标不存在，所以程序执行“error” 。二、单链表的操作二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素 x 插入到单链表中第 i 个元素之后；（3）删除元素操作：删除单链表中值为 x 的元素。 【创建操作原理创建操作原理】在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储线性表的长度等的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位
10、置） 。【插入操作原理插入操作原理】为插入数据元素 x，首先要生成一个数据域为 x 的结点，然后数据结构与算法分析课程设计11插入在单链表中。根据插入操作的逻辑定义，还需要修改结点 a 中的指针域，令其指向结点 x，而结点 x 中的指针域应指向结点 b，从而实现 3 个元素 a、b 和 x 之间逻辑关系的变化。假设 s 为指向结点 x 的指针，则上述指针修改用语描述即为：s;nextpnext spnext 【删除操作原理删除操作原理】反之，在线性表中删除元素 b 时，为在单链表中实现元素 a、b和 c 之间逻辑关系的变化，仅需要修改结点 a 中的指针域即可。假设 p 为指向结点 a 的指针，
11、则上述指针修改用语描述即为：;pnextpnextnext 【NO.2【NO.2 代码代码】#include#includetypedef struct node /定义链表 int data;struct node *next;snode;snode* creat() /创建链表的函数 数据结构与算法分析课程设计12snode *head, *p, *q;head = (snode *)malloc(sizeof(snode);p = head;int x;printf(“请输入创建链表的值，用“0”结束输入。n“);printf(“x = “);scanf(“%d“, while (x !
12、= 0)q = (snode *)malloc(sizeof(snode);q-data = x;p-next = q;p = q;printf(“x = “);scanf(“%d“, p-next = NULL; return head;int length(snode *head)/测链表的结点数int i = 0;数据结构与算法分析课程设计13snode *p = head-next;while (p != NULL)p = p-next;i+; return i;void display(snode *head) snode *p = head-next;for(int i = 0;
13、i data);p = p-next;printf(“ “);int locate(snode *head, int x) snode *p = head-next;int i = 1;数据结构与算法分析课程设计14while (p != NULL i+;if (p = NULL) return 0;else return i;int insnode(snode *head, int x, int i) /把 x 插入到链表的第i 的位置 int j;snode *p = head-next, *s;if(i (length(head) + 1)return 0;else if (i = 1)
14、 s = (snode *)malloc(sizeof(snode); s-next = p; head-next = s; 数据结构与算法分析课程设计15s-data = x;else for (j = 1; j next;s = (snode *)malloc(sizeof(snode);s-next = p-next;p-next = s;s-data = x; return 1;int delnode(snode *head, int i)/删除链表中第 i 个结点snode *p = head-next, *q = head;if(i length(head)return 0;els
15、e if (i = 1) head-next = p-next;free(p);数据结构与算法分析课程设计16 else for (int j = 1; j next; q = q-next;q-next = p-next;free(p); return 1;void sort(snode *head) /把链表中每个结点的值按从小到大排列snode *p, *q;int k;for(p = head-next; p != NULL; p = p-next)for(q = p-next; q != NULL; q = q-next)if (p-data q-data) k = p-data; p-data = q-data; 数据结构与算法分析课程设计17q-data = k; void insert(snode *head, int x) /在有序链表中插入 x,插入后仍保持有序 snode *p = head-next, *s,
