[人工智能]实验二链表实验奇偶数分类

链表实现奇偶数分类

一、需求分析

1、数据存储结构为链表
2、输入形式为键盘包括数字1-9、空格、和回车
3、输出形式为打印形式
4、包含链表的基本操作
5、能够完成指定要求的排序操作
6、能够从一个链表中分离出奇数和偶数
7、能够删除非指定数字

二、概要设计

一、抽象数据类型定义

ADT numbers{
数据对象：{}
数据关系：{<a,b>}
基本操作：
MakeNode(Link &p, ElemType e)
操作结果：分配由p指向的值为e的结点
FreeNode(Link &p)
操作结果：释放p所指的结点
InitList(LinkList &L)
操作结果：初始化一个链表L
ClearList(LinkList &L)
初始条件：链表存在
操作结果：链表L重置为空表，并释放原链表的结点空间
DestroyList(LinkList &L)
初始条件：链表L存在
操作结果：销毁链表L，L不再存在
InsFirst(LinkList &L,Link s)
初始条件：链表L存在
操作结果：将s所指结点插入在第一个结点之前
GetCurElem(Link p)
操作结果：返回p所指结点中数据元素的值
Compare(Link p1, Link p2)
操作结果：如果p1所指元素大于p2则返回TURE，否则返回FALSE
ExchangeData(Link &p1,Link &p2)
操作结果：交换两个结点的数据
sort(LinkList &L)
操作结果：将链表排序为非递增链表
DeleteNode(LinkList &L, Link s)
初始条件：链表L不为空
操作结果：删除s所指结点
PrintList(LinkList &L)
初始条件：链表L存在
操作结果：在屏幕上打印出链表中的元素
}

二、宏定义部分

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

三、主程序流程图

四、程序结构图

三、详细设计

一、数据类型设计

/*顺序表的定义/
typedef struct LNode{ // 结点类型
ElemType data; //数据域
struct LNode *next; //指针域
} *Link, *Position;

typedef struct { // 链表类型
Link head; // 头结点
Link tail; // 最后一个结点
int len; // 线性链表中的数据元素格式
} LinkList;

二、数据操作

Status MakeNode(Link &p, ElemType e){
// 分配由p指向的值为e的结点。若分配失败，则返回ERROR
p = (Link)malloc(sizeof(LNode));
if(!p){
return ERROR;
}
p->data = e;
}

void FreeNode(Link &p){
// 释放p所指结点
free§;
p = NULL;
}

Status InitList(LinkList &L){
// 构造一个空的线性链表L
Link p;
p = (Link)malloc(sizeof(LNode)); // 生成头结点
if§{
p->next = NULL;
L.head = L.tail = p;
L.len = 0;
}
else
return ERROR;
}

void ClearList(LinkList &L){ // 将线性链表L重置为空表，并释放原链表的结点空间
Link p,q;
if(L.head!=L.tail) // 不是空表
{
p=q=L.head->next;
L.head->next=NULL;
while(p!=L.tail)
{
p=q->next;
free(q);
q=p;
}
free(q);
L.tail=L.head;
L.len=0;
}
}

Status DestroyList(LinkList &L){ // 销毁线性链表L，L不再存在(见图2.44)
ClearList(L); // 清空链表
FreeNode(L.head);
L.tail=NULL;
L.len=0;
}

Status InsFirst(LinkList &L,Link s){ // 形参增加L,因为需修改L
// h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前
Link h = L.head;
s->next=h->next;
h->next=s;
if(h==L.tail) // h指向尾结点
L.tail=h->next; // 修改尾指针
L.len++;
}

Status Compare(Link p1, Link p2) {
if(p1->data > p2->data){
return TRUE;
}else{
return FALSE;
}
}

void ExchangeData(Link &p1,Link &p2){ // 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
ElemType temp = p1->data;
p1->data = p2->data;
p2->data = temp;
}

ElemType GetCurElem(Link p){ // 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
return p->data;
}

void sort(LinkList &L){
for (int i = 0; i < L.len; i++)
{
Link p2 = L.head->next;
if(p2->next==NULL){
return;
}
Link p1 = L.head->next->next;
for (int j = 0; j <= L.len-2; j++)
{
if(Compare(p1,p2)){
ExchangeData(p1, p2);
}
p1 = p1->next;
p2 = p2->next;
}

}

}

Status DeleteNode(LinkList &L, Link s){
if(s == L.head || L.head == L.tail){
return FALSE;
}
if(s == L.tail){
Link p = L.head;
while(p->next!=L.tail){
p = p->next;
}
p->next = NULL;
L.tail = p;
FreeNode(s);
L.len–;
return TRUE;
}
Link p = L.head;
while(p->next!=s){
p = p->next;
}
p->next = p->next->next;
FreeNode(s);
L.len–;
return TRUE;
}

void PrintList(LinkList &L){
Link p = L.head->next;
for (int i = 0; i < L.len; i++)
{
printf("%d ", p->data);
p = p->next;
}

}

三、运算功能

void Function_1(LinkList &L, int mink, int maxk){//筛选出指定范围的数据
Link p1 = L.head;
while (p1->next!=NULL)
{
Link p2 = p1;
p1 = p1->next;
if(p1->data<mink || p1->data>maxk){
DeleteNode(L, p1);
p1 = p2;
}
}
}
void Function_2(LinkList &L_A, LinkList &L_B, LinkList &L_C){//分离出奇偶数
Link p = L_A.head;
while (p->next!=NULL)
{
p = p->next;
if (p->data%2==1)
{
Link s;
MakeNode(s, p->data);
InsFirst(L_B, s);
}
else
{
Link s;
MakeNode(s, p->data);
InsFirst(L_C, s);
}
}
}

四、主程序

int main(){
LinkList L_A, L_B, L_C;
InitList(L_A);
InitList(L_B);
InitList(L_C);

char a;
int b;
scanf("%d", &b);
scanf("%c", &a);
while (a!='\n')
{
    Link p;
    MakeNode(p, b);
    InsFirst(L_A, p);
    scanf("%d", &b);
    scanf("%c", &a);
}
Link p;
MakeNode(p, b);
InsFirst(L_A, p);

sort(L_A);
Function_1(L_A, 0, 20);
Function_2(L_A, L_B, L_C);
sort(L_B);
sort(L_C);
printf("\nL_A:");
PrintList(L_A);
printf("\nL_B:");
PrintList(L_B);
printf("\nL_C:");
PrintList(L_C);

}

四、调试分析

一、主要问题与解决方案
1、发现排序出现问题，调试后发现是遍历链表时循环一遍结束后未让指针指向下一个元素。
2、筛选函数出现报错，调试后发现指针在结点删除后变成空指针，未重新指向下一个结点，导致报错。

五、用户使用说明

一、本程序运行环境为Windows操作系统下的Microsoft Visual C++ 6.0。
二、在VC环境下打开程序后，输入整数，并用一个空格分隔，敲击“回车符”输入，即可以显示要求的结果。
三、按下任意键以继续。

六、测试结果

七、附录

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;  /**Status是函数类型，其值是函数结果状态代码，如OK等*/
typedef int ElemType;

/**顺序表的定义*/
typedef struct LNode{ // 结点类型
    ElemType data; //数据域
    struct LNode *next; //指针域
} *Link, *Position;

typedef struct { // 链表类型
    Link head; // 头结点
    Link tail; // 最后一个结点
    int len; // 线性链表中的数据元素格式
} LinkList;

Status MakeNode(Link &p, ElemType e){
    // 分配由p指向的值为e的结点。若分配失败，则返回ERROR
    p = (Link)malloc(sizeof(LNode));
    if(!p){
        return ERROR;
    }
    p->data = e;
}

void FreeNode(Link &p){
    // 释放p所指结点
    free(p);
    p = NULL;
}

Status InitList(LinkList &L){
    // 构造一个空的线性链表L
    Link p;
    p = (Link)malloc(sizeof(LNode)); // 生成头结点
    if(p){
        p->next = NULL;
        L.head = L.tail = p;
        L.len = 0;
    }
    else
        return ERROR;
}

void ClearList(LinkList &L){ // 将线性链表L重置为空表，并释放原链表的结点空间
    Link p,q;
    if(L.head!=L.tail) // 不是空表
    {
        p=q=L.head->next;
        L.head->next=NULL;
        while(p!=L.tail)
        {
            p=q->next;
            free(q);
            q=p;
        }
        free(q);
        L.tail=L.head;
        L.len=0;
    }
}

Status DestroyList(LinkList &L){ // 销毁线性链表L，L不再存在(见图2.44)
    ClearList(L); // 清空链表
    FreeNode(L.head);
    L.tail=NULL;
    L.len=0;
}

Status InsFirst(LinkList &L,Link s){ // 形参增加L,因为需修改L
 // h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前
    Link h = L.head;
    s->next=h->next;
    h->next=s;
    if(h==L.tail) // h指向尾结点
        L.tail=h->next; // 修改尾指针
    L.len++;
}

Status Compare(Link p1, Link p2) {
    if(p1->data > p2->data){
        return TRUE;
    }else{
        return FALSE;
    }
}

void ExchangeData(Link &p1,Link &p2){ // 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
    ElemType temp = p1->data;
    p1->data = p2->data;
    p2->data = temp;
}

ElemType GetCurElem(Link p){ // 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
    return p->data;
}

void sort(LinkList &L){
    for (int i = 0; i < L.len; i++)
    {
        Link p2 = L.head->next;
        if(p2->next==NULL){
            return;
        }
        Link p1 = L.head->next->next;
        for (int j = 0; j <= L.len-2; j++)
        {
            if(Compare(p1,p2)){
                ExchangeData(p1, p2);
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        
    }
    
}

Status DeleteNode(LinkList &L, Link s){
    if(s == L.head || L.head == L.tail){
        return FALSE;
    }
    if(s == L.tail){
        Link p = L.head;
        while(p->next!=L.tail){
            p = p->next;
        }
        p->next = NULL;
        L.tail = p;
        FreeNode(s);
        L.len--;
        return TRUE;
    }
    Link p = L.head;
    while(p->next!=s){
        p = p->next;
    }
    p->next = p->next->next;
    FreeNode(s);
    L.len--;
    return TRUE;
}

void PrintList(LinkList &L){
    Link p = L.head->next;
    for (int i = 0; i < L.len; i++)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    
}

void Function_1(LinkList &L, int mink, int maxk){
    //筛选出指定范围的数据
    Link p1 = L.head;
    while (p1->next!=NULL)      
    {
        Link p2 = p1;
        p1 = p1->next;
        if(p1->data<mink || p1->data>maxk){
            DeleteNode(L, p1);
            p1 = p2;
        }
    }
    
}

void Function_2(LinkList &L_A, LinkList &L_B, LinkList &L_C){
    //分离出奇数和偶数
    Link p = L_A.head;
    while (p->next!=NULL)
    {
        p = p->next;
        if (p->data%2==1)
        {
            Link s;
            MakeNode(s, p->data);
            InsFirst(L_B, s);
        }
        else
        {
            Link s;
            MakeNode(s, p->data);
            InsFirst(L_C, s);
        }   
    }
    
}


int main(){
    LinkList L_A, L_B, L_C;
    InitList(L_A);
    InitList(L_B);
    InitList(L_C);

    char a;
    int b;
    scanf("%d", &b);
    scanf("%c", &a);
    while (a!='\n')
    {
        Link p;
        MakeNode(p, b);
        InsFirst(L_A, p);
        scanf("%d", &b);
        scanf("%c", &a);
    }
    Link p;
    MakeNode(p, b);
    InsFirst(L_A, p);

    sort(L_A);
    Function_1(L_A, 0, 20);
    Function_2(L_A, L_B, L_C);
    sort(L_B);
    sort(L_C);
    printf("\nL_A:");
    PrintList(L_A);
    printf("\nL_B:");
    PrintList(L_B);
    printf("\nL_C:");
    PrintList(L_C);
}