算法與數(shù)據(jù)結(jié)構(gòu)
概念
抽象數(shù)據(jù)類型是一種思考問題的方式舆蝴，它隱藏繁雜的細節(jié)岳遥，只保留所需要的信息
數(shù)據(jù)是一類相同性質(zhì)元素的集合雄人，結(jié)構(gòu)就是元素之間的關(guān)系哟冬，
按照取值不同數(shù)據(jù)類型分為原子類型嫂便，
原子類型是不可以再分解的基本數(shù)據(jù)類型捞镰，包括，整型毙替，浮點岸售，字符型
結(jié)構(gòu)類型是由若干類型組合的，是可以再分解的厂画，es結(jié)構(gòu)體結(jié)構(gòu)可以按邏輯結(jié)構(gòu)和物理結(jié)構(gòu)劃分
邏輯結(jié)構(gòu)：
線性結(jié)構(gòu)：包括鏈表凸丸，棧（后進先出）、隊列（先進先出）木羹、字符串甲雅，可以想像成邏輯上是把一個一個數(shù)據(jù)元素串起來。
非線性結(jié)構(gòu)：樹狀坑填，網(wǎng)狀抛人，集合，也就是圖結(jié)構(gòu)脐瑰，樹結(jié)構(gòu)妖枚，集合結(jié)構(gòu)
物理結(jié)構(gòu)：存儲在內(nèi)存中的結(jié)構(gòu)，可以分為順序存儲結(jié)構(gòu)苍在、鏈式存儲結(jié)構(gòu)（內(nèi)存空間不連續(xù)绝页，但是關(guān)系是通過指針串起來的）
算法
-
定義： 算法就是解決特定問題求解步驟的描述,在計算機中表現(xiàn)為指令的有限序列,
并且每個指令表示?個或多個操作.
特性：a.有窮性荠商，也就是要有出口，不能死循環(huán) b.確定性续誉，要有確定的輸出結(jié)果 c.要有輸出莱没，輸入 d可行性
評價標準：正確性，可讀性酷鸦，健壯性饰躲，高效性，時間復(fù)雜度（大O表示法）臼隔，空間復(fù)雜度(額外消耗的內(nèi)存空間)
大O表示法：
常數(shù)階 ,用1表示 O(1)
線性階：O(N)
平方階：O(N^2)
對數(shù)階：O(log N)
nlogn階：O(Nlog N)
立方階：O(N^3)
指數(shù)階：O(2^N)
image.png
-
數(shù)據(jù)結(jié)構(gòu)的基本數(shù)據(jù)單位
數(shù)據(jù)-> 數(shù)據(jù)對象->數(shù)據(jù)元素 -> 數(shù)據(jù)項
數(shù)據(jù)
image.png
非空線性列表的線性結(jié)構(gòu)特點：存在唯一第一個嘹裂，唯一最后一個，除第一個外都有后續(xù)摔握，除最后一個外都有前驅(qū)
image.png
通常增加頭節(jié)點，這樣便于首元節(jié)點的處理氨淌，非空表和空表的統(tǒng)一處理
傳送門：https://github.com/CoderRWL/20200331-
代碼演示
- 線性順序存儲
#include <iostream>
using namespace std;
//線性數(shù)據(jù)邏輯結(jié)構(gòu) 順序存儲
//自定義屬于自己的宏和類型名稱
#define OK 1
#define ERROR 0
#define MAXSIZE 15
typedef int ElemType;
typedef enum {faild,success}status;
//定義一個數(shù)據(jù)元素
/* 數(shù)據(jù)->數(shù)據(jù)對象->數(shù)據(jù)元素->數(shù)據(jù)項 泊愧，其中數(shù)據(jù)元素是數(shù)據(jù)的基本單位*/
class Person{
ElemType *data;//使用數(shù)組來存儲多個數(shù)據(jù)項
int size;//記錄當前存儲數(shù)量/長度
public:
Person(){
//申請堆空間
data = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);//返回void *需要轉(zhuǎn)換一下
size = 0;
}
~Person(){
if (data) {
free(data);
size = 0;
}
}
//增刪改，實際中應(yīng)該加鎖
//增
status insertElem(ElemType e,int index){
//保持健壯性,邊界值判斷宁舰，容錯判斷
if (size == MAXSIZE) return faild;//容量已達最大
if(index > size) return faild;//下標不對拼卵，超過最大長度
//判斷是否需要移動數(shù)據(jù)項
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) {
//移動數(shù)據(jù)
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;//只改動第一次出現(xiàn)的地方
}
}
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存儲數(shù)據(jù)蛮艰，next存儲與其他數(shù)據(jù)項的關(guān)系
typedef struct Person{
ElemType data;
struct Person *next;
}Person;
//定義一個節(jié)點數(shù)組,注意要跟結(jié)構(gòu)體指針區(qū)分開，
//typedef struct Person* personList;
//數(shù)組的地址,初始化一個數(shù)組雀彼，則把數(shù)組的地址傳過來壤蚜，要改變形參，需要傳地址徊哑，可以這么理解
status InitPerson(Person **list){
//創(chuàng)建頭節(jié)點. list是數(shù)組首地址
//先分配一個首元節(jié)點空間袜刷，后續(xù)動態(tài)添加，哨兵莺丑，一直在最第一個位置
*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;//計數(shù)
Person *pre_p = p;
while (pre_p && k < index) {
//查找index-1的節(jié)點
k++;
pre_p = pre_p->next;
}
//如果沒有哨兵，上面就要 < index-1,pre_p->next時正好來到index-1
if (!pre_p) {
return faild;//沒有找到
}
/*要添加節(jié)點的關(guān)系指向下一個節(jié)點
讓前驅(qū)節(jié)點的關(guān)系指向當前節(jié)點*/
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){
//找到前后節(jié)點道宅，刪掉前后驅(qū)關(guān)系
//前面判斷跟增加節(jié)點是一致的
if (!p) {
return faild;
}
int k = 0;//計數(shù)
Person *pre_p = p;
while (pre_p && k < index) {
//查找index-1的節(jié)點
k++;
pre_p = pre_p->next;
}
if (!pre_p) {
return faild;//沒有找到
}
/*讓前節(jié)點的關(guān)系指向刪除節(jié)點的后驅(qū)節(jié)點
釋放刪除節(jié)點空間
*/
Person *deleteP = pre_p->next;
pre_p->next = deleteP->next;
free(deleteP);
return success;
}
//改
status modify(Person *p,ElemType e,int index){
/*只需改動值臼朗，不需要改動關(guān)系*/
if (!p) {
return faild;
}
int k = 0;//計數(shù)
Person *p_index = p;
while (p_index && k <= index) {
//查找index-1的節(jié)點
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;//計數(shù)
Person *p_index = p;
while (p_index && k <= index) {
//查找index-1的節(jié)點
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;
/*
新加入的節(jié)點指向第一個節(jié)點
頭節(jié)點指向新加入的節(jié)點
*/
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;
}
/*
直接加到最后 ,為節(jié)點關(guān)系指向新添加節(jié)點
*/
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);//傳地址過去，內(nèi)部初始化
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
循環(huán)鏈表
-
也就是尾節(jié)點再指向頭節(jié)點
image.png 代碼
//
// main.c
// 線性循環(huán)鏈表
//
// 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){//因為需要改變頭節(jié)點指針昏名，所以需要傳**
if (!(*L)) {
return faild;
}
List *l_add = malloc(sizeof(List));
l_add->data = e;
if (!l_add) {
return faild;
}
//首節(jié)點比較特殊,因為要使 L指向添加的節(jié)點
if (place == 0) {
/*
查找最后的節(jié)點
*/
List *tempL = *L;
while (tempL->next!= (*L) ){
tempL = tempL->next;
}
tempL->next = l_add;//為節(jié)點指向新節(jié)點
l_add->next = *L;//新節(jié)點指向頭節(jié)點
*L =l_add;//頭節(jié)點指向新節(jié)點
}else{
/*
查找最后的節(jié)點
*/
List *tempL = *L;
int g= 0;
while (tempL->next!= (*L) && g<place-1 ){
g++;
tempL = tempL->next;
}
if (tempL->next == *L) {
//找完也沒有找到,可能place 超出最大長度
return faild;
}
//找到前面一個節(jié)點
l_add->next = tempL->next;
tempL->next = l_add;
}
return success;
}
//刪
status deletList(List**L,int place){
if (!(*L)) {
return faild;
}
//處理特殊情況涮雷，刪除頭節(jié)點，需要改變尾節(jié)點指向
if (place == 0) {
//只有一個的時候
if ((*L)->next == *L){
free(*L);
return success;
}
//找到尾節(jié)點
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{
//找到刪除節(jié)點前驅(qū)
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
