1.數據結構

1.概念

程序 ==數據結構 + 算法

• 描述數據存儲和操作的結構

• 操作數據對象的方法

2.衡量代碼質量和效率

在理想情況下，無論代碼操作數據量多大，都希望程序代碼的運行時間保持恒定。

因此，當代碼操作數據量增大的時候，代碼運行時間增速緩慢就表明代碼的質量和效率高，為了衡量這種數據量和時間的關系，引入時間復雜度和空間復雜度的概念

1.時間復雜度

數據量的增長與程序運行時間的增長所呈現的比例關系就稱為時間漸進復雜度函數，也就是時間復雜度

• 常見的時間復雜度：
  • O(1)：程序運行時間維持恒定
  • O(n)：數據量和運行時間關系為線性
  • O(logn)：數據量少時運行時間增長較快，數據量大時運行時間趨于穩定
  • O(nlogn)，O(n^2),O(n3),O(2^n)……

2.空間復雜度

數據的增長與程序占據空間的增長所呈現的比例函數關系，稱為空間復雜度

3.數據結構分類

1.邏輯結構

• 線性結構：表(一對一)
• 非線性結構：樹(一對多)、圖(多對多)

2.存儲結構

• 順序存儲
• 鏈式存儲
• 散列存儲
• 索引存儲

3.常見的數據結構

• 順序表、鏈式表
• 順序棧、鏈式棧
• 順序隊列、鏈式隊列
• 二叉樹、鄰接表、鄰接矩陣

2.鏈表

1.與順序表的區別

• 順序表（數組）特點：
  • 存儲空間連續，訪問元素方便
  • 無法利用小的空間，空間必須連續
  • 順序表元素必須有限
  • 插入和刪除效率低
• 鏈表特點：
  • 存儲空間可以不連續，訪問元素不方便
  • 可以利用一些小的存儲空間
  • 鏈表元素可以沒有上限
  • 插入和刪除效率高

2.鏈表分類

1.單向鏈表

只能通過鏈表節點找到后一個節點，訪問鏈表元素的方向是單向的

1.定義鏈表節點類型

代碼實現：

typedef int datatype;/*鏈表節點類型*/
typedef struct node {datatype data;          // 數據域,存放數據struct node *pnext;     // 指針域，指向下一個節點
} linknode;

2.空鏈表的創建

• 創建一個空的鏈表節點
• data不需要賦值，空白節點不存放數據，主要為了保證鏈表操作的便利性
• pnext必須賦值為NULL，表示該節點為最后一個節點
• 將節點地址返回

代碼實現：

linknode *create_empty_linklist(void){linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(ptmpnode == NULL){printf("filed to malloc");return NULL;}ptmpnode->pnext = NULL;return ptmpnode;
}

3.鏈表的頭插法

• 申請新的節點空間
• 將想要存放的數據存放到新申請的數據控件中
• 將新申請節點的pnext賦值為空白節點的pnext
• 將空白節點的pnext賦值為新申請節點

代碼實現：

int insert_head_linklist(linknode *phead,datatype tmpdata){linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));ptmpnode->data = tmpdata;ptmpnode->pnext = phead->pnext;phead->pnext = ptmpnode;return 0;
}

4.鏈表的遍歷

代碼實現：

方法一：while(p != NULL){p = p->pnext;}	//多用于遍歷鏈表所有元素
方法二：while(p->next != NULL){p = p->next;}	//多用于找出鏈表的最后一個節點
void show_linklist(linknode *phead){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode != NULL){printf("%d ",ptmpnode->data);ptmpnode = ptmpnode->pnext;}printf("\n");return 0;
}

5.鏈表元素刪除

• 定義兩個指針ptmpnode,pprenode,ptmpnode用來遍歷鏈表查找要刪除的元素，pprenode永遠指向ptmpnode的前一個節點
• 當ptmpnode找到要刪除的節點元素，讓pprenode->pnext賦值為ptmpnode ->ptext
• 將要刪除的元素釋放，再將ptmpnode賦值為pprenode->pnext
• 讓ptmpnode判斷下一節點元素是否刪除,直到該指針指向NULL為止

代碼實現：

int delete_linklist(linknode *phead,datatype tmpdata){linknode *ptmpnode = NULL;linknode *pprenode = NULL;pprenode = phead;ptmpnode = phead->pnext;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){pprenode->pnext = ptmpnode->pnext;free(ptmpnode);ptmpnode = pprenode->pnext;}else{ptmpnode = ptmpnode->pnext;pprenode = pprenode->pnext;}}retuen 0;
}

3.makefile

工程管理工具，主要用來管理代碼的編譯

• makefile可以根據文件中的規則來選擇符合條件的代碼完成編譯
• makefile能夠根據依賴關系來決定哪些代碼需要編譯，哪些代碼不需要編譯

使用規則：

• 在工程目錄下，新建一個makefile文件
• 在makefile中編寫對應的文件編譯規則
• 在工程目錄下使用make調用makefile中的規則完成代碼編譯
• 編譯代碼成功后即可運行可執行程序

語法規則：

要生成的文件:依賴的所有文件
生成命令方式

習題

1. 封裝一個函數返回鏈表中第一個指定元素節點的地址

   代碼實現：

   void search_linklist(linknode *phead, int tmpdata){linknode *ptmpnode = NULL;linknode *pprenode = NULL;ptmpnode = phead->pnext;pprenode = phead;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){printf("find it! %p\n", ptmpnode);return;}else{ptmpnode = ptmpnode->pnext;pprenode = pprenode->pnext;}}return;}
   

2. 封裝一個函數將鏈表中指定元素的值更新為新值

代碼實現：

void change_linklist(linknode *phead, int tmpdata,int overdata){linknode *ptmpnode = NULL;linknode *pprenode = NULL;ptmpnode = phead->pnext;pprenode = phead;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){ptmpnode->data = overdata;}ptmpnode = ptmpnode->pnext;pprenode = pprenode->pnext;}return;}

3. 封裝一個函數實現尾插法

代碼實現：

void insert_tail_linklist(linknode *phead,int tmpdata){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode->pnext != NULL){ptmpnode = ptmpnode->pnext;}linknode *pnewnode = NULL;pnewnode = malloc(sizeof(linknode));ptmpnode->pnext = pnewnode;pnewnode->data = tmpdata;pnewnode->pnext = NULL;return;
}

LL){

       ptmpnode = ptmpnode->pnext;}linknode *pnewnode = NULL;pnewnode = malloc(sizeof(linknode));ptmpnode->pnext = pnewnode;pnewnode->data = tmpdata;pnewnode->pnext = NULL;return;

}