算法与数据结构
概念
抽象数据类型是一种思考问题的方式，它隐藏繁杂的细节，只保留所需要的信息
数据是一类相同性质元素的集合，结构就是元素之间的关系，
按照取值不同数据类型分为原子类型，
原子类型是不可以再分解的基本数据类型，包括，整型，浮点，字符型
结构类型是由若干类型组合的，是可以再分解的，es结构体结构可以按逻辑结构和物理结构划分
逻辑结构：
线性结构：包括链表，栈（后进先出）、队列（先进先出）、字符串，可以想像成逻辑上是把一个一个数据元素串起来。
非线性结构：树状，网状，集合，也就是图结构，树结构，集合结构
物理结构：存储在内存中的结构，可以分为顺序存储结构、链式存储结构（内存空间不连续，但是关系是通过指针串起来的）
算法
-
定义： 算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,
并且每个指令表示⼀个或多个操作.
特性：a.有穷性，也就是要有出口，不能死循环 b.确定性，要有确定的输出结果 c.要有输出，输入 d可行性
评价标准：正确性，可读性，健壮性，高效性，时间复杂度（大O表示法），空间复杂度(额外消耗的内存空间)
大O表示法：
常数阶 ,用1表示 O(1)
线性阶：O(N)
平方阶：O(N^2)
对数阶：O(log N)
nlogn阶：O(Nlog N)
立方阶：O(N^3)
指数阶：O(2^N)
image.png
-
数据结构的基本数据单位
数据-> 数据对象->数据元素 -> 数据项
数据
image.png
非空线性列表的线性结构特点：存在唯一第一个，唯一最后一个，除第一个外都有后续，除最后一个外都有前驱
image.png
通常增加头节点，这样便于首元节点的处理，非空表和空表的统一处理
传送门：https://github.com/CoderRWL/20200331-
代码演示
- 线性顺序存储
#include <iostream>
using namespace std;
//线性数据逻辑结构 顺序存储
//自定义属于自己的宏和类型名称
#define OK 1
#define ERROR 0
#define MAXSIZE 15
typedef int ElemType;
typedef enum {faild,success}status;
//定义一个数据元素
/* 数据->数据对象->数据元素->数据项 ，其中数据元素是数据的基本单位*/
class Person{
ElemType *data;//使用数组来存储多个数据项
int size;//记录当前存储数量/长度
public:
Person(){
//申请堆空间
data = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);//返回void *需要转换一下
size = 0;
}
~Person(){
if (data) {
free(data);
size = 0;
}
}
//增删改，实际中应该加锁
//增
status insertElem(ElemType e,int index){
//保持健壮性,边界值判断，容错判断
if (size == MAXSIZE) return faild;//容量已达最大
if(index > size) return faild;//下标不对，超过最大长度
//判断是否需要移动数据项
if (index < size) {
for (int i = size; i>index; i--) {
data[i] = data[i-1];
}
}
data[index] = e;
size++;
return success;
}
//删
status deleteElem(ElemType e){
if (size == 0) return faild;
for (int i = 0; i<size; i++) {
if (data[i] == e) {
//移动数据
for (int j = i; j<size-1; j++) {
data[j] = data[j+1];
}
size--;
break;
}
}
return success;
}
status deleteElemAtIndex(int index){
if (size == 0) return faild;
for (int j = index; j<size-1; j++) {
data[j] = data[j+1];
}
size--;
return success;
}
//改
status modify(ElemType old_e,ElemType new_e){
if (size == 0) return faild;
for (int i =0; i< size ; i++) {
if (data[i] == old_e) {
data[i] = new_e;
//break;//只改动第一次出现的地方
}
}
return success;
}
status modifyAtIndex(ElemType e,int index){
if (size == 0) return faild;
if (index > size-1) return faild;
data[index] = e;
return success;
}
//查
status search(int index,ElemType &e){
if (size == 0) return faild;
if (index > size-1) return faild;
e = data[index];
return success;
}
//遍历打印
status travel(){
if (data == NULL) return faild;
for (int i = 0; i<size; i++) {
cout << data[i] << endl;
}
return success;
}
};
int main(int argc, const char * argv[]) {
// insert code here...
cout << "Hello, World!\n";
Person p;
for (int i =0; i<10; i++) {
p.insertElem(i, 0);
}
p.modify(5, 50);
p.modifyAtIndex(90, 0);
ElemType e ;
p.search(4, e);//当形参是&类型时，传递时可以直接传变量名
p.travel();
return 0;
}
- 线性链式储存
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 15
typedef enum {faild,success}status;
typedef int ElemType;
//线性链式存储
//data存储数据，next存储与其他数据项的关系
typedef struct Person{
ElemType data;
struct Person *next;
}Person;
//定义一个节点数组,注意要跟结构体指针区分开，
//typedef struct Person* personList;
//数组的地址,初始化一个数组，则把数组的地址传过来，要改变形参，需要传地址，可以这么理解
status InitPerson(Person **list){
//创建头节点. list是数组首地址
//先分配一个首元节点空间，后续动态添加，哨兵，一直在最第一个位置
*list =(Person *)malloc(sizeof(Person));
if (!*list) {
return faild;
}
(*list)->data = 0;//可以赋值一些有意义的值，比如长度
(*list)->next = NULL;
return success;
}
//增
status Insert(Person *p,ElemType e,int index){
if (!p) {
return faild;
}
int k = 0;//计数
Person *pre_p = p;
while (pre_p && k < index) {
//查找index-1的节点
k++;
pre_p = pre_p->next;
}
//如果没有哨兵，上面就要 < index-1,pre_p->next时正好来到index-1
if (!pre_p) {
return faild;//没有找到
}
/*要添加节点的关系指向下一个节点
让前驱节点的关系指向当前节点*/
Person *add_p = malloc(sizeof(Person));
if (!add_p) {
return faild;
}
add_p->data = e;
add_p->next = pre_p->next;
pre_p->next = add_p;
return success;
}
//删
status delete(Person *p ,int index){
//找到前后节点，删掉前后驱关系
//前面判断跟增加节点是一致的
if (!p) {
return faild;
}
int k = 0;//计数
Person *pre_p = p;
while (pre_p && k < index) {
//查找index-1的节点
k++;
pre_p = pre_p->next;
}
if (!pre_p) {
return faild;//没有找到
}
/*让前节点的关系指向删除节点的后驱节点
释放删除节点空间
*/
Person *deleteP = pre_p->next;
pre_p->next = deleteP->next;
free(deleteP);
return success;
}
//改
status modify(Person *p,ElemType e,int index){
/*只需改动值，不需要改动关系*/
if (!p) {
return faild;
}
int k = 0;//计数
Person *p_index = p;
while (p_index && k <= index) {
//查找index-1的节点
k++;
p_index = p_index->next;
}
if (!p_index) {
return faild;//没有找到
}
p_index->data = e;
return success;
}
//查
status search(Person *p,int index,ElemType *e){
if (!p) {
return faild;
}
int k = 0;//计数
Person *p_index = p;
while (p_index && k <= index) {
//查找index-1的节点
k++;
p_index = p_index->next;
}
if (!p_index) {
return faild;//没有找到
}
*e = p_index->data;
return success;
}
//单链表前插和后插法
status creatHead(Person *p ,int count){
if (!p) {
return faild;
}
Person * p_first = p->next;
/*
新加入的节点指向第一个节点
头节点指向新加入的节点
*/
while (count-- >0) {
Person *p_add = malloc(sizeof(Person));
if (!p_add) {
return faild;
}
p_add->data = count;//arc4random_uniform(100);
p_add->next = p_first;
p->next = p_add;
p_first = p_add;
}
return success;
}
status creatAfter(Person *p ,int count){
if (!p) {
return faild;
}
Person * p_after = p;
while (p_after->next) {
p_after = p_after->next;
}
/*
直接加到最后 ,为节点关系指向新添加节点
*/
while (count-- >0) {
Person *p_add = malloc(sizeof(Person));
if (!p_add) {
return faild;
}
p_add->data = count;//arc4random_uniform(100);
p_after->next =p_add;
p_after = p_add;
if (count == 0) {
p_after->next = NULL;
}
}
return success;
}
void travel(Person p){
// printf("%d\n",p.data);//哨兵可以不打印
Person *nextp = p.next;
while (nextp) {
printf("%d\n",nextp->data);
nextp = nextp->next;
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
Person *p;
InitPerson(&p);//传地址过去，内部初始化
for (int i = 0; i<10; i++) {
Insert(p, i, 0);
}
// Insert(p, 100, 5);
// Insert(p, 100, 11);
// delete(p, 0);
// delete(p, 8);
//
// modify(p, 60, 2);
//
// ElemType e;
// search(p, 2, &e);
//
// if (p) {
// travel(*p);
// }
// creatHead(p, 10);
creatAfter(p, 5);
travel(*p);
return 0;
}
-
比较
image.png
循环链表
-
也就是尾节点再指向头节点
image.png 代码
//
// main.c
// 线性循环链表
//
// Created by RWLi on 2020/4/1.
// Copyright © 2020 RWLi. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
typedef enum{faild,success}status;
typedef int ElemType ;
typedef struct List{
ElemType data;
struct List* next;
}List;
status initList(List **list,ElemType e){
*list = malloc(sizeof(List));
if (!(*list)) {
return faild;
}
(*list)->data = e;
(*list)->next = *list;
return success;
}
//增
status listInsert(List**L, ElemType e ,int place){//因为需要改变头节点指针，所以需要传**
if (!(*L)) {
return faild;
}
List *l_add = malloc(sizeof(List));
l_add->data = e;
if (!l_add) {
return faild;
}
//首节点比较特殊,因为要使 L指向添加的节点
if (place == 0) {
/*
查找最后的节点
*/
List *tempL = *L;
while (tempL->next!= (*L) ){
tempL = tempL->next;
}
tempL->next = l_add;//为节点指向新节点
l_add->next = *L;//新节点指向头节点
*L =l_add;//头节点指向新节点
}else{
/*
查找最后的节点
*/
List *tempL = *L;
int g= 0;
while (tempL->next!= (*L) && g<place-1 ){
g++;
tempL = tempL->next;
}
if (tempL->next == *L) {
//找完也没有找到,可能place 超出最大长度
return faild;
}
//找到前面一个节点
l_add->next = tempL->next;
tempL->next = l_add;
}
return success;
}
//删
status deletList(List**L,int place){
if (!(*L)) {
return faild;
}
//处理特殊情况，删除头节点，需要改变尾节点指向
if (place == 0) {
//只有一个的时候
if ((*L)->next == *L){
free(*L);
return success;
}
//找到尾节点
List *tempL = *L;
List *firstL = *L;
while (tempL->next!= (*L) ){
tempL = tempL->next;
}
tempL->next = (*L)->next;
*L = (*L)->next;
free(firstL);
return success;
}else{
//找到删除节点前驱
List *tempL = *L;
int g= 0;
while (tempL->next!= (*L) && g<place-1 ){
g++;
tempL = tempL->next;
}
if (tempL->next == *L) {
//找完也没有找到,可能place 超出最大长度
return faild;
}
List *deleL = tempL->next;
tempL->next = deleL->next;
free(deleL);
}
return success;
}
//改
status modifyList(List *L, ElemType e,int place){
if (!L) {
return faild;
}
List *modifyL = L;
int g = 0;
while (modifyL->next != L && g < place ) {
modifyL = modifyL->next;
g++;
}
if (modifyL->next == L) {
return faild;
}
modifyL->data = e;
return success;
}
//查
status searchList(List *L ,int place,ElemType *e){
if (!L) {
return faild;
}
List *searchL = L;
int g = 0;
while (searchL->next != L && g < place ) {
searchL = searchL->next;
g++;
}
if (searchL->next == L) {
return faild;
}
*e = searchL->data;
return success;
}
void travelList(List *list){
if (!list) {
return;
}
List *temp = list;
do {
printf("%d\n",temp->data);
temp = temp->next;
} while (temp != list);
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
List *circelList;
for (int i = 0; i<10; i++) {
if (!circelList) {
initList(&circelList, i);
}else{
listInsert(&circelList, i, 0);
}
}
listInsert(&circelList, 100, 5);
listInsert(&circelList, 99, 12);
deletList(&circelList, 5);
deletList(&circelList, 9);
deletList(&circelList, 0);
modifyList(circelList, 20, 2);
ElemType e;
searchList(circelList,2,&e);
travelList(circelList);
return 0;
}
- demo传递门
[demo]https://github.com/CoderRWL/20200331-.git
