初阶数据结构前部分总结

1.什么是数据结构

指将数据按特定的规则,存储到特定的结构中

2.算法效率

指解决问题的效率。解决某问题的算法的好坏取决于所需内存空间

和花费的时间

而其时间和空间用复杂度来衡量(采用大O的渐进表示法)

时间复杂度:算法运行的快慢》》》》基本操作的执行次数

空间复杂度:算法运行所需的空间》》》运行中额外产生的内存消耗

推导大O阶方法(以时间复杂度为例)

1.用常数1取代运行时间中所需要的加法常数

2.在修改后的运行次数函数中,只保留最高阶项

3.如果最高阶项存在且不是1,则去出与这个项目相乘的常数,得到的结果就是大O阶

实质:去掉对结果影响不大的数

如用二分查找递增数集的某个数

其时间的复杂度为以2为底的log(n)

斐波那契数列的递归算法的时间复杂度为2的n次方

通常情况下,时间复杂度和空间复杂度越接近O(1),其算法就越优。

3.线性表

就是具有线性关系的数据结构

如顺序表,链表,栈,队列....

顺序表就是个数组,可以根据实际情况变形为动态和非动态增长

其结构特点为,数据连续存放,且只能从前往后放,不能越界存储

由于是个数组,顺序表支持随机访问,从空间的角度看,数据是连续存放的

可通过malloc函数或realloc函数实现动态增长,有利于充分利用空间

bool SeqListempty(SeqList*ps)
{
	return ps->capacity == ps->size;

}
void check_capacity(SeqList*ps)
{
	if (ps->capacity == ps->size)//判断增容
	{
		if (ps->capacity == 0)
		{
			ps->capacity = 4;
		}
		else
		{
			ps->capacity *= 2;
		}
		SLDateType*tmp = (SLDateType*)realloc(ps->a, ps->capacity*sizeof(SLDateType));
		if (tmp == NULL)
		{
			printf("增容失败\n");
		}
		else
		{
			ps->a = tmp;
		}
	}
}
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void SeqListDestory(SeqList* ps)
{
	free(ps->a);
	ps->size = 0;
	ps->capacity = 0;

}
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	size_t i = 0;

	for ( i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{
	assert(ps);
	check_capacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{
	assert(ps);
	check_capacity(ps);
	size_t i = 0;
	SLDateType tmp = 0;
	SLDateType tmp1 = 0;
	tmp = ps->a[i];
	ps->a[i] = x;
	ps->size++;
	for (i=1; i < (ps->size); i++)
	{
		tmp1 = tmp;
		tmp = ps->a[i];
		ps->a[i] = tmp1;
	}
}
void SeqListPopFront(SeqList* ps)
{
	assert(ps&&ps->size);

	SeqList*tmp = ps;
	ps->a = ps->a + 1;
	free(tmp);
	ps->size--;

}
void SeqListPopBack(SeqList* ps)
{
	assert(ps&&ps->size);
	ps->size--;
}

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps&&ps->size);
	size_t i = 0;
	while (isize)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	printf("没找到\n");
	return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
	assert(ps);
	check_capacity(ps);
	ps->size++;
	SLDateType tmp = ps->a[pos];
	SLDateType tmp1 = 0;
	ps->a[pos] = x;
	size_t i = pos + 1;
	while (isize)
	{
		tmp1 = ps->a[i];
		ps->a[i] = tmp;
		tmp = tmp1;
		i++;
	}

}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps&&ps->size);
	check_capacity(ps);
	size_t i = pos;
	while (isize-1)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;

}


上面对顺序表的增删查改的接口函数实现(老久之前写的,没仔细检查过,可能存在漏洞,懒得看了)

接下来是链表

链表按结构上划分有8种结构

而实际上常用得只有两种

一种是无头单向非循环链表(结构简单,实现有点麻烦)也叫单链表

另一个是带头双向循环链表(结构较上复杂那么点,但实现起来方便)

单链表就是定义一个结构体,里面放则下一个结构体的地址,和所需存储的数据

根据该地址可以找到下一个结点,具体如图

初阶数据结构前部分总结_第1张图片

下面是单链表接口函数的实现

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode*tmp = (SListNode*)malloc(sizeof(SListNode));
	if (tmp == NULL)
	{
		printf("开辟空间失败\n");
	}
	else
	{
		tmp->data = x;
		tmp->next = NULL;
		return tmp;
	}
}
// 单链表打印
void SListPrint(SListNode* plist)
{
	assert(plist);
	while (plist)
	{
		printf("%d ", plist->data);
		plist = plist->next;
	}
	printf("\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	(*pplist)->next=BuySListNode(x);

}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode*tmp = *pplist;
	(*pplist)=BuySListNode(x);
	(*pplist)->next = tmp;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	SListNode *tmp = (*pplist);
	while ((*pplist)->next != NULL)
	{
		tmp = (*pplist);
		(*pplist) = (*pplist)->next;
	}
	free(tmp->next);
	*pplist = NULL;


}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	SListNode*tmp = (*pplist)->next;
	free(*pplist);
	*pplist = tmp;


}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	while (plist)
	{
		if (plist->data == x)
		{
			printf("找到了\n");
			return plist;
		}
		plist=plist->next;
	}
	printf("没找到\n");
	return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入?
//就单链表而言,后面位置比前面位置更容易处理
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);

	SListNode*p_tmp = NULL;
	SListNode*tmp=pos->next;
	p_tmp = BuySListNode(x);
	pos->next = p_tmp;
	p_tmp = tmp;
	
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置?
//如果删除pos位置,会使前一个位置不易找到
void SListEraseAfter(SListNode* pos)
{
	assert(pos||pos->next);
	SListNode*tmp=pos->next;
	if (tmp->next == NULL)
	{
		free(tmp);
		pos->next = NULL;
	}
	else
	{
		pos->next = tmp->next;
		free(tmp);

	}
}
// 单链表的销毁
void SListDestory(SListNode* plist)
{
	while (plist)
	{
		SListNode*tmp = plist;
		plist = plist->next;
		free(tmp);
	}
}

 (写的时间过于久远,没有排查过是否有漏洞,但大体思路应该没问题)

而带头双向循环链表其结构如下(可能是)

初阶数据结构前部分总结_第2张图片

画图表示的话是这样的

初阶数据结构前部分总结_第3张图片

 具体接口函数的代码实现不知道放哪了,就不写出来了吧

接下来是有关链表的几个实际OJ题(只有思路,过程懒得写)这里的链表指的是单链表

1. 删除链表中等于给定值 val 的所有节点

考察的是对链表的数据删除

定义两个一指针A,B,还有个删除指针C

一个指针A在前,一个指针B在后,往后迭代寻找

如果相同,把A所指向的结点付给C,A往后走,B指向A

然后释放C所指向的空间即可


2. 反转一个单链表。

两个思路,一个是在原链表上进行操作

初阶数据结构前部分总结_第4张图片

 另一个思路是

给一个头指针,利用单链表的头增,将数据一个一个的移下来


3. 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个
中间结点。

思路:用快慢指针即可解决


4. 输入一个链表,输出该链表中倒数第k个结点。

思路:上一题的快慢指针的变形题


5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成
的。

思路:定义3个指针,一个负责形成新链表,另两个用来操作原链表

给两个链表都定义一个指针。按一定规则比较后,拿下来,指针往后走,循环即可


6. 编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。

思路:形成两个新链表,一个放小于X的部分。另个放大于X的

最后将其连接即可


链接
7. 链表的回文结构

思路:找到中间结点。将后半部分反转,再与前半部分比较即可


8. 输入两个链表,找出它们的第一个公共结点

思路:算出两个链表的长度

定义两个指针,让一个先走K步,最后同时走,当地址相同时返回即可

9. 给定一个链表,判断链表中是否有环

思路:快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表其实位置开始运行,如果链表
带环则一定会在环中相遇,否则快指针率先走到链表的末尾。(课件上的,我偷懒了)

 这个实际上就是个追及问题,在该循环结构中,如果一个慢指针走一步,快指针走两步,则他们之间的距离会一个一个的减少,最终会相遇。

顺序表和链表的区别

存储空间上:顺序表是连续存储,而链表在逻辑上连续。但实际物理储存不一定连续

随机访问:顺序表支持,链表不支持

任意位置删除或插入元素:顺序表可能需要搬动元素,而链表改动指针指向即可

插入:动态顺序表,空间不够时扩容,链表没有容量的概念

——————————————————————————————————————————

接下来是栈

栈的结构特点是先进后出

即数据先进去的最后出来

可以用数组栈或链式栈实现(从效率角度来看,用数组来实现栈更优)

这是栈的有关接口函数的实现

#include"stack.h"


// 初始化栈 
void StackInit(Stack* ps)
{
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	int newcapacity = 0;
	if (ps->_capacity == ps->_top)
	{
		if (ps->_capacity == 0)
		{
			newcapacity = 4;
		}
		else
		{
			newcapacity = ps->_capacity * 2;
		}
		
		STDataType*tmp = (STDataType*)realloc(ps->_a, newcapacity*sizeof(STDataType));
		assert(tmp);
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	if(ps->_top > 0)
	{
		ps->_top--;
	}
	else
	{
		printf("栈数据为空,pop失败\n");
	}
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_a);
	return ps->_a[ps->_top-1];
}


// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	assert(ps->_a);
	if (ps->_top == 0)
	{
		return ps->_top;
	}
	else
	{
		return ps->_top - 1;
	}
}

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0;
}


// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0; 
	ps->_top = 0;
}




MyQueue* myQueueCreate() {

	MyQueue*tmp = (MyQueue*)malloc(sizeof(MyQueue));

	StackInit(&tmp->s1);
	StackInit(&tmp->s2);

	return tmp;
}

void myQueuePush(MyQueue* obj, int x) {

	if (obj->s1._top != 0)
	{
		StackPush(&obj->s1, x);
	}
	else
	{
		StackPush(&obj->s2, x);
	}
}

int myQueuePop(MyQueue* obj) {

	Stack* nonestack = &obj->s1;
	Stack* _stack = &obj->s2;

	if (obj->s1._top != 0)
	{
		nonestack = &obj->s2;
	}

	while (_stack->_top>1)
	{
		StackPush(nonestack, _stack->_a[_stack->_top - 1]);
		StackPop(_stack);
	}
	STDataType tmp = _stack->_a[0];
	StackPop(_stack);

	while (nonestack->_top)
	{
		StackPush(_stack, nonestack->_a[nonestack->_top - 1]);
		StackPop(nonestack);
	}
	return tmp;
}

int myQueuePeek(MyQueue* obj) {

	if (obj->s1._top != 0)
	{
		return obj->s1._a[0];
	}
	else
	{
		return obj->s2._a[0];
	}
}

bool myQueueEmpty(MyQueue* obj) {

	return (obj->s1._top == 0) && (obj->s2._top == 0);

}

void myQueueFree(MyQueue* obj) {

	StackDestroy(&obj->s1);
	StackDestroy(&obj->s2);

	free(obj);
}

下面是队列

队列的特点的先进先出

即先存储的数据先出去

额,好像也没啥了

下面是其接口函数的实现

#include"Queue.h"


void QueueInit(Queue*pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}


void QueueDestroy(Queue*pq)
{
	assert(pq);
	QueueNode*cur = pq->head;
	while (cur != NULL)
	{
		QueueNode*next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}

void QueuePush(Queue*pq, QDataType x)
{
	assert(pq);
	QueueNode*newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->next = NULL;
	newnode->data = x;
	if (pq->head==NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue*pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode*next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}
QDataType QueueFront(Queue*pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}


QDataType QueueBack(Queue*pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

int QueueSize(Queue*pq)
{
	assert(pq);
	int n = 0;
	QueueNode*cur = pq->head;
	while (cur)
	{
		++n;
		cur = cur->next;
	}
	return n;
}

bool QueueEmpty(Queue *pq)
{
	assert(pq);

	return pq->head == NULL;
}

除此之外还可以用两个队列来实现栈。或两个栈实现队列

单纯怕忘了整理一下

你可能感兴趣的