数据结构线性表基本操作(C语言).doc

#include<stdio.h>
#include<stdlib.h>
#include<Define.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;

Status InitList_Sq(SqList *L); //构造空的线性表
void DestroyList_Sq(SqList *L); //销毁一个线性表
void ClearList_Sq (SqList *L); //将L置为空表
Status ListEmpty_Sq (SqList L); //空表返回TRUE
Status ListLength_Sq (SqList L); // 返回元素个数
Status GetElem_Sq (SqList L, int i, ElemType *e); //用e返回第i个元素 算法2.2中使用
Status LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType)); // 在L中找到一个值与e满足compare()的元素的位序
Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType *pre_e); //用pre_e返回cur_e的前驱
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType *next_e); //用next_e返回cur_e的后继
Status ListInsert_Sq(SqList *L, int i, ElemType e); //在第i位插入新的元素e
Status ListDelete_Sq(SqList *L, int i, ElemType *e); //删除第i个元素 用e返回

//算法2.3
Status InitList_Sq(SqList *L) // 构造空的线性表
{
L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (! L->elem)
{
printf("构造失败!\n");
exit(OVERFLOW);
}
L->length = 0;
L->listsize = LIST_INIT_SIZE;
printf("构造成功！\n");

return OK;
}

void DestroyList_Sq(SqList *L) // 销毁一个线性表
{
if (L->elem != NULL)
{
free (L->elem);
L->elem = NULL;
L->length = 0;
L->listsize = 0;
printf("已销毁线性表!\n");
}
}

void ClearList_Sq (SqList *L) //将L置为空表
{
if(L->elem != NULL)
{
L->length = 0;
printf("已将L置为空表!\n");
}
}

Status ListEmpty_Sq (SqList L) // 空表返回TRUE
{
if (L.elem != NULL)
{
if (L.length == 0)
{
printf("是空表\n");
return TRUE;
}
else
{
printf("不是空表\n");
return FALSE;
}
}
else
{
exit(ERROR);
}
}
Status ListLength_Sq (SqList L) // 返回元素个数
{
if (L.elem != NULL)
{
return L.length;
}
else
{
return ERROR;
}
}

Status GetElem_Sq (SqList L, int i, ElemType *e) //用e返回第i个元素 算法2.2中使用
{
if (ListEmpty_Sq(L))
{
printf("为空表!\n");
return ERROR;
}
if (i < 1 || i > L.length)
{
printf("不存在地%d个位置!\n", i);
return ERROR;
}
*e = L.elem[i - 1];

return OK;
}

//算法2.6
Status LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType)) // 在L中找到一个值与e满足compare()的元素的位序
{
int i = 1;
int *p = L.elem;

while (i <= L.length && !(* compare)(*p ++, e))
{
++i;
}
if (i <= L.length)
{
return i;
}
else
{
return 0;
}
}/*指向函数的指针*/

Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType *pre_e) //用pre_e返回cur_e的前驱
{
int i = 2;

while (i <= L.length)
{
if (cur_e == L.elem[i - 1])
{
*pre_e = L.elem[i - 2];

return OK;
}
i ++;
}

return ERROR;
}
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType *next_e) //用next_e返回cur_e的后继
{
int i = 1;

while (i < L.length)
{
if (cur_e == L.elem[i - 1])
{
*next_e = L.elem[i];

return OK;
}
i ++;
}

return ERROR;
}

//算法2.4
Status ListInsert_Sq(SqList *L, int i, ElemType e) //在第i位插入新的元素e
{
ElemType *newbase, *p, *q;
if (i < 1 || i > L->length +1)
{
return ERROR;
}
if (L->length >= L->listsize)
{
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;
}

//算法2.5
Status ListDelete_Sq(SqList *L, int i, ElemType *e) //删除第i个元素 用e返回
{
ElemType *p, *q;
if (i < 1 || i > L->length)
{
return ERROR;
}
p = &(L->elem[i -1]);
*e = *p;
q = L->elem + L->length - 1;
for (++ p; p <= q; p ++)
{
*(p - 1) = *p;
}
-- L->length;

return OK ;
}

Status main(void)
{
SqList L;
ElemType i, n = 0, e = 0, cur_e = 0, pre_e = 0, next_e = 0;
char ch;
printf("初始化线性表···");
InitList_Sq(&L);
printf("是否销毁线性表L? 'Y'OR'N' ");
ch = getchar();
if (ch == 'Y')
{
DestroyList_Sq(&L);

return 0;
}
else
{
ClearList_Sq(&L);
}
for (i = 1; i <= LISTINCREMENT; i ++)
{
L.elem[i - 1] = i;
L.length ++;
}
printf("线性表内初始数值为:\n");
for (i = 1; i <= LISTINCREMENT; i ++)
{
printf("%4d", L.elem[i - 1]);
}
printf("\n");
n = ListLength_Sq (L);
printf("线性表内元素个数为 %3d\n", n);
printf("欲知道第i位数字 i = ");
scanf("%d", &i);
GetElem_Sq(L, i, &e);
printf("第%d位数字为%d\n", i, e);

cur_e = e;
PriorElem_Sq(L, cur_e, &pre_e);
printf("%d的前驱是%d\n", cur_e, pre_e);

NextElem_Sq(L, cur_e, &next_e);
printf("%d的后继是%d\n", cur_e, next_e);

printf("请输入要插入的位数和要插入的数字:");
scanf("%d %d", &n, &e);
ListInsert_Sq(&L, n, e);
printf("插入后线性表内%d个数据为:\n", L.length);
for (i = 1; i <= L.length; i ++)
{
printf("%4d", L.elem[i - 1]);
}
printf("\n");
ListDelete_Sq(&L, n, &e);
printf("删除线性表中第%d个数据%d后，线性内%d个数据为:\n", n, e, L.length);
for (i = 1; i <= L.length; i ++)
{
printf("%4d", L.elem[i - 1]);
}
printf("\n");

return 0;
}