結構體與鏈表

結構體

　　用一組變數定義一個事物

    struct student   //student 是一種數據類型
    {
        int id;
        char name[20];
　　　　　char sex;
　　　　　int age;

    }mike,bob;
變數定義除了跟在結構體定義後面，還可以：student std1，std2；跟int a，b；類似

結構體的初始化及在記憶體的存儲方式：

 註：結構體在記憶體的存儲方式和數組類似，都是利用了一片連續的記憶體

　　使用點訪問結構體變數的成員值；

　　結構體變數賦值，是copy結構體的值

　　結構體做函數返回值，是copy一份返回值給調用者

結構體與指針

 註：（*one).id_num 還可以寫成 one->id_num , -> 是指向運算符

當指針指向結構體變數時，就可以使用指向運算符訪問結構體的成員變數；

結構體數組：

對結構體數組名進行++操作，跨過的是整個結構體；

即結構體數組名指向的是數組的第一個結構體的地址；

鏈表

註：鏈表頭head，是一個指針

　　鏈表節點包括2部分，第一部分是當前節點數據

　　　　　　　　　　　　第二部分是下一個節點的地址，

　　　　　　　　　　　　如果是雙向鏈表，還包括上一個節點的地址。

　　NULL 代表空指針

new 運算符：開闢存儲空間，返回新存儲空間的地址

　　int *pint  =  new int（1024）// int代表這片存儲空間的數據類型，括弧內是初始值（可以不寫）

　　int *pia  =  new int[4]   // 開闢用來存儲4個整形元素的數組

delete pint   #釋放指針指向的存儲空間。

delete [] pia # []表示要釋放的地址是指向數組的區域

動態創建鏈表：

首先創建一個結構體：

註：student *next； 是創建指向student類型的指針

第一次：head=new student；

　　　　student *temp=head； //temp 用來指向最新節點

如果需要創建下一個節點：

　　temp->next=new student;

　　temp=temp->next; //即將temp往前移動一個結構體

如果不再需要創建新節點：

　　temp->next=NULL;

struct student
{
    int id;
    student* next;
};

student *create() {
    student *head, *temp; int num, n = 0;
    head = new student;
    temp = head;//temp是最新節點
    cin >> num; //輸入學生學號
    while (num!=-1) //學號為-1代表不再有學生
    {
        n++; //統計是鏈表的第幾個節點
        temp->id = num; 
        temp->next = new student;
        temp = temp->next;
        cin >> num;
    }
    if (n == 0)head = NULL; else temp->next = NULL;
    return head;
}

鏈表的遍歷：

鏈表節點刪除：

如果是刪除鏈表的第一個節點，直接讓head指向鏈表的第二個節點

即：temp=head；head=head->next; delete temp；

如果是刪除中間節點，即讓它的前一個節點指向後一個節點；

比如：要刪除的是temp節點，follow->next=temp->next; delete temp；

註：while迴圈執行完，follow節點是要刪除節點的前一個節點，temp節點是要刪除的節點；

節點插入：

比如要插入unit 節點；

如果要在所有元素的前面插入節點：unit->next=head;head=unit;

如果在鏈表中間插入節點：

unit->next=temp;follow->next=unit;

雙向鏈表：

刪除節點：

如果刪除的是中間節點：

插入新節點，如果插入位置是中間：