数据结构学习 days2

1.线性表

线性表主要分为2种，一种是顺序线性表，一种是链式线性表，先来看看顺序线性表

1.1.顺序线性表

最简单的，也是我们一开始接触线性表，就是数组。在数组中，元素之间的地址是相连的，例如在int数组中，二个元素之间的地址之差为4，在long数组中则为8，显然二者地址之间的差值与数组的数据类型有关。在数组中，我们通过查找下标的方式来对对应元素进行查找、修改。

1.2.链式线性表

接下来我们再来看看链式线性表。链式线性表中的元素不像数组那样在一开始就进行分配的，而是根据需求来进行动态分配。同时而在创建链表之前，我们要对链表进行初始化操作

typedef struct linklist
{
    int n;
    struct linklist *next;
}linklist;//结构体初始化链表元素

linklist *listlinkfirst()
{
    linklist *head = malloc(sizeof(linklist));  //创建头结点
	head -> next = NULL;   //将头结点的指针指向NULL
	return head;
}

函数返回的值为链表的头结点

接着在另一函数中传入头结点，创建n个链表单元，并将其链接起来

void linklistcreate(int n,linklist *head)//创建链表元素
{
    linklist *q,*p = head;
    for (int i = 0;i < n;i++)
    {
        q = malloc(sizeof(linklist));//利用malloc函数创建链表元素
        scanf("%d",&q -> n);//将数据传入单个链表元素中
        p -> next = q;//将单个元素链接起来
        p = q;
    }
    p -> next = NULL;//末尾的链表指向NULL
}

随后在另一函数中遍历链表

void linklistcheck(int n,linklist *head)//遍历链表
{
    linklist *q = head;
    for (int i = 0;i < n;i++)
    {
        q = q -> next;
        printf("%d\n",q -> n);
    }
}

一个简单的链表创建+遍历程序如下图所示

#include<stdio.h>
#include<stdlib.h>
typedef struct linklist
{
    int n;
    struct linklist *next;
}linklist;//结构体初始化链表元素

linklist *listlinkfirst()
{
    linklist *head = malloc(sizeof(linklist));  //创建头结点
	head -> next = NULL;   //将头结点的指针指向NULL
	return head;
}
void linklistcreate(int n,linklist *head)//创建链表元素
{
    linklist *q,*p = head;
    for (int i = 0;i < n;i++)
    {
        q = malloc(sizeof(linklist));//利用malloc函数创建链表元素
        scanf("%d",&q -> n);//将数据传入单个链表元素中
        p -> next = q;//将单个元素链接起来
        p = q;
    }
    p -> next = NULL;//末尾的链表指向NULL
}
void linklistcheck(int n,linklist *head)//遍历链表
{
    linklist *q = head;
    for (int i = 0;i < n;i++)
    {
        q = q -> next;
        printf("%d\n",q -> n);
    }
}
int main()
{
    int n;
    scanf("%d",&n);//创建n个链表元素
    linklist *k = listlinkfirst();
    linklistcreate(n,k);
    linklistcheck(n,k);
}

目前来看，链表和数组貌似并无太大的差异，看上去链表相比数组还要更为复杂，那么他们之间有什么不同的地方吗？

接下来我们看看如何在链表中添加/删除元素

int linklistadd(int n,int m,int num,linklist *head)//在数据为m的位置的前方添加num元素
{
    linklist *q = head;
    linklist *p = malloc(sizeof(linklist));
    p -> n = num;
    for (int i = 0;i < n;i++)
    {
        q = q -> next;
        if (q -> n == m)
        {
            p -> next = q -> next;
            q -> next = p;
            n++;
            break;
        }
    }
    return n;
}

int linklistdelete(int n,int num,linklist *head)//删除数据为num的元素
{
    linklist *q = head,*p;
    for (int i = 0;i < n;i++)
    {
        q = q -> next;
        if (q -> next -> n == num)
        {
            p = q -> next;
            q -> next = q -> next -> next;
            free(p);//将删除点的内存的释放
            n--;
            break;
        }
    }
    return n;
}

通过上方的代码，我们很明显可以看出，在链表中删除/添加元素更为简便，相比之下，数组只能通过移位的方式来完成操作。

同时，数组的空间分配是固定，分配完之后无法再添加，如果有空间未被使用则会造成空间上的浪费。而链表则更为灵活，可以动态分配所需的空间。

最后再通过一个简单的例题来熟练一下链表吧

有n个学生的信息(包括学号、姓名、成绩)，要求按照成绩的高低顺序输出各学生的信息。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

typedef struct student

{

    char code[20];

    char name[20];

    int grade;

}student;

typedef struct node

{

    student sum;

    struct node *next;

}node;



node *listcreate(int n);//创建链表



void printflist(node *head,int n);//输出排序后的链表



void bubblesort(node *head);//冒泡排序排列链表



int main()

{

    int n;

    printf("请输入学生的数量；\n");

    scanf("%d",&n);

    node *l = listcreate(n);

    bubblesort(l);

    printflist(l,n);

}



node *listcreate(int n)

{

    node *head,*end,*p;

    head = malloc(sizeof(node));

    head -> next = NULL;

    end = head;

    printf("请分别输入%d位学生的学号,姓名，成绩\n",n);

    for (int i = 0;i < n;i++)

    {

        p = malloc(sizeof(node));

        scanf("%s %s %d",&p -> sum.code,&p -> sum.name,&p -> sum.grade);

        end -> next = p;

        end = p;

    }

    end -> next = NULL;

    return head;

}

void printflist(node *head,int n)

{

    node *p = head -> next;

    printf("将成绩由高到低排名后，结果如下：\n");

    for (int i = 0;i < n;i++)

    {

        printf("%s %s %d\n",p -> sum.code,p -> sum.name,p -> sum.grade);

        p = p -> next;

    }

}

void bubblesort(node *head)

{

    student t;

    for (node *turn = head -> next;turn -> next != NULL;turn = turn -> next)

    {

        for (node *move = head -> next;move -> next != NULL;move = move -> next)

        {

            if (move -> sum.grade < move -> next -> sum.grade)

            {

                t = move -> sum;

                move -> sum = move -> next -> sum;

                move -> next -> sum = t;

            }

        }

    }

}