数据结构1

发布时间:2024年01月04日

ru 第一章? ?绪论

一·、

数据-----能输入到计算机中去的描述客观事物的符号

·数值型数据

·非数值型数据

数据元素----数据的基本单位,也称结点,或者记录

数据项----独立含义的数据元素的最小单位

数据 > 数据元素 > 数据域

数据对象:相同特性数据元素的集合

数据结构:数据元素之间存在一种或多种的关系的数据元素集合

逻辑结构:从逻辑上描述数据,它与数据的存储无关,是独立与计算机的

1 集合? ?-------? 数据元素之间除了属于同一集合外,无其他关系

2. 线性结构? ------ 数据元素之间存在一一对应的关系

3.树形? ?------- 数据之间存在一对多的关系

4.图状结构? ------- 数据元素之间存在多对多的关系

存储结构:数据对象在计算机中的存储表示,也称为物理结构

顺序存储结构:借助元素中的相对位置来表示元素的逻辑关系

链式存储结构:借助地址指针

散列存储结构:借助关键字

抽象数据类型:由基本数据类型组成,并包括一系列操作

二、举一个例子:

一张学生基本信息表,包括学生的学号、姓名、性别、籍贯和专业。每个学生的基本信息对应一个数据元素。学生记录按序号排序,形成勒学生基本信息的记录线性序列。对于整个表来说,开始节点无前驱,终端节点无后继,其他元素均有一个前驱与一个后继,学生记录之间的关系确定了学生表的逻辑结构。

而学生记录在计算机中的存储表示就是存储结构,如果用连续的存储单元来存放这些记录,则称为顺序存储结构;如果存储的空间不连续,而使用指针来连接,则称为链式存储结构

三、时间复杂度分析

x = 90;y = 100
while(y>0)
if(x>100)
{x=x-10;y--}
else x++;

O(1) 程序执行的次数为常数

for(i = 0 ;i<n;i++)
{
    for(j=0;j<m;j++)
      a[i][j]=0;
}

O(m*n),循环语句的执行次数为m*n

s=0;
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
   s+=B[i][j];
sun = s;

O(n*n),循环语句的执行次数为n*n

i = 1;
while(i<=n)
    i=i*3

O(log3n),循环语句的执行次数为log3n

s=0;
for(i=1;i<n;i++)
   for(j=1;j<n-i;j++)
     s++;

O(n*n) 语句s++循环为 n-1 +?n-2 +?.....+1=n(n-1)/2 = n*n

x=n;
y=0;
while(x>=(y+1)*(y+1))
y++;


O(根号2)

第二章 线性表

2.1 定义

同一列表中的元素必定有相同的特性,属于同一数据对象,相邻元素之间存在着序偶的关系,由n个数据特性相同的元素组成的有限序列,称为线性表;当n为0时,称为空表。其特点为

(1)只有一个前端

(2)只有一个末端

(3)除了第一个元素,所有元素只有一个前驱

(4)除了最后一个元素,所有元素只有一个后继

2.2.1线性表的顺序表示

顺序指的是用一组地址连续的存储单元依次储存线性表的数据元素,也称为顺序表。只要确定了顺序表的起始位置,线性表中的任意数据都可以随机存取。

#define MAXSIZE 100   //最大长度
typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型
typedef struct
{
    ElemType *elem;  //存储空间基地址
    int length;
}SqList;

如果存储的为稀疏多项式,就需要对指数 系数也进行保存,这个和我们保存学生信息很类似,我们可以按照下面的方法来定义
?

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型

#define MAXSIZE 100			//顺序表可能达到的最大长度
struct Book {
	string id;//ISBN
	string name;//书名
	double price;//定价
};
typedef struct {
	Book *elem; //存储空间的基地址
	int length; //当前长度
} SqList;

2.2.2 顺序表基本操作的实现

我们可以看到这些算法时间复杂度都是O(1)

1. 初始化

建立一个空的顺序表

步骤:

1、为顺序表L分配一个预定义大小的数组空间,让elem指向这段空间

2、设当前长度为0

#include<iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型

#define MAXSIZE 100			//顺序表可能达到的最大长度


Status InitList_Sq(SqList &L) { //算法2.1 顺序表的初始化
	//构造一个空的顺序表L
	L.elem = new Book[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
	if (!L.elem)
		exit(OVERFLOW); //存储分配失败退出
	L.length = 0; //空表长度为0
	return OK;
}

2.取值

直接通过数组下标定位得到,elem[i-1]单元件存储第i个数据元素(从0开始)

步骤

1、判断指定位置i是否合理

2、合理返回数据给e,不合理返回error

Status GetElem(SqList L, int i, Book &e) {//算法2.2 顺序表的取值
	if (i < 1 || i > L.length)
		return ERROR; //判断i值是否合理,若不合理,返回ERROR
	e = L.elem[i - 1]; //elem[i-1]单元存储第i个数据元素
	return OK;
}

3.查找

找出表中与元素e相等的值。找到就返回出其位置序号

步骤

1、 从第1个元素开始比较,找到返回,没找到返回1

int LocateElem_Sq(SqList L, double e) { //算法2.3 顺序表的查找
	//顺序表的查找
	for (int i = 0; i < L.length; i++)
		if (L.elem[i].price == e)
			return i + 1;//查找成功,返回序号i+1
	return 0;//查找失败,返回0
}

因为每个元素都得查找,所以时间复杂度为O(n) (n+1? /? 2)

4.插入

插入新数据后,这个数据后的数据需要向后移动

步骤

1、判断插入位置i是否合理

2、判断存储空间是否已满

3、将n个位置到i个位置向后移动一个单元

4、将需要的新元素e插入到第i个位置

5、表长+1

Status ListInsert_Sq(SqList &L, int i, Book e) { //算法2.4 顺序表的插入
	//在顺序表L中第i个位置之前插入新的元素e
	//i值的合法范围是1<=i<=L.length+1
	if ((i < 1) || (i > L.length + 1))
		return ERROR; //i值不合法
	if (L.length == MAXSIZE)
		return ERROR; //当前存储空间已满
	for (int j = L.length - 1; j >= i - 1; j--)
		L.elem[j + 1] = L.elem[j]; //插入位置及之后的元素后移
	L.elem[i - 1] = e; //将新元素e放入第i个位置
	++L.length; //表长增1
	return OK;
}

一样的,因为都需要遍历,平均次数为2/n,所以时间长度为O(n)

5. 删除

把第i个数据删去,就需要把i个以后的数据均向前位移一段

步骤不在说明

Status ListDelete_Sq(SqList &L, int i) { //算法2.5 顺序表的删除
	//在顺序表L中删除第i个元素,并用e返回其值
	//i值的合法范围是1<=i<=L.length
	if ((i < 1) || (i > L.length))
		return ERROR; //i值不合法
	for (int j = i; j <= L.length; j++)
		L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
	--L.length; //表长减1
	return OK;
}

但是我们知道,这些操作我们都需要操作大量的元素,由于其有固定的长度的和相对固定的静态特性,数量多时,必定导致空间浪费

2.3 链表

2.3.1 定义

用任意的存储单元存储线性表的数据,每个元素除了自身的信息之外,还需要存储一个指示其后继的信息,称为节点。存储数据信息的区域称为数据域,存储直接后继存储位置的区域称为指针域

一般情况下,为了方便处理,单链表的第一个节点之前附设一个节点,称为头节点,头节点的数据域可以不存任何数据。头指针时指向链表第一个节点的指针,如果没有头节点,指向的则是首元节点

增加头节点后,无论链表是否为空,头指针都是指向头节点的非空指针,若为空表,则头节点的指针域为空(记为 L -> next == NULL)

链表为顺序存取结构,每个元素的存储位置都包含在其前驱节点的信息之中

1.初始化

#include<iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型


typedef struct LNode{  
    int data;    //节点数据
    struct LNode *next;  //节点指针
}LNode,*LinkList;

Status InitList(LinkList &L)
{
    L = new LNode;
    L -> next=NULL;
    return OK;
}

2、取值

链表中逻辑相邻的节点并没有存储物理相邻的单元中,这样,根据给定的节点位置序号i,我们不能像顺序表那样随机访问,只能从寿元结点出发,顺着next向下访问

Status GetElem(LinkList L,int i,ElemType &e)
{//在带头节点的单链表L中,根据序号i获取元素的值,用e返回L中的第i个元素的值
   LNode *p =L->next;int j=1;  //初始化,p指向首元节点,计数器j初值为1
   while(p&&j<i)   //满足条件
   {
    p=p->next;    //p指向下一个节点
    ++j;          //计数器加1
   }
   if(!p||j>1) return ERROR;  //不满足
   e=p->data;  //取第j个节点的数据域
   return OK;
  
}

平均次数也为n-1/2,所以时间复杂度为O(n)

3、查找?

和取值类似

LNode *LocateElem(LinkList L,ElemType e)
{
   LNode *p =L->next;    
   while(p&&p->data!=e)   //向后查找,直到p为空域p或者节点数据域为e
    p = p->next;
    return p;
}

4、插入

为了插入数据,我们需要先生成一个数据域为x的节点,然后修改a的指针域,让其指向x,而指针x的指针域指向后者

Status ListInsert(LinkList &L,int i,ElemType e)
{// 在第i个位置,插入数值为e的新节点
   LNode *p =L;int j=0;  //初始化,p指向首元节点,计数器j初值为1
   while(p&&j<i-1)   //查找第i-1个节点
   {
    p=p->next;    //p指向下一个节点
    ++j;          //计数器加1
   }
   if(!p||j>i-1) return ERROR;  //不满足

   LNode *s = new LNode;  //生成新节点*s
   s->data=e;             //节点*s的数据域为e
   s->next=p->next;       //将节点*s的指针域指向节点
   p->next =s;
   return OK;
}

5、删除、

删除只需要修改a中的指针直接指向c即可


Status ListInsert(LinkList &L,int i)
{
    LNode *p =L;int j=0;  //初始化,p指向首元节点,计数器j初值为1
   while(p&&j<i-1)   //满足条件
   {
    p=p->next;    //p指向下一个节点
    ++j;          //计数器加1
   }
   if(!p||j>i-1) return ERROR;  //不满足

   LNode *q = p->next;
   p->next = q->next;
   delete q;
   return OK;
}

6、创建单链表

前面的初始化操作是创建一个只有头节点的空链表,我们接下来则需要建立一个包含节点的链表

(1)前插法

通过将新节点插入头部来创建

void CreateList_H(LinkList &L,int n)
{
    //逆位输入n个元素值,插入链表
     L = new LNode;
     L->next =NULL;
     for(int i=0;i<n;++i)
     {
        LNode *p = new LNode;
        cin >>p->data;
        p->next = L->next;
        L->next=p;
     }
}

(2)后插法

把新的节点插入后面


void CreateList_R(LinkList &L,int n)
{
     L = new LNode;
     L->next =NULL;
     LNode *r = L;
     for(int i=0;i<n;++i)
     {
        LNode *p = new LNode;
        cin >>p->data;
        p->next = NULL;
        r->next=p;
        r = p;
     }
}

2.4.3 循环列表

表中最后一个节点指向头节点,差别在终止的条件不同,条件为? ? p!=L

2.5.3双向链表

在单链表种,查找后继为O(1),但查找前驱为O(n),为了克服这个缺点,我们可以设置两个指针域,这样可以查找前驱

typedef struct DuLNode
{
   ElemType data;
   struct DuLNode *prior;
   struct DuLNode *next;
}DuLNode,DuLink;

双向链表的插入和删除都是O(n),他在进行操作的时候需要操作四个指针

2.6 顺序表与链表的比较

2.6.1 空间性能比较

(1)顺序存储必须先分配存储空间 元素数量有一定限制.而链表不需要先分配空间。

(2)从存储密度上说,链表还需要存储指针域,存储密度=数据元素本身的存储量/节点结构占用的存储量,所以链表的存储密度就低。

2.6.2 时间性能的比较

(1)存取元素的效率:顺序表为随机存取,但链表是一种顺序存取,必须按照位置向后访问开始遍历,复杂度为O(n)

(2)删除:顺序表每次删除都需要移动大量元素,但链表无需移动数据,只要改变指针的指向,时间复杂度为O(1),而顺序表为O(n)

2.7 线性表的应用

2.7.1 顺序表的合并

扩大其中一个线性表,把另一个不同的值插入就可以实现合并,这种方法是直接插在其中一个表后

2.7.2 有序表的合并

如果AB两表都是有序的,那么表中的数据就可以相互比较,这样就可以建立两个指针分别指向,然后把小的/大的值取出,存入C表,然后向后移动,当一个表完成后,把另一个表剩下的数据全部导入即可

如果是链表的有序表,就不需要开辟新空间,只要改变指针重新连接即可

(注意 -> next 为指向下一个指针域,而没有改变当前的位置,例如 s - > next,为s的下一个指向。)

栈与队列

栈是先进后出,队列是先进先出
1. 顺序栈的表示与实现

附设指针top指示栈顶元素在顺序栈中的位置。base指示栈底元素在顺序栈的位置,当top和base相等时,表示空

#include<iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型
typedef int SELemType;

#define MAXSIZE 100 
typedef struct 
{
    SELemType *base;
    SELemType *top;
    int stacksize;
    /* data */
}S1Stack;


base 为栈低指针,初始化完成后,栈底指针base始终指向栈底的位置,base为NULL,则代表栈结构不存在。每当插入新元素时,top增1;删除 top-1.top始终指向栈顶元素的上一个位置;

由于顺序栈的插入和删除只在栈顶进行,因此顺序栈的基本操作比顺序表要简单的多

1. 初始化


Status InitStack(S1Stack &S)
{
    S.base = new SELemType[MAXSIZE];
    if(!S.base) exit(OVERFLOW);
    S.top =S.base;
    S.stacksize = MAXSIZE;
    return OK;
    
}

2. 入栈

Status Pushk(S1Stack &S,SELemType e)   
{
    if(S.top-S.base == S.stacksize) return ERROR;
    *S.top ++=e;
    return OK;
}

先给TOP当前所指的位置赋值,再让他移动

3.出栈

Status Pushk(S1Stack &S,SELemType &e)   
{
    if(S.top==S.base) return ERROR;
    e=*--S.top;
    return OK;
}

4. 取栈顶元素


Status GetTop(S1Stack S)   
{
    if(S.top!=S.base) 
    return *(S.top-1);

}

链栈采用单链表的形式

存储结构

typedef struct StackNoede{  
    int data;    //节点数据
    struct StackNoede *next;  //节点指针
}StackNoede,*LinkStack;

1.初始化:

Status InitStack(LinkStack &S)
{
    S = NULL;
    return OK;
}

入栈

Status Push(LinkStack &S ,SELemType e)
{
    StackNoede *p = new StackNoede;
    p->data = e;
    p->next =S;
    S = p;
    return OK;
}

链栈的top并不是空的

出栈

Status Pop(LinkStack &S ,SELemType &e)
{
    StackNoede *p = new StackNoede;
    if(S==NULL) return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p ;
    return OK;
}

删除栈就需要一个新的指针p来存储被删除的位置,然后让S移动

to be continue

1

文章来源:https://blog.csdn.net/ArtoriaLili/article/details/135082010
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。