赞
踩
数据结构进阶实训课程笔记和算法练习
输入数字n,按顺序打印输出从1到最大的n位十进制数。比如输入3,则打印出1,2,3,一直到最大的3位数999。
- 要考虑若n很大,我们求最大的n位数用int 或long long 也可能会溢出;
- 考虑大数问题;
- 提示:关于大数的表示和存储:用字符数组(取值为数字型字符)来表达大数
这题主要解决大数问题。我用字符串来解决大数问题。
那么字符串中所有字符都是数字;
首先动态分配字符串空间为(n+1)*char,字符串最后要有一个结束符’\0’,初始化其他位为0;
然后每一次为字符串表示的数字加1,再打印出来;
方法print()会遍历字符串,直到遇到第一个非0字符后,打印后面的字符;
关键方法printRecursively(),每10个数,对具体位数加1,然后进位,递归。
void printRecursively(char *number, int n, int index){ int i; if(index == n){ print(number, n); return; } for(i = 0; i<10; i++){ number[index] = i + '0'; // printf("NUMBER: %s\n", number); printRecursively(number, n, index + 1); } } void printToMaxOfNDigits(int n){ if (n <= 0) return; char *number = (char *)malloc((n+1)*sizeof(char)); memset(number, '0', (n+1)*sizeof(char)); // 在一段内存块中填充某个给定的值,初始化为0 number[n] = '\0'; printRecursively(number, n, 0); free(number); }
已知一个顺序表L(整数)
实现一个函数将调整顺序表中的数字顺序,使得所有奇数位于表L的前半部分,所有偶数位于数组的后半部分。
- 如果把题目改成把顺序表中的数按照大小分为两部分,负数都在非负数的前面,该怎么做?再定义一个函数??
- 或者再改为:把顺序表中的数分为两部分,
能被3整除的数放在前面,不能被3整除的数放在后面;再定义一个函数??
- 是否有更好的办法?增加代码的可扩展性。
定义一个规则rule方法,根据用户输入,确定排序规则,增加代码复用性;
三种排序规则思想一样:
(1)start=0从顺序表头开始往后,end从尾开始往前,
start遇到偶数停止,end遇到奇数停止,交换下标为start和下标为end的元素,然后继续前进;
(2)start=0从顺序表头开始往后,end从尾开始往前,
start遇到正数停止,end遇到负数停止,交换下标为start和下标为end的元素,然后继续前进;
(3)start=0从顺序表头开始往后,end从尾开始往前,
start遇到不能被3整除的数停止,end遇到能被3整除的数停止,交换下标为start和下标为end的元素,然后继续前进。
/*宏定义*/ #define MAXSIZE 30 //宏定义布尔类型 #define BOOL int #define TRUE 1 #define FALSE 0 typedef int ElemType; /*顺序表中存放整型元素*/ typedef struct{ ElemType elem[MAXSIZE]; int last; }SeqList; /*函数声明*/ void initList(SeqList *L); void printList(SeqList L); BOOL rule(int elem, int select); void sortList(SeqList *L, SeqList *L1, int select); void main(){ SeqList La, Lb; Lb.last=-1; // 初始化Lb int select; initList(&La); // 给出一个顺序表La printf("Give a sequence table: \nLa = "); printList(La); /* 给出下列几种排序规则: 奇数在前,偶数在后; 负数在前,非负数在后; 能被3整除的数在前面,不能被3整除的数在后面. */ printf("\nGive the following sorting rules: \ \n1.Odd number first, even number behind;\ \n2.Negative numbers first, non-negative numbers last;\ \n3.Numbers divisible by 3 are in the front, \ and numbers that are not divisible by 3 are in the back.\ \nPlease select the sorting rule you want and enter the rule number:"); scanf("%d", &select); while(select != 1 && select != 2 && select != 3){ printf("Please reselect: "); scanf("%d", &select); } sortList(&La, &Lb, select); printf("The adjusted sequence table is: \n"); printList(Lb); system("pause"); } /*函数定义*/ void initList(SeqList *L){ L->last=-1; int i=0; for(i; i<MAXSIZE; i++){ L->elem[i]=rand()%100 - 50; } L->last=MAXSIZE-1; } void printList(SeqList L){ int i; printf("("); for(i=0; i<=L.last; i++) printf("%d ", L.elem[i]); printf(")\n"); } void sortList(SeqList *L, SeqList *L1, int select){ int i=0, end=L->last, start=0; for(i; i<=L->last; i++){ if( rule(L->elem[i], select) == TRUE){ // 偶数尾插法 L1->elem[end] = L->elem[i]; end--; } else{ // 奇数前插法 L1->elem[start] = L->elem[i]; start++; } } L1->last=L->last; } BOOL rule(int elem, int select){ switch (select) { case 1: if(elem%2==0) return TRUE; return FALSE; break; case 2: if(elem>=0) return TRUE; return FALSE; break; case 3: if(elem%3!=0) return TRUE; return FALSE; break; default: return FALSE; break; } }
给定一个整数数组,删除相邻的重复数字,结果数组中不能存在任何相邻的重复数字。
将数组存入顺序表;
遍历顺序表,将下标为i和下标i+1的元素比较如果相等,进行判断:
如果下标为i和下标i+2的元素相等,所有元素往前移动1位;
如果下标为i和下标i+2的元素不相等,所有元素往前移动2位;
持续上述循环,结束的标志是遍历顺序表,没有相邻相同元素就结束循环。
while(flag==1){ if(L.last==0) // 代表顺序表中只有一个元素 break; if(L.elem[i]==L.elem[j]){ if(L.elem[i]==L.elem[j+1]){ // 判断是否3数相连 for(k=i; k<L.last; k++){ L.elem[k]=L.elem[k+1]; // 所有元素前移1位 } L.last = L.last-1; } else{ // 不是3数相连,那就是2数相连 for(k=i; k<L.last-1; k++){ L.elem[k]=L.elem[k+2]; // 所有元素前移2位 } L.last = L.last-2; if(j>L.last){ i=0; j=1; } } } if(j==L.last){ for(k=0; k<L.last; k++){ if(L.elem[k]==L.elem[k+1]){ flag=1; break; } else flag=0; } i=-1; j=0; } i++; j++; }
已知顺序表L(数组表示即可),编写一个时间复杂度O(n),空间复杂度为O(1)的算法
将表L中所有值为x 的元素删除。
- 表中元素无序。
遍历顺序表,将顺序表a的元素赋给顺序表b,遇到要删除的元素就跳过。
void deleteList(SeqList *LA, SeqList *LB, int n){
int count=0, i=0, j=0;
for(i; i<LA->last+1; i++){
if(LA->elem[i]==n){
count++; // 记录删除元素的个数
}
else{
LB->elem[j] = LA->elem[i];
j++;
}
}
LB->last = LA->last-count;
}
将n 个整数存入顺序表L,实现将L中的整数序列循环左移p(0<p<n)个位置,
即将L中的数据序列
(x0, x1, ... , xp-1, xp, xp+1, ... , xn-1)
变换为
(xp, xp+1, ... , xn-1, x0, x1, ... , xp-1)
- 类似的实现循环右移K位;
- 要求:时间复杂度为O(n)。空间复杂度为S(1)。
将下标0到p的元素逆置;
将下标p+1到n 的元素逆置;
最后将整个顺序表逆置得到最终结果。
void main(){ SeqList L = {{1,2,3,4,5,6,7,8,9,10},10}; int n; int temp; char direction; printf("Give a sequence table: \n"); printlist(L); printf("Please enter a positive integer n to cycle through the sequence: "); scanf("%d", &n); getchar(); // 吃掉回车 printf("Please select the direction of movement (L for left, R for right): "); while(direction!='R' && direction!='L'){ scanf("%c", &direction); getchar(); if(direction=='L'){ n = n%L.last; } else if(direction=='R'){ // 右移n格就是左移L.last-n格 n = L.last - n%L.last; } else{ printf("Wrong input, please re-enter: "); } } int i = 0, j = n-1; //将子表(X0,X1...,Xp-1)逆序为(Xp-1,...,X1,X0) reverse(&L, i, j); //将子表(Xp,Xp+1,...,Xn-1)逆序为(Xn-1,...,Xp+1,Xp) i = n; j = L.last-1; reverse(&L, i, j); //将整张表(Xp-1,...,X1,X0,Xn-1,...,Xp+1,Xp)逆序为(Xp,Xp+1,...,Xn-1,X0,X1...,Xp-1) i = 0; j = L.last-1; reverse(&L, i, j); printf("The sequence table after moving is: \n"); printlist(L); system("pause"); } void reverse(SeqList *L,int i, int j){ int temp; while(i < j){ temp = L->elem[i]; L->elem[i] = L->elem[j]; L->elem[j] = temp; ++i; --j; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。