数据结构分为8类有：数组、栈、队列、链表、树、散列表、堆、图。数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 

1、数组

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

2、栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。  

3、队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队。

4、链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 

5、树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

6、散列表

散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

7、堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

8、图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

—数据结构

实验一：线性表运算的实现

班级 姓名 学号

一、实验预备知识

1 复习C++中编写函数的相关内容。

2 复习如何用主函数将多个函数连在一起构成一个C++完整程序。

二、实验目的

1 掌握线性表的顺序和链式存储结构

2 熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算

3 熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算

三、实验要求

1 编写初始化并创建线性表和输出线性表的算法。

2 编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。

3 编写一个主函数，将上面函数连在一起，构成一个完整的程序。

4将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。

四、实验步骤

◇顺序表实验内容：

1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．初始化并建立顺序表。

3．编写顺序表输出算法。（内存中开辟的单元数为8）

4．依次插入3，21，15三个数，分别插入在第4，6和2位置，每插入一次都要输出一次顺序表。

5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次顺序表。 ◇单链表实验内容：

1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．建立一个带表头结点的单链表（前插入法和尾插入法都可以）。

3．编写单链表输出算法。

4．依次插入3，21，15三个数，分别插入在第4，6和12位置，每插入一次都要输出一次单链表。

5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次单链表。

五、实验程序

◇顺序表实验

//LinkListh

#define MAXSIZE 8

typedef int DataType;

typedef struct{

DataType data[MAXSIZE];

int last;

}Seqlist;

void creat_seqlist(Seqlist &s);

void display_seqlist(Seqlist &s);

int insert_seqlist(Seqlist &s, int i, DataType x);

int delet_seqlist(Seqlist &s, int i);

//LinkListcpp

#include

#include"Seqlisth"

void creat_seqlist(Seqlist &s)

{

int x, i = 0;

cout

cin>>x;

while(x != -1){

sdata[i] = x;

cin>>x;

i ++;

}

slast = i-1;

}

void display_seqlist(Seqlist &s)

{

int i;

cout

for(i = 0; i

cout

cout

}

int insert_seqlist(Seqlist &s, int i, DataType x)

{

int j;

if(slast == MAXSIZE-1){

}

cout slast + 2){ cout= i-1;j --) sdata[j+1] = sdata[j]; sdata[i-1] =x ; slast ++; return 1;

int delet_seqlist(Seqlist &s, int i)

{

int j;

if(i slast+1){

cout

return -1;

}

for(j = i; j

sdata[j-1] = sdata[j];

slast --;

return 1;

}

//maincpp

#include

#include"Seqlisth"

int main()

{

int x,d,s;

Seqlist s_list;

creat_seqlist(s_list);

cout>d; cout>x; s=insert_seqlist(s_list ,d,x); if(s==1){ cout>d; s=delet_seqlist(s_list,d);

}

if(s==1){ cout

运行结果:

请输入数据（以输入-1结束）

12 25 7 42 19 38 -1

顺序表为：

12 25 7 42 19 38

插入操作

请输入插入的位置:4

请输入要插入的数据：3

插入后的顺序表为：

12 25 7 3 42 19 38

请输入插入的位置:6

请输入要插入的数据：21

插入后的顺序表为：

12 25 7 3 42 21 19 38

请输入插入的位置:2

请输入要插入的数据：15

表满！

删除操作

请输入删除元素的位置：5

删除后的顺序表为：

12 25 7 3 21 19 38

请输入删除元素的位置：3

删除后的顺序表为：

12 25 3 21 19 38

请输入删除元素的位置：12

不存在该元素！

Press any key to continue

◇单链表实验

//LinkListh

typedef int DataType;

typedef struct Node{

DataType data;

struct Node next;

}LNode,LinkList;

void Creat_LinkList(LinkList &L); //创建链表

void Show_LinkList(LinkList &L); //显示数据

LNode Get_LinkList(LinkList &L, int i); //获得第i个结点的地址 int Insert_linklist(LinkList &L,int i,DataType x); //插入结点

int Delete_LinkList(LinkList &L,int i); //删除结点

//LinkListcpp

#include

#include"LinkListh"

void Creat_LinkList(LinkList &L)

{

LNode s;

L = NULL;

s = new LNode;

s->next = L;

L = s;

int x;

}

//头插法创建带头结点的链表 cout>x; while(x != -1){ s = new LNode; s->next = L; L->data = x; L = s; cin>>x; }

void Show_LinkList(LinkList &L)

{

LNode p;

p = L->next;

while(p!=NULL){

coutdata

p = p->next; //显示数据

}

cout

}

LNode Get_LinkList(LinkList &L, int i)

{

int j = 1;

LNode q;

q = L->next;

while(q != NULL && j

q = q->next;

j++;

}

return q;

}

//获得第i个结点的地址

int Insert_LinkList(LinkList &L, int i, DataType x)//插入结点 {

LNode p, s;

p = Get_LinkList(L,i-1);

if(p == NULL){

}

coutdata = x; s->next = p->next; p->next = s; return 1; }

int Delete_LinkList(LinkList &L,int i)

{

LNode p, s;

p = Get_LinkList(L,i-1);

if(p == NULL){

//删除结点 coutnext == NULL){ cout

return 0;

}

else{

s = p->next;

p->next = s->next; delete s;

return 1;

}

}

//maincpp

#include #include"LinkListh"

int main()

{

int x,d,s;

LinkList H;

Creat_LinkList(H); Show_LinkList(H);

} cout>d; cout>x; s = Insert_LinkList(H,d,x); if(s == 1){ cout>d; s = Delete_LinkList(H,d); if(s == 1){ cout

运行结果：

请输入数据（以输入-1结束） 12 25 7 42 19 38 -1 单链表为：

38 19 42 7 25 12

插入操作

请输入插入的位置:4 请输入要插入的数据：3 插入后的单链表为： 38 19 42 3 7 25 12 请输入插入的位置:6 请输入要插入的数据：21 插入后的单链表为：

38 19 42 3 7 21 25 12 请输入插入的位置:12 请输入要插入的数据：15 插入位置错误!

删除操作

请输入删除元素的位置：5 删除后的单链表为：

38 19 42 3 21 25 12 请输入删除元素的位置：3 删除后的单链表为： 38 19 3 21 25 12

请输入删除元素的位置：12 插入位置的前驱结点不存在!

单循环链表：将循环链表的终端结点的指针域NULL改为指向表头结点或开始结点。

循环链表：是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表分为两类，分别是单循环链表和多重链的循环链表。

填写：顺序表

线性表中最常用的操作是取第i个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。

单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。

通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

扩展资料：

数据存储对象包括数据流在加工过程中产生的临时文件或加工过程中需要查找的信息。数据以某种格式记录在计算机内部或外部存储介质上。

数据存储要命名，这种命名要反映信息特征的组成含义。数据流反映了系统中流动的数据，表现出动态数据的特征；数据存储反映系统中静止的数据，表现出静态数据的特征。

从连接方式上对比，DAS采用了存储设备直接连接应用服务器，具有一定的灵活性和限制性；NAS通过网络（TCP/IP，ATM，FDDI）技术连接存储设备和应用服务器，存储设备位置灵活，随着万兆网的出现，传输速率有了很大的提高。

SAN则是通过光纤通道技术连接存储设备和应用服务器，具有很好的传输速率和扩展性能。三种存储方式各有优势，相互共存，占到了磁盘存储市场的70%以上。SAN和NAS产品的价格仍然远远高于DAS。许多用户出于价格因素考虑选择了低效率的直连存储而不是高效率的共享存储。

——顺序表

——数据存储

studenth 文件代码如下:

#define _CRT_SECURE_NO_WARNINGS

#include <stdioh>

#include <stdlibh>

#include <stringh>

struct student

{

char name[20];

int age;

int num;

};

//单链表的结构体

typedef struct SingleList

{

struct student mystudent;

//指针域

struct SingleList next;

}LIST, LPLIST;

/

别名:习惯大写

起别名---小名

//好处:单词少,好看(含义更精简)

struct SingleList  换一种叫法:  LIST;

strcut SingleList   换一种叫法: LPLIST

/

//------->2创建链表  ---任何结构都需要用一个东西去表示

LPLIST CreateList()

{

//创建过程就是初始化过程---初始化基本数据成员过程

//需要内存空间

LPLIST List = (LPLIST)malloc(sizeof(LIST));

if (List == nullptr)

{

printf("失败了\n");

system("pause");

exit(0);

}

//初始化基本数据成员----有表头的链表

List->next = nullptr;

return List;

}

//------->3创建结点  

LPLIST CreateNode(struct student mystudent)

{

//1需要内存

LPLIST Node = (LPLIST)malloc(sizeof(LIST));

//2初始化基本数据成员

strcpy(Node->mystudentname, mystudentname);

Node->mystudentage = mystudentage;

Node->mystudentnum = mystudentnum;

Node->next = nullptr;

return Node;

}

//------->42 尾插法

void InsertListTailNode(LPLIST List, struct student mystudent)

{

//找到表尾--->定义一个移动的指针

LPLIST tailNode = List;

while (tailNode->next != nullptr)

{

tailNode = tailNode->next;

}

//创建插入的结点

LPLIST newNode = CreateNode(mystudent);

tailNode->next = newNode;

}

//------->5判断是否为空

//和创建的时候比较

int  IsEmptyList(LPLIST List)

{

if (List->next == nullptr)

return 1; //返回1表示为空

return 0; //表示不为空

}

////------->6打印数据

void PrintList(LPLIST List)

{

if (IsEmptyList(List))

{

printf("链表为空,无法打印");

system("pause");

exit(0);

}

LPLIST pNext = List->next;

while (pNext != nullptr)

{

printf("姓名:%s\t年龄:%d\t编号:%d\n", pNext->mystudentname, pNext->mystudentage, pNext->mystudentnum);

pNext = pNext->next;

}

}

//------->9按照编号指定位置删除

void DeleteListAppoinNode_num(LPLIST List, int num)

{

//创建两个移动的指针:去找指定位置和指定位置的前面

LPLIST frontNode = List;

//frontNode->next==taiNode:判断相邻

LPLIST tailNode = List->next;

//判断是否为空

while (tailNode->mystudentnum != num)

{

/

frontNode=frontNode->next;

tailNode=tailNode->next;

/

frontNode = tailNode;

tailNode = frontNode->next;

if (tailNode == nullptr)

{

printf("未找到指定位置\n");

system("pause");

exit(0);

}

}

frontNode->next = tailNode->next;

free(tailNode);

}

//------->9按照姓名指定位置删除

void DeleteListAppoinNode_name(LPLIST List, char name)

{

//创建两个移动的指针:去找指定位置和指定位置的前面

LPLIST frontNode = List;

//frontNode->next==taiNode:判断相邻

LPLIST tailNode = List->next;

//判断是否为空

while (strcmp(tailNode->mystudentname, name))

{

/

frontNode=frontNode->next;

tailNode=tailNode->next;

/

frontNode = tailNode;

tailNode = frontNode->next;

if (tailNode == nullptr)

{

printf("未找到指定位置\n");

system("pause");

exit(0);

}

}

frontNode->next = tailNode->next;

free(tailNode);

}

void Menu()

{

printf("\t\t\t1录入信息\n");

printf("\t\t\t2删除信息\n");

printf("\t\t\t3浏览信息\n");

}

LPLIST List = CreateList(); //List创建成功

void key_down()

{

char name[20] = "";

int num = 0;

fflush(stdin);

char choice = getchar();

int DChoice = 1;

switch (choice)

{

case '1':

system("cls");

struct student mystudent;

printf("请输入:\t姓名:\t年龄:\t编号:\n");

scanf("%s%d%d", mystudentname, &mystudentage, &mystudentnum);

InsertListTailNode(List, mystudent);

break;

case '2':

system("cls");

fflush(stdin);

printf("\t\t\t1按照姓名删除\n");

printf("\t\t\t2按照编号\n");

DChoice = getchar();

switch (DChoice)

{

case '1':

printf("请输入要删除的姓名:\n");

scanf("%s", name);

DeleteListAppoinNode_name(List, name);

break;

case '2':

printf("请输入要删除的编号:\n");

scanf("%s", name);

DeleteListAppoinNode_num(List, num);

}

break;

case '3':

system("cls");

printf("学生信息:\n");

PrintList(List);

break;

default:

printf("输入错误\n");

system("pause");

}

}

studentcpp:

#include "studenth"

//更多精彩点击我头像,有惊喜

int main()

{

while (1)

{

Menu();

key_down();

}

system("pause");

return 0;

}