线性表

线性表的概念

线性表：线性表是最常用且最简单的以重数据结构，是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;
}