# 初阶数据结构前部分总结

1.什么是数据结构

2.算法效率

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

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

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

3.线性表

``````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--;

}

``````

``````// 动态申请一个节点
{
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);

}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
assert(pplist);
SListNode*tmp = *pplist;
(*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;
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);
}
}
``````

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

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

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

2. 反转一个单链表。

另一个思路是

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

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

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

7. 链表的回文结构

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

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->tail = NULL;
}

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

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

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

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

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