数据结构与算法分析课程设计.doc

数据结构与算法分析课程设计*大学数据结构与算法分析课程设计题 目：数据结构上机试题学生姓名： 学 号：专 业：信息管理与信息系统班 级：指导教师： 2014年04月目录一、顺序表的操作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【直接插入排序原理】40【快速排序原理】40【NO.5代码】41【运行截图演示】46一、顺序表的操作（1）插入元素操作：将新元素x插入到顺序表a中第i个位置；（2）删除元素操作：删除顺序表a中第i个元素。【插入操作原理】线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要是长度为n的线性表：变成长度为n+1的线性表：数据元素和之间的逻辑关系发生了变化。（其【插入原理】在课本P23的算法2.3有解释）【删除操作原理】反之，线性表的删除操作是使长度为n的线性表：变成长度为n-1的线性表：数据元素、和之间的逻辑关系发生变化，为了在存储结构上放映这个变化，同样需要移动元素。（其【删除原理】在课本P24的算法2.4有解释）【NO.1代码】#include#define MAX 100typedef int datatype;typedef structdatatype dataMAX;int list; sequenlist; /*顺序表*/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=&s; int indata,inlocate,deletedx; input(p); printf( 请输入要插入的数： ); scanf( %d,&indata ); printf( 请输入要插入的位置： ); scanf( %d,&inlocate ); insert( p,indata,inlocate ); printf( 插入后的数据： );output(p);printf( 请输入要删除的位置： ); scanf( %d,&deletedx );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 ) int i;printf( 请输入原始数据个数： ); scanf( %d,&( L-list ) ); L-list-; printf( 请输入原始数据： ); for( i=0; i list; i+ ) scanf( %d,&( L-datai ) ); printf( 原始数据为： ); output(L); return (1);int insert( sequenlist *L, int x, int i ) int j; if ( ( (*L).list )=MAX-1 ) printf( overflow ); return 0; else if ( (i ( (*L).list )+1 ) ) printf( errorn ); return 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 for ( j=i;jlist;j+ ) L-dataj-1=L-dataj;L-list-; return(1);【运行截图演示】、如下面的运行截图所示，当输入的线性表长度设置为12的时候，该线性表最多能输入12位数的长度。输入要插入的数和插入数的位置下标，便可以进行插入操作；同理当输入要执行删除操作数的位置下标，可以将该数删除出线性表。、如下面的运行截图所示，当初始设置的线性表长度为5的时候，其5个数分别是-3、4、5、0、1。若是要执行程序中输入的插入数字“2”，其插入数的位置在“-4”的时候，程序是不能执行插入操作的。此时的线性表能插入的下标范围为“15”，明显“-4”数值上限“5”数值，所以程序执行“error”。、如下面的运行截图所示，初始设置的线性表插入数字2之后，要删除位置7已超过线性表的最大长度n=6，所以程序执行“error”。、如下面的运行截图所示，同理该线性表要删除数的位置“0”下标不存在，所以程序执行“error”。二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素x插入到单链表中第i个元素之后；（3）删除元素操作：删除单链表中值为x的元素。 【创建操作原理】在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储线性表的长度等的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。【插入操作原理】为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中。根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。假设s为指向结点x的指针，则上述指针修改用语描述即为： 【删除操作原理】反之，在线性表中删除元素b时，为在单链表中实现元素a、b和c之间逻辑关系的变化，仅需要修改结点a中的指针域即可。假设p为指向结点a的指针，则上述指针修改用语描述即为：【NO.2代码】#include#includetypedef struct node /定义链表 int data; struct node *next;snode;snode* creat() /创建链表的函数 snode *head, *p, *q;head = (snode *)malloc(sizeof(snode); p = head; int x; printf(请输入创建链表的值，用“0”结束输入。n); printf(x = ); scanf(%d, &x); while (x != 0)q = (snode *)malloc(sizeof(snode);q-data = x;p-next = q;p = q;printf(x = );scanf(%d, &x); p-next = NULL; return head;int length(snode *head)/测链表的结点数int i = 0;snode *p = head-next;while (p != NULL)p = p-next;i+; return i;void display(snode *head) snode *p = head-next;for(int i = 0; i data); p = p-next; printf( );int locate(snode *head, int x) snode *p = head-next; int i = 1; while (p != NULL & x != p-data)p = p-next;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) s = (snode *)malloc(sizeof(snode); s-next = p; head-next = s; s-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; else if (i = 1) head-next = p-next; free(p); 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; q-data = k; void insert(snode *head, int x) /在有序链表中插入x,插入后仍保持有序 snode *p = head-next, *s, *q = head; while (p != NULL & p-data next; p = p-next; s = (snode *)malloc(sizeof(snode);s-next = q-next; s-data = x; q-next = s;void del_min_max(snode *head, int min, int max) /删除有序链表中值min到值max中的结点snode *p = head-next, *q = head; while (p != NULL & p-data next; while (p != NULL & p-data next = p-next; free(p); p = q-next; void del_min(snode *head) snode *p = head-next, *q = head; snode *p_min, *q_min; p_min = p; q_min = q;while (p != NULL)q = p; p = p-next; if (p != NULL & p-data data)q_min = p_min; p_min = p; q_min-next = p_min-next; free(p_min);int main() int min, max; snode *headl = creat(); /创建链表 printf(最初的链表如下：); display(headl);printf(nn); int num, location; printf(请输入您要查找的数：);scanf(%d, &num); if (locate(headl, num) printf(数字%d在链表中的位置为：%dnn, num, locate(headl, num); else printf(数字%d在链表中不存在!nn, num); printf(请分别输入您要插入到链表中的数以及想插入的位置（用空格号间隔开）：); scanf(%d %d, &num, &location); if (insnode(headl, num, location) printf(插入新值以后的链表如下：); display(headl);printf(nn); else printf(输入有误!nn); printf(请输入您想删除的结点位置：); scanf(%d, &location); if (delnode(headl, location) printf(删除第%d个结点后的链表如下：, location); display(headl);printf(nn); elseprintf(输入有误! nn);【运行截图演示】、如下面的运行截图所示，创建带有头结点且长度为8的单链表：4、8、2、-4、-6、1、9、-1。输入要查询的数“-6”，则查询到单链表中数“-6”的存储位置为“5”的下标号。输入要插入的数和插入数的位置下标，便可以进行插入操作。程序中要求插入的数是“3”，插入数的位置下标为“5”，两者之间用空格号隔开，则插入后的新单链表为：4、8、2、-4、3、-6、1、9、-1。同理当输入要执行删除操作的数位置下标，可以对该数删除出线性表。程序中要求删除的数下标是7，则执行该删除操作之后的新单链表为：4、8、2、-4、3、-6、9、-1。、如下面的运行截图所示，创建带有头结点且长度为8的单链表，要查询的数“3”不在该单链表中，所以程序执行“error”。、如下面的运行截图所示，创建带头结点且长度为8的单链表，要插入数的位置下标“-1”不在该单链表中，所以程序执行“error”。、如下面的运行截图所示，创建带头结点且长度为8的单链表，要插入的位置下标“9”为单链表最大长度，所以程序执行插入操作。、如下面的运行截图所示，创建带头结点且长度为8的单链表，要插入的位置下标“10”超出单链表长度，所以程序不执行插入操作。、如下面的运行截图所示，创建带头结点且长度为8的单链表，要删除数的位置下标“-2”不在该单链表中，所以程序执行“error”。、如下面的运行截图所示，创建带头结点且长度为8的单链表，要删除数的位置下标“10”超出单链表长度，所以程序执行“error”。三、顺序栈的操作在顺序栈上实现将非负十进制数转换成二进制数。【数值转换原理】十进制数N和其他d进制数的转换时计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：（其中：div为整除运算，mod为求余运算）假设现在要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的二进制数。由于上述计算过程是从低位到高位顺序产生二进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的二进制数的各位顺序进栈，则按出栈序列打印输出的即为输入对应的二进制数。（其【数值转换】在课本P48的算法3.2有解释）【NO.3代码】#include #include #define MaxSize 50typedef char ElemType;char digit = 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ;typedef structElemType dataMaxSize;int top;SqStack;void InitStack(SqStack *&s)s = (SqStack *)malloc(sizeof(SqStack);s - top = -1;int Push(SqStack *&s, ElemType e)if(s - top = MaxSize - 1)return 0;s - top+;s - datas - top = e;return 1;int Pop(SqStack *&s, ElemType &e)if(s - top = -1)return 0;e = s - datas - top;s - top-;return 1;int GetTop(SqStack *s, ElemType &e)if(s - top = -1)return 0;e = s - datas - top;return 1;void DispStack(SqStack *s) int i;for(i = s - top; i = 0; i-) printf(%c, s - datai);printf(n);int fun(SqStack *s,int num, int k) /可将十进制转换成任意进制static int count = 0;int n;if(num k)Push(s, digitnum);return count;n = num % k;Push(s, digitn);fun(s,num/k, k);int main()SqStack *t;int i;InitStack(t);printf(请输入一个非负十进制数：);scanf(%d, &i);fun(t, i, 2); printf(其二进制数为：);DispStack(t);free(t);return 0;【运行截图演示】、如下面的运行截图所示，输入非负十进制整数“14”，经过数值转换之后的二进制数为“1110”。、如下面的运行截图所示，输入十进制整数“-2”，由于“-2”为负数，所以无法经过数值转换为二进制数。、如下面的运行截图所示，输入非负十进制整数“0”，经过数值转换之后的二进制数为“0”。四、查找算法在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置。【顺序查找原理】从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。在等概率情况下顺序查找的平均长度为：【折半查找原理】先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。折半查找过程是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小小于零时（表明查找不成功）为止。假设表中每个记录的查找概率相等，则查找成功时折半查找的平均查找长度：【NO.4代码】#include #include #define MAXL 1000#define INF 32767int processMAXL,pn;/顺序表的存储结构typedef int KeyType;typedef int InfoType;typedef struct KeyType key;InfoType data; NodeType;typedef NodeType SeqListMAXL;/索引表的存储结构typedef struct KeyType key;int link; IdxType;typedef IdxType IDXMAXL;/顺序查找算法int SeqSearch(SeqList R,int n,KeyType k) int i=0; pn=0; while(i=n) return -1; else return i; /折半查找算法int BinSearch(SeqList R,int n,KeyType k) int low=0,high=n-1,mid; pn=0; while(lowk) processpn+=Rmid.key;high=mid-1; else processpn+=Rmid.key;low=mid+1; return -1; int main() int n,i,k,m; SeqList R; IDX I; printf(1)请输入有/无序顺序表的元素个数：n); while(scanf(%d,&n)!=EOF) printf(请输入有/无序顺序表的%d个元素：n,n); for(i=0;in;i+) scanf(%d,&Ri.key); printf(请输入要查找的关键字：n);scanf(%d,&k); printf(使用顺序查找算法，); if(SeqSearch(R,n,k)!=-1) printf(关键字%d的下标为：n%dtn查找过程为：n,k,SeqSearch(R,n,k); for(i=0;ipn;i+) printf(%d ,processi); printf(%dnn,k); else printf(要查找的关键字%d不在无序顺序表中nn,k); printf(2)请输入有序顺序表的元素个数：n);/10 scanf(%d,&n);printf(请输入有序顺序表的%d个元素：n,n); for(i=0;in;i+) scanf(%d,&Ri.key); printf(请输入要查找的关键字：n);scanf(%d,&k); printf(使用折半查找算法，); if(BinSearch(R,n,k)!=-1) printf(关键字%d的下标为：n%dtn查找过程为：n,k,BinSearch(R,n,k); for(i=0;ipn;i+) printf(%d ,processi); printf(%dnn,k); else printf(要查找的关键字%d不在有序顺序表中nn,k); return 0;【运行截图演示】、如下面的运行截图所示，使用顺序查询算法和折半查找算法，查找数“5”，其查找过程分别为：-3、5、8、9、-2、-1；3、-2、-1。、如下面的运行截图所示，在无序顺序表中使用顺序查询算法，查找数“6”，因数“6”位置下标超过表最大长度，即程序查找不到。、如下面的运行截图所示，在无序顺序表中使用顺序查询算法，查找数“1”，因为数“1”不在该表中，所以程序查找不到数“1”。、如下面的运行截图所示，在有序顺序表中使用折半查询算法，查找数“1”，因为数“1”不在该表中，所以程序查找不到数“1”。五、排序算法将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。【直接插入排序原理】是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。排序的基本操作为：比较两个关键字的大小和移动记录。先分析一趟插入排序的情况。For循环的次数取决于待插记录的关键字与前i-1个记录的关键字之间的关系。则在整个排序过程（进行n-1趟插入排序）中，当待排序列中记录按关键字非递减有序排列，所需进行关键字间比较的次数达最小值n-1，记录不需移动；反之，当待排序列中记录按关键字非递增有序排列是，总的比较次数达到最大值，记录移动的次数也达最大值。若待排序记录是随机的，即待排序列中的记录可能出现的各种排列的概率相同，则我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行关键字间的比较次数和移动记录的次数。【快速排序原理】快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。【NO.5代码】#include#include#define MAX 100/将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列typedef struct int dataMAX;int length;sqlist;void init(sqlist &a)/线性表初始化a.length=0;void insert(sqlist &a ,int i,int x)/ 插入元素,构造无序数列int j;if(ia.length+1|a.length=100);elsefor(j=a.length+1;ji;j-)a.dataj=a.dataj-1;a.dataj=x;a.length+; /放在a.datan中，被排序的记录放在a.data0.n-1中，直接插入排序算法。void insertsort(sqlist &a)/直接插入排序算法int i,j;int n=a.length;for(i=n-2;i=0;i-) if(a.dataia.datai+1) a.datan=a.datai;/a.datan是哨兵 j=i+1; do a.dataj-1=a.dataj; j+;while(a.dataja.datan);a.dataj-1=a.datan;int Partition(sqlist &a,int i,int j)int pivot=a.datai;while(ij)while(i=pivot) j-; if(ij) a.datai+=a.dataj; while(ij&a.datai=pivot) i+; if(ij) a.dataj-=a.datai;