线性表
线性表的概念
线性表：线性表是最常用且最简单的以重数据结构，是n个数据元素的的有序序列。
线性结构的特点：在非空线性结构表中，
- 存在唯一的一个被称为“第一个”的结点。
- 存在唯一的一个被称为“最后一个”的结点。
- 除第一个之外，表中的每个结点均只有一个前驱结点。
- 除最后一个之外，表中的每个结点均只有一个后继结点。
空表：线性表中元素n的个数为0，即n=0.
线性表的顺序存储结构（C语言）
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef int Status;
typedef struct
{
int *elem;
int length;
int listsize;
}SqList;
//构造一个空的线性表L
//该线性表预定义大小为LIST_INIT_SIZE
Status InitList_Sq(SqList &L)
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L.elem) return OK; // 存储分配失败
L.length = 0; // 空表长度为0
L.listsize = LIST_INIT_SIZE; // 初始存储容量
return OK;
}
//销毁线性表L
//销毁成功返回OK
Status DestroyList_Sq(SqList &L)
{
if(L.elem)
{
free(L.elem);
return OK;
}
else return ERROR;
}
//清除线性表L，重置为空表
Status ClearList_Sq(SqList &L)
{
if(!L.elem) return ERROR; //线性表不存在
L.length = 0; //记录表长（空表）
return OK;
}
Status ListLength(SqList &L)
{
return L.length;
}
Status GetElem(SqList &L,int i,ElemType &e)
{
if(i<L.length) return ERROR;
e = L.elem[i];
return OK;
}
//若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱。
Status PriorElem(SqList &L,ElemType cur_e,ElemType &pre_e)
{
int i = 0;
while(L.elem[i] != cur_e && i<L.length) {i++;}
if(i<L.length)
{
pre_e = L.elem[i-1];
return OK;
}
else return ERROR;
}
// 在顺序线性表L的第i个元素之前插入新的元素e，
// i的合法值为1≤i≤ListLength_Sq(L)+1
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
ElemType *p;
if (i < 1 || i > L.length+1) return ERROR; // i值不合法
if (L.length >= L.listsize) // 当前存储空间已满，增加容量
{
ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase) return ERROR; // 存储分配失败
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存储容量
}
ElemType *q = &(L.elem[i-1]); // q为插入位置
for (p = &(L.elem[L.length-1]); p>=q; --p)
*(p+1) = *p; // 插入位置及之后的元素右移
*q = e; // 插入e
++L.length; // 表长增1
return OK;
}
//在顺序线性表L中删除第i个元素，并用e返回其值。
//i的合法值为1≤i≤ListLength_Sq(L)。
Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
ElemType *p, *q;
if (i<1 || i>L.length) return ERROR; // i值不合法
p = &(L.elem[i-1]); // p为被删除元素的位置
e = *p; // 被删除元素的值赋给e
q = L.elem+L.length-1; // 表尾元素的位置
for (++p; p<=q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移
--L.length; // 表长减1
return OK;
}
// 输出顺序表中的所有元素
int Load_Sq(SqList &L)
{
int i;
if(L.length == 0) printf("The List is empty!");
else
{
printf("The List is: ");
for(int i=1;i<L.length+1;i++) printf("%d ",L.elem[i-1]);
}
printf("\n");
return OK;
}
int main()
{
SqList T;
int a, i;
ElemType e, x;
if(InitList_Sq(T)) // 判断顺序表是否创建成功
{
printf("顺序表创建成功\n");
}
while(1)
{
printf("1:插入数值\n2:删除数值\n3:打印所有数值\n");
printf("4:输出特定位置的数值\n");
printf("5:输出特定数值之前的数值\n");
printf("6:输出顺序表长\n");
printf("7:清空表\n");
printf("0:退出\n请选择:\n");
scanf("%d",&a);
switch(a)
{
case 1: scanf("%d%d",&i,&x);
if(!ListInsert_Sq(T,i,x)) printf("插入失败!\n"); // 判断i值是否合法，请填空
else printf("数值 %d 已经被成功插入!\n", x);
break;
case 2: scanf("%d",&i);
if(!ListDelete_Sq(T,i,e)) printf("删除失败!\n"); // 判断i值是否合法，请填空
else printf("数值 %d 已经被成功删除!\n", e);
break;
case 3: Load_Sq(T);
break;
case 4: scanf("%d",&i);
if(!GetElem(T, i, e)) printf("获取失败!\n");
else printf("第 %d 个数值是 %d!\n", i, e);
break;
case 5: scanf("%d",&i);
if(!PriorElem(T, i, e)) printf("无法找到!\n");
else printf("%d 前面是 %d\n",i,e);
break;
case 6: printf("表长是%d\n",ListLength(T));
break;
case 7: ClearList_Sq(T);
break;
case 0: return 1;
}
}
return 0;
}
