分类 数据结构 下的文章

NCIAE_ Data_Structure

项目地址:https://github.com/TyrantJoy/NCIAE_Data_Structure

概述

​ 本项目是源自于北华航天工业学院大二数据结构科目的结业实训,整体来说较为简单,主要是数据结构中一些基础知识:例如线性表的删除、遍历、增加、排序;图的生成与迪杰斯特拉算法;文件的读写等。

​ 本项目在Dev C++环境下开发,clone本项目到本地之后,使用Dev C++打开Management System.dev文件,即可使用代码。

谈一谈为什么写这个东西

  • 致敬一下我的大学生活,这个实训是我当年的实训的项目,当时没有好好写,这次算是给老师交一个作业
  • 复习一下C语言和数据结构,好久不碰,害怕手生忘记

模块设计

1.初始化模块(init.cpp)

  • 初始化用户信息
  • 初始化图信息

2. 用户信息管理模块(user.cpp)

  • 增加用户
  • 删除用户
  • 查找用户
  • 修改用户

3. 排序模块(rank.cpp)

  • 冒泡排序

4. 辅助功能模块(tools.cpp)

  • 求平均步数
  • 求连续运动天数
  • 求星期
  • 数组转置
  • 打印菜单

5. 图结构模块(map.cpp)

  • 构建图
  • 迪杰斯特拉算法

数据结构设计

  • 用户信息结构体
typedef struct user
{
    char name[20];                // 用户昵称
    char phoneNumber[12];        // 用户编号
    char sex[2];                // 用户性别
    int record[7];                // 用户7天步数
    int age;                    // 用户年龄
    double averageSteps;        // 用户7天平均步数
    int motionDays;                // 用户连续运动天数
}user;
  • 图结构体
typedef struct graph
{
    char vexs[MAX][MAX];        // 地点名称
    int vexnum;                   // 节点数目
    float matrix[MAX][MAX];        // 地图边数
}Graph, *PGraph;

运行截图示例

main

user

rank

map

基本概念

  • 逆波兰式:用比较通俗的语言来讲,就是将多项式的操作数和符号重新排列,操作数在前,符号在后
  • 栈:这种数据结构是一种特殊的线性表,只能在一头进行插入和删除,所以有着先进后出的特点

算法实现

  • 中缀式转逆波兰式

需要一个符号栈,初始为空,遍历多项式的每项,如果是数字,记录进结果,如果是符号,判断当前符号和栈顶符号的优先级(括号 < + - < * /),如果优先级大于栈顶符号,则进栈;如果优先级小于栈顶符号,栈顶出栈,如果出栈的不是括号,记录至结果中,直至栈顶优先级小于当前符号,而后符号进栈,直至遍历完整个表达式,最后将符号栈中的符号出栈记录至结果

  • 计算逆波兰式

需要一个结果栈,初始为空,遍历逆波兰式,如果是数字,进栈,遇到符号,出栈两个操作数,进行计算并将计算结果进栈,直至遍历完成,此时栈顶为表达式结果

代码实现

stack.py

import readline
import time
expression = input("请输入表达式(每个字符用空格隔开):")
expression = expression.split()

def get_Reverse_Polish_Notation(expression):
    '''转化逆波兰式'''
    stack = list()
    result = list()
    symbol = ['(', ')', '+', '-', '*', '/']
    value = {
        '(':1,
        ')':1,
        '+':2,
        '-':2,
        '*':3,
        '/':3,
    }
    for i in expression:
        #如果元素是数字,直接进栈
        if i.isdigit():
            result.append(i)
        #如果元素是符号,进入判断
        if i in symbol:
            #如果栈不为空,则判断符号优先级
            if stack:
                #判断如果符号优先级不高于栈顶符号优先级,则出栈,直至优先级大于栈顶符号
                if value[i] <= value[stack[-1]] and i != '(':
                    #如果符号为右括号,则进行匹配左括号
                    if i == ')':
                        while stack[-1] != '(':
                            result.append(stack.pop())
                        stack.pop()
                    #如果不是右括号,则进行出栈操作,直到大于栈顶符号为止
                    else:
                        while True:
                            result.append(stack.pop())
                            if stack:
                                if value[i] > value[stack[-1]] :
                                    stack.append(i)
                                    break
                            else:
                                    stack.append(i)
                                    break

                #如果大于栈顶符号,直接进栈
                else:
                    stack.append(i)
            #如果初始栈为空,则直接进栈第一个符号
            else:
                stack.append(i)
    #遍历完整个表达式,将栈中剩余的符号出栈
    while stack:
        result.append(stack.pop())
    #返回结果列表
    return result

def count_result(result):
    '''计算逆波兰式'''
    stack = list()
    #遍历逆波兰式,如果是数字,直接进栈,如果是符号,则出栈两个操作数,计算出结果入栈
    for i in result:
        if i.isdigit():
            stack.append(i)
        else:
            if i == '+':
                temp = float(stack[-2]) + float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '-':
                temp = float(stack[-2]) - float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '*':
                temp = float(stack[-2]) * float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
            elif i == '/':
                temp = float(stack[-2]) / float(stack[-1])
                stack.pop()
                stack.pop()
                stack.append(str(temp))
    return float(stack[-1])

2018.10.2 数据结构学习---双向链表的实现

/*
 * 学习时间:2018-10-2
 * 学习内容:数据结构之尾插法实现双向链表,以及链表的增删查改
 * 学习人:田超
 * QQ:770925351
 * Email:770925351@qq.com
 * 开发环境:Ubuntu 16.04 + CLion
 * */
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
typedef struct DLNode   //定义循环链表结构体
{
    int data;
    struct DLNode *prior;
    struct DLNode *next;
}DLNode;

void createDList(DLNode *&L,int a[],int n)  //创建双向链表
{
    DLNode *s,*r;                           //s用于新建节点,r用于跟踪L的尾端节点
    int i;                                  //for循环临时变量
    L=(DLNode*)malloc(sizeof(DLNode));      //开辟循环链表头结点空间
    L->prior=NULL;                          //初始化头结点前驱指针
    L->next=NULL;                           //初始化头结点后继指针
    r=L;                                    //初始化r
    for(i=0;i<n;i++)
    {
        s=(DLNode*)malloc(sizeof(DLNode));  //开辟新节点空间
        s->data=a[i];                       //将数值赋值给新节点的数据域
        r->next=s;                          //将r指向的后继变成s
        s->prior=r;                         //将s指向的前趋设置为r
        r=s;                                //r移位,变成链表的最后一个节点
    }
    r->next=NULL;                           //此时r为最后一个节点,将它的后继指针变成NULL,创建链表结束
}

void travelNode(DLNode *L)
{
    DLNode *p=L->next;
    while(p!=NULL)
    {
        printf("data=%d\n",p->data);
        p=p->next;
    }
}

DLNode* findNode(DLNode *L,int x)           //在双向链表中查找x元素
{
    DLNode *p=L->next;                      //p为指向链表的指针,并初始化指向除头节点第一个节点
    while(p!=NULL)                          //当p不为空时候,一直循环
    {
        if(p->data==x)                      //比较值的大小,如果相等,则找到,立即结束循环
            break;
        p=p->next;                          //没有找到,p指向下一个节点
    }
        return p;                           //返回p指针,如果找到则会返回节点的地址,如果找不到,说明p到了最后一个节点,最后一个节点的next指针是NULL
}

void insertNode_tail(DLNode *L,int x)       //在双向链表中插入x元素,尾插法
{
    DLNode *p,*s;                           //s用来新建节点,p用来寻找当前链表中最后一个节点
    p=L->next;                              //初始化p节点
    while(p&&p->next!=NULL)                 //循环找到L的最后一个节点,并赋值给p,在这里判断的逻辑是:p不能为空且p的后继指针不能为空,当为空时候结束循环,说明p是最后一个节点
    {
        p=p->next;
    }
    s=(DLNode*)malloc(sizeof(DLNode));      //新建节点
    s->data=x;                              //将传进来的数据赋值给s
    if(p==NULL)                             //如果此时链表为空,则插入的节点是第一个节点
    {
        s->prior=L;                         //s节点的前趋指向头结点
        s->next=p;                          //s节点的后继指向p,也就是NULL
        L->next=s;                          //此时s作为链表的第一个节点,也就是L->next
    }
    else
    {
        s->prior=p;                         //将s的前趋指针指向p
        s->next=p->next;                    //将s的后继指针指向原先p的后继,因为p是最后一个节点,所以是NULL,如果说是中间的节点的话,就不是NULL
        p->next=s;                          //将p的后继重新指向s
    }

}

void insertNode_head(DLNode *L,int x)       //在双向链表中插入x元素,头插法
{
    DLNode *s;                              //s用来新建节点
    s=(DLNode*)malloc(sizeof(DLNode));      //为s开辟空间
    s->data=x;                              //将数据赋值给新建的节点s的data域
    s->prior=L;                             //将s的前趋指针指向头结点
    s->next=L->next;                        //将s的后继指针指向原先的第一个节点
    if(L->next==NULL)                       //如果此时链表为空,那么s节点将
        L->next=s;
    else
    {
        L->next->prior=s;                   //将原先第一个节点的前趋指针指向s
        L->next=s;                          //将头节点的next指针指向s
    }

}

int deleteNode(DLNode *L,int x)             //在双向链表中删除节点
{
    DLNode *p=L->next;                      //让p指向除头节点外的第一个节点
    while(p!=NULL)                          //循环至最后一个节点
    {
        if(p->data==x)                      //如果找到节点
        {
            if(p->next==NULL)               //如果找到的是最后一个节点
            {
                p->prior->next = p->next;   //将p节点前趋的后继指针指向NULL
                free(p);                    //释放空间
            }
            else
            {
                p->prior->next = p->next;   //将p节点前趋的后继指针指向p的后继
                p->next->prior = p->prior;  //将p节点后继的前趋指针指向p的前趋
                free(p);                    //释放空间
            }
            return TRUE;                    //返回真
        }
        p=p->next;                          //没有找到将p指向下一个节点
    }
    return FALSE;                           //循环结束,没有找到,返回假
}

int main()
{
    int a[5]={1,2,3,4,5};
    int n=5;
    DLNode *L;
    createDList(L,a,n);
    travelNode(L);
    printf("\n");
    deleteNode(L,5);
    travelNode(L);
    printf("\n");
    insertNode_tail(L,6);
    travelNode(L);
    printf("\n");
    insertNode_head(L,7);
    travelNode(L);
    printf("\n");
    return 0;
}

2018.10.04 数据结构学习---链栈的实现

/*
 * 学习时间:2018-10-4
 * 学习内容:数据结构之链栈的实现
 * 学习人:田超
 * QQ:770925351
 * Email:770925351@qq.com
 * 开发环境:Ubuntu 16.04 + CLion
 * */
#include <stdio.h>
#include <stdlib.h>

typedef struct LNode            //定义链栈节点结构体
{
    int data;
    struct LNode *next;
}LNode;

void initStack(LNode *&L)       //初始化栈
{
    L=(LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    L->data=-1;
}

int isEmpty(LNode *L)           //判断是否栈空
{
    if(L->next==NULL)
        return 1;
    else
        return 0;
}

void push(LNode *L,int x)       //进栈,采用头插法
{
    LNode *p;
    p=(LNode*)malloc(sizeof(LNode));
    p->data=x;
    p->next=L->next;
    L->next=p;
    (L->data)++;
}

int pop(LNode *L,int &x)        //出栈,采用删除第一个节点
{
    LNode *p;
    if(isEmpty(L))
        return 0;
    p=L->next;
    x=p->data;
    L->next=p->next;
    (L->data)--;
    free(p);
    return 1;
}

int main()
{
    return 0;
}

  • 循环队列是顺序队的一种,意在解决队首和队尾指针同同时等于MAXSIZE-1的时候,会发声假上溢的情况,利用循环队列解决了这个问题
  • 判断是否队空,则看rear=front==0
  • 判断是否队满,则看(rear+1)%MAXSIZE==front
/*
 * 学习时间:2018-10-11
 * 学习内容:数据结构之循环队列的实现
 * 学习人:田超
 * QQ:770925351
 * Email:770925351@qq.com
 * 开发环境:Ubuntu 16.04 + CLion
 * */
#include <stdio.h>
#define MAXSIZE 10
#define TRUE 1
#define ERROR 0

typedef struct SqQueue
{
    int front;                  //队首
    int rear;                   //队尾
    int data[MAXSIZE];          //数据域
}SqQueue;

void initQueue(SqQueue &qu)     //初始化队
{
    qu.front=qu.rear=0;         //初始化队首
}

int isQueueEmpty(SqQueue qu)    //判断队是否为空
{
    if(qu.front==qu.rear)
        return TRUE;
    else
        return ERROR;
}

int isQueueFull(SqQueue qu)     //判断队是否已满
{
    if((qu.rear+1)%MAXSIZE==qu.front)
        return TRUE;
    else
        return ERROR;
}

int inQueue(SqQueue &qu,int x)  //入队
{
    if(isQueueFull(qu))
        return ERROR;

    qu.rear=(qu.rear+1)%MAXSIZE;
    qu.data[qu.rear]=x;

    return TRUE;
}

int outQueue(SqQueue &qu,int &x) //出队
{
    if(isQueueEmpty(qu))
        return ERROR;

    qu.front=(qu.front+1)%MAXSIZE;
    x=qu.data[qu.front];

    return TRUE;
}

int main() 
{
    return 0;
}