数据结构
一、绪论
1.基本概念和术语
数据结构：是一种或多种特定关系的数据元素的集合（结构是关系）
数据结构：分为(集合结构、树形结构、线性结构、图形结构)(计算机中数据逻辑结构的存储形式，又称存储结构)
存储结构：顺序存储和链式存储。
2.抽象数据类型
数据类型：集合一组具有相同性质的值并定义该值
数据类型的作用：
-
1.约束变量的内存空间
-
2.限制变量或常量的值范围
-
3.约束变量或常量的操作
抽象数据类型：抽象现有数据结构（）
抽象数据类型的概念与面向对象的概念是一致的。
3.算法
程序=数据结构 算法
算法：算法是解决特定问题解决步骤的描述，是计算机中指令的有限序列，每个指令表示一个或多个操作
时间复杂：T(n)=O(f(n))
常见时间复杂度比较：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n!)<O(nn)
空间复杂：S(n)=O(f(n))
算法所需的存储空间存储空间实现算法的空间复杂性，所需的存储空间是指算法在运行过程中
4.组织架构
数据结构可以进一步分为线性结构和图形结构（树是一种特殊的图）
二、线性表（一般线性表）
1.基本概念
（1）定义：线性表就是n个数据元素()的有限序列
（2）特点：存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素
除第一个之外的数据元素均只有一个前驱 除最后一个之外的数据元素均只有一个后继
存在首尾，除首尾都有前驱和后继
2.顺序存储结构
在计算机中用一组的存储单元依次存储线性表的各个数据元素 ，这种方法存储的线性表称作顺序表。
描述顺序存储结构需要三个属性：
（1）存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
（2）线性表的最大存储容量：数组长度MaxSize。
（3）线性表的当前长度：length。
顺序表存入或者取出数据时间复杂度为（通过公式直接计算），这种存储结构称为随机存取结构
优缺点
优点：（1）无需为表中元素之间的逻辑关系增加额外的空间 （2）快速查找
缺点：（1）插入删除移动大量元素 （2）存储空间固定
//顺序存储结构线性表
include<stdio.h>
include<stdlib.h>
define MAXSIZE 20
typedef struct{
int data[MAXSIZE];
int length;
}Sqlist;
/* typedef struct{ int*data; int MAXSIZE; int length; }Sqlist; */
//线性表的初始化
void Initlist(Sqlist* p) {
p->length = 0;
}
/* void Initlist(Sqlist* p){ p->data = (int*)malloc(sizeof(int)); if(p->data==NULL) { printf("动态内存分配失败"); exit(-1); } p->length = 0; } */
//线性表的创建
void CreateList(Sqlist* p,int n) {
int i,m;
for (i = 0; i < n; i++)
{
scanf("%d", &m);
p->data[i] = m;
p->length++;
}
}
//获取元素操作
int GetElem(Sqlist* p, int e) {
int i; //第几个元素
scanf("%d", &i);
if (i > p->length)
{
exit(0);
}
e = p->data[i - 1];
return e;
}
顺序存储结构线性表中
插入一个元素，平均需要移动 n/2个元素
删除一个元素，平均需要移动 n-1/2个元素
//插入元素
算法思路：
如果插入位置不合理，抛出异常；
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
将要插入元素填入位置i处，表长加1。
Sqlist* ListInsert(Sqlist* p) {
int k,i,a;
scanf("%d", &i);
scanf("%d", &a);
if (p->length == MAXSIZE)
{
printf("线性表已满");
exit(0);
}
if (i<1 || i>p->length + 1)
{
printf("插入位置不在范围内 ");
exit("error");
}
if (i <= p->length)
{
//将要插入位置后数据元素向后移动一位
for (k = p->length - 1; k >= i - 1; k--)
{
p->data[k + 1] = p->data[k];
}
p->data[i - 1] = a;
p->length++;
return p;
}
}
//删除元素
如果删除位置不合理，抛出异常；
取出删除元素；
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
表长减1。
Sqlist* ListDelete(Sqlist* p) {
int k, i;
scanf("%d", &i);
if (p->length == 0) //线性表为空
{
exit(0);
}
if (i<1 || i>p->length + 1)
{
printf("删除位置不在范围内 ");
exit(0);
}
if (i < p->length)
{
for (k = i; k < p->length; k++)
{
p->data[k - 1] = p->data[k];
}
}
p->length--;
return p;
}
//插入和删除的平均时间复杂度均为O（n）
int main(void)
{
int n,j,e = 0;//初始化e
Sqlist* p = (Sqlist*)malloc(sizeof(Sqlist)); //初始化p
Initlist(p);
scanf("%d", &n);
CreateList(p, n);
//e = GetElem(p, e);
//p = ListInsert(p);
//p = ListDelete(p);
for (j = 0; j < p->length; j++)
{
printf("%d ", p->data[j]);
}
return 0;
}
3.链式存储结构
用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
头结点与头指针
头指针是指向链表第一个结点的指针，如果有头结点就是指向头结点的指针，具有标识作用，常被冠以链表名字
头结点是为了统一第一个元素与其他元素插入删除操作的统一
由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是**“工作指针后移”**
//链式存储结构线性表 #include<stdio.h> #include<stdlib.h> typedef struct Lnode { int data; struct Lnode* next; }Lnode, * LinkList; //链式结构线性表不用规定长度（没有length）,存储的元素个数不受限制（没有MAXSIZE） //初始化 LinkList InitList(LinkList h) { h = (LinkList)malloc(sizeof(Lnode)); if (!h) { exit(-1); } h->next = NULL; } //尾插法创建单链表 LinkList CreateList(LinkList h) { LinkList p,s; int i,len; scanf("%d", &len); p = h; for (i = 0; i < len; i++) { s = (LinkList)malloc(sizeof(Lnode)); scanf("%d", &s->data); s->next = NULL; p->next = s; p = s; } return h; } //头插法创建 //LinkList CreateList(LinkList h) { // LinkList s; // int i, len; // scanf("%d", &len); // for (i = 0; i < len; i++) // { // s = (LinkList)malloc(sizeof(Lnode)); // scanf("%d", &s->data); // s->next = h->next; // h->next = s; // } // return h; //} //读取、遍历和查找 查找算法思路 1.声明一个指针p指向链表第一个结点，初始化j从1开始； 2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1； 3.若到链表末尾p为空，则说明第i个结点不存在； 4.否则查找成功，返回结点p的数据。 int GetElem(LinkList h) { int i, j=1, e; LinkList p; //声明一个指针p指向链表第一个结点，初始化j从1开始 scanf("%d", &i); p = h->next; while (p && j < i) { p = p->next; j++; } if (!h || j > i) { exit(0); //第i个节点不存在 } e = p->data; return e; } //插入元素 LinkList ListInsert(LinkList h) { int i, j=1, e; LinkList s; LinkList p = h; scanf("%d", &i); scanf("%d", &e); while (p && j < i) //寻找第i-1个结点 { p = p->next; j++; } if (!p || j > i) { exit("error"); } s = (LinkList)malloc(sizeof(Lnode)); s->data = e; s->next = p->next; p->next = s; return h; } //删除元素 LinkList ListDelete(LinkList h) { int i, j = 1; LinkList p = h; LinkList q; scanf("%d", &i); while (p->next && j < i)//寻找第i-1个结点 { p = p->next; j++; } if (!(p->next) || j > i) { exit("error"); } q = p->next; p->next = q->next; //e = q->data free(q); return h; } //单链表整表删除 LinkList ClearList(LinkList h) { LinkList p, q; p = h->next; while (p) { q = p->next; free(p); p = q; } h->next = NULL; return h; } int main(void) { int i; LinkList h = (LinkList)malloc(sizeof(Lnode)); h = InitList(h); h = CreateList(h); h = h->next; while (h != NULL) { printf("%d ", h->data);