山东大学数据结构与算法分析:实验1 ADT表的编程与实现

一、实验目的

加深对抽象数据类型ADT表的理解；

二、实验原理

参照课本p.44-49，及Figure3.6-3.13.

三、实验内容

编写程序实现ADT表的定义，及常用操作：

1) 判断表是否为空；

2) 获取第i个节点的内容

3) 删除

4) 插入

四、实验要求

1) 复习C语言相关知识；

2) 实现完整的ADT表结构及操作，并给出应用。

五、实验源程序

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

typedef struct{
    int *elem;
    int length;
}List;

void InitList(List &L)                //构造一个空的线性表
{
    L.elem=(int*)malloc(sizeof(int));
    L.length=0;
}

int IsEmpty(List L)                   //判断表是否为空
{   
    if(!L.length)return 1;
    else return 0;
}

int Find(List L,int i)                  //找到第i个元素
{
    int e=L.elem[i-1];
    return e;
}

void Delete(List &L,int i)              //删除第i个节点
{
    int *p,*q;
    p=&(L.elem[i-1]);
    q=(L.elem+L.length-1);
     for (++p;p<=q;++p) *(p-1)=*p;
    L.length--;
}
void Insert(List &L,int i,int e)
{
    int *q,*p;
     q=&(L.elem[i]);
     for(p=&(L.elem[L.length-1]);p>=q;--p)   *(p+1)=*p;
     *q=e;
     L.length++;        
}
int main()
{
    List L;     //定义一个链表
    int intlength;
    int intelem;
    int i,e;
    int n;
    InitList(L);//初始化
    printf("请输入创建链表的节点个数:");
    scanf("%d",&intlength);
    printf("请依次输入数据：\n");
    for(int m=0;m<intlength;m++)
    {
        scanf("%d",&intelem);
        L.elem[m]=intelem;
        L.length++;
    }     
    printf("表中的数据依次为：");
    for(int n=0;n<L.length;n++)
    {
        printf("%d  ",L.elem [n]);
    }
    if(IsEmpty(L))printf("\n表为空\n\n");        //判断表是否为空
    else printf("\n表不为空\n\n");     

    printf("\n获取第i个节点的内容\n\n");     //获取第i个节点的数据
    printf("请输入想要获取第几个节点的内容:");
    scanf("%d",&i);
    printf("第%d个节点的内容为：%d\n",i,e=Find(L,i));

    printf("\n删除操作\n\n");                //删除第i个节点的数据
    printf("请输入想要删除第几个节点的内容:");
    scanf("%d",&i);
    Delete(L,i);//调用Delete函数
    printf("删除后的表中数据为：");
    for(n=0;n<L.length;n++)
    {
        printf("%d  ",L.elem [n]);
    }
    printf("\n长度为：%d\n",L.length);

    printf("\n插入操作\n\n");                //在第i个节点插入数据
    printf("请输入想要插入第几个节点后:");
    scanf("%d",&i);
    printf("请输入想要插入数据:");
    scanf("%d",&e);
    Insert(L,i,e);
    printf("插入后的表中数据为:");
    for(n=0;n<L.length;n++)
    {
        printf("%d  ",L.elem [n]);
    }
    printf("\n");
}