C++學習（三十四）（C語言部分）之 鏈表

1、棧和隊列 操作 增查改刪
重點 插入刪除
先進先出 -->隊列
先進後出 -->棧
2、鏈表 寫之前先畫圖
存儲數據的方式 通過指針將所有的數據鏈在一起
數據結構的目的 管理存儲數據 方便快速查找使用

鏈表定義 鏈式存儲的線性表 一對一的關係
結構體 指針 函數 迴圈

結構體複習：
struct 點運算符（結構體變數） 箭頭運算符（結構體指針）
結構體變數.成員 的方式訪問成員
字元數組 gets strcpy

鏈表操作
剛開始只有一個結構體
增 插入一個節點 需要申請記憶體
刪 刪除一個節點 需要釋放記憶體

鏈表 需要插入的時候申請節點 需要刪除的時候直接釋放節點 會節約記憶體

靜態數組 1.棧區大小 放不了態度數據
2.數組大小不能改變
動態數組 1.如果有一個數據 插入 重新申請記憶體 所有數據都要移動一次
2.插入刪除不便
3.申請大的空間可能會申請失敗

鏈表 有一個數據 申請一個 刪除時只需要刪除節點 不會影響其他節點
每次一個結構體大小 所以空間比較小 會比較節省記憶體 申請失敗的可能性小
插入和刪除比較簡單不需要大規模的移動

測試的代碼筆記如下：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef struct node  //定義結構體
  5 {
  6     //數據  數據域
  7     int data;
  8     //指針  指針域  存放下一個節點的地址
  9     struct node*next;
 10 }NODE, *PNODE;  //別名
 11 //結構體的類型裡面不能放數據  變數裡面放數據
 12 //PNODE就是struct node*  結構體指針類型  就好比int和int*
 13 
 14 void insert(PNODE head,int data)  //增
 15 {
 16     //準備要插入的節點
 17     PNODE p = (PNODE)malloc(sizeof(NODE));
 18     p->data = data;
 19     p->next = NULL;
 20     //開始插入
 21 #if 0    
 22     //頭插法  head->A（沒有數據）->C->D->NULL 指向要插入的節點B
 23     p->next = head->next;  //B 去保留C的地址
 24     head->next = p;  //A保留的是B的首地址
 25     //head->A（沒有數據）->B->C->D->NULL
 26 #else
 27     //尾插法
 28     PNODE temp;
 29     temp = head;  //找到第一個節點的位置
 30     while (temp->next!=NULL)  //判斷是不是最後的節點 next是NULL
 31     { 
 32         temp = temp->next;
 33     }
 34     //迴圈退出之後 temp指向它的最後一個節點
 35     temp->next = p;
 36 
 37 #endif
 38 }
 39 
 40 void findData(PNODE head, int data)  //查
 41 {
 42     //查找
 43     PNODE temp = head->next;  //從第二個元素開始
 44     while (temp!=NULL)  //從頭到尾一個一個找
 45     {
 46         if (temp->data == data)
 47         {
 48             //數據匹配
 49         }
 50         temp = temp->next;
 51     }
 52     
 53     //PNODE temp = head;
 54     //while (temp->next!=NULL)
 55     //{
 56     //    if (temp->next->data == data)  //temp指向第一個節點
 57     //    {
 58 
 59     //    }
 60     //    temp = temp->next;
 61     //}
 62 }
 63 
 64 void changeNode(PNODE head, int data, int newData)  //改
 65 {
 66     //修改
 67     PNODE temp = head->next;  //從第二個元素開始
 68     while (temp != NULL)  //從頭到尾一個一個找
 69     {
 70         if (temp->data == data)
 71         {
 72             //數據匹配
 73             temp->data = newData;  //修改數據
 74         }
 75         temp = temp->next;
 76     }
 77 }
 78 
 79 void deleNode(PNODE head, int data)  //刪
 80 {
 81     //刪除
 82     PNODE p = head;
 83     while (p->next!=NULL)
 84     {
 85         if (p->next->data == data)  //下一個節點的data
 86         {
 87             //要刪除的節點 p->next
 88             PNODE temp = p->next;
 89             p->next = p->next->next;  //連接成功
 90             free(temp);  //釋放掉temp  記憶體
 91         }
 92     }
 93 }
 94 
 95 void deleAllNode(PNODE head)  //釋放所有節點
 96 {
 97     PNODE temp;  //臨時的指針作為輔助
 98     while (head != NULL)
 99     {
100         temp = head;
101         head = head->next;
102         free(temp);
103     }
104 }
105 
106 void print(PNODE head)//列印全部節點
107 {
108     PNODE temp = head->next;//從第二個元素開始   列印內容
109     while (temp != NULL)
110     {
111         printf("%d->", temp->data);
112         temp = temp->next;
113     }
114     printf("NULL)");
115 }
116 //鏈表 所有的節點都在堆區 用一個指針去管理這個鏈表 每次插入一個數據 重新申請節點
117 //事先申請好空間 數組/動態數組 臨時申請
118 
119 int main()
120 {
121     PNODE head;  //指針 結構體類型的指針
122     head = (PNODE)malloc(sizeof(PNODE)); //申請一個空的節點 為了後面的增查改刪
123     //第一個節點可以竄數據但是不存 以浪費空間的代價 換取後面操作的簡單
124     head->next = NULL;  //表示後面沒有其他節點
125     for (int i = 0; i < 10; ++i)
126     {
127         insert(head, i);
128     }
129     print(head);
130     deleAllNode(head);
131 
132     getchar();
133     return 0;
134 }

2019-04-01  08:31:37