###1.數據在內存中的存儲方式
數據在計算機程序中都是存儲在內存空間中的.
1. 連續內存空間，比如申請一個數組，申請內存的大小事先知道。【數組】
1. 非連續內存空間，特點是申請次數無限制，每次固定大小。【鏈表】
###2.時間復雜度和空間復雜度
- 時間復雜度：同一問題可用不同的算法解決，一個算法的質量優劣將影響算法乃至程序的效率。算法的時間復雜度是一個函數，定量描述算法的運行時間，通常用O表示.
- 空間復雜度：一個算法在運行過程中占用存儲空間大小的度量，包括算法本身所占的存儲空間、數據輸出數據所占用的存儲空間的大學、運行過程中臨時占用的存儲空間的大小這三個方面。
###3.衡量一個算法的優劣的標準
- **正確性**.
所寫算法能滿足具體問題的要求，對于任何合法的輸入可以得出正確的結果。
- **可讀性.**
晦澀難懂的算法不易于交流、推廣、修改、拓展、維護，在寫算法的時候，要盡量寫的簡明易懂。
- **健壯性.**
輸入數據非法時，算法也會做出相應的判斷，不會因為輸入的錯誤造成程序癱瘓。
- **時間復雜度和空間復雜度.**
理想的算法應該是時間復雜度和空間復雜度都最佳。對于一個算法，時間復雜度和空間復雜度往往相互影響。
###4.鏈表基本操作
##### 4.1鏈表結構體定義
~~~
#include <stdio.h>
#include <stdlib.h>
#include <MATH.h>
typedef struct linklist
{
int data;
struct linklist *next; //單鏈表
}linknode,*linklistp;
~~~
##### 4.2.頭部插入新節點
~~~
//返回頭部
linklistp insert_head(linklistp head,linklistp newnode){
newnode->next=head;
head=newnode;
return head;
}
~~~
##### 4.3. 尾部插入新節點
~~~
linklistp insert_tail(linklistp head,linklistp newnode){
if(head==NULL){
head=newnode;
}else{
linklistp temp=head;
while(temp->next!=NULL){
temp=temp->next;
}
newnode->next=temp->next;
temp->next=newnode;
}
return head;
}
~~~
##### 4.4 刪除子節點
~~~
//刪除節點
linklistp list_delete(linklistp head,int a){
linklistp temp=head;
//1.temp為空，返回NULL
if(temp==NULL){
printf("鏈表為空\n");
return NULL;
}
//2.正好是首節點
if(temp->data==a){
head=head->next;
free(temp);
return head;
}
//3.不在首節點
linklistp prev=head;
temp=head->next;
while(temp!=NULL&&temp->data!=a){
prev=temp;
temp=temp->next;
}
//3.1 沒找到
if(temp==NULL){
printf("不存在\n");
return NULL;
}
prev->next=temp->next;
return head;
}
~~~
##### 4.5查找節點
~~~
//查找第i個元素
int getElem(linklistp head,int i,int a){
if (head->next==NULL)
{
printf("link list is NULL");
return 0;
}
linklistp temp=head;
int j=0;
while(temp->next&&j<i){
temp=temp->next;
++j;
}
if(!temp||j>i){
printf(" 不存在第i個元素\n");
}
a=temp->data;
return a;
}
~~~
##### 4.6 判斷鏈表是否為空
~~~
//判斷鏈表是否為空
_Bool isEmpty(linklistp head){
if (head->next==NULL)
{
printf("鏈表為空\n");
return 1;
}
return 0;
}
~~~
#####4.7遍歷鏈表
~~~
void output(linklistp head){
linklistp temp=head;
while(temp){
printf("%d\t", temp->data);
temp=temp->next;
}
printf("\n");
}
~~~
##### 4.8 測試代碼
~~~
int main(){
linklistp head=NULL;
for (int i = 0; i < 10; ++i)
{
/* code */
linklistp newnode=(linklistp)malloc(sizeof(linknode));
newnode->data=i*10+2;
newnode->next=NULL;
head=insert_head(head,newnode);
}
output(head);
printf("*********刪除節點*******\n");
int data=0;
printf("請輸入要刪除的數據：\n");
scanf("%d",&data);
linklistp temp=list_delete(head,data);
if (temp==NULL)
{
printf("def failture or not has this node");
}else{
head=temp;
output(head);
}
printf("**************************\n");
printf("enter the num you want to find:\n");
printf("%d\n",getElem(head,2,data));
return 0;
}
~~~
