文章目录
1.顺序结构1.0结构体1.1初始化1.2取值1.3查找1.4插入1.5输出
2.链式结构(无头结点的单链表)2.0结构体2.1初始化2.2插入(递归)2.3查找
3.有序表
1.顺序结构
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std
;
#define MAXSIZE 100
typedef int ElemType
;
typedef struct{
ElemType
*elem
;
int length
;
}SqList
;
void InitList(SqList
&L
){
L
.elem
= new ElemType
[MAXSIZE
];
L
.length
= 0;
return;
}
void GetElem(SqList L
, int i
, ElemType
&e
){
e
= L
.elem
[i
- 1];
return;
}
bool
LocateElem(SqList L
, ElemType e
){
for (int i
= 0; i
< L
.length
; i
++)
if (e
== L
.elem
[i
])return true
;
return false
;
}
void InsertList(SqList
&L
, int i
, ElemType e
){
if (i
<1 || i
>(L
.length
+ 1) || (L
.length
== MAXSIZE
)||LocateElem(L
,e
))return;
for (int j
= L
.length
- 1; j
>= i
- 1; j
--)
L
.elem
[j
+ 1] = L
.elem
[j
];
L
.elem
[i
- 1] = e
;
++L
.length
;
return;
}
void WatchList(SqList L
){
if (L
.length
== 0){
printf("表空\n");
return;
}
printf("顺序表:");
for (int i
= 0; i
< L
.length
; i
++)
printf("%d ", L
.elem
[i
]);
printf("\n");
return;
}
int main(){
SqList A
, B
;
InitList(A
); InitList(B
);
int n
, m
, e
;
cout
<< "A:";
cin
>> n
;
for (int i
= 1; i
<= n
; i
++){
cin
>> e
;
InsertList(A
, i
, e
);
}
cout
<< "B:";
cin
>> m
;
for (int i
= 1; i
<= m
; i
++){
cin
>> e
;
InsertList(B
, i
, e
);
}
for (int i
= A
.length
+ 1, j
= 1; i
<= A
.length
+ B
.length
&&j
<= B
.length
; j
++){
GetElem(B
, j
, e
);
if (LocateElem(A
, e
))
continue;
InsertList(A
, i
, e
);
i
++;
}
WatchList(A
);
system("PAUSE");
return 0;
}
1.0结构体
#define MAXSIZE 100
typedef int ElemType
;
typedef struct{
ElemType
*elem
;
int length
;
}SqList
;
1.1初始化
void InitList(SqList
&L
){
L
.elem
= new ElemType
[MAXSIZE
];
L
.length
= 0;
return;
}
1.2取值
void GetElem(SqList L
, int i
, ElemType
&e
){
e
= L
.elem
[i
- 1];
return;
}
1.3查找
bool
LocateElem(SqList L
, ElemType e
){
for (int i
= 0; i
< L
.length
; i
++)
if (e
== L
.elem
[i
])return true
;
return false
;
}
1.4插入
void InsertList(SqList
&L
, int i
, ElemType e
){
if (i
<1 || i
>(L
.length
+ 1) || (L
.length
== MAXSIZE
)||LocateElem(L
,e
))return;
for (int j
= L
.length
- 1; j
>= i
- 1; j
--)
L
.elem
[j
+ 1] = L
.elem
[j
];
L
.elem
[i
- 1] = e
;
++L
.length
;
return;
}
1.5输出
void WatchList(SqList L
){
if (L
.length
== 0){
printf("表空\n");
return;
}
printf("顺序表:");
for (int i
= 0; i
< L
.length
; i
++)
printf("%d ", L
.elem
[i
]);
printf("\n");
return;
}
2.链式结构(无头结点的单链表)
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std
;
#define MAXSIZE 100
#define ERROR 9999999
typedef int ElemType
;
typedef struct LNode
* LinkList
;
typedef struct LNode
{
ElemType data
;
LinkList next
;
}LNode
;
void InitList(LinkList
&L
){
L
= new LNode
;
L
->next
= NULL;
return;
}
void InsertList(LinkList
&L
, ElemType e
){
if (!L
){
InitList(L
);
L
->data
= e
;
}
else if (L
->data
!=e
)
InsertList(L
->next
, e
);
return;
}
int LocateList(LinkList L
, int i
,int length
){
if (i
< 1 || i
>length
)return ERROR
;
else
while (--i
){
L
= L
->next
;
}
return L
->data
;
}
int main(){
LinkList A
=NULL, B
=NULL;
int n
,m
;
ElemType e
;
cout
<< "A:";
cin
>> n
;
while (n
--){
cin
>> e
;
InsertList(A
, e
);
}
cout
<< "B:";
cin
>> n
;
m
= n
;
while (n
--){
cin
>> e
;
InsertList(B
, e
);
}
for (int i
= 1; i
<= m
; i
++){
e
= LocateList(B
, i
,m
);
if (e
!=ERROR
)
InsertList(A
, e
);
}
printf("合并:");
while (A
!=NULL){
printf("%d ", A
->data
);
A
= A
->next
;
}
system("PAUSE");
return 0;
}
2.0结构体
#define MAXSIZE 100
#define ERROR 9999999
typedef int ElemType
;
typedef struct LNode
* LinkList
;
typedef struct LNode
{
ElemType data
;
LinkList next
;
}LNode
;
2.1初始化
void InitList(LinkList
&L
){
L
= new LNode
;
L
->next
= NULL;
return;
}
2.2插入(递归)
void InsertList(LinkList
&L
, ElemType e
){
if (!L
){
InitList(L
);
L
->data
= e
;
}
else if (L
->data
!=e
)
InsertList(L
->next
, e
);
return;
}
2.3查找
int LocateList(LinkList L
, int i
,int length
){
if (i
< 1 || i
>length
)return ERROR
;
else
while (--i
){
L
= L
->next
;
}
return L
->data
;
}
3.有序表
1.可有相同元素,所以去掉插入和合并时查找相同元素若有则跳过的条件 2.有序 2.1顺序表加入快排 例如
bool
comp(ElemType a
,ElemType b
){
return a
< b
;
}
sort(A
.elem
, A
.elem
+ A
.length
, comp
);
2.2链表 在插入的时候有序插入,因为他不是顺序的结构,可以在插入的时候就比较大小,若不符合排序顺序则插入元素和当前元素的值(不是地址)互换再插入