2019-10-10 09:31:11 weixin_44568899 阅读数 64

C++数据结构之线性表

  1. 线性表的长度是指线性表中的数据元素的个数
  2. 李春葆-数据结构C++ P44代码实现

list.h

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include <iostream>
using namespace std;
#define MaxSize 10000

template <class T>
class SqListClass
{
    T *data;
    int length;
public:
    SqListClass();//构造函数
    ~SqListClass();//析构函数
    void CreateList(T a[],int n);//由a数组中的元素建立顺序表
    void DispList();//输出
    int ListLength();//顺序表长度
    bool GetElem(int i,T &e);//求顺序表中某序号的元素值
    int LocateElem(T e);//按元素值查找其序号
    bool ListInsert(int i,T e);//插入数据元素
    bool ListDelete(int i);//删除数据元素
};


template <class T>
SqListClass<T>::SqListClass()//构造函数的实现
{
    data = new T[MaxSize];
    length = 0;
}
template <class T>
SqListClass<T>::~SqListClass()
{
    delete [] data;
}


template <class T>
void SqListClass<T>::CreateList(T a[],int n)
{
    int i;
    for(i = 0;i < n;i++)
        data[i] = a[i];
    length = i;
}

template <class T>
void SqListClass<T>::DispList()
{
    int i;
    if(length > 0)
    {
        for(i=0;i<length;i++)
        {
            cout << data[i] << " ";
        }
        cout << endl;
    }

}

template <class T>
int SqListClass<T>::ListLength()
{
    return length;
}

template <class T>
bool SqListClass<T>::GetElem(int i,T &e)//求顺序表中某序号的元素值
{
    if(i<1 || i>length)//i是逻辑序号
        return false;
    else
        e = data[i-1];//i-1是物理序号
        return true;

}

template <class T>
int SqListClass<T>::LocateElem(T e)//按元素值查找其逻辑序号
{
    int i = 0;//i是逻辑序号
    while(i<length && data[i]!=e)//找到e
        i++;
    if(i >= length)
        return 0;
    else
        return i+1;//返回逻辑序号
}

template <class T>
bool SqListClass<T>::ListInsert(int i,T e)
{
    int j;
    if(i<1 || i>length)//i是逻辑序号
        return false;
    for(j = length;j>=i;j--)
        data[j] = data[j-1];
    data[i-1]=e;
    length++;
    return true;
}

template <class T>
bool SqListClass<T>::ListDelete(int i)
{
    int j;
    if(i<1 || i>length)
        return false;
    for(j = i-1;j<length-1;j++)
        data[j] = data[j+1];
    length--;
    return true;
}

#endif // LIST_H_INCLUDED

main

#include <iostream>
#include "list.h"
using namespace std;

int main()
{
    SqListClass<int> list;
    int a[5] = {1,2,3,4,5};
    list.CreateList(a,5);
    list.DispList();
    list.ListInsert(2,9);
    list.DispList();
    list.ListDelete(3);
    list.DispList();
    return 0;
}

在这里插入图片描述

2019-01-03 19:35:40 ME__WE 阅读数 527

1.1 什么是数据结构

1.1.1 数据结构的定义

数据(data)是描述客观事物的数和字符的集合。从计算机的角度看,数据是所有能被输入到计算机中,且能被计算机处理的符号的集合。数据的基本单位是数据元素(data element)。

数据项(data item)是具有独立含义的数据最小单位,也称为字段或域。

注:一个数据元素可以由若干个数据项组成。

数据对象(data object)是指性质相同的数据元素的集合,它是数据的一个子集。

数据结构(data structure)是指所有数据元素以及数据元素之间的关系,可以看做是相互之间存在着某种特定关系的数据元素的集合。即 数据结构 = 数据 + 结构。

数据结构通常包括以下几个方面:

    1. 逻辑结构:由数据元素之间的逻辑关系构成。

    2. 存储结构:数据元素及其关系在计算机存储中的表示,也称为数据的物理结构。

    3. 运算:施加在该数据上的操作。

1.1.2 逻辑结构

数据的逻辑结构是从数据元素的逻辑关系上描述数据的。数据的逻辑关系与数据的存储无关,是独立于计算机的。

数据结构中元素关系主要是指相邻关系或邻接关系。

1. 逻辑结构的表示

(1)图表。就是表格,没什么好说的。

(2)二元组。

        二元组是一种通用的逻辑结构表示方法。

        一个二元组表示为:B=(D, R),其中B是一种数据结构,它由数据元素的集合D和D上二元关系的集合R所组成。

        D=\begin{Bmatrix} d_{i} | 1\leqslant i\leqslant n, n\geqslant 0 \end{Bmatrix}:数据元素的集合

        R=\begin{Bmatrix} r_{j} | 1\leqslant j\leqslant m, m\geqslant 0 \end{Bmatrix}:关系的集合

        每个关系的用若干个序偶来表示:

        序偶\left \langle x, y \right \rangle \left ( x,y\in D \right ),x为第一元素,y为第二元素。x为y的前驱元素。y为x的后继元素。若某个元素没有前驱元素,则称该元素为开始元素;若某个元素没有后继元素,则称该元素为终端元素。

        序偶<x,y>表示x,y是有向的,序偶(x,y)表示x,y是无向的。

2. 逻辑结构的类型

(1)集合

元素之间关系:无

特点:数据元素之间除了“属于同一个集合”的关系外,别无其他逻辑关系。是最松散的,不受任何制约的关系。

(2)线性结构

元素之间关系:一对一

特点:开始元素和终端元素都是唯一的,除此之外,其余元素都有且仅有一个前驱元素和一个后继元素。

(3)树形结构

元素之间关系:一对多

特点:开始元素唯一,终端元素不唯一。除终端元素以外,每个元素有一个或多个后续元素;除开始元素外,每个元素有且仅有一个前驱元素。

(4)图形结构

元素之间关系:多对多

特点:所有元素都可能有多个前驱元素和多个后继元素。

 

       
 

 

 

 

 

 

 

 

 

 

 

2019-07-05 11:42:40 COCO56 阅读数 1787

1. 关键词

李春葆-数据结构(C++版)-第五版 教学视频+配套资源、数据结构C++版视频教程、C++视频教程

2. 相关推荐

C++ Primer视频教程(初级中级高级):https://blog.csdn.net/COCO56/article/details/95260291

3. 下载地址

https://www.cnblogs.com/coco56/p/11223189.html
视频教程\数据结构那里。
在这里插入图片描述

4. 章节目录

├─第01章_绪论
├─第02章_线性表
├─第03章_栈和队列
├─第04章_串
├─第05章_递归#
├─第06章_数组和广义表
├─第07章_树和二叉树
├─第08章_图
├─第09章_查找
├─第10章_内排序
├─第11章_外排序
├─第12章_文件
├─第13章_面向对象
└─附
2019-11-12 23:38:12 weixin_45092452 阅读数 122

李春葆《数据结构》第五版

第二章:线性表
实验一:实现顺序表各种基本运算的算法

#include <stdio.h>
#include <malloc.h>
#define Maxsize 50
typedef char Elemtype;
typedef struct 
{Elemtype data[Maxsize];
int length;
}sqlist ;
void createlist(sqlist*&l,Elemtype a[ ],int n)
{l=(sqlist*)malloc(sizeof(sqlist));
for(int i=0;i<n;i++)
	l->data[i]=a[i];
l->length =n;
}
void initlist(sqlist*&l)
{l=(sqlist*)malloc(sizeof(sqlist));
l->length =0;
}
void destroylist (sqlist*&l)
{ free(l);
}
bool listempty (sqlist*l)
{ return (l->length==0);
}
int listlength (sqlist*l)
{ return (l->length);
}
void  displist(sqlist*l)
{for(int i=0;i<l->length;i++)
printf("%c",l->data[i]);
printf("\n");
}
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 listinsert (sqlist*&l,int i,Elemtype e)
{int j;
if(i<1||i>l->length+1) 
	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 ;
}
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];
l->length --;
return true;
}

主函数程序如下:
int main()
{ sqlist *l;
Elemtype e;
printf("顺序表的基本运算如下:\n");
printf("(1)初始化顺序表l\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:");displist(l);
printf("(4)顺序表l长度:%d\n",listlength(l));
printf("(5)顺序表l为%s\n",(listempty(l)?"空":"非空"));
getelem(l,3,e);
printf("(6)顺序表l的第3个元素:%c\n",e);
printf("(7)元素a的位置:%d\n",locateelem(l,'a'));
printf("(8)在第4个元素位置上插入f元素\n");
listinsert(l,4,'f');
printf("(9)输出顺序表l:");displist(l);
printf("(10)删除l的第3个元素:\n");
listdelete(l,3,e);
printf("(11)输出顺序表l:");displist(l);
printf ("(12)释放顺序表l\n");
destroylist(l);
return 1;
}

实验结果:
在这里插入图片描述

这里是引用
李春葆《数据结构教程 上机实验指导》

2019-12-17 14:09:41 weixin_44885612 阅读数 175

数据结构课程设计

题目要求: 利用单链表实现职工管理系统,设有职工文件emp.dat,建立单链表,数据包括职工编号(no), 姓名(name),部门(depno),工资(salary)。且具有排序,文件读写,删除等功能。 -- 题目来源(数据结构教程-第五版-李春葆-P.77)da

代码如下

#include<iostream>
#include<windows.h>
#include<fstream>
#include<string>
#include<stdlib.h>
#include<time.h>
using namespace std;


int people_num = 0;


typedef struct employee
{
    int no;
    string name;
    int depno;
    int salary;

    struct employee *pnext;
}Emp;

void Initial_list( Emp *&L )
{   
    L = new Emp;
    L->pnext = nullptr;
}

void Create_List( Emp *& L )
{
    Emp *Root = L;
    fstream fs( "f1.dat", ios::in );

    string NO;
    string DEPNO;
    string NAME;
    string SALARY;

    while( !fs.eof() )
    {
        if( !fs )
        {
            cout << "Create() 打开文件错误 " << endl;
            return ;
        }
        else
        {
            Emp *node;
            node = new Emp;

            fs >> NO;
            fs >> NAME;
            fs >> DEPNO;
            fs >> SALARY;

            node->no = atoi( NO.c_str() );
            node->name =  NAME;
            node->depno = atoi( DEPNO.c_str() );
            node->salary = atoi( SALARY.c_str() );

            while( L->pnext != nullptr )
            {
                L = L->pnext;
            }
            L->pnext = node;
            node->pnext = nullptr;
            people_num++;

            //L  = Root;
        
        }
    }
    L = Root;
    fs.close();
    cout << "由文件创建链表成功" << endl;

}

void Add_List( Emp *& L, int no, string name, int depno, int salary )
{
    Emp *Root = L;
    Emp *node;
    node = new Emp;

    node->no = no;
    node->name = name;
    node->depno = depno;
    node->salary = salary;

    //fstream fs("f1.dat", ios::out );
    //fs << no << "\t" << name << "\t" << depno << "\t" << salary << endl;
    
    while( L->pnext != nullptr )
    {
        L = L->pnext;
    }
    L->pnext =  node;
    node->pnext = nullptr;
    people_num++;
    L = Root;
}

void Sort_no( Emp *& L )
{
        cout << "Sort in no :  " << endl;
    Emp *Root = L;
    //L = L->pnext;

    for( int i = 0; i < people_num; i++ )
    {
        //L = L->pnext;        
        while( L->pnext->pnext != nullptr )     //如果有下一个
        {
            if( L->pnext->no > L->pnext->pnext->no )   //当前和下一个的编号进行比较
            {
                Emp *pt_one;  //保存当前
                Emp *pt_two;  //保存下一个的后续
                pt_one = L->pnext;
                pt_two = L->pnext->pnext->pnext;

                L->pnext = L->pnext->pnext;
                L->pnext->pnext = pt_one;

                L->pnext->pnext->pnext = pt_two;  
            }
            L = L->pnext;
        }
        L = Root;     
    }
}

void Sort_depno( Emp *& L )
{
    Emp *Root = L;
    //L = L->pnext;

    for( int i = 0; i < people_num; i++ )
    {
        //L = L->pnext;        
        while( L->pnext->pnext != nullptr )     //如果有下一个
        {
            if( L->pnext->depno > L->pnext->pnext->depno )   //当前和下一个的编号进行比较
            {
                Emp *pt_one;  //保存当前
                Emp *pt_two;  //保存下一个的后续
                pt_one = L->pnext;
                pt_two = L->pnext->pnext->pnext;

                L->pnext = L->pnext->pnext;
                L->pnext->pnext = pt_one;

                L->pnext->pnext->pnext = pt_two;  
            }
            L = L->pnext;
        }
        L = Root;     
    }
}

void Sort_salary( Emp *& L )
{

    Emp *Root = L;
    //L = L->pnext;

    for( int i = 0; i < people_num; i++ )
    {
        //L = L->pnext;        
        while( L->pnext->pnext != nullptr )     //如果有下一个
        {
            if( L->pnext->salary > L->pnext->pnext->salary )   //当前和下一个的编号进行比较
            {
                Emp *pt_one;  //保存当前
                Emp *pt_two;  //保存下一个的后续
                pt_one = L->pnext;
                pt_two = L->pnext->pnext->pnext;

                L->pnext = L->pnext->pnext;
                L->pnext->pnext = pt_one;

                L->pnext->pnext->pnext = pt_two;  
            }
            L = L->pnext;
        }
        L = Root;     
    }
}

void Delete_no( Emp *& L, int no )
{
    Emp *Root = L;
    while( L->pnext != nullptr )
    {
        if( L->pnext->no == no )
        {
            L->pnext = L->pnext->pnext;
            people_num--;
        }
        L = L->pnext;
    }
    L = Root;
}

void Delete_file( Emp *& L )
{

}

void Storage_file( Emp * L )
{
    cout << "文件保存 "<< endl;
    fstream fs("f1.dat", ios::out | ios::in );
    
    while( L->pnext != nullptr )
    {
        fs << L->pnext->no << "\t" << L->pnext->name << "\t" << L->pnext->depno << "\t" << L->pnext->salary;
        if( L->pnext->pnext != nullptr )
        {
            fs << endl;
        }
        L = L->pnext;
    }
    fs.close();

    cout << "文件保存成功 " << endl;
}

void Dispaly_List( Emp *L )
{
    int count = 0;
    if( L != nullptr )
    {
        L = L->pnext;
        while( L != nullptr )
        {
            cout << "第 " << count + 1 <<" 个员工 : " << "编号 " << L->no <<" 姓名 " << L->name << " 部门号 " << L->depno <<" 工资数 " << L->salary << endl;
            L = L->pnext;
            count++;
        }
    }
}


int main()
{
    Emp *L;

    Initial_list( L );
    Create_List( L );   //由文件创建

    cout << "由文件创建的链表如下 : " << endl;
    Dispaly_List( L );

    //  Add_List( L, 2, "闪电法师", 15, 8000 );
    //  Add_List( L, 1, "掘地矿工", 13, 7000 );

    cout << "调用函数添加如下 : " << endl;
     Add_List( L, 3, "暗夜女巫", 16, 5000 );
     Add_List( L, 5, "黑暗王子", 13, 6000 );
     Add_List( L, 4, "小蝙蝠", 11,  4000);
     Add_List( L, 0, "小雪人", 12, 9000 );


    Dispaly_List( L );

    cout << "按编号排序如下 : " << endl;
    Sort_no( L );
    Dispaly_List( L );

    Sort_depno( L );
    cout << "按部门排序如下 : " << endl;
    Dispaly_List( L );

    Sort_salary( L );
    cout << "按工资排序如下 : " << endl;
    Dispaly_List( L );

    Delete_no( L, 4 );
    cout << "删除编号为 4 的员工,显示如下 : " << endl;
    Dispaly_List( L );



    Storage_file( L );

    
    fstream fs( "f1.dat", ios::out | ios::in );
    if( !fs )
    {
        cout << "main() 打开文件错误 " << endl;
    }
    fs.close();
    cout << endl;
    
    system("pause");
    return 0;
}

好好学习,天天向上,一起学习哈!😀

 

没有更多推荐了,返回首页