1 实验2 顺序表其它操作 2 实验目的 3 1.进一步掌握在线性表的顺序存储结构上的一些其它操作。 4 实验内容 5 程序1 6 已知一个线性表，用另辟空间和利用原表两种方法把线性表逆置。 7 设计要求：在程序中构造三个子程序分别为 8 SeqList reverse(SeqList A) /*顺序表的就地逆置 */ 9 void ListTraverse(SeqList L) /* 遍历顺序表 */10 SeqList create(int n) /* 建立顺序表 */11 12 程序213 已知两个非递减有序的线性表LA和LB，将LA和LB合并成一个线性表LC，LC也非递减有序。14 设计要求：在程序中构造三个子程序分别为15 SeqList MergeSeqList(SeqList La,SeqList Lb) /*合并顺序表*/16 void ListTraverse(SeqList L) /* 遍历顺序表 */17 SeqList create() /* 建立顺序表 */18 19 程序320 已知两个非递减有序的线性表LA和LB，长度分别为m和n，假设LA的空间足够大，利用原表LA，将LA和LB合并成一个仍然非递减有序的线性表。要求时间复杂度为O(m+n)。21 设计要求：在程序中构造三个子程序分别为22 SeqList MergeSeqList(SeqList La,SeqList Lb,int m,int n)23 /*合并顺序表*/24 void ListTraverse(SeqList L) /* 遍历顺序表 */25 SeqList create() /* 建立顺序表 */26 27 程序428 约瑟夫环问题：任给正整数N和K，按下述方法可以得到1,2, …,n的一个置换，将数字1,2,…,n环形排列，按顺时针方向自1开始报数，报到K时输出该位置上的数字，并使其出列。然后从他在顺时针方向的下一个数字继续报数，如此下去，直到所有的数字全部出列为止。例如N=10，K=3，则正确的出列顺序应为3，6，9，2，7，1，8，5，10，4。29 设计要求：在程序中构造一个子程序为30 void Js(int n,int k) /*按正确的输出次序输出约瑟夫环中的元素*/
1 /* 2 程序1 3 已知一个线性表，用另辟空间和利用原表两种方法把线性表逆置。 4 设计要求：在程序中构造三个子程序分别为 5 SeqList reverse(SeqList A) //顺序表的就地逆置 6 void ListTraverse(SeqList L) //遍历顺序表 7 SeqList create(int n) //建立顺序表 8 */ 9 10 #include11 #include 12 13 //顺序表的大小 14 #define MAXSIZE 1000 15 16 //顺序表的存储数据类型 17 typedef int DateType; 18 19 typedef struct{ 20 DateType data[MAXSIZE]; 21 int length; 22 }SeqList; 23 24 SeqList reverse1(SeqList A) //顺序表的就地逆置 25 { 26 int i; 27 for(i=0;i =0;i--) 41 B.data[A.length-i-1] = A.data[i]; 42 B.length = A.length; 43 printf("逆置成功\n"); 44 return B; 45 } 46 void ListTraverse(SeqList L) //遍历顺序表 47 { 48 int i; 49 for(i=0;i
1 /* 2 程序2 3 已知两个非递减有序的线性表LA和LB，将LA和LB合并成一个线性表LC，LC也非递减有序。 4 设计要求：在程序中构造三个子程序分别为 5 SeqList MergeSeqList(SeqList La,SeqList Lb) //合并顺序表 6 void ListTraverse(SeqList L) //遍历顺序表 7 SeqList create() //建立顺序表 8 */ 9 10 #include11 #include 12 13 //顺序表的大小 14 #define MAXSIZE 1000 15 16 //顺序表的存储数据类型 17 typedef int DateType; 18 19 typedef struct{ 20 DateType data[MAXSIZE]; 21 int length; 22 }SeqList; 23 24 SeqList La,Lb,Lc; 25 26 SeqList MergeSeqList(SeqList La,SeqList Lb) //合并顺序表 27 { 28 SeqList Lc; 29 int i = 0,j = 0,k = 0; 30 while(i!=La.length && j!=Lb.length){ //依次将La和Lb中较小的元素放入Lc中 31 if(La.data[i] < Lb.data[j]) 32 Lc.data[k++] = La.data[i++]; 33 else 34 Lc.data[k++] = Lb.data[j++]; 35 } 36 while(j!=Lb.length) 37 Lc.data[k++] = Lb.data[j++]; 38 while(i!=La.length) 39 Lc.data[k++] = La.data[i++]; 40 Lc.length = La.length + Lb.length; 41 printf("合并顺序表成功!\n"); 42 return Lc; 43 } 44 void ListTraverse(SeqList L) //遍历顺序表 45 { 46 int i; 47 for(i=0;i
1 /* 2 程序3 3 已知两个非递减有序的线性表LA和LB，长度分别为m和n，假设LA的空间足够大，利用原表LA，将LA和LB合并成一个仍然非递减有序的线性表。要求时间复杂度为O(m+n)。 4 设计要求：在程序中构造三个子程序分别为 5 SeqList MergeSeqList(SeqList La,SeqList Lb,int m,int n) //合并顺序表 6 void ListTraverse(SeqList L) // 遍历顺序表 7 SeqList create() // 建立顺序表 8 */ 9 10 #include11 #include 12 13 //顺序表的大小 14 #define MAXSIZE 1000 15 16 //顺序表的存储数据类型 17 typedef int DateType; 18 19 typedef struct{ 20 DateType data[MAXSIZE]; 21 int length; 22 }SeqList; 23 24 SeqList La,Lb,Lc; 25 26 SeqList MergeSeqList(SeqList La,SeqList Lb,int m,int n) //利用原表LA合并顺序表 27 { 28 int i = La.length - 1,j = Lb.length - 1,k = m + n - 1; 29 while(i>=0 && j>=0){ //将较大的元素放到后面 30 if(La.data[i] > Lb.data[j]) 31 La.data[k--] = La.data[i--]; 32 else 33 La.data[k--] = Lb.data[j--]; 34 } 35 while(i>0) 36 La.data[k--] = La.data[i--]; 37 while(j>0) 38 La.data[k--] = Lb.data[j--]; 39 La.length = m + n; 40 printf("合并顺序表成功！\n"); 41 return La; 42 } 43 44 void ListTraverse(SeqList L) //遍历顺序表 45 { 46 int i; 47 for(i=0;i
1 /* 2 程序4 3 约瑟夫环问题：任给正整数N和K，按下述方法可以得到1,2, …,n的一个置换，将数字1,2,…,n环形排列，按顺时针方向自1开始报数，报到K时输出该位置上的数字，并使其出列。然后从他在顺时针方向的下一个数字继续报数，如此下去，直到所有的数字全部出列为止。例如N=10，K=3，则正确的出列顺序应为3，6，9，2，7，1，8，5，10，4。 4 设计要求：在程序中构造一个子程序为 5 void Js(int n,int k) //按正确的输出次序输出约瑟夫环中的元素 6 */ 7 8 #include9 #include 10 11 //顺序表的大小12 #define MAXSIZE 100013 14 //顺序表的存储数据类型15 typedef int DateType;16 17 typedef struct{18 DateType data[MAXSIZE];19 int length;20 }SeqList;21 22 SeqList sq;23 24 SeqList create(int n) //建立顺序表25 {26 SeqList sq; //分配顺序表的空间27 sq.length = n;28 return sq;29 }30 31 32 /* 检查顺序表是否为空 */33 34 int ListEmpty(SeqList L)35 {36 if(L.length==0) //是空的37 return 1;38 else //不是空的39 return 0;40 }41 42 43 /* 从顺序表中删除元素 */44 45 void ListDelete(SeqList* L,int i) 46 {47 int j;48 for(j=i;j length;j++){ //向前覆盖 49 L->data[j-1] = L->data[j]; 50 }51 L->length--; //长度减152 return ;53 }54 55 void Js(int n,int k) //按正确的输出次序输出约瑟夫环中的元素56 {57 int t = 0;58 printf("约瑟夫环中的元素:\n");59 while(!ListEmpty(sq)){60 t = (t + k - 1) % sq.length;61 printf("%d ",sq.data[t]);62 ListDelete(&sq,t+1);63 }64 printf("\n");65 }66 67 int main()68 {69 int n,k;70 printf("请输入N和K:（输入 0 0 停止）\n");71 while(scanf("%d%d",&n,&k)!=EOF){72 if(n==0 && k==0) break;73 sq = create(n);74 printf("请给顺序表赋值\n");75 int t;76 for(t=1;t<=sq.length;t++){77 scanf("%d",&sq.data[t-1]);78 }79 Js(n,k); //按正确的输出次序输出约瑟夫环中的元素80 printf("\n");81 printf("请输入N和K:（输入 0 0 停止）\n");82 }83 return 0;84 }