线性表的定义

• 由零个或多个数据元素组成的有限序列

• 若元素存在多个,则第一个元素无前驱,而最后一个元素无后继,其他元素都有且只有一个前驱和后继

抽象数据类型(Abstract Data Type,ADT)

• 数据类型:一组性质相同的值得集合及定义在此集合上的一些操作的总称

• 抽象:抽取出事物具有的普遍性的本质.它要求抽出问题的特征而忽略非本质的细节,是对具体事务的一个概括.抽象是一种思考问题的方式,它隐藏了繁杂的细节

• 抽象数据类型:是指一个数据模型以及定义在该模型上的一组操作

线性表的抽象数据类型

• Data:线性表的数据对象集合为{a1,a2,...an},每个元素的类型均为DataType.其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素.数据元素之间的关系是一对一的关系

• Operation:

  • InitList(*L):初始化操作,建立一个空的线性表L

  • ListEmpty(L):判断线性表是否为空表,若线性表为空,返回true,否则返回false

  • ClearList(*L):将线性表清空

  • GetElement(L,i,*e):将线性表L中的第i个元素位置返回给e

  • LocateElement(L,e):在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败

  • ListInsert(*L,i,e):在线性表L中第i个位置插入新的元素e

  • ListDelete(L,i,e):删除线性表L中第i个位置元素,并用e返回其值

  • ListLength(L):返回线性表L的元素个数

线性表的顺序存储

• 顺序存储的结构代码:

#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    //线性表当前长度
    int length;
}SQList;

• 获得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

Status GetElem(SQList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
    {
        return ERROR;
    }
    *e = L.data[i-1];

    return OK;
}

• 插入操作

Status ListInsert(SQList *L, int i,ElemType e)
{
    int k;

    //线性表已将满了
    if(L->length == MAXSIZE)
    {
        return ERROR;
    }
    //不在范围内
    if(i < 1 || i>L->length + 1)
    {
        return ERROR;
    }
    if(i <= L->length)
    {
        //将要插入位置后数据元素相互移动一位
        for(k=L->length-1; k>=i-1; k--)
        {
            L->data[k+1] = L->data[k];
        }
    }
    //插入新元素
    L->data[i-1] = e;
    L->length++;

    return OK;
}

• 删除操作

Status ListDelete(SQList *L,int i,ElemType *e)
{
    int k;

    if(L->length ==0)
    {
        return ERROR;
    }
    if(i<1 || i>L->length)
    {
        return ERROR;
    }

    *e = L->data[i-1];

    if(i< L->length)
    {
        for(k=i; k<L->length; k++)
        {
            L->data[k-1] = L->data[k];
        }
    }

    L->length--;

    return OK;
}

线性表顺序存储的优缺点

• 优点

  • 无需为表中元素之间的逻辑关系而增加额外的存储空间

  • 可以快速地存取表中任意位置的元素

• 缺点

  • 插入和删除操作需要移动大量元素

  • 当线性表长度变化较大时,难以确定存储空间的容量

  • 容易造成存储空间的"碎片"

线性表链式存储结构定义

• 线性表链式存储的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以存储在内存中未被占用的任意位置

• 比起顺序存储结构每个元素只需要存储一个位置就可以了.现在链式存储结构中,处理要存储数据元素信息外,还要存储它的后继元素的存储地址(指针)

• 我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域.指针域中存储的信息称为指针或链.这两部分信息组成的数据元素称为存储映像,称为结点(Node)

• n个节点链接成一个链表,即为线性表的链式存储结构

单链表

• 因为此链表的每个节点中只包含一个指针域,所以叫做单链表

• 我们把链表中的第一个节点的存储位置叫做头指针,最后一个节点指针为空(NULL)

• 头指针

  • 头指针是指链表指向第一个节点的指针,若链表有头结点,则是指向头结点的指针

  • 头指针具有标志作业,所以常用头指针冠以链表的名字

  • 无论链表是否为空,头指针均不为空

• 头结点

  • 头结点是为了操作的同一和方便而设立的,放在第一个元素结点之前,其数据域一般无意义(也可以用来存放链表的长度)

  • 由来头结点,对在第一个元素结点前插入结点和删除第一个节点的操作与其他结点的操作就统一了

  • 头结点不是链表必须元素

• 单链表存储结构

typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node* next;
}Node;

typedef struct Node* LinkList;

• 假设p是指向线性表第i个元素的指针,则该节点ai的数据域我们可以用p->data的值是一个数据元素,结点ai的指针域可以用p->next来表示,p->next的值是一个指针

• 获取元素操作

Status GetElem(LinkList L,int i,ElemType *e)
{
    //当前位置
    int j;
    LinkList p;

    p = L->next;
    j = 1;

    while(p && j>i)
    {
        p = p->next;
        ++j;
    }

    if(!p || j>i)
    {
        return ERROR;
    }

    *e = p->data;

    return OK;
}

• 插入元素操作

Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,s;

    p = *L;
    j = 1;

    while(p && j < i)
    {
        p = p->next;
        ++j;
    }

    if(!p || j>i)
    {
        return ERROR;
    }

    s = (LinkList)malloc(sizeof(Node));
    s->data = e;

    s->next = p->next;
    p->next = s;

    return OK;

}

• 删除操作

Status ListDelete(LinkList *L,int i,ElemType *e)
{
    int j;
    LinkList p,q;

    p = *L;
    j = 1;

    while(p && j < i)
    {
        p = p->next;
        ++j;
    }

    if(!p || j>i)
    {
        return ERROR;
    }

    q = p->next;
    p->next = q->next;

    *e = q->data;
    free(q);

    return OK;
}

头插发简历单链表

• 头插法从一个空表开始,生成新节点,读取数据存放到新节点的数据域中,然后将新节点插入到当前链表的表头上,知道结束为止

• 简单来说就是把新加进来的元素放到表头后的第一个位置

void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int i;

    //初始化随机数种子
    srand(time(0));

    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;

    for(i = 0;i < n; i++)
    {
        //生成新节点
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100+1;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

尾插法建立单链表

• 头插法建立链表虽然算法简单,但生成的链表中节点的顺序和输入的顺序相反

void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int i;

    //初始化随机数种子
    srand(time(0));

    *L = (LinkList)malloc(sizeof(Node));
    r = *L;

    for(i = 0;i < n; i++)
    {
        //生成新节点
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        //r指向p,重点
        r = p;
    }

    r->next = NULL;
}

• 单链表的整表删除

Status ClearList(LinkList *L)
{
    LinkList p,q;

    p = (*L)->next;

    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

单链表结构与顺序存储结构优缺点

• 我们分别从存储分配方式,时间性能,空间性能三方面来做对比

• 存储分配方式

  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素

  • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素

• 时间性能

  • 查找

    • 顺序存储结构O(1)

    • 单链表O(n)

  • 插入和删除

    • 顺序存储结构需要平均移动表长一般的元素,时间为O(n)

    • 单链表在计算出某位置的指针后,插入和删除时间仅为O(1)

• 空间性能

  • 顺序存储结构需要预分配存储空间,分大了,容易造成空间浪费,分小了,容易发生溢出

  • 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制

• 结论

  • 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构

  • 若需要频繁插入和删除操作时,宜采用单链表结构

静态链表

头指向第一个没有数据的地方,尾指向第一个有数据的地方

• 线性表的静态链表存储结构

#define MAXSIZE 1000
typedef struct
{
    //数据
    ElemType data;
    //游标
    int cur;
}Component,StaticLinkList[MAXSIZE];

• 对静态链表进行初始化(相当于初始化数组)

Status InitList(StaticLinkList space)
{
    int i;
    for(i=0;i<MAXSIZE-1;i++)
    {
        space[i].cur = i+1;
    }
    space[MAXSIZE-1].cur = 0;

    return OK;
}

• 数组的第一个元素,即下标为0的那个元素的cur就存放在没有存数据的第一个节点的下标

• 数组的最后一个元素,即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标,相当于单链表中的头结点的作用

• 最后一个可用元素的游标为0

• 静态链表的插入操作

  • 为了辨明数组中哪些分量未被使用,解决的办法是将所有未被使用过的及已被删除的用游标链成一个备用链表

• 获取空闲分量的下标

int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;
    if(space[0].cur)
        space[0].cur = space[i].cur;
    return i;
}

• 插入操作

Status ListInsert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE - 1;
    if(i<1 || i>ListLength(L)+1)
    {
        return ERROR;
    }
    j = Malloc_SLL(L);
    if(j)
    {
        L[j].data = e;
        for(l=1;l<=i-1;l++)
        {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

• 删除操作

Status ListDelete(StaticLinkList L,int i)
{
    int j,k;

    if(i<1 || i>ListLength(L))
    {
        return ERROR;
    }

    k = MAX_SIZE - 1;

    for(j=1;j<=i-1;j++)
    {
        k = L[k].cur;
    }

    j = L[k].cur;
    L[k].cur = L[j].cur;

    Free_SLL(L,j);
    return OK;
}

//将下标为k的空间回收到备用链表
void Free_SLL(StaticLinkList space,int k)
{
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;

    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

• 静态链表优缺点

  • 优点

    • 在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

  • 缺点

    • 没有解决连续存储分配带来的表长难以确定的问题

    • 失去了顺序存储结构随机存取的特性

单链表小结:腾讯面试题

• 题目:快速找到未知长度单链表的中间节点

• 普通方法很简单,首先遍历一遍单链表以确定单链表的长度L.然后再次从头结点出发循环L/2次找到单链表的中间节点,算法复杂度为:O(L+L/2)=O(3L/2)

• 利用快慢指针原理:设置两个指针*search,*mid都指向单链表的头节点.其中*search的移动速度是*mid的2倍.当*search指向末尾节点的时候,mid正好就在中间了.这也是标尺的思想,时间复杂度为O(L/2)

Status GetMidNode(LinkList L,ElemType *e)
{
    LinkList search,mid;
    mid = search = L;

    while(search->next!=NULL)
    {
        if(search->next->next!=NULL)
        {
            search = search->next->next;
            mid = mid->next;
        }
        else
        {
            search = search->next;
        }
    }
    *e = mid->data;
    return OK;
}

循环链表

循环链表不一定要有头结点

• 其实循环链表的单链表的主要差异就在于循环的判断空链表的条件上,原来判断head->next是否为null,现在则是head->next是否等于head

• 链表存储结构的定义

typedef struct CLinkList
{
    int data;
    struct CLinkList *next;
}node;

• 初始化部分

void ds_init(node **pNode)
{
    int item;
    node *temp;
    node *target;

    printf("输入节点的值,输入0完成初始化\n");

    while(1)
    {
        scanf("%d",&item);
        fflush(stdin);

        if(item == 0)
            return;

        //循环链表只有一个节点
        if((*pNode) == NULL)
        {
            *pNode = (node*)malloc(sizeof(struct CLinkList));
            if(!(*pNode))
                exit(0);
            (*pNode)->data = item;
            (*pNode)->next = *pNode;
        }
        else
        {
            /*找到next指向第一个节点的节点*/
            for(target = (*pNode);target->next !=
            (*pNode);target=target->next);
            //生成一个新节点
            temp = (node *)malloc(sizeof(struct CLinkList));

            if(!temp)
                exit(0);
            temp->data = item;
            temp->next = *pNode;
            target->next = temp;
        }
    }
}

• 插入部分

void ds_insert(node **pNode,int i)
{
    node *temp;
    node *target;
    node *p;
    int item;
    int j=1;

    printf("输入要插入节点的值:");
    scanf("%d",&item);

    if(i==1)
    {
        //新插入节点作为第一个节点
        temp = (node*)malloc(sizeof(struct CLinkList));

        if(!temp)
            exit(0);

        temp->data = item;

        //寻找最后一个节点
        for(target = (*pNode);target->next!=(*pNode);target=target->next);

        temp->next = (*pNode);
        target->next = temp;
        *pNode = temp;
    }
    else
    {
        target = *pNode;

        for(;j<(i-1);j++)
        {
            target = target->next;
        }

        temp = (node*)malloc(sizeof(struct CLinkList));

        if(!temp)
            exit(0);

        temp->data = item;
        p = target->next;
        target->next = temp;
        temp->next = p;
    }
}

• 删除部分

void ds_delete(node **pNode,int i)
{
    node *target;
    node *temp;
    int j = 1;

    if(i==1)
    {
        for(target = (*pNode);target->next!=(*pNode);target=target->next);
        temp = *pNode;
        *pNode = (*pNode)->next;
        target->next = *pNode;
        free(temp);
    }
    else
    {
        target = *pNode;
        for(;j<i-1;j++)
        {
            target = target->next;
        }

        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
}

• 返回节点所在位置

int ds_search(node *pNode,int elem)
{
    node *target;
    int i = 1;

    for(target = pNode;target->data!=elem&&target->next!=pNode;i++)
    {
        target = target->next;
    }

    if(target->next==pNode)
        return 0;
    else
        return 1;
}

约瑟夫问题

• 据说注明犹太历史学家Josephus有过以下故事:在罗马人占领桥塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被抓到,于是决定了一个自杀的方式,41个人排成一圈,由第1个人开始报数,没报到第3人该人就必须自杀,然后再由下一个重新报数,知道所有人都自杀身亡为止.然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏

• 代码

#include <stdio.h>
#include <stdlib.h>

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

node *create(int n)
{
    node *p = NULL,*head;
    head = (node*)malloc(sizeof(node));
    p = head;
    node *s;
    int i=1;

    if(0!=n)
    {
        while(i<=n)
        {
            s = (node*)malloc(sizeof(node));
            s->data = i++;
            p->next = s;
            p = s;
        }
        s->next = head->next;
    }
    free(head);
    return s->next;
}

int main()
{
    int n = 41;
    int m = 3;
    int i;
    node *p = create(n);
    node *temp;

    m%=n;

    while(p!=p->next)
    {
        for(i=1;i<m-1;i++)
        {
            p = p->next;
        }
        printf("%d->",p->next->data);
        temp = p->next;
        p->next = temp->next;

        free(temp);

        p = p->next;
    }
    printf("%d\n",p->data);
    return 0;
}

提高难度

• 变化为1-N的N个人按顺时针方向围坐一圈,没人持有一个秘密(正整数,可以自由输入),开始人选一个正整数作为上报数上限值M,从第一个人按顺时针方向自1开始顺序报数,报到M时停止报数.报M的人出列,将他的密码作为新的M值,从他顺时针方向上的下一个人开始从1报数,如此下去,直至所有人全部出列为止

将两个带尾指针的循环链表合并

//两个参数为非空链表尾指针
LinkList Connect(LinkList A,LinkList B)
{
    //保存A表的头结点位置
    LinkList p = A->next;
    //B表的开始结点连接到A表尾
    A->next = B->next->next;
    //释放B表的头结点,初学容易忘记
    free(B->next);

    B->next=P;
    //返回新增循环链表的尾指针
    return B;
}

判断单链表中是否有环

• 方法一:使用p,q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样.如图,当p从6走到3时,用了6部,此时若q从head出发,则只需两步就到3,因而步数不等,出现矛盾,存在环

int HasLoop1(LinkList L)
{
    LinkList cur1 = L;
    int pos1 = 0;

    while(cur1)
    {
        LinkList cur2 = L;
        int pos2 = 0;
        while(cur2)
        {
            if(cur2==cur1)
            {
                if(pos1 == pos2)
                    break;
                else{
                    printf("环的位置在第%d个结点处.\n\n,pos2");
                    return 1;
                }
            }

            cur2 = cur2->next;
            pos2++;
        }
        cur1 = cur1->next;
        pos1++;
    }
    return 0;
}

• 方法二:使用p,q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p==q,则存在环

int HasLoop2(LinkList L)
{
    int step1 = 1;
    int step2 = 2;
    LinkList p = L;
    LinkList q = L;

    while(p!=NULL && q!= NULL && q->next!= NULL)
    {
        p = p->next;
        if(q->next!=NULL)
            q = q->next->next;
        printf("p:%d,q:%d \n",p->data,q->data);

        if(p==q)
            return 1;
    }
    return 0;
}

魔术师发牌问题

• 问题描述:魔术师利用一副牌中的13张黑牌,预先将它们排好后叠到一起,牌面朝下.对观众说:"我不看牌,只数数就可以猜到每张牌是什么,我大声数数,你们听,不信?现场演示"魔术师将最上面的那张牌数为1,把它反过来正好是黑桃A,将黑桃A放在桌子上,第二次数1,2,强![第一张牌放在这些牌的下面,将第二张牌翻过了,正好是黑桃2,也将它放在桌子上这样依次进行将13张牌全部翻出,准确无误

#include <stdio.h>
#include <stdlib.h>

#define CardNumber 13

typedef struct node
{
    int data;
    struct node *next;
}sqlist,*linklist;

linklist CreateLinkList()
{
    linklist head = NULL;
    linklist s,r;
    int i;

    r = head;

    for(i=1;i<=CardNumber;i++)
    {
        s = (linklist)malloc(sizeof(sqlist));
        s->data = 0;

        if(head == NULL)
            head = s;
        else
            r->next = s;

        r = s;
    }

    r->next = head;

    return head;
}
//发牌顺序计算
void Magician(linklist head)
{
    linklist p;
    int j;
    int Countnumber = 2;

    p = head;
    p->data = 1;

    while(1)
    {
        for(j=0;j<Countnumber;j++)
        {
            p = p->next;
            if(p->data!=0)
            {
                //p->next;
                j--;
            }
        }
        if(p->data == 0)
        {
            p->data = Countnumber;
            Countnumber ++;

            if(Countnumber == 14)
                break;
        }
    }
}

void DestoryList(linklist *list)
{
    linklist ptr = *list;
    linklist buff[CardNumber];
    int i = 0;

    while(i<CardNumber)
    {
        buff[i++] = ptr;
        ptr = ptr->next;
    }
    for(i=0;i<CardNumber;i++){
        free(buff[i]);

        *list = 0;
    }
}

int main()
{
    linklist p;
    int i;

    p=CreateLinkList();
    Magician(p);

    printf("按如下顺序排列:\n");
    for(i=0;i<CardNumber;i++)
    {
        printf("黑桃%d ",p->data);
        p = p->next;
    }
    DestoryList(&p);

    return 0;
}

拉丁方阵问题

• 拉丁方阵是一种n×n的方阵,方阵中恰有n种不同的元素,每种元素恰有n个,并且每种元素在一行和一列恰好出现一次.著名数学家和物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的符号,拉丁方阵因此而得名

双向链表

• 双向链表结点结构

typedef struct DualNode
{
    ElemType data;
    //前驱结点
    struct DualNode *prior;
    //后继结点
    struct DualNode *next;
}DualNode,*DuLinkList;

• 插入操作

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s

• 删除操作

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

双向循环链表实践

• 要求用户输入一个数使得26个字母的排列发生变化,例如用户输入3,输出结果:

• DEFGHIJKLMNOPQRSTUVWXYZABC

• 同时需要支持负数,例如用户输入-3,输出结果:

• XYZABCDEFGHIJKLMNOPQRSTUVW

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;

typedef struct DualNode
{
    ElemType data;
    struct DualNode *prior;
    struct DualNode *next;
}DualNode,*DuLinkList;

Status InitList(DuLinkList *L)
{
    DualNode *p,*q;
    int i;

    *L = (DuLinkList)malloc(sizeof(DualNode));
    if(!(*L))
    {
        return ERROR;
    }

    (*L)->next = (*L)->prior = NULL;
    p = (*L);
    for(i=0;i<26;i++)
    {
        q = (DualNode *)malloc(sizeof(DualNode));
        if(!q)
        {
            return ERROR;
        }

        q->data = 'A'+i;

        q->prior = p;
        //为了程序灵活?
        q->next = p->next;
        p->next = q;
        p = q;
    }
    p->next = (*L)->next;
    (*L)->next->prior = p;
    return OK;
}

void Caesar(DuLinkList *L,int i)
{
    if(i>0)
    {
        do
        {
            (*L) = (*L)->next;
        }while(--i);
    }

    if(i<0)
    {
        do
        {
            (*L) = (*L)->next;
        }while(++i);
    }
}

int main()
{
    DuLinkList L;
    int i,n;
    scanf("%d",&n);
    InitList(&L);
    Caesar(&L,n);
    for(i=0;i<26;i++)
    {
        L = L->next;
        printf("%c ",L->data);
    }
    printf("\n");
    return 0;
}

维吉尼亚(Vigenere)加密

• 当输入明文,自动生成随机密匙匹配明文中每个字母并移位加密

• 随机密匙不能丢掉,丢掉了就很难把明文还原了,建议把随机密匙和密文存储到一起