我是靠谱客的博主 幸福蜡烛,这篇文章主要介绍数据结构①:线性表的基本操作,现在分享给大家,希望可以做个参考。

一、要求:

1.顺序表的操作

复制代码
1
2
3
4
5
6
①随机产生一组2位整数,建立线性表的顺序存储结构,要求表中元素互不相同。 ② 实现该线性表的遍历。 ③ 在该顺序表中查找某一元素,查找成功显示查找元素,否则显示查找失败。 ④ 在该顺序表中删除或插入指定元素。 ⑤ 建立两个按值递增有序的顺序表,将他们合并成一个按值递减有序的顺序表。

2.单链表的操作

复制代码
1
2
3
4
5
① 输入一组整型元素序列,使用尾插法建立一个带有头结点的单链表。 ② 实现该线性表的遍历。 ③ 实现单链表的就地逆置。 ④ 建立两个按值递增有序的单链表,将他们合并成一个按值递增有序的单链表。要求利用原来的存储空间,并且新表中没有相同的元素。

二、思路:

1.顺序表:

复制代码
1
2
3
4
5
6
①首先定义结构体类型,随机产生一组两位数,需引入库文件<time.h>。生成顺序表时,为保证表中元素互不相同, 则每生成一个随机数后,需与前面生成的随机数进行挨个比较,若当前随机数与之前某一元素相同,则需重新生成该随机数,为保证不浪费顺序表的储存空间,此时for循环中的i应自减一,利用continue开始下一次生成随机数。若该随机数与之前的随机数都不相同,则加入随需表中。 ②顺序表的遍历操作可用for循环挨个打印显示出来。 ③查找某一元素时,需遍历顺序表,直至找到为止。若遍历至顺序表最后没找到,则不存在。 ④在指定为止插入或删除某元素时,需先定位到该位置。插入时,该位置及其后的元素依次后移一位,并将该元素插到该位置;删除某元素时,该位置及其以后的元素依次前移一位,并将顺序表长度减一。 ⑤将两个按值递增有序的顺序表,合并成一个按值递减有序的顺序表时,需从两个顺序表的最后开始扫描并比较,若La的最后一个元素大于Lb的最后一个元素,则将La的最后一个元素添加到新的空顺序表Lc中,否则将Lb最后的最后一个元素插入到Lc中。扫描到La穷尽时,则将Lb内的剩余元素倒序加入到Lc中,反之加La入Lc中。

2.链表:

复制代码
1
2
3
4
5
①尾插法建立单链表,即每读入一个元素,就将还元素的结点插到链表的末尾,在所有元素都被读取后,将最后一个结点的指针域赋为NULL。 ②链表的遍历即当结点p->next不为空的话,一直向后扫描并显示p->data。 ③单链表的就地逆置,利用头插法建立逆置后的链表。首先设P指向链表的首元结点,将链表设置成为只有头结点的空链表, 从P开始遍历链表,每访问一个结点,就将该结点插入到头结点的后面,直至遍历结束。 ④遍历La和Lb,若Pa->data<=Pb->data,则将Pa所指结点连接到Lc的最后,否则将Pb所指结点连接到Lc最后。首先应设置pre,用来记住Lc的最后一个结点,并不断对其进行更新。直至La或Lb的所有结点全部遍历完为止,然后将另一个链表中的所有剩余结点连接到Lc的最后即可。

三、代码和结果:

1)顺序表的①–④操作

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<stdio.h> #include<stdlib.h> #include<time.h> #define ListInitSize 100 #define ListIncrement 10 typedef struct{ int *base; int length; int listsize; }SqList; //******顺序表的初始化********// void InitSqList(SqList &L){ L.base = (int*)malloc(ListInitSize*sizeof(int)); if(!L.base) return ; L.length = 0; L.listsize = ListInitSize; } //******顺序表的建立********// void create(SqList &L){ int i,j,k; printf("请输入顺序表元素的个数:n"); scanf("%d",&L.length); srand(time(NULL)); for(i=0;i<L.length;i++){ k = rand()%90+10; //随机生成2位整数 j=0; while(j<i && k!=L.base[j]){ j++; } if(j<i){ //如果当前k与前面某一个数相同,则重新生成k i--; continue; } else L.base[i] = k; } } //******遍历显示顺序表********// void show(SqList L){ int j; for(j=0;j<L.length;j++) printf("%3d",L.base[j]); printf("n"); } //********查找某元素***********// int SearchElem(SqList L){ int i,e; i = 0; printf("请输入要查找的元素:"); scanf("%d",&e); while(i<L.length && L.base[i] != e) i++; if(i<L.length){ printf("查找成功n"); printf("该元素为%d,位置为%dn",L.base[i],i+1); } else printf("查找失败n"); printf("n"); return 0; } //*******删除第i个元素*********// void ListDelete(SqList &L,int i){ int j,s; if(i<1 || i>L.length) //i值非法 return ; for(j=i-1;j<L.length;j++){ L.base[j] = L.base[j+1]; } L.length--; printf("删除后第%d个元素后顺序表为:n",i); for(s=0;s<L.length;s++) printf("%3d",L.base[s]); printf("n"); } //******在第i个位置前插入元素**********// void ListInsert(SqList &L,int i,int e){ int s,j; int *newbase; if(i<1 || i>L.length+1) //i值非法 return; //若储存空间已满,需扩充 if(L.length >= L.listsize){ newbase = (int*)realloc(L.base,(L.listsize+ListIncrement)*sizeof(int)); if(!newbase) return ; L.base = newbase; L.listsize += ListIncrement; } for(j=L.length-1;j>=i-1;j--) L.base[j+1] = L.base[j]; L.base[i-1] = e; L.length++; printf("在第%d个位置插入%d后顺序表为:n",i,e); for(s=0;s<L.length;s++) printf("%3d",L.base[s]); printf("n"); } //******主函数********// int main() { SqList L; InitSqList(L); create(L); show(L); SearchElem(L); ListDelete(L,5); ListInsert(L,6,20); return 0; }

结果:
在这里插入图片描述
2)顺序表的⑤操作

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h> #include<stdlib.h> #define ListInitSize 30 #define ListIncrement 10 typedef struct{ int *base; int length; int listsize; }SqList; //*****初始化********// void InitSqList(SqList &L){ L.base = (int*)malloc(ListInitSize*sizeof(int)); if(!L.base) return ; L.length = 0; L.listsize = ListInitSize; }//InitSqList //*****建立顺序表*******// void create(SqList &L){ int i; printf("请输入顺序表元素的个数:n"); scanf("%d",&L.length); printf("请按递增顺序输入元素:"); for(i=0;i<L.length;i++) scanf("%d",&L.base[i]); } //*****遍历显示顺序表*******// void show(SqList L){ int j; for(j=0;j<L.length;j++) printf("%3d",L.base[j]); printf("n"); } //*****将两个按值递增的顺序表,合并成一个按值递减有序的顺序表*******// void MergeList(SqList La,SqList Lb,SqList &Lc){ int i,j,k; Lc.base = (int*)malloc((La.length+Lb.length)*sizeof(int)); Lc.listsize = La.length + Lb.length; i=La.length-1; j=Lb.length-1; k=0; while(i>=0 && j>=0) if(La.base[i]>=Lb.base[j]) Lc.base[k++] = La.base[i--]; else Lc.base[k++] = Lb.base[j--]; while(i>=0) Lc.base[k++] = La.base[i--]; while(j>=0) Lc.base[k++] = Lb.base[j--]; Lc.length = k; } //*****主函数*******// int main() { SqList La,Lb,Lc; InitSqList(La); InitSqList(Lb); create(La); create(Lb); show(La); show(Lb); MergeList(La,Lb,Lc); show(Lc); return 0; }

结果:
在这里插入图片描述
3)链表的①–③操作:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h> #include<stdlib.h> typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; //*******初始化链表*******// void InitLinkList(LinkList &L){ L = (LinkList)malloc(sizeof(LNode)); if(!L) return ; L->next = NULL; } //*******尾插法建立链表*******// void CreateLinkList_Tail(LinkList &L,int n){ int i; LinkList pre,p; L = (LinkList)malloc(sizeof(LNode)); pre = L; printf("请输入%d个整形元素:n",n); for(i=0;i<n;i++){ p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); pre->next = p; pre = p; } pre->next = NULL; } //*******遍历显示链表*******// void show(LinkList L,int n){ LinkList p; p = L->next; printf("链表为:n"); while(p){ printf("%5d",p->data); p = p->next; } printf("n"); } //*******就地逆置链表*******// void Reverse(LinkList &L){ LinkList p,q; p = L->next; //p指向首元结点,将L置为空链表 L->next = NULL; while(p){ //遍历单链表 q = p; //用q记住p,p结点后移 p = p->next; q->next = L->next; //将q结点插到链表L中 L->next = q; } printf("原地转置后:n"); show(L,10); } //*******主函数*******// void main() { int m; LinkList L; InitLinkList(L); printf("请输入链表元素的个数:n"); scanf("%d",&m); CreateLinkList_Tail(L,m); show(L,m); Reverse(L); }

结果:
在这里插入图片描述
4)链表的第④个操作:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<stdio.h> #include<stdlib.h> typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; //**********尾插法建立链表**********// void CreateLinkList_Tail(LinkList &L,int n){ int i; LinkList pre,p; L = (LinkList)malloc(sizeof(LNode)); pre = L; for(i=0;i<n;i++){ p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); pre->next = p; pre = p; } pre->next = NULL; } //**********遍历显示**********// void show(LinkList L,int n){ LinkList p; p = L->next; while(p!=NULL){ printf("%5d",p->data); p = p->next; } printf("n"); } //*******求链表长度********// int ListLength(LinkList L){ int count; count = 0; LinkList p; p = L->next; while(p){ count++; p = p->next; } return count; } //*****将两个按值递增有序的单链表,合并成一个按值递增有序的单链表,且新表中没有相同的元素*****// int ListMerge(LinkList La,LinkList Lb,LinkList &Lc){ LinkList pre,pa,pb; Lc = pre = La; pa = La->next; pb = Lb->next; while(pa && pb){ if(pa->data < pb->data){ pre->next = pa; pre = pa; pa = pa->next; } else if(pa->data == pb->data){ pre->next = pa; pre = pa; pa = pa->next; pb = pb->next; } else{ pre->next = pb; pre = pb; pb = pb->next; } } if(pa) pre->next = pa; else pre->next = pb; free(Lb); return ListLength(Lc); } //**********主函数**********// void main() { int x,y,z; LinkList La,Lb,Lc; printf("请输入第一个链表的长度:n"); scanf("%d",&x); printf("请按递增顺序入第一个链表的元素:n"); CreateLinkList_Tail(La,x); printf("请输入第二个链表的长度:n"); scanf("%d",&y); printf("请按递增顺序输入第二个链表的元素:n"); CreateLinkList_Tail(Lb,y); printf("第一个链表为:n"); show(La,x); printf("第二个链表为:n"); show(Lb,y); z = ListMerge(La,Lb,Lc); printf("合并后链表为:n"); show(Lc,z); }

结果:
在这里插入图片描述


Directions:

初识数据结构

最后

以上就是幸福蜡烛最近收集整理的关于数据结构①:线性表的基本操作的全部内容,更多相关数据结构①:线性表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(124)

评论列表共有 0 条评论

立即
投稿
返回
顶部