数据结构---顺序表---单链表
目录
一、什么是程序？
程序 = 数据结构 + 算法
二、一个程序是否优秀的两个标准
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;
}六、总结
顺序表和链表的区别很明显，链表空间地址不是连续的，顺序表空间地址是连续的；链表需要的空间大，但是理论上可以存储无限数据，而顺序表需要空间较小，存储的元素个数有限；顺序表访问元素比链表方便。