数据结构与算法概述及链表的相关知识回顾

原 作者 祝一迪 | 发表于 | 分类于 2015级

数据结构及其概念

  • 数据:客观事物的符号表示
  • 数据元素:数据的基本单位
  • 数据对象:性质相同的数据元素的集合
  • 数据结构:是指相互之间具有一定里埃的数据元素的集合. 元素之间的相互关系称为逻辑结构

数据的逻辑结构

算法及其概念

算法:解决问题的步骤的描述, 在计算机中表现为指令的有限序列

算法的特性:

  • I/O:算法有0个或者多个输入, 至少有一个输出
  • 有穷性:无死循环, 能在可以接受的时间内完成
  • 确定性:算法的每一步骤都有确定的含义, 不会出现二义性
  • 可行性:算法的每一步都必须是可行的

线性表

线性表主要分为一般线性表, 串, 受限线性表(如栈, 队列等), 广义表等.

  • 一般线性表是最基础, 最常用, 最简单的一种数据结构, 其主要的作用就是存储数据
  • 按照物理结构可以划分为连续式和非连续式

链表

链表:是一种物理存储单元上非连续, 非顺序的存储结构. 数据元素的逻辑顺序是通过链表中的指针链接次序实现的. 链表由一系列节点组成, 每个节点包括两个部分:数据域和指针域.

链表的基本操作:

  • 链表的创建
  • 链表的插入
  • 链表的删除
  • 链表的逆置
  • 链表的排序

下来就用一个例子来实现一下链表的创建, 逆置及其排序吧

#include<stdio.h>
#include<malloc.h>

typedef struct NODE
{
    int data;
    struct NODE *next;
}NODE;

NODE *createList();
void showList(NODE *head);
NODE *reverseList(NODE *head);
void sortList(NODE *head);

void sortList(NODE *head)
{
    NODE tmp; 
    NODE *pi;
    NODE *pj;
    NODE *ptmp;
    NODE *phead;

    //phead.next = head;

    for(pi = head; pi; pi = pi->next)
    {
        for(pj = pi->next; pj; pj = pj->next)
        {
            if(pi->data > pj->data)
            {
                tmp = *pi;
                *pi = *pj;
                *pj = tmp;

                ptmp = pi->next;
                pi->next = pj->next;
                pj->next = ptmp;
            }
        }
    }
}

NODE *reverseList(NODE *head)
{
    NODE *pre = NULL;
    NODE *cur = head;
    NODE *nxt = NULL;

    if(head == NULL && head->next == NULL)
    {
        return head;
    }

    while(cur)
    {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }

    return pre;
}

void showList(NODE *head)
{
    NODE *p;

    for(p = head; p; p = p->next)
    {
        printf("%d\n", p->data);
    }
    printf("\n");
}

NODE *createList()
{
    NODE * head;
    NODE *cur;
    NODE *pre;
    int number = 5;
    int n = 1;

    if(!number)
    {
        return NULL;
    }

    head = (NODE *)malloc(sizeof(NODE));
    scanf("%d", &head->data);
    head->next = NULL;

    pre = head;
    cur = NULL;

    while(n++ < 5)
    {
        cur = (NODE *)malloc(sizeof(NODE));
        scanf("%d", &cur->data);
        cur->next = NULL;
        pre->next = cur;
        pre = cur;
    }

    return head;
}

int main(int argc,char *argv[])
{
    NODE *head = createList();
    printf("\n");
    head = reverseList(head);
    showList(head);
    sortList(head);
    showList(head);
}

运行结果如下:

[dela@server1 dela_c]$ ./a.out
1
2
5
3
4

4
3
5
2
1

1
2
3
4
5

程序说明:

创建链表就是一个很常规的过程, 这里重点说一下链表的逆置和排序.

  • 链表的逆置:
    1.先把当前节点的下一个节点保存起来, 以防链断掉(即:nxt = cur->next;)
    2.再把当前节点的指针域改为指向前一个节点(即:cur->next = pre;)
    3.再把指针向后移, 处理下一个节点(即:pre = cur; cur = nxt;)

  • 链表的排序:
    链表的排序我没有按照杜仑学长的方法, 而是另外一种办法

    1. 按照选择排序法或冒泡排序法判断数据域的大小, 若需要交换时, 将整个节点都交换过来
    2. 把整个节点都交换之后会造成指针域的混乱, 所以再把指针域交换回来, 这样就完成了链表的排序.

    是不是很简单!