目录

一、什么是程序？

 程序 = 数据结构 + 算法

二、一个程序是否优秀的两个标准 

2.1.时间复杂度

2.2.空间复杂度 

三、数据结构

3.1.数据结构间的关系

1.逻辑结构

1）线性关系

2）非线性关系

2.存储结构

1）顺序存储结构

2）链式存储结构

3）离散存储结构

4）索引存储结构

3.2.主要的数据结构

1.表

2.栈

3.队列

4.树

5.图 

四、顺序表

4.1.定义

 4.2.初始化申请空间

4.3.判断函数

​编辑 

4.4.尾添加

​编辑 

4.5.指定位置插入

​编辑 4.6.遍历

 4.7.删除

4.8.清空

​编辑 

4.8.销毁

​编辑   

五、单链表 

 六、总结

---

一、什么是程序？

 程序 = 数据结构 + 算法

二、一个程序是否优秀的两个标准 

2.1.时间复杂度

 时间复杂度：数据量增长与程序的执行时间的一种函数关系；

 时间复杂排序由小到大：O(c) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)；

2.2.空间复杂度 

空间复杂度：数据增长量与程序所占的空间的一种函数关系；

三、数据结构

3.1.数据结构间的关系

1.逻辑结构

1）线性关系

一对一----表

2）非线性关系

一对多---树

多对多---图 

2.存储结构

1）顺序存储结构

2）链式存储结构

3）离散存储结构

4）索引存储结构

3.2.主要的数据结构

1.表

2.栈

3.队列

4.树

5.图 

四、顺序表

4.1.定义

 这里以int为例子

 4.2.初始化申请空间

 

4.3.判断函数

4.4.尾添加

4.5.指定位置插入

注意：指定位置插入后，需要将该位置的往后的所有现有的向后移动 

 4.6.遍历

注意：很重要，里面的函数指针，用来操作查询到的数据的，可以用来查询和修改

 4.7.删除

4.8.清空

4.8.销毁

注意：销毁要释放空间 ，注意主函数

   

五、单链表 

#ifndef _LINKLIST__H_
#define _LINKLIST__H_typedef int DataType;typedef struct node
{DataType data;struct node *pnext;}LinkList;extern LinkList *CreateLinkList(void);
extern int HeadInsertLinkList(LinkList *phead, DataType data);
extern int TailInsertLinkList(LinkList *phead, DataType data);
extern int PrintLinkList(LinkList *phead);
extern int SelectLinkList(LinkList *phead, DataType data);
extern int UpdateLinkList(LinkList *phead, DataType olddata, DataType newdata);
extern int DeleteLinkList(LinkList *phead, DataType data);
extern int CleanLinkList(LinkList *phead);
extern int DestoryLinkList(LinkList *phead);#endif 

#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>/* 创界一个含有头节点的单链表 */
LinkList *CreateLinkList(void)
{LinkList *phead = NULL;phead = malloc(sizeof(LinkList));if (phead == NULL){return NULL;}phead->pnext = NULL;return phead;
}/* 头插法 */
int HeadInsertLinkList(LinkList *phead, DataType data)
{LinkList *pnode = NULL;pnode = malloc(sizeof(LinkList));if (pnode == NULL){return 0;}pnode->data = data;pnode->pnext = phead->pnext;phead->pnext = pnode;return 0;}/* 尾插法 */
int TailInsertLinkList(LinkList *phead, DataType data)
{LinkList *pnode = NULL;LinkList *p = NULL;p = phead;pnode = malloc(sizeof(LinkList));if (pnode == NULL){return 0;}pnode->data = data;while (p->pnext != NULL){p++;}pnode->pnext = NULL;p->pnext = pnode;return 0;}/* 打印数据 */
int PrintLinkList(LinkList *phead)
{  LinkList *ptmp = NULL;if (phead->pnext == NULL){return -1;}ptmp = phead->pnext;while (ptmp != NULL){printf("%d ",ptmp->data);ptmp = ptmp->pnext;}printf("\n");return 0;}/* 查寻 */
int SelectLinkList(LinkList *phead, DataType data)
{LinkList *ptmp = NULL;if (phead->pnext == NULL){return -1;}ptmp = phead->pnext;while (ptmp != NULL){if (ptmp->data == data){printf("%d存在!\n", data);break;}ptmp = ptmp->pnext;}return 0;
}/* 修改 */
int UpdateLinkList(LinkList *phead, DataType olddata, DataType newdata)
{LinkList *ptmp = NULL;if (phead->pnext == NULL){return -1;}ptmp = phead->pnext;while (ptmp != NULL){if (ptmp->data == olddata){ptmp->data = newdata;break;}ptmp = ptmp->pnext;}return 0;
}/* 删除 */
int DeleteLinkList(LinkList *phead, DataType data)
{LinkList *ptmp = NULL;LinkList *qtmp = NULL;if (phead->pnext == NULL){return -1;}ptmp = phead->pnext;qtmp = phead;while (ptmp != NULL){if (ptmp->data == data){qtmp->pnext = ptmp->pnext;free(ptmp);break;}ptmp = ptmp->pnext;qtmp = qtmp->pnext;}return 0;
}/* 清空 */
int CleanLinkList(LinkList *phead)
{LinkList *ptmp = NULL;LinkList *qtmp = NULL;if (phead->pnext == NULL){return -1;}ptmp = phead->pnext;qtmp = phead->pnext;while (ptmp != NULL){ptmp = ptmp->pnext;free(qtmp);qtmp = ptmp;}phead->pnext = NULL;return 0;
}/* 销毁 */
int DestoryLinkList(LinkList *phead)
{LinkList *ptmp = NULL;LinkList *qtmp = NULL;if (phead->pnext == NULL){return -1;}ptmp = phead;qtmp = phead;while (ptmp != NULL){ptmp = ptmp->pnext;free(qtmp);qtmp = ptmp;}return 0;
}

#include "linklist.h"
#include <stdio.h>int main(void)
{LinkList *phead = NULL;phead = CreateLinkList();for (int i = 1; i < 10; i++){//HeadInsertLinkList(phead, i);TailInsertLinkList(phead, i);}PrintLinkList(phead);SelectLinkList(phead, 8);UpdateLinkList(phead, 8, 10);PrintLinkList(phead);DeleteLinkList(phead, 10);PrintLinkList(phead);CleanLinkList(phead);PrintLinkList(phead);DestoryLinkList(phead);return 0;
}

 六、总结

        顺序表和链表的区别很明显，链表空间地址不是连续的，顺序表空间地址是连续的；链表需要的空间大，但是理论上可以存储无限数据，而顺序表需要空间较小，存储的元素个数有限；顺序表访问元素比链表方便。