结构体与链表

结构体

　　用一组变量定义一个事物

    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;

 

双向链表：

删除节点：

如果删除的是中间节点：

 

插入新节点，如果插入位置是中间：