数据结构实验一：顺序表

实现顺序表的各种基本运算的算法

1 实验目的

领会顺序表存储结构和掌握顺序表中的各种基本运算算法设计。

2 实验内容

编写一个程序sqlist.cpp，实现顺序表的各种基本运算和整体建表算法（假设顺序表的元素类型 ElemType 为 char），并在此基础上设计一个程序exp2-1.cpp完成以下功能。

1. 初始化顺序表L。
2. 依次插入a、b、c、d、e元素。
3. 输出顺序表L。
4. 输出顺序表L的长度。
5. 判断顺序表L是否为空。
6. 输出顺序表L的第3个元素。
7. 输出元素a的位置。
8. 在第4个元素位置上插入f元素。
9. 输出顺序表L。
10. 删除顺序表L的第三个元素。
11. 输出顺序表L。
12. 释放顺序表L。

3 软件程序

#include <stdio.h>  
#include <stdlib.h>  
#include <malloc.h>  
  
#define MaxSize 20  
typedef char ElemType;  
  
typedef struct  
{  
    ElemType data[MaxSize];  
    int length;  
}SqList;  
  
  
void InitList(SqList * &L)  
{  
    L = (SqList *)malloc(sizeof(SqList));  
    L->length = 0;  
}  
bool ListInsert(SqList * &L,int i,ElemType e)  
{  
    int j;  
    if(i<1 || i>L->length+1 || L->length==MaxSize) return false;  
    i--;  
    for (j=L->length;j>i;j--) L->data[j]=L->data[j-1];  
    L->data[i] = e;  
    L->length++;  
    return true;  
}  
void DispList(SqList *L)  
{  
    for (int i=0;i<L->length;i++) printf("%c",L->data[i]);  
    printf("\n");  
}  
int ListLength(SqList *L)  
{  
    return(L->length);  
}  
bool ListEmpty(SqList *L)  
{  
    return (L->length == 0);  
}  
bool GetElem(SqList *L,int i,ElemType &e)  
{  
    if(i<1 || i>L->length) return false;  
    e = L->data[i-1];  
    return true;  
}  
int LocateElem(SqList *L,ElemType e)  
{  
    int i = 0;  
    while(i<L->length && L->data[i]!=e)  
        i++;  
    if(i>=L->length)  
        return 0;  
    else  
        return i+1;  
}  
bool ListDelete(SqList * &L,int i,ElemType &e)  
{  
    int j;  
    if(i<1 || i>L->length)  
        return false;  
    i--;  
    e = L->data[i];  
    for (j=i;j< L->length-1;j++)  
        L->data[j]=L->data[j+1];  
    return true;  
}  
void DestoryList(SqList * &L)  
{  
    free(L);  
}  
  
  
int main(){  
    SqList *L;  
    ElemType e;  
    printf("(1)初始化线性表\n");  
    InitList(L);  
    printf("(2)依次插入 a、b、c、d、e 元素\n");  
    ListInsert(L,1,'a');  
    ListInsert(L,2,'b');  
    ListInsert(L,3,'c');  
    ListInsert(L,4,'d');  
    ListInsert(L,5,'e');  
    printf("(3)输出顺序表 L\n");  
    DispList(L);  
    printf("(4)输出顺序表 L 的长度\n");  
    printf("%d\n",ListLength(L));  
    printf("(5)判断顺序表 L 是否为空\n");  
    if(ListEmpty(L))  
        printf("顺序表 L 为空\n");  
    else  
        printf("顺序表 L 不为空\n");  
    printf("(6)输出顺序表 L 的第 3 个元素\n");  
    if(GetElem(L,3,e))  
        printf("%c\n",e);  
    else  
        printf("不存在第 3 个元素\n");  
    printf("(7)输出元素 a 的位置\n");  
    printf("%d\n",LocateElem(L,'a'));  
    printf("(8)在第 4 个元素位置上插入 f 元素\n");  
    ListInsert(L,4,'f');  
    printf("(9)输出顺序表 L\n");  
    DispList(L);  
    printf("(10)删除顺序表 L 的第 3 个元素\n");  
    if(ListDelete(L,3,e))  
        printf("已删除第 3 个元素：%c\n",e);  
    else  
        printf("删除第 3 个元素失败！\n");  
    printf("(11)输出顺序表 L\n");  
    DispList(L);  
    printf("(12)释放顺序表 L\n");  
    DestoryList(L);  
    return 0;  
}  

4 实验结果