如何设计一个支持长尾词检索的高效数据结构？
- 内容介绍
- 文章标签
- 相关推荐
本文共计812个文字，预计阅读时间需要4分钟。
实现以下排序表的下列操作：（数据元素为int）1. 排序表的初始化：InitList(L)2. 读取排序表的第i个元素：GetElem(L, i, e)3. 排序表的插入：ListInsert(L, i, e)4. 排序表的遍历：ListTraverse(L, visit())
作业要求
编程实现顺序表(数据元素为int)的下列操作 1.顺序表的初始化：InitList(&L) 2.读取顺序表的第i个元素：GetElem(L,i,&e) 3.顺序表的插入:ListInsert(&L,i,e) 4.顺序表的遍历：ListTraverse(L,visit()) 5.顺序表排序(升序)：ListSort(&L) 6.顺序表的归并：MergeList(La,Lb,&Lc) 7.在main函数中调用ListInsert建立表A和表B，其长度为m,n(通过键盘输入，m,n为大于0小于20的整数）， 表中数据元素为随机整数（随机数的产生方法请自行查阅）。 之后调用ListSort将表A和表B排序 再调用MergeList将表A和表B归并为表C 最后调用ListTraverse将表C遍历输出。
代码实现
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define ERROR 0
#define FALSE 0
#define OVERFLOW -2
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList* L)
{//1.顺序表的初始化
L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L->elem)
exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
Status GetElem(SqList L, int i, ElemType* e)
{//2.读取顺序表的第i个元素
if (i<1 || i>L.length)
return -1;
*e = L.elem[i - 1];//第i-1个单元存储第i个数据
return OK;
}
Status ListInsert(SqList* L, int i, ElemType e)
{//3.顺序表的插入
ElemType* p = NULL, * q = NULL;
if (i<1 || i>L->length + 1)
return ERROR;
if (L->length >= L->listsize)
{
ElemType* newbase;
newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L->elem = newbase;
L->listsize += LISTINCREMENT;
}
q = &(L->elem[i - 1]);
for (p = &(L->elem[L->length - 1]); p >= q; p--)
*(p + 1) = *p;
*q = e;
L->length++;
return OK;
}
Status ListTraverse(SqList L, int (*visit)(ElemType x))
{//4.顺序表的遍历
int i;
for (i = 1; i <= L.length; i++)
(*visit)(L.elem[i - 1]);
return OK;
}
Status visit(ElemType e)
{
printf("%d\t", e);
return OK;
}
int ListSort(SqList *L)
{//5.升序排序
ElemType i,j,temp=0;
for(i=0;i<=L->length-1;i++){
for(j=i+1;j<=L->length-1;j++){
if(L->elem[i]>L->elem[j]){
temp=L->elem[i];
L->elem[i]=L->elem[j];
L->elem[j]=temp;
}
}
}
return OK;
}
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc)
{//6.顺序表的归并
ElemType* pa, * pb, * pc = NULL;
ElemType* pa_last, * pb_last = NULL;
pa = La.elem;
pb = Lb.elem;
pc = Lc->elem = (ElemType*)malloc(Lc->listsize * sizeof(ElemType));
Lc->listsize = Lc->length = La.length + Lb.length;
if (!Lc->elem)
exit(OVERFLOW);
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()
{
int m, n;
int i, j;
SqList A, B, C;
int ret1 = 0, ret2 = 0;
InitList(&A);
InitList(&B);
printf("请输入表A和表B的长度:\n");
scanf_s("%d %d", &m, &n);
srand((unsigned int)time(NULL));
printf("\n表A：\n");
for (i = 1; i <= m; i++)
{
ret1 = rand() % 100 + 1;
ListInsert(&A, i, ret1);
printf("%d ", A.elem[i - 1]);
}
printf("\n表B：\n");
for (j = 1; j <= n; j++)
{
ret2 = rand() % 100 + 1;
ListInsert(&B, j, ret2);
printf("%d ", B.elem[j - 1]);
}
ListSort(&A);
ListSort(&B);
MergeList_Sq(A, B, &C);
printf("\n表c:\n");
ListTraverse(C, visit);
return 0;
}
测试结果
本文共计812个文字，预计阅读时间需要4分钟。
实现以下排序表的下列操作：（数据元素为int）1. 排序表的初始化：InitList(L)2. 读取排序表的第i个元素：GetElem(L, i, e)3. 排序表的插入：ListInsert(L, i, e)4. 排序表的遍历：ListTraverse(L, visit())
作业要求
编程实现顺序表(数据元素为int)的下列操作 1.顺序表的初始化：InitList(&L) 2.读取顺序表的第i个元素：GetElem(L,i,&e) 3.顺序表的插入:ListInsert(&L,i,e) 4.顺序表的遍历：ListTraverse(L,visit()) 5.顺序表排序(升序)：ListSort(&L) 6.顺序表的归并：MergeList(La,Lb,&Lc) 7.在main函数中调用ListInsert建立表A和表B，其长度为m,n(通过键盘输入，m,n为大于0小于20的整数）， 表中数据元素为随机整数（随机数的产生方法请自行查阅）。 之后调用ListSort将表A和表B排序 再调用MergeList将表A和表B归并为表C 最后调用ListTraverse将表C遍历输出。
代码实现
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define ERROR 0
#define FALSE 0
#define OVERFLOW -2
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType* elem;
int length;
int listsize;
}SqList;
Status InitList(SqList* L)
{//1.顺序表的初始化
L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L->elem)
exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
Status GetElem(SqList L, int i, ElemType* e)
{//2.读取顺序表的第i个元素
if (i<1 || i>L.length)
return -1;
*e = L.elem[i - 1];//第i-1个单元存储第i个数据
return OK;
}
Status ListInsert(SqList* L, int i, ElemType e)
{//3.顺序表的插入
ElemType* p = NULL, * q = NULL;
if (i<1 || i>L->length + 1)
return ERROR;
if (L->length >= L->listsize)
{
ElemType* newbase;
newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L->elem = newbase;
L->listsize += LISTINCREMENT;
}
q = &(L->elem[i - 1]);
for (p = &(L->elem[L->length - 1]); p >= q; p--)
*(p + 1) = *p;
*q = e;
L->length++;
return OK;
}
Status ListTraverse(SqList L, int (*visit)(ElemType x))
{//4.顺序表的遍历
int i;
for (i = 1; i <= L.length; i++)
(*visit)(L.elem[i - 1]);
return OK;
}
Status visit(ElemType e)
{
printf("%d\t", e);
return OK;
}
int ListSort(SqList *L)
{//5.升序排序
ElemType i,j,temp=0;
for(i=0;i<=L->length-1;i++){
for(j=i+1;j<=L->length-1;j++){
if(L->elem[i]>L->elem[j]){
temp=L->elem[i];
L->elem[i]=L->elem[j];
L->elem[j]=temp;
}
}
}
return OK;
}
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc)
{//6.顺序表的归并
ElemType* pa, * pb, * pc = NULL;
ElemType* pa_last, * pb_last = NULL;
pa = La.elem;
pb = Lb.elem;
pc = Lc->elem = (ElemType*)malloc(Lc->listsize * sizeof(ElemType));
Lc->listsize = Lc->length = La.length + Lb.length;
if (!Lc->elem)
exit(OVERFLOW);
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()
{
int m, n;
int i, j;
SqList A, B, C;
int ret1 = 0, ret2 = 0;
InitList(&A);
InitList(&B);
printf("请输入表A和表B的长度:\n");
scanf_s("%d %d", &m, &n);
srand((unsigned int)time(NULL));
printf("\n表A：\n");
for (i = 1; i <= m; i++)
{
ret1 = rand() % 100 + 1;
ListInsert(&A, i, ret1);
printf("%d ", A.elem[i - 1]);
}
printf("\n表B：\n");
for (j = 1; j <= n; j++)
{
ret2 = rand() % 100 + 1;
ListInsert(&B, j, ret2);
printf("%d ", B.elem[j - 1]);
}
ListSort(&A);
ListSort(&B);
MergeList_Sq(A, B, &C);
printf("\n表c:\n");
ListTraverse(C, visit);
return 0;
}