数据结构与数据库实验（数据结构部分）——实验1 ADT表的编程与实现

一、实验目的

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

二、实验原理

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

三、实验内容

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

判断表是否为空；
获取第i个节点的内容
删除
插入

四、实验要求

复习C语言相关知识；
实现完整的ADT表结构及操作，并给出应用。

五、实验源程序

ADTList.h 头文件

#ifndef _ADTList_H
struct Node;
#ifndef _ADTList_H
struct Node;
typedef struct Node* PtrToNode;     //将Node结构体首地址定义为PtrToNode
typedef PtrToNode List;         //链表首节点地址
typedef PtrToNode Position;     //当前位置地址

List MakeEmpty();    //创建链表头结点
int IsEmpty();      //测试一个链表是否为空链表
int IsLast(Position P);         //测试当前位置是否为链表的末尾的函数
Position Find(int X);   //查找某元素，并返回元素所在结构体的指针
Position FindPrevious(int X);   //查找某元素，并返回元素所在结构体的前一个结构体的指针
void Delete(int X);     //删除某元素
Position FindPrevious(int X);   //查找某个元素的前驱
void Insert(int X,Position P);  //插入某元素到链表
void PrintList();       //打印链表
void RefreshNode();     //刷新链表各节点node元素

#endif // !_ADTList_H

ADTList.c 主程序文件

#include<stdio.h>
#include<ADTList.h>
#include<stdlib.h>
List ListStart;
Position pin;
int nodenum = 0;
struct Node
{
    int element;
    int node;
    Position next;
};
List MakeEmpty()
{
    List L= (List)malloc(sizeof(struct Node));
    L->element = 0;
    L->next = NULL;
    L->node = nodenum;
    nodenum++;
    return L;
}

void ListOrder(int X)
{
    Position p2=(Position)malloc(sizeof(struct Node));
    pin->next = p2;
    p2->element = X;
    p2->next = NULL;
    p2->node = nodenum;
    pin = p2;
    nodenum++;
}

int IsEmpty()
{
    return ListStart->next == NULL;
}

int IsLast(Position P)
{
    return P->next == NULL;
}

Position Find(int X)
{
    Position P;
    P = ListStart->next;
    while ( P != NULL && P -> element!=X)
    {
        P = P -> next;
    }
    return P;
}

Position FindPrevious(int X)
{
    Position P,TmpCell;
    TmpCell = ListStart;
    P = ListStart->next;
    while ( P != NULL && P -> node!=X)
    {
        TmpCell = P;
        P = P -> next;
    }
    return TmpCell;
}

void Delete(int X)
{
    Position P,TmpCell;
    P = FindPrevious(X);
    if(!IsLast(P))
    {
        TmpCell = P->next;
        P->next = TmpCell->next;
        free(TmpCell);
        
        nodenum--;
    }
    RefreshNode();
}

void Insert(int X, Position P)
{
    Position TmpCell = (Position)(malloc(sizeof(struct Node)));
    if (TmpCell == NULL)
        printf("Out of space");
    TmpCell->element = X;
    TmpCell->next = P->next;
    P->next = TmpCell;
    nodenum++;
    RefreshNode();
}

void PrintList()
{
    Position P = ListStart;
    do
    {
        printf("节点%d:\t%d\n", P->node, P->element);
        P = P->next;
    } while (P != NULL);
    printf("节点个数为：%d\n", nodenum);
}

void RefreshNode()
{
    Position ptemp = ListStart;
    int j = 0;
    do
    {
        ptemp->node = j;
        ptemp = ptemp->next;
        j++;
    } while (ptemp != NULL);
}


//.c文件中声明的函数
void DeleteX()
{
    int X;
    printf("请输入要删除的节点：");
    scanf_s("%d", &X);
    if (X != 0)
    {
        Delete(X);
    }
    else
    {
        printf("不能删除头结点！");
    }
}

void FindX()
{
    int X;
    printf("请输入要查找的整数元素数值：");
    scanf_s("%d", &X);
    Position P = Find(X);
    printf("%d位于链表的第%d个节点\n", X, P->node);

}

void InsertX()
{
    int num;
    int X;
    Position P=ListStart;
    printf("请输入要插入的位置：");
    scanf_s("%d",&num);
    while ((P->next)->node!=num)
    {
        P = P->next;
    }
    printf("请输入要插入的整数元素：");
    scanf_s("%d",&X);
    Insert(X,P);
    
}

int main(void)
{
     ListStart = MakeEmpty();
    int temp, i,x;
    Position p1=ListStart;
    pin = ListStart;
    while (1)
    {
        printf("请选择要执行的事项：1. 按顺序输入链表    2.插入链表节点    3.删除链表节点    4.根据元素值查找位置 5.输出链表  6.判断元素当前位置是否为链表末端   7.判断链表是否为空\n");
        scanf_s("%d", &temp);
        switch (temp)
        {
            case 1: 
                printf("请输入要插入的整数元素：");
                scanf_s("%d", &x);
                ListOrder(x);
                break;
            case 2:
                InsertX(ListStart);
                break;
            case 3:
                DeleteX(ListStart);
                break;
            case 4:
                FindX(ListStart);
                break;
            case 5:
                PrintList(ListStart);
                break;
            case 6:
                printf("请输入要查询的节点位置：");
                scanf_s("%d", &i);
                while (p1->node != i)
                {
                    p1 = p1->next;
                }
                if (IsLast(p1))
                    printf("该位置是链表末端\n");
                else printf("该位置不是链表末端\n");
                break;
            case 7:
                if (IsEmpty(ListStart))
                    printf("这是一个空链表\n");
                else printf("这不是一个空链表\n");
                break;

        }
    }
}