数据结构实验报告1顺序表-田媛.doc

南方医科大学生物医学工程学院_电子信息工程_系数据结构实验报告姓名田媛学号113200880200009专业年级08电子信息工程单元第2章内容线性表日期2010-6-7实验题目实验一 线性结构（综合性实验 3学时）实验目的本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可复习高级语言的使用方法。实验内容 一、必做题：二、选做题：问题描述 约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据 m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。实验要求及讨论（本次实验的要求是否达到，有何问题，是怎么解决的）一、 抄写自己所选择的题目。二、 写出算法设计思路。三、 编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范围等可能出现的异常问题）。 四、写出算法设计、编程和调试运行的体会。一、 抄写自己所选择的题目。1、已知一顺序表A，其元素非递减有序排列，编写一个算法，删除顺序表中值相同多余的元素（相同值保留一个）。2、已知带头结点的单链表L中的节点是按整数值递增排序的，试写一算法，将值为x的节点插入到表L中，使得表L仍然有序。分析算法的时间复杂度。二、 写出算法设计思路。1建立一个顺序表用于存储一组非递减排序的整形数据，对顺序表中的每个元素与其下一个元素进行比较操作。用指针记录当前所比较的元素，如果相等则对当前指针所指向的元素进行删除操作，并将它后面的数据前移，再与下一个元素比较，如果还相等就继续删除操作，否则指向下个元素，再比较直至无重复的元素。2. 建立一个带头节点的单链表，其节点按整数值递增排序。创建一个新的节点，并由键盘输入节点的值。将其与链表中原有的节点（头节点不参与比较）按顺序作比较，并用指针指向当前的位置，若不大于当前节点，则在当前位置这前作插入操作，否则在最后作插入操作。三、编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范围等可能出现的异常问题）。解1#include stdio.h#include conio.h#define SIZE 18#define ERROR 0#define OK 1int length; /* 定义宏观变量*/typedef int status;typedef struct int *elem; int length; int listsize; SqList;status ListDelete(SqList *L) /*删除顺序表L中值相同多余的元素（相同值保留一个）*/ int i=0,j,n=0; SqList *p=L; if(!p) return ERROR; while(ilength) if(*(p-elem+i)=*(p-elem+i+1) /*删除相同多余的元素*/ for(j=i;jlength;j+) *(p-elem+j)=*(p-elem+j+1); n+; p-length-; if(!(*(p-elem+i)=*(p-elem+i+1) /*判断第i个数是否任和下一个数相同*/ i+; length=SIZE-n; return n;main()int aSIZE=1,2,2,5,6,7,7,12,13,13,13,18,19,20,21,24,24,39,t; int n,m; SqList A; A.elem=a; for(n=0;nSIZE;n+) printf(%d ,an); A.length=A.listsize=SIZE; t=ListDelete(&A) ; if(!t)printf(ListDelete ERROR!n); else printf(nThe new one is:n); for(n=0;ndata=ai;for(i=1;inext=(node *)malloc(sizeof(node); p=p-next; p-data=ai;p-next=NULL;L-next=h;return OK;status ListInsert(node *L,int x) int i,k; for(i=0;i=ai&x=k;i-) ai+1=ai; ak=x; main()node *L,*p; int t,x,i,k; printf(Please input the number you want to insert x:n); scanf(%d,&x); printf(The List is:n); for(i=0;iSIZE;i+) printf(%d ,ai); printf(nAfter inert,the new one is:n); L=(node *)malloc(sizeof(node); if(!L) printf(ERROR!n);return; t=CreatList(L); /*创建链表*/ if(!t) printf(ERROR!n);return; ListInsert(L,x); for(i=0;iSIZE+1;i+) printf(%d ,ai); getch();时间复杂度为：O(n)四、