数据结构课程设计.doc

桂林航天工业学院实验报告系（部）：计算机科学与工程系课程名称:数据结构专业班级:计算机应用技术1班学号:学生姓名:完成日期：2016年12月22日运行环境操作系统：Windows1064位操作系统编译软件：MicrosoftVisualC++6.0处理器：Intel（R）Core（TM）2CPU6320@1.86GHz1.86GHz安装内存（RAM）：2.00GB算法设计的思想和设计分析及流程图1.线性表的顺序存储1．插入：算法思想：查找到元素X需要插入到线性表L的位置i，将该位置i后面的元素后移，将要元素X插入到i位置，表长加1。设计分析：先使用if(L->last==MAXSIZE1-1)提示空间满elseif(i<1||i>L->last+2)提示位置错误函数判断位置i在该线性表L中是否存在，若位置i正确再使用for(j=L->last;j>=i-1;j--){L->data[j+1]=L->data[j];}使该位置i后面的数据元素后移，然后将数据元素插入到位置i，表长加1。流程图：2．删除：算法思想：先判断线性表L是否存在数据元素i，然后在线性表L中删除序号为i的数据元素，删除后使序号为i+1,i+2,...,n的元素变为序号为i,i+1,...,n-1，删除后新表长=原表长-1。设计分析：先使用if(i<1||i>L->last+1)提示数据元素不存在判断元素i在线性表L中是否存在，若数据元素i存在再使用for(j=i;j<=L->last;j++){L->data[j-1]=L->data[j];}L->last--;使数据元素i后面的数据元素前移，将数据元素i覆盖删除，然后表长减1。流程图：3．查找：算法思想：调用函数查找数据元素i，如果其调用函数结果返回在线性表L中首次出现的值为i的那个元素的序号或地址，称为查找成功;否则，在L中未找到值为ｘ的数据元素，返回某特殊值表示查找失败。设计分析：先使用while(y<=L->last&&L->data[y]!=x)y++;查找数据元素i在线性表L中的位置，如果查找失败则使用if(y>L->last)return-1;返回特殊值，否则使用elsereturny+1;返回该数据元素的地址。流程图：4．Main主函数：算法思想：使用Do…while实现主函数的菜单界面，使用switch…case实现函数的调用。设计分析：使用do…while做出主菜单，使用scanf("%d",&k);getchar();switch(k){case1:case2:case3:case4:case5:}实现函数的调用。2.线性表的链式存储1．建表：算法思想：使用头插入法建立单链表，该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。设计分析：使用p=(LNode2*)malloc(sizeof(LNode2));开辟一个动态空间使用p->data=c;p->next=head;进行赋值和使指针后移，再用head=p;使head与p同指向。流程图：2．按序号查找：算法思想：调用函数查找数据元素i，从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0个结点。设计分析：使用while(p->next&&j<i)限定i的合法性使用p=p–>next;j++;进行地址和指针后移，再用if(i==j)returnp;elsereturnNULL;返回查找结果。流程图：3．插入：算法思想：插入运算是将值为x的新结点插入到表的第i个结点的位置上首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*q，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。设计分析：使用p=Get_LinkList(L,i-1);if(p==NULL){printf("位置错误");return0;}判断i的是否存在，若存在，则使用q=(LNode*)malloc(sizeof(LNode));q->data=x;q->next=p->next;p->next=q;进行插入，再用return1返回插入结果。流程图：4．删除：算法思想：将表的第i个结点删去，是在单链表中结点ai的存储地址是在其直接前趋结点aai-1的指针域next中，所以我们必须首先找到ai-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。设计分析：使用p=Get_LinkList(L,i-1);if(p->next==NULL){return0;}判断i