顺序表

xiaoxiao2021-03-01  13

Part1 序幕? 

学习板块一 c++ 引用&

:引用的多方面学习 香菇网站1:学习c++引用

县官学习网站二:引用的简单介绍 : 以下说明来自本连接

(2)数据类型是指目标变量的数据类型。

(3)声明引用时,必须同时对其进行初始化。

(4)引用声明完毕后,相当于目标变量名有两个名称,即该目标变量的原名称和引用名,且不能再把该引用名作为其他变量名的别名。 ra=1; 等价于 a=1;

(5)声明一个引用,不是新定义了一个变量,它只表示该引用名是目标变量名的一个别名,因此引用本身不占存储单元,系统也不给引用分配存储单元。故:对引用求地址,就是对目标变量求地址,即&ra=&a。

(6)不能建立数组的引用。因为数组是一个由若干个元素所组成的集合,所以无法建立一个数组的别名。

(7)引用常作为函数的参数来使用,在函数的内部对引用进行操作,就相当于对原变量进行操作,这个用法类似于变量的指针。

Part 2 正文 !!! 如有侵权, 不要举报, 联系我, 我负责。

一、逆置(位置互换)

顺序表应用4:元素位置互换之逆置算法

Time Limit: 10 ms Memory Limit: 570 KiB

Problem Description

一个长度为len(1<=len<=1000000)的顺序表,数据元素的类型为整型,将该表分成两半,前一半有m个元素,后一半有len-m个元素(1<=m<=len),设计一个时间复杂度为O(N)、空间复杂度为O(1)的算法,改变原来的顺序表,把顺序表中原来在前的m个元素放到表的后段,后len-m个元素放到表的前段。 注意:先将顺序表元素调整为符合要求的内容后,再做输出,输出过程只能用一个循环语句实现,不能分成两个部分。

 Input

 第一行输入整数n,代表下面有n行输入; 之后输入n行,每行先输入整数len与整数m(分别代表本表的元素总数与前半表的元素个数),之后输入len个整数,代表对应顺序表的每个元素。

Output

 输出有n行,为每个顺序表前m个元素与后(len-m)个元素交换后的结果

 Sample Input

2 10 3 1 2 3 4 5 6 7 8 9 10 5 3 10 30 20 50 80

Sample Output

4 5 6 7 8 9 10 1 2 3 50 80 10 30 20

思路: 

一个顺序表中的元素被分为两部分,将两部分的数据交换,假设将顺序表中的每个元素左移,将第一个元素放在最后,那么就实现了第一个元素与其他元素的换位,所以前一部分元素有n个,也就是移动n次。

1、先把前m个逆置, 再把后len-m 个逆置, 最后把总体len个 逆置。

2、或者 先逆置总体len, 再逆置前len - m 个, 再逆置后m 个。

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #define INF 0x3f3f3f3f using namespace std; #define MAXN 10010 struct sl { int data[MAXN]; int len; }; void creat(sl &l, int m) { l.len = m; for(int i = 0; i < l.len; i++) cin >> l.data[i]; } void change(sl &l, int m, int n) { while(m < n) { int temp = l.data[m]; l.data[m] = l.data[n]; l.data[n] = temp; m++; n--; } } void print(sl &l) { for(int i = 0; i < l.len; i++) if(i == l.len - 1) cout << l.data[i] << endl; else cout << l.data[i] << " "; } int main() { int n; ios::sync_with_stdio(0); cin >> n; while(n--) { int len, m; cin >> len >> m; sl l; creat(l, len); change(l, 0, len-1); change(l, 0, len - 1 - m); change(l, len - m, len - 1); print(l); } return 0; }

二、 逆置算法(数据改进)

       

顺序表应用4-2:元素位置互换之逆置算法(数据改进)

Time Limit: 80 ms Memory Limit: 600 KiB

Problem Description

一个长度为len(1<=len<=1000000)的顺序表,数据元素的类型为整型,将该表分成两半,前一半有m个元素,后一半有len-m个元素(1<=m<=len),设计一个时间复杂度为O(N)、空间复杂度为O(1)的算法,改变原来的顺序表,把顺序表中原来在前的m个元素放到表的后段,后len-m个元素放到表的前段。 注意:交换操作会有多次,每次交换都是在上次交换完成后的顺序表中进行。 

Input

第一行输入整数len(1<=len<=1000000),表示顺序表元素的总数;

第二行输入len个整数,作为表里依次存放的数据元素;

第三行输入整数t(1<=t<=30),表示之后要完成t次交换,每次均是在上次交换完成后的顺序表基础上实现新的交换

之后t行,每行输入一个整数m(1<=m<=len),代表本次交换要以上次交换完成后的顺序表为基础,实现前m个元素与后len-m个元素的交换;

Output

输出一共t行,每行依次输出本次交换完成后顺序表里所有元素。

 Sample Input

10 1 2 3 4 5 6 7 8 9 -1 3 2 3 5 Sample Output 3 4 5 6 7 8 9 -1 1 2 6 7 8 9 -1 1 2 3 4 5 1 2 3 4 5 6 7 8 9 -1

 

 

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #define INF 0x3f3f3f3f using namespace std; typedef struct sl { int *elem; // 指针变量 int len; }list; void creat(list &l, int m) { l.elem = (int *)malloc(m * sizeof(int)); for(int i = 0; i < m; i++) scanf("%d",&l.elem[i]); l.len = m; } void change(list &l, int m, int n) { while(m < n) { int temp = l.elem[m]; l.elem[m] = l.elem[n]; l.elem[n] = temp; m++; n--; } } int main() { int n, a, m; list l; scanf("%d",&a); creat(l,a); scanf("%d",&n); while(n--) { scanf("%d",&m); change(l, 0, a-1); change(l, 0, a - 1 - m); change(l, a - m, a - 1); for(int i = 0; i < a; i++){ if(i == a - 1) printf("%d\n",l.elem[i]); else printf("%d ",l.elem[i]); } } return 0; }

三、互换&移位

顺序表应用3:元素位置互换之移位算法

Time Limit: 1000 ms Memory Limit: 570 KiB

Submit Statistic

Problem Description

一个长度为len(1<=len<=1000000)的顺序表,数据元素的类型为整型,将该表分成两半,前一半有m个元素,后一半有len-m个元素(1<=m<=len),借助元素移位的方式,设计一个空间复杂度为O(1)的算法,改变原来的顺序表,把顺序表中原来在前的m个元素放到表的后段,后len-m个元素放到表的前段。 注意:先将顺序表元素调整为符合要求的内容后,再做输出,输出过程只能用一个循环语句实现,不能分成两个部分。

Input

 第一行输入整数n,代表下面有n行输入; 之后输入n行,每行先输入整数len与整数m(分别代表本表的元素总数与前半表的元素个数),之后输入len个整数,代表对应顺序表的每个元素。

Output

 输出有n行,为每个顺序表前m个元素与后(len-m)个元素交换后的结果

Sample Input

2 10 3 1 2 3 4 5 6 7 8 9 10 5 3 10 30 20 50 80

Sample Output

4 5 6 7 8 9 10 1 2 3 50 80 10 30 20

 

#include<bits/stdc++.h> using namespace std; const int N=100001; class Sqlist { private: int data[N]; int length; public: Sqlist(int n); int locateelem(int e); void listinsert(int i,int e); void Delete(int i); void del_elem(); void set_elem(int i); int get_elem(int i) { return data[i]; } void show(); }; Sqlist::Sqlist(int n) { int i; for(i=0; i<n; ++i) cin>>data[i]; length=n; } void Sqlist::Delete(int i) { for(int k=i+1; k<length; k++) data[k-1]=data[k]; length--; } void Sqlist::del_elem() { int i,j; for(i=0; i<length; i++) { for(j=i+1; j<length;) if(data[j]==data[i]) { Delete(j); } else j++; } } void Sqlist::show() { for(int i=0; i<length; i++) cout<<data[i]<<" "; cout<<endl; } int main() { int i,n,m; cin>>n; while(n--) { cin>>m; Sqlist L(m); L.del_elem(); L.show(); } return 0; } /*************************************************** User name: jk170806郭庆福 Result: Accepted Take time: 56ms Take Memory: 240KB Submit time: 2018-09-19 14:22:22 ****************************************************/

 

#include <stdio.h> #include <stdlib.h> struct node { int data; int len; }s[10010]; int main() { int n, p,j,t, m,i; scanf("%d",&n); while(n--) { scanf("%d%d",&p,&m); for(i=0;i<p;i++) { scanf("%d",&s[i].data); } for(i=0;i<m;i++) { t=s[0].data; for(j=0;j < p-1;j++) { s[j].data = s[j+1].data; } s[p-1].data = t; } for(i=0;i<p;i++) { printf("%d%c",s[i].data,i==p-1 ? '\n' : ' '); } } return 0; } /* #include <stdio.h> #include <stdlib.h> struct node { int data; int len; }s[10010]; void change( struct node s[],int m,int n) { while(m<n) { int tmp = s[m].data; s[m].data = s[n].data; s[n].data = tmp; m++;n--; } } int main() { int n, p, m,i; scanf("%d",&n); while(n--) { scanf("%d%d",&p,&m); for(i=0;i<p;i++) { scanf("%d",&s[i].data); } change(s,0,p-1); change(s,0,p-m-1); change(s,p-m,p-1); for(i=0;i<p;i++) { printf("%d%c",s[i].data,i==p-1 ? '\n' : ' '); } } return 0; } */

 四、顺序表应用1:多余元素删除之移位算法

Time Limit: 1000 ms Memory Limit: 650 KiB

Problem Description

一个长度不超过10000数据的顺序表,可能存在着一些值相同的“多余”数据元素(类型为整型),编写一个程序将“多余”的数据元素从顺序表中删除,使该表由一个“非纯表”(值相同的元素在表中可能有多个)变成一个“纯表”(值相同的元素在表中只保留第一个)。 要求:        1、必须先定义线性表的结构与操作函数,在主函数中借助该定义与操作函数调用实现问题功能;        2、本题的目标是熟悉顺序表的移位算法,因此题目必须要用元素的移位实现删除

Input

 第一行输入整数n,代表下面有n行输入; 之后输入n行,每行先输入整数m,之后输入m个数据,代表对应顺序表的每个元素。

Output

 输出有n行,为每个顺序表删除多余元素后的结果

Sample Input

4 5 6 9 6 8 9 3 5 5 5 5 9 8 7 6 5 10 1 2 3 4 5 5 4 2 1 3

Sample Output

6 9 8 5 9 8 7 6 5 1 2 3 4 5 这道题目要求的是用移位的方法来去掉重复的元素,所以就是遍历顺序表找到重复的元素,在相同元素的第二个的位置开始依次向前移, 从而把第二个重复的元素覆盖掉,第三第四个重复元素也是如此,最终留下全不重复的元素。

代码一:

#include <stdio.h> #include <stdlib.h> int len; typedef struct node { int elem[10001]; }list; void creatlist(list *l,int n) { int i; len = 0; // l->elem = (struct node *)malloc(10001 * sizeof(struct node)); for(i=0; i < n; i++) { scanf("%d",&l->elem[i]); len++; } } void deletelist(list *l) { int n,i,j; n = 0; while(n < len) { for(i = n+1; i < len; i++) { if(l->elem[i] == l->elem[n]) { for(j = i; j < len; j++) l->elem[j] = l->elem[j+1]; len--; i--; } } n++; } } int main() { list l; int m,n; scanf("%d",&m); while(m--) { scanf("%d",&n); creatlist(&l,n); // &在此不是求地址运算,而是引用。 deletelist(&l); int i; for(i=0;i<len;i++) { if(i == len - 1) printf("%d\n",l.elem[i]); else printf("%d ",l.elem[i]); } } return 0; }

 

#include <iostream> #include <cstdlib> using namespace std; typedef struct { int *elem; int len; }list; void creatlist(list &l,int n) { int i; l.elem = new int [10001]; l.len = 0; for(i=0; i < n; i++) { cin>>l.elem[i]; l.len++; } } void deletelist(list &l) { int n,i,j; n = 0; while(n < l.len) { for(i = n+1; i < l.len; i++) { if(l.elem[i] == l.elem[n]) { for(j = i; j < l.len; j++) l.elem[j] = l.elem[j+1]; l.len--; i--; } } n++; } } int main() { list l; int m,n; cin>>m; while(m--) { cin>>n; creatlist(l,n); deletelist(l); int i; for(i=0;i<l.len;i++) { if(i == l.len - 1) cout<<l.elem[i]<<endl; else cout<<l.elem[i]<<" "; } } return 0; }

五、顺序表应用2:多余元素删除之建表算法

Time Limit: 3 ms Memory Limit: 600 KiB

Problem Description

一个长度不超过10000数据的顺序表,可能存在着一些值相同的“多余”数据元素(类型为整型),编写一个程序将“多余”的数据元素从顺序表中删除,使该表由一个“非纯表”(值相同的元素在表中可能有多个)变成一个“纯表”(值相同的元素在表中只保留第一个)。 要求:        1、必须先定义线性表的结构与操作函数,在主函数中借助该定义与操作函数调用实现问题功能;        2、本题的目标是熟悉在顺序表原表空间基础上建新表的算法,要在原顺序表空间的基础上完成完成删除,建表过程不得开辟新的表空间;        3、不得采用原表元素移位删除的方式。

Input

 第一行输入整数n,代表下面有n行输入; 之后输入n行,每行先输入整数m,之后输入m个数据,代表对应顺序表的每个元素。

Output

  输出有n行,为每个顺序表删除多余元素后的结果

Sample Input

4 5 6 9 6 8 9 3 5 5 5 5 9 8 7 6 5 10 1 2 3 4 5 5 4 2 1 3

Sample Output

6 9 8 5 9 8 7 6 5 1 2 3 4 5

 注意 一边建立, 一边删除。先判再建。

#include <stdio.h> #include <stdlib.h> typedef struct { int data[10010]; }SL; void creat(SL *l,int n) { int i; for(i=0;i<n;i++) { scanf("%d",&l->data[i]); } } int dele(SL * l, int n) { int p = 0; int i,j; for(i=0;i<n;i++) { int f = 0; for(j = 0; j < p; j++) { if(l->data[j] == l->data[i]) { f = 1; break; } } if(!f) { l->data[p++] = l->data[i]; } } return p; } void show(SL *l, int n) { int i; for(i=0;i<n;i++) { if(i==n-1) printf("%d\n",l->data[i]); else printf("%d ",l->data[i]); } } int main() { int n,m,t; scanf("%d",&t); while(t--) { scanf("%d",&n); SL l; creat(&l, n); m = dele(&l,n); show(&l,m); } return 0; }

以下代码转载 来自  文章  顺序表(多余元素删除移位与建表法)

// 插入LH 的代码, 相比之下, 下面代码就比较规整了,看起来也舒服。 #include<stdio.h> #include<stdlib.h> #include<string.h> #define s 100 #define z 10 #define OK 1 #define OVERFLOW -1 typedef struct { int *elem; int length; int listsize; }S; void InitList(S&L) { L.elem=(int *)malloc(s*sizeof(int)); L.length=0; L.listsize=s; } void ListInsert(S&L,int i,int e) { if(L.length>=L.listsize) { int *newbase=(int*)realloc(L.elem,(L.listsize+z)*sizeof(int)); L.elem=newbase; L.listsize=L.listsize+z; } L.elem[i]=e; L.length++; } void purge(S&L) { int k=-1,j; for(int i=0;i<L.length;i++) { j=0; while(j<=k&&L.elem[i]!=L.elem[j]) j++; if(k==-1||j>k)L.elem[++k]=L.elem[i]; } L.length=k+1; } //void purge(S&L) //{ // for(int i=0;i<L.length-1;i++) // { // int j; // j=i+1; // while(j<L.length) // { // if(L.elem[j]!=L.elem[i])j++; // else // { // for(int k=j+1;k<L.length;k++) // { // L.elem[k-1]=L.elem[k]; // } // L.length--; // } // } // } //} void print(S&L) { for(int i=0;i<L.length;i++) { if(i==0)printf("%d",L.elem[i]); else printf(" %d",L.elem[i]); } printf("\n"); } int main() { int n; S L; scanf("%d",&n); while(n--) { InitList(L); int t; scanf("%d",&t); for(int i=0;i<t;i++) { int w; scanf("%d",&w); ListInsert(L,i,w); } purge(L); print(L); } return 0; }

 

 六、顺序表应用5:有序顺序表归并

Time Limit: 100 ms Memory Limit: 880 KiB

Problem Description

已知顺序表A与B是两个有序的顺序表,其中存放的数据元素皆为普通整型,将A与B表归并为C表,要求C表包含了A、B表里所有元素,并且C表仍然保持有序。

Input

 输入分为三行: 第一行输入m、n(1<=m,n<=10000)的值,即为表A、B的元素个数; 第二行输入m个有序的整数,即为表A的每一个元素; 第三行输入n个有序的整数,即为表B的每一个元素;

Output

 输出为一行,即将表A、B合并为表C后,依次输出表C所存放的元素。

Sample Input

5 3 1 3 5 6 9 2 4 10

Sample Output

1 2 3 4 5 6 9 10

Hint

Source

一:可以用链表做, 就是 之前有序链表的归并

二:由于都是排好序的, 你也可以只进行一次大小比较, 做一次循环输出, 然后输出他们剩下的所有夏天。

三: 用顺序表做。

 看代码吧

#include <stdio.h> #include <stdlib.h> struct node { int a; struct node *next; }; struct node *creat(int n); struct node *merge(struct node *head1, struct node *head2); void display(struct node *head); int main() { int m, n; struct node *head1, *head2, *head; scanf("%d%d", &m, &n); head1=creat(m); head2=creat(n); head=merge(head1, head2); display(head); return 0; } struct node *creat(int n) { struct node *head, *p, *tail; int i; head=(struct node *)malloc(sizeof(struct node)); head->next=NULL; tail=head; for(i=0;i<n;i++) { p=(struct node *)malloc(sizeof(struct node)); scanf("%d", &p->a); p->next=NULL; tail->next=p; tail=p; } return head; }; struct node *merge(struct node *head1, struct node *head2) { struct node *p1, *p2, *tail; p1=head1->next; p2=head2->next; head1->next=NULL; tail=head1; free(head2); while(p1&&p2) { if(p1->a<p2->a) { tail->next=p1; tail=p1; p1=p1->next; tail->next=NULL; } else { tail->next=p2; tail=p2; p2=p2->next; tail->next=NULL; } } if(p1) { tail->next=p1; } else { tail->next=p2; } return head1; } void display(struct node *head) { struct node *p; p=head->next; while(p!=NULL) { if(p->next == NULL) { printf("%d\n", p->a); } else { printf("%d ", p->a); } p=p->next; } } /*************************************************** User name: jk1708 i am your father. Result: Accepted Take time: 12ms Take Memory: 776KB Submit time: 2018-08-02 16:10:10 ****************************************************/ #include<stdio.h> int a[10010],b[10010]; int main() { int i,j,n,m,k,t; scanf("%d %d",&n,&m); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<m;i++) scanf("%d",&b[i]); k=0; for(i=0,j=0;j<m&&i<n;) { if(a[i]<b[j]) { if(k==0) printf("%d",a[i]); else printf(" %d",a[i]); i++; } else { if(k==0) printf("%d",b[j]); else printf(" %d",b[j]); j++; } k++; } for(k=i;k<n;k++) printf(" %d",a[k]); for(k=j;k<m;k++) printf(" %d",b[k]); printf("\n"); } #include<stdio.h> #include<stdlib.h> typedef struct node { int data[100010]; int last; }ST; void creat(ST *head) { int i; for(i = 0; i < head->last; i++) { scanf("%d", &head->data[i]); } } void bine(ST *head, ST *tail, ST *p) { int i, j, k; i = 0; j = 0; k = 0; while(i < head->last && j < tail->last) { if(head->data[i] < tail->data[j]) { p->data[k++] = head->data[i++]; } else { p->data[k++] = tail->data[j++]; } } if(i == head->last) { for(j = j; j < tail->last; j++) { p->data[k++] = tail->data[j]; } } if(j == tail->last) { for(i = i; i < head->last; i++) { p->data[k++] = head->data[i]; } } p -> last = k; } int main() { ST *head, *tail, *p; int i; head = (ST *)malloc(sizeof(ST)); tail = (ST *)malloc(sizeof(ST)); p = (ST *)malloc(sizeof(ST)); scanf("%d %d", &head->last, &tail->last); creat(head); creat(tail); bine(head,tail,p); for(i = 0; i < p->last; i++) { printf("%d", p->data[i]); if(i != p -> last - 1) printf(" "); else printf("\n"); } return 0; } /*************************************************** User name: jk1708 i am your father Result: Accepted Take time: 8ms Take Memory: 316KB Submit time: 2018-08-02 19:31:27 ****************************************************/

ok, last but not last, i wanna say : 

 

 

转载请注明原文地址: https://www.6miu.com/read-4050084.html

最新回复(0)