###数组实现顺序表

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
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 //定义顺序表的最大容量
#define ElemType int
typedef struct //顺序存储结构的线性表的类型
{
ElemType date[MAXSIZE];
int length;
}SeqList;
SeqList SeqListInit() //顺序表的初始化
{
SeqList L;
L.length = 0;
return L;
}
SeqList Seqlistcreat(SeqList L) //顺序表的建立
{
int x;
while (scanf("%d",&x)) {
L.date[L.length] = x;
L.length++;
}
return L;
}
SeqList Deletesamenum(SeqList L) //删除相同元素
{
int i=0;
while (i<L.length) {
if (L.date[i]==L.date[i+1]) {
for (int j=i+1; j<L.length; j++)
L.date[j]=L.date[j+1];
L.length--;
i--;
}
i++;
}
return L;
}
int findmax(SeqList L) //找顺序表中的最大值
{
int max=L.date[0];
for (int i=0; i<L.length; i++) {
if(L.date[i]>max)
max=L.date[i];
}
return max;
}
int findmin(SeqList L) //找最小值
{
int min=L.date[0];
for (int i=0; i<L.length; i++) {
if(L.date[i]<min)
min=L.date[i];
}
return min;
}
SeqList SeqlistInsert(SeqList L,int i,ElemType x) //顺序表的插入
{
if (L.length == MAXSIZE)
printf("表已经满了\n");
else if (i<1 || i>L.length)
printf("插入位置错误\n");
int j;
for (j=L.length-1; j>=i-1; j--) {
L.date[j+1]=L.date[j];
}
L.date[i-1]=x;
L.length++;
return L;
}
int main()
{
SeqList seqlist;
seqlist = SeqListInit();
int i,j;
ElemType x;
seqlist = Seqlistcreat(seqlist);
printf("顺序表最大数为:%d\n",findmax(seqlist));
printf("顺序表最小数为:%d\n",findmin(seqlist));
printf("顺序表为:\n");
for (i=0; i<seqlist.length; i++) {
printf("%d ",seqlist.date[i]);
}
printf("\n顺序表长度为:%d\n",seqlist.length);
getchar();
printf("请输入插入元素位置:\n");
scanf("%d",&j);
printf("请输入插入元素的值:\n");
scanf("%d",&x);
seqlist = SeqlistInsert(seqlist,j,x);
printf("插入 %d 后顺序表为:\n",x);
for (i=0; i<seqlist.length; i++) {
printf("%d ",seqlist.date[i]);
}
seqlist = Deletesamenum(seqlist);
printf("\n删除相似元素后顺序表为:\n");
for (i=0; i<seqlist.length; i++) {
printf("%d ",seqlist.date[i]);
}
printf("\n删除相似元素后顺序表长度为:%d\n",seqlist.length);
return 0;
}

###指针实现

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<stdio.h>
#include<stdlib.h>
#define Null 0
typedef struct Lnode
{
int data;
struct Lnode *pnext;
}Lnode,*Linklist;
Linklist creat_list(void)
{
Linklist r;
int len,i;
int val;
Linklist phead=(Linklist)malloc(sizeof(Lnode));
if(phead==NULL)//如果节点为空
printf("分配失败.\n");
phead->pnext=NULL;
r=phead;
printf("请输入您需要生成的链表节点的个数:");
scanf("%d", &len);
printf("请输入节点的值:");
for(i=0;i<len;i++)
{
Linklist pnew=(Linklist)malloc(sizeof(Lnode));//分配一个新的临时节点
if(pnew==Null)//如果新节点为空
printf("分配失败.\n");
pnew->pnext=NULL;
scanf("%d",&val);
pnew->data=val;
r->pnext=pnew;
r=r->pnext;
}
return phead;
}
Linklist serch(Linklist phead,int n) //按值查找表结点
{
Linklist p=phead->pnext;
while (p!=NULL && p->data!=n)
p=p->pnext;
return p;
}
Linklist get_value(Linklist L,int i) //按序号查找结点值
{
int j=1;
Linklist p=L->pnext; //头结点指针赋给 p
if(i==0) return L;
if(i<1) return NULL;
while (p&&j<i) {
p=p->pnext;
j++;
}
return p;
}
Linklist insert_list(Linklist pHead,int pos,int val)
{
int i=0;
Linklist p=pHead;
while (p!=NULL && i<pos-1) {
p=p->pnext;
++i;
}
if (i>pos-1 && p==NULL) return NULL;
Linklist new_node=(Linklist)malloc(sizeof(Lnode));
if (new_node==NULL)
printf("动态内存分配失败");
new_node->data=val;
new_node->pnext=p->pnext;
p->pnext=new_node;
return p;
}
Linklist delete_node(Linklist pHead,int pos)
{
int i=0;
Linklist p=pHead;
while (p != NULL && i<pos-1) {
p=p->pnext;
++i;
}
if (i>pos-1 || p->pnext == NULL) {
return NULL;
}
Linklist tem = p->pnext; //零时储存,方便后面删除
p->pnext=p->pnext->pnext; //删除p后面的结点
free(tem);
tem=NULL;
return p;
}
int length(Linklist phead)
{
Linklist p = phead->pnext;
int len=0;
while (p!=NULL) {
++len;
p=p->pnext;
}
return len;
}
void print(Linklist L)
{
Linklist p=L->pnext;
printf("\n -------开始打印------- \n");
while(p!=Null)
{
printf(" [%d]",p->data);
p=p->pnext;
}
printf("\n -------打印结束------- \n");
}
int main()
{
int n,val,p;
Linklist L;
L=creat_list();
print(L);
printf("链表长度为: %d \n",length(L));
printf("请输入您想在链表中查找的值:");
scanf("%d",&n);
if (serch(L, n)==NULL)
printf("链表不存在该值。\n");
else
printf("链表存在该值。\n");
printf("请输入结点的序号:");
scanf("%d",&n);
if (get_value(L, n)==NULL)
printf("不存在该结点\n");
else
printf("第 %d 个结点的值为 %d \n",n,get_value(L, n)->data);
printf("\n请输入你想要在链表中插入的位置和值:");
scanf("%d %d",&p,&val);
insert_list(L, p, val);
print(L);
printf("请输入你想要删除的结点:");
scanf("%d",&p);
if(delete_node(L, p)==NULL)
printf("删除失败,结点不存在");
print(L);
return 0 ;
}