太原理工大学数据结构试验报告.doc

《太原理工大学数据结构试验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验指导书计算机学院2012年10月实验一 线性表一．目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。二．例题[问题描述]用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。[输入]初始字符串，插入位置，插入字符，删除字符。[输出]已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。[存储结构]采用链式存储结构[算法的基本思想]建立链表：当读入字符不是结束符

2、时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。三．实习题1．设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。1．法一#includeintinsert(intx,int*a,intlen){intl,r,m;printf("%3d

3、->",x);l=-1;r=len;m=(l+r)/2;while(r-l>1){if(a[m]r;l--)a[l]=a[l-1];a[l]=x;}return++len;}voidprint(int*a,intl){inti;for(i=0;i

4、,0,0};intlen=10,t;printf("输入要插入得数：");scanf("%d",&t);print(a,len);len=insert(t,a,len);print(a,len);}心得：数组有随机存储的特性，因此可用数组来描述数据结构中的顺序存储。法二#include#includevoidmain(){intP[11],j,t,i,n,N;i=0;printf("输入10个数字：");for(i=0;i<10;i++){scanf("%d",&P[i]);}for(j=1;j<10;j++)for(t=0;t<

5、10-j;t++)if(P[t]>=P[t+1]){n=P[t];P[t]=P[t+1];P[t+1]=n;}for(i=0;i<=9;i++){printf("%5d",P[i]);}printf("");printf("输入要插入的数：");scanf("%d",&N);j=9;for(i=9;i>=0;i--){if(N<=P[i]){P[i+1]=P[i];j--;}else{P[i]=P[i];}}P[j+1]=N;printf("输出插入后数据：");for(i=0;i<=10;i++){printf("%5d",P[i]);}printf("")

6、;}输出结果：3.．设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。#include  #include  #define NULL 0 char typedef struct Lnode{  char name;  struct LNode *next; }LNode,*LinkList;  void writemember(Link

7、List L,int m,int i){  if(i>0){   int j=1;   while(jnext;    j++;   }   printf("%c >> ",L->next->name,i);   L->next=L->next->next;   writemember(L,m,--i);      } }   int ListInsert(LinkList head,int i,char e){  LinkList p=head,s;  int j=0;  while(p&&jn