结构体与链表

一、结构体

结构体数据类型的特性与普通数据类型的特性是一致的。

1.定义

struct student            //名字为student的结构体类型
{
    int id;
    char name[20];
}student3, student4;                //注意此处有一个分号，可同时定义变量

student student1, student2;    //student变成了一种类似与int的数据类型

2.使用

int main()
{
    student mike = {123, {'m', 'i', 'k', 'e', '\0'}};
    mike.id = 20130000 + mike.id;
    for(int i = 0; mike.name[i] != '\0'; i++)
    {
        mike.name[i] = toupper(mike.name[i]);
        cout<<mike.id<<" "<<mike.name<<endl;
        return 0;   
    }
    return 0;
}

存储方式与数组类似，为一片连续的内存空间。

结构体存储方式

3.赋值计算

可以将一个结构体变量赋值给另一个。即一下代码

student mike1 = {123, {'m', 'i', 'k', 'e', '\0'}}, mike2;  
mike2 = mike1;

是没有问题的，且赋完值之后两个结构体变量完全一样，相当于将原变量复制了一份存在新变量中。

4.结构体做函数参数

将一个结构体变量作为参数传递给函数，相当于是把这个变量复制了一份给函数使用，实际上不会影响原变量的使用。这一点与数组完全不同。例子如下：

#include<iostream>
using namespace std;
struct student
{
  int id;
};
void renew(student one)
{
  one.id = 20130000 + one.id;
  cout<<one.id;
}
int main()
{
  student mike = {123};
   renew(mike);
  cout<<mike.id;
}
//输出结果为：
20130123
123

5.结构体做函数返回值

#include<iostream>
using namespace std;
struct student
{
  int id;
};
student newone()
{
  student one = {20130123, {'m', 'i', 'k', 'e', '\0'}};
  return one;
}
int main()
{
  student mike = newone();
  cout<<mike.id<<" "<<mike.name<<endl;
  return 0;
}
输出结果为：
20130123 mike

6.结构体变量与指针

#include<iostream>
using namespace std;
struct student
{
  int id;
};
int main()
{
  student mike = {20130123, {'m', 'i', 'k', 'e', '\0'}};
  student *one = &mike;
  cout<<(*one).id<<" "<<(*one).name<<endl;
  cout<<one->id<<" "<<one->name<<endl;  //两种方式都可以
  return 0;
}
输出结果为：
123 mike
123 mike

->为指向运算符。

7.指向结构体的指针作为函数参数

#include<iostream>
using namespace std;
struct student
{
  int id;
  char name[10];
};
void renew(student *one)
{
  one->id = 20130000 + one->id;
  for(int i = 0; one->name[i] != 0; i++)
    one->name[i] = toupper(one->name[i]);
}
int main()
{
  student mike = {20130123, {'m', 'i', 'k', 'e', '\0'}};
  renew(&mike);
  cout<<mike.id<<" "<<mike.name<<endl;
  return 0;
}
输出：
20130123 MIKE

8.利用结构体定义数组

利用结构体定义数组

二、新运算符new, delete

new：动态的申请内存空间，返回起始地址值
delete：释放指针变量指向的内存空间

• 申请一个int空间并赋初始值1024（不必须赋值）：
  int *pint = new int(1024);，delete pint;
• 申请一个四元素整形数组：
  int *pia = new int[4];，delete [] pia;

三、链表

用指针把结构体变量串起来

1.链表的组成：

• 链表头：指向第一个链表结点的指针
• 链表节点：链表中的每一个元素，包括当前结点的数据和下一个节点的地址
• 链表尾：不再指向其他结点的结点，其地址部分放一个NULL，表示链表到此结束

2.链表创建

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

student *create()
{
    student *head, *temp;
    int num, n = 0;
    head = new student;     //链表头head指向第一个结点 
    temp = head;            //temp指向第一个节点 
    cin>>num;               //输入学号 
    while(n != -1)           
    {
        n++;                 
        temp->id = num;     //学号赋给结点的id 
        temp->next = new student;   //此结点的next指向下一个结点 
        temp = temp->next;      //temp指向下一个结点 
        cin>>num;               //继续输入学号 
    }
    if(n == 0)head = NULL;      //一个结点都没有 
    else temp->next = NULL;
    return head;                //返回链表头 
}

3.链表的操作

遍历

int main()
{
    student *pointer = create();
    while(pointer->next != NULL)
    {
        cout<<pointer->id<<endl;
        pointer = pointer->next;
    }
    return 0;
}

删除

temp指向要被删除的结点，follow指向temp前一个结点
删除首结点：temp = head;head = head->next;delete temp;
删除中间即尾节点：follow->next = temp->next;delete temp;

插入

新结点地址为unit。
插入第一个结点前：

unit->next = head;
head = unit;

插入follow与temp结点之间：

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

4.双向链表

双向链表

删除temp

temp->ahead->next = temp->next;
temp->next->ahead = temp->ahead;

在temp前增加unit

unit->next = temp->next;
unit->ahead = temp;
temp->next = unit;
temp->next->ahead = unit;