数据结构基本知识

概论 

一.基本概念和术语

基本概念

1. 数据:是信息的载体，是描述客观事实属性的数。
2. 数据元素:是数据的基本单位，由若干个数据项组成，数据项是数据元素不可分割的最小单位。
3. 数据对象:是具有相同性质的数据元素集合，是数据的一个子集。

数据	信息载体，描述客观事物属性的数
数据对象	相同性质的数据元素集合，是数据的子集
数据元素	数据的基本单位，最小单位是数据项

数据的逻辑结构

逻辑结构指的是数据元素之间的逻辑关系，与数据的存储无关，独立于计算机。

分为线性结构和非线性结构

集合:结构中数据元素同属于一个集合外无其它关系

线性结构:结构中的数据元素之间只存在一对一的关系

树形结构:结构中的数据元素存在一对多的关系

图状结构或网状结构:结构中的数据元素存在多对多的关系

线性结构	非线性结构
一般线性表	集合
受限线性表  (栈和队列)	树  (一般树，二叉树)
线性表推广  (数组)	图  (有向图，无向图)

数据的存储结构

1）顺序存储。把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元中。优点是可以实现随机存取，每个元素占用空间最少。缺点是可能会产生较多的外部碎片。

2）链式存储。逻辑相邻但物理上不要求相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。优点是不会出现碎片现象，能充分利用所有的存储单位。缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。

3）索引存储。存储元素信息的同时，建立附加的索引表，索引表中的每项称为索引项，索引项(关键字,地址)。优点是检索速度快；缺点是附加索引表占用额外空间，修改数据也要修改索引表。

4）散列存储。根据元素的关键字直接计算出该元素的地址，也称哈希（Hash）存储。优点是检索，增加，删除结点都很快。缺点是若散列函数不好，则会出现元素存储单元的冲突，解决冲突产生额外开销。

 二.算法的基本概念

算法的概念

算法:是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

1） 有穷性。一个算法必须总在执行有穷步后停止，且每一步都有穷。

2)   确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

3）可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

4）输入。零个或多个。

5）输出。一个或多个。

好算法的目标:

1.正确性 2.可读性 3.健壮性 4.高效率与低存储量需求

算法效率的度量

1.时间复杂度

一个语句的频度指的是该语句在算法中被重复执行的次数，频度之和T(n)

T(n) = O(f(n))

2.空间复杂度

一个程序在执行时除需要存储空间来存放本身指令，常数，变量和输入输出外，还需要的辅助空间，除输入和程序之外的空间。

S(n)=O(g(n))

线性表 

线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列

特点:个数有限；具有逻辑上的顺序性，有其先后次序；都是数据元素，每个元素都是单个元素；

数据类型都相同，占有空间大小相同；表中元素具有抽象性，仅讨论元素间的逻辑关系。

线性表的基本操作

InitList(&L);//初始化表，构建空的线性表
Length(L);//求表长
LocateElem(L, e);//按值查找操作
GetElem(L, i);//按位查找操作
ListInsert(&L, i, e);//插入操作
ListDelete(&L, i, &e);//删除操作
PrintList(L);//输出操作
Empty(L);//判空操作
DestroyList(&L);//销毁操作

顺序表的定义

线性表的顺序存储也称顺序表，特点是表中元素逻辑顺序与其存储的物理顺序相同。

注意:线性表中元素的位序是从1开始的，而数组中元素的下标从0开始。

#define MaxSize 100 //静态分配的顺序表
typedef struct {            
	ElemType data[MaxSize];
	int length;
}SqList; //顺序表的类型定义

//动态分配的顺序表
typedef struct {
	ElemType *data;
	int MaxSize; //最大容量
	int length;  //当前个数
}SqList; //顺序表的类型定义
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);//C
L.data = new ElemType[InitSize];//C++

顺序表上的基本操作实现

1.顺序表的初始化

静态动态分配的顺序的初始化是不同的。

void InitList(SqList &l)//静态顺序表的初始化
{
	l.length = 0;
}

动态顺序表初始化

void InitList_P(SqList &l)
{
    l.data=(ElemType*)malloc(InitSize*sizeof(*ElemType));
	l.MaxSize = InitSize;//初始存储容量
	l.length = 0;
	
}

2.插入操作

bool ListInsert(SqList &l, int n,int e)//√
{
	if (l.length == MaxSize-1)//满
	{
		return 0;
	}
	for (int i = l.length; i > n; i--)//后面的元素后移一个单位
	{
		l.data[i] = l.data[i + 1];
	}
	l.data[n] = e;
    l.length++;
	return 1;
}

3.删除操作

bool ListDelete(SqList &l, int i,int &e)//√
{
	if (i<1||i>l.length)
	{
		return false;
	}
	e=l.data[i-1];
	for(int j = i; j < l.length; i++)//后面的数组元素前移
	{
	 	l.data[j-1] = l.data[j];
	    l.length--;
    }
	return true;

}

4.按值查找

int LocateElem(SqList l, int e)
{
	for (int i = 0; i < l.length; i++)
	{
		if (l.data[i] == e)
		{
			n = i + 1;//下标为i的元素值等于e,返回其位序i+1
			return n;
		}
	}
	return 0;
}

线性表的链式表示

线性表的链式存储也叫做单链表，是通过一组任意的存储单元来存储线性表中的数据元素。为建立数据元素之间的关系，对每个链表结点还需存储除自身元素外的后继指针。

typedef struct ListNode
{
	int data; //数据域
	struct ListNode* next; //指针域
}ListNode,*LinkList;

非随机存储

引入头结点后带来两个优点: 

1.第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表其它位置上的操作一致。

2.无论链表是否为空，其头指针都是指向头结点的非空指针，处理空表和非空表操作统一。

单链表上的基本操作实现

单链表的初始化

bool InitLNode(ListNode &p)//初始化 带头结点
{
    p = (ListNode*)malloc(sizeof(ListNode));//创建头结点
	p->data = 0;
    p->next = NULL;
    return true;
}

bool InitLNode(ListNode* p)//不带头结点初始化
{
	p->data = 0;
    p->next = NULL;
    return true;
}

求表长操作

int Length(LinkList L)
{
    int len=0;
    ListNode* p=L;
    while(p->next!=NULL)
    {
        p=p->next;
        len++;
    }
    return len;
}

按照序号查找结点

ListNode* GetElem(ListNode* L, int i)
{
	ListNode* p = L;
	int j = 0;
	while (p!=NULL&&j<i)
	{
		p = p->next;
		j++;
	}
	return p;
}

按值查找表结点

ListNode* LocateElem(ListNode* p,int e)//查找
{
	ListNode* t = p->next;
	while (t != NULL&&t->data!=e)
	{
		t = t->next;
	}
	return t;
}

插入结点操作

bool ListInsert(LinkList& L, int i, int e)
{
	ListNode* t = L;
	int j = 0;
	while (t != NULL && j < i-1)
	{
		t = t->next;
		j++;
	}
	if (t == NULL)
		return false;
	ListNode* s = (ListNode*)malloc(sizeof(ListNode));
	s->data = e;
	s->next = t->next;
	t->next = s;
	return true;
}

删除结点操作

bool ListDelete(ListNode*& L, int i, int& e)
{
	ListNode* p = L;
	int j = 0;
	while (p->next != NULL && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (p->next == NULL)
		return false;
	ListNode* q = p->next; //q指向被删除的结点
	e = q->data;           //e返回删除值
	p->next = q->next;     //断开*q结点
	free(q);
	return true;
}

采用头插法建立单链表

ListNode* List_HeadInsert(ListNode* &L)
{
	ListNode* s; int x;
	L = (ListNode*)malloc(sizeof(ListNode)); //创建头结点
	L->next = NULL;
	scanf("%d", &x);
	while (x != 9999)     //输入9999结束
	{
		s = (ListNode*)malloc(sizeof(ListNode)); //将新结点插入表中 L为头指针
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}

采用尾插法建立单链表

ListNode* List_TailInsert(ListNode*& L)
{
	int x;
	L = (ListNode*)malloc(sizeof(ListNode)); //创建头结点
	ListNode* s,*r=L;                      //r为表尾指针
	scanf("%d", &x);
	while (x != 9999)     //输入9999结束
	{
		s = (ListNode*)malloc(sizeof(ListNode)); 
		s->data = x;
		r->next = s;
		r = s;                   //r指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL; //尾结点指空
	return L;
}

 双链表

克服从头遍历，增加前驱指针prior，引入双链表

//双链表
typedef struct DNode {
	int data;
	DNode* next, *prior;
}DNode,*DLinkList;

双链表的插入操作

核心代码

s->next = p->next;  //将结点*s插入到结点*p之后
p->next->prior = s;
s->prior = p;
p->next = s;

双链表删除操作

核心代码

p->next = q->next;
q->next->prior = p;
free(q);

循环链表 (略)

首尾相连

循环单链表 

循环双链表

静态链表

#define Max 50
typedef struct StaticList
{
	int data;
	int next;
}SL[Max];