数据结构-线性表的顺序表示实现
程序员文章站
2024-03-20 14:28:52
...
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Elemtype;
typedef struct {
Elemtype* elem;
int length;
int listsize;
}SqList;
//初始化
void InitList_Sq(SqList*L) {
(*L).elem = (Elemtype*)malloc(LIST_INIT_SIZE * sizeof(Elemtype));
if (!(*L).elem) {
printf("内存申请失败");
return ;
}
(*L).length = 0;
(*L).listsize = LIST_INIT_SIZE;
printf("初识化成功\n");
}//插入数据
void ListInsert_Sq(SqList*L, int i, Elemtype e) {
if (i<1 || i>(*L).length + 1) {
printf("插入数据 %d 失败!!!\n",e);
return;
}
if ((*L).length >= (*L).listsize) {
int* newbase=NULL;
newbase = (Elemtype*)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(Elemtype));
if (!newbase) {
printf("内存申请失败");
return;
}
(*L).elem = newbase;
L->listsize += LISTINCREMENT;
}
int* q,*p;
q = &((*L).elem[i - 1]);
for (p = &((*L).elem[(*L).length - 1]); p >= q; --p)
{
*(p + 1) = *p;
}
*q = e;
++(*L).length;
printf("插入数据 %d 成功\n",e);
}
//删除表中第i位置数据
void ListDelete_Sq(SqList* L, int i, Elemtype* e) {
if ((i < 1) || (i > (*L).length)) {
printf("无法删除第 %d 位置上的元素\n", i);
return;
}
int* p,*q;
p = &((*L).elem[i-1]);
(*e) = *p;
q = (*L).elem + (*L).length - 1;
for (++p; p <= q; ++p) *(p - 1) = *p;
--(*L).length;
printf("删除元素 %d 成功\n", *e);
return;
}
//线性表已存 在将L重置为空表
void ClearList_Sq(SqList* L){
if ((*L).elem != NULL) {
(*L).length = 0;
printf("线性表已清空\n");
}
else {
printf("线性表不存在\n");
}
}
//线性表存在 若L为空返回True,否则返回false
void ListEmpty_Sq(SqList* L) {
if ((*L).elem != NULL) {
if ((*L).length == 0) {
printf("线性表为空\n");
}
else {
printf("线性表不为空\n");
}
}
else {
printf("线性表不存在\n");
}
}
//线性表存在 销毁线性表
void DestroyList_Sq(SqList* L) {
if ((*L).elem != NULL) {
free((*L).elem);
(*L).length = 0;
(*L).listsize = 0;
(*L).elem = NULL;
printf("线性表销毁成功\n");
}
else{
printf("线性表不存在\n");
}
}
//线性表存在 返回L中元素的个数
int ListLength_Sq(SqList* L) {
if ((*L).elem != NULL) {
printf("线性表的长度是 %d\n", (*L).length);
return (*L).length;
}
else {
printf("线性表不存在\n");
return -1;
}
}
//线性表存在 用e返回L中的第i个数据元素的值
void GetElem(SqList* L,int i,Elemtype *e) {
if ((*L).elem != NULL){
if (i<1 || i>(*L).length) {
printf("无法获取此位置上的元素\n");
return ;
}
(*e) =(*L).elem[i - 1];
}
else {
printf("线性表不存在\n");
}
}
//比较两个元素是否相等
int compare(Elemtype a , Elemtype b) {
if (a == b) {
return 1;
}
else {
return 0;
}
}
//线性表L已存在,compare()是数据元素判定函数 返回L中第一个与e满足关系compare()的数据元素的位,若这样的数据元素不存在,则返回0
int LocateElem_Sq(SqList *L, Elemtype e, int (*compare)(Elemtype,Elemtype)){
Elemtype * p;
int i;
i = 1;
p = (*L).elem;
while (i <= L->length && !(*compare)(*p++, e))++i;
if (i <= (*L).length) return i;
else return 0;
}
//线性表L已存在cur_e是L的数据元素且不是第一个 返回元素cur_e的前驱元素
void PriorElem(SqList* L, Elemtype cur_e, Elemtype* pre_e){
int i=LocateElem_Sq(L, cur_e, compare);
*pre_e = (*L).elem[i-2];
}
//线性表L已存在cur_e是L的数据元素且不是最后一个 返回元素next_e的后继元素
void NextElem(SqList* L, Elemtype cur_e, Elemtype* pre_e) {
int i = LocateElem_Sq(L, cur_e, compare);
*pre_e = (*L).elem[i];
}
void visit(Elemtype i) {
printf(" %d", i);
}
//线性表已存在 依次对L的每个数据元素调用函数visit()
void ListTraverse_Sq(SqList* L, void (*visit)(Elemtype)) {
int i = 0;
while (i < (*L).length) {
(*visit)((*L).elem[i]);
i++;
}
printf("\n");
}
int equal(SqList* L, Elemtype *e) {
int i=0;
while (i < (*L).length) {
if ((*e) == (*L).elem[i]) return 1;
i++;
}
return 0;
}
int LocateElem(SqList* L, Elemtype e, int (*equal)(SqList*, Elemtype)){
return (*equal)(L, &e);
}
void Aunion(SqList *La,SqList Lb){
int La_len = ListLength_Sq(La);
int Lb_len = ListLength_Sq(&Lb);
for (int i = 1; i <= Lb_len; i++) {
int e;
GetElem(&Lb, i, &e);
if (!LocateElem(La, e, equal)) ListInsert_Sq(La, ++La_len, e);
}
}
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc) {
Elemtype * pa, * pb,*pc;
pa = La.elem; pb = Lb.elem;
(*Lc).listsize = (*Lc).length = La.length + Lb.length;
pc = (*Lc).elem = (Elemtype*)malloc((*Lc).listsize * sizeof(Elemtype));
if (!(*Lc).elem) {
printf("内存申请失败");
return;
}
Elemtype* pa_last, * pb_last;
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last) {
if (*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while (pa <= pa_last)*pc++ = *pa++;
while (pb <= pb_last)*pc++ = *pb++;
}
int main() {
//SqList L;
//InitList_Sq(&L);
//
测试
printf(" %d %d", L.length,L.listsize);
//
//int i=0;
//while (i<10) {
// L.elem[i] = i;
// i++;
// L.length++;
//}
//
测试
///*int j = 0;
//while (j < 10) {
// printf("%d ", L.elem[j]);
// j++;
//
//}*/
//
//ListInsert_Sq(&L, 1, 10);
//
测试是否插入成功
///*int x = 0;
//while (x < 11) {
// printf("%d ", L.elem[x]);
// x++;
//}*/
//
//ListInsert_Sq(&L, 0, 11);
//int e;
//ListDelete_Sq(&L, 2, &e);
//printf("e = %d\n", e);
测试
//int x = 0;
//while (x < L.length) {
// printf("%d ", L.elem[x]);
// x++;
//}
//printf("\n");
//ListLength_Sq(&L);
//
//GetElem(&L, 1, &e);
//printf("获取元素为e = %d\n", e);
//
//e = LocateElem_Sq(&L, 10, compare);
//printf("元素 10 的位置为 %d\n", e);
//e = LocateElem_Sq(&L, 5, compare);
//printf("元素 5 的位置为 %d\n", e);
//
//int pre_e;
//PriorElem(&L, 1, &pre_e);
//printf("1的前驱元素是 %d\n", pre_e);
//NextElem(&L, 1, &pre_e);
//printf("1的元素是 %d\n", pre_e);
//ListTraverse_Sq(&L,visit);
//ClearList_Sq(&L);
//ListEmpty_Sq(&L);
//DestroyList_Sq(&L);
//ListEmpty_Sq(&L);
//--------------------------------------------
SqList L2;
InitList_Sq(&L2);
int i2 = 0;
while (i2 < 5) {
L2.elem[i2] = i2;
i2++;
L2.length++;
}
SqList L3;
InitList_Sq(&L3);
int i3 = 0;
while (i3 < 5) {
L3.elem[i3] = i3+5;
i3++;
L3.length++;
}
//int j = 0;
//while (j < L2.length) {
// printf("%d ", L2.elem[j]);
// j++;
//}
//printf("\n");
//j = 0;
//while (j < L3.length) {
// printf("%d ", L3.elem[j]);
// j++;
//}
//printf("\n");
//Aunion(&L3, L2);
//j = 0;
//while (j < L3.length) {
// printf("%d ", L3.elem[j]);
// j++;
//}
//printf("\n");
//--------------------------------------------
SqList L4;
InitList_Sq(&L4);
MergeList_Sq(L2,L3,&L4);
int j = 0;
while (j < L4.length) {
printf("%d ", L4.elem[j]);
j++;
}
system("pause");
return 0;
}
上一篇: HSSFWorkbook生成excel中文名下载防乱码
下一篇: 关于java数组的一点小技巧