实验一 顺序表和单链表的建立和操作

1
2
3
 在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 中的第i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表：
L=(a1，…a i-1，e，ai，ai+1，…，an)

1
2
3
在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除结点ai(1≦i≦n)，使其成为线性表：
L= (a1，…ai-1，ai+1，…，an)

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
#include "stdio.h"
#include "malloc.h"
#define maxsize 1024
typedef char elemtype;
typedef struct
{
elemtype list[maxsize];
int length;
}sequenlist;
//创建顺序表 
void creatlist(sequenlist *L);
//插入元素 
int insert(sequenlist *L,elemtype x,int i);
//删除元素 
int dellist(sequenlist *L,int i);
//输出顺序表 
void printout(sequenlist *L);
//创建顺序表 
void creatlist(sequenlist *L)
{
int n,i;
char tmp;
printf("请输入数据的个数：");
scanf("%d",&n);
for(i = 0; i < n; i ++)
{
printf("list[%d] = ",i);
fflush(stdin);//清空输入缓冲区，通常是为了确保不影响后面
的数据的读入
scanf("%c",&tmp);
L -> list[i] = tmp;
}
L -> length = n-1;
}
//插入元素 
int insert(sequenlist *L,elemtype x,int i)
{
int j;
if(L -> length == maxsize - 1)//判满
{
printf("overflow");
return 0;
}
else if((i < 0) || (i > L -> length)) //判插入位置是否合法
{
printf("error,please input the right 'i'n");
return 0;
}
else
{
for(j = L-> length; j >= i; j --)
L -> list[j+1] = L -> list[j];
L -> list[i] = x;
L -> length = L -> length + 1;
}
return 1;
}
//删除元素 
int dellist(sequenlist *L,int i)
{
if((i < 0) || (i > L -> length))
{
printf("error,please input the right 'i'n");
return 0;
}
else
{
for( ; i < L -> length; i++)
L -> list[i] = L -> list[i+1];
L -> length = L -> length - 1;
return 1;
}
}
//输出顺序表 
void printout(sequenlist *L)
{
int i;
for(i = 0; i <= L -> length; i ++)
{
printf("list[%d]=",i);
printf("%cn",L->list[i]);
}
}
main()
{
sequenlist *L;
char cmd,x;
int i;
L = (sequenlist *)malloc(sizeof(sequenlist));
creatlist(L);
do
{
printf(" i,I
插入n");
printf(" d,D
删除n");
printf(" q,Q
退出n");
do
{
fflush(stdin);
scanf("%c", &cmd);
}
while((cmd !='d') && (cmd != 'D') && (cmd != 'q') && (cmd != 'Q') && (cmd != 'i') && (cmd != 'I'));
switch(cmd)
{
case 'i':
case 'I':
printf("请输入你要插入的数据：");
fflush(stdin);
scanf("%c", &x);
printf("请输入你要插入的位置：");
scanf("%d", &i);
insert(L,x,i);
printout(L);
break;
case 'd':
case 'D':
printf("请输入你要删除的数据的位置：");
fflush(stdin);
scanf("%d", &i);
dellist(L,i);
printout(L);
break;
}
}
while((cmd != 'q') && (cmd != 'Q'));
}

1
2
动态地建立单链表的常用方法有如下两种：**头插入法，尾插入法**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
linklist creat (int n)//创建单链表，采用头插法建表
{
linklist head,p; //定义头指针head指针,p指针指向当前新生成的结点
int x,i;
head=(node *)malloc(sizeof(node));//生成头结点
head->next=NULL;
printf("输入数字:n");
for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据
{
scanf("%d",&x);
p=(node *)malloc(sizeof(node));
p->data=x;//读入第一个节点的数据
p->next=head->next;//把第一个节点始终插在头结点的后面
head->next=p;//循环以便于生成第二个节点
}
return head;//返回头指针
}

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
#include<stdio.h>
#include<stdlib.h>
typedef struct liu{
char data;
struct liu *next;
}test;
liu *p,*head;
int m=sizeof(test);
void build() //字母链表的生成，要一个一个慢慢链入
{
int i;
head = (test*)malloc(m); //m=sizeof(test) 前面已求出
p = head;
for(i = 1; i < 26; i ++) //因尾结点要特殊处理，故i≠26
{
p -> data = i+‘a’-1; // 第一个结点值为字符a 
p -> next = (test*)malloc(m);
p = p->next；} //让指针变量P改为指向后继结点
p -> data = i + ‘a’-1; //最后一个元素要单独处理
p -> next = NULL ;
} //单链表尾结点的指针域要置空！
void display() /*字母链表的输出*/
{
p = head;
while (p->next!=NULL)
{
printf("%c",p->data);
p = p->next; }
printf(“%cn”,p->data);
}

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include "stdio.h"
#include "malloc.h"
typedef char Elemtype;
typedef struct node
//定义存储节点
{
Elemtype data;
struct node *next;
} node,*linklist;
//建立单链表 
linklist creat(int n);
//插入元素
int insert(linklist &l, int i, Elemtype e);
//删除元素 
int delect(linklist &l, int i, Elemtype &e);
//查找元素 
int GetElem(linklist l, int i, Elemtype &e);
//输出单链表 
void output(linklist head);
//建立单链表，采用头插法建表
linklist creat(int n)
{
linklist head,p;
//定义头指针head指针,p指针指向当前新生成的结点
int x,i;
head = (node*)malloc(sizeof(node));
//生成头结点
head ->next = NULL;
printf("输出数字：n");
for(i = n; i > 0; i --)
//for 循环用于生成第一个节点并读入数据
{
scanf("%d", &x);
p = (node*)malloc(sizeof(node));
p -> data = x;
//读入第一个节点的数据
p -> next = head -> next;
//把第一个节点始终插在头结点的后面
head -> next = p;
}
return head;
}
//插入元素
int insert(linklist &l, int i, Elemtype e)
{
int j = 0;
linklist p = l, s;
while( j < i - 1 && p)
{
p = p -> next;
++ j;
}
if( !p || j > i -1)
printf("无法插入");
else
{
s = (node*)malloc(sizeof(node));
s -> data = e;
s -> next = p -> next;
p -> next = s;
}
return 1;
}
//删除元素 
int delect(linklist &l, int i, Elemtype &e)
{
int j = 0;
linklist p = l,q;
while( j < i - 1 && p -> next)
{
p = p -> next;
++ j;
}
if( !p -> next || j > i - 1)
printf("无法删除");
else
{
q = p -> next;
p -> next = q -> next;
e = q ->data;
free(q);
}
return 1;
}
//查找元素 
int GetElem(linklist l, int i, Elemtype &e)
{
linklist p;
int j;
p = l -> next;
j = 1;
while( p && j < i)
{
p = p -> next;
++ j;
}
if( !p || j > i)
printf("无法查找");
e = p -> data;
return e;
}
//输出单链表 
void output(linklist head)
{
linklist p;
p = head -> next;
do
{
printf("%3d", p -> data);
p = p -> next;
}
while(p);
printf("n");
}
main()
{
linklist la;
int n;
int i,j;
Elemtype e;
char cmd;
printf("输出链表元素的个数：");
scanf("%d", &n);
la =
creat(n);
printf("输出链表：n");
output(la);
do
{
printf("g,G
查找n");
printf("i,I
插入n");
printf("d,D
删除n");
printf("q,Q
退出n");
do
{
scanf("%c", &cmd);
}
while((cmd != 'g') && (cmd != 'G') && (cmd != 'd') && (cmd != 'D') && (cmd != 'q') && (cmd != 'Q') && (cmd != 'i') && (cmd != 'I'));
switch(cmd)
{
case 'g':
case 'G':
printf("请输入要查找元素的位置：n");
scanf("%d", &i);
j = GetElem(la, i, e);
printf("要查找的元素是%dn", j);
break;
case 'i':
case 'I':
printf("请输入你要插入的数据：");
scanf("%d", &e);
printf("请输入你要插入的位置：");
scanf("%d", &i);
insert(la, i ,e);
printf("插入后的链表：n");
output(la);
break;
case 'd':
case 'D':
printf("请输入要删除的位置:n");
scanf("%d",&i);
delect(la,i,e);
printf("删除的那个元素是:%dn",e);
printf("输出删除后的顺序表:n");
output(la);
break;
}
}
while((cmd != 'q')&&(cmd != 'Q'));
}