数据结构与算法小结1_常用的数据结构(线性表)

0.

这里会介绍线性表，数组，背包，队列和栈。
会根据内容的多少将这些数据结构分开进行介绍。
关于数，图以及字符串的内容会在后面的算法里介绍。

1.

先说一下我对这些基本的数据结构的认识，因为我并没有什么实践经验，而且也没怎么真正用过这些数据结构，所以可能只是自己的一家之谈。我认为这些数据结构重要的是其所包含的思想（当然不懂实现，就真的是纸上谈兵了）。队列是一种先进先出的数据结构，栈是一种先进后出的数据结构。我们说栈和队列的时候，说的是先进先出和先进后出这种思想而不是说其具体实现。
这些基本思想简单的几句话就说完了，在这个博客里，重点介绍的还是这些数据结构以及其操作的实现。

2.线性表

线性表是0个或多个数据元素的有限序列。序列说明了各个数据元素之间是有顺序关系的。

在这里说一下线性表的基本操作有哪些？
InitList(*L)； //初始化操作，建立一个空的线性表L
ClearList(*L); //将线性表L清空
GetElem(L,i,*e); //将线性表L的第i个位置元素值返回给e
ListInsert(*L,i,e); //在线性表L的第i个位置插入新元素e
ListDelete(*L,i,*e);//删除线性表L中的第i个位置元素，并用e返回其值
ListLength(L); //返回线性表的元素个数
线性表还有很多操作，这里就只介绍这几种

线性表有两种实现方式：顺序表示 以及 链式表示。
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。一般都是通过数组去实现线性表的顺序表示。
线性表的链式表示就是我们通常所说的链表了。

3.线性表的顺序表示

这里可以通过动态数组或者静态数组实现。
静态数组版本：

#include<stdio.h>
#define MAXSIZE 20      //线性表的初始大小
typedef int ElemType;   //线性表中的元素类型

typedef struct
{
    ElemType data[MAXSIZE];
    int length;
}SqList;                //通过静态数组定义线性表结构体

void InitList(SqList *L)
//初始化操作，建立一个空的线性表L 
{
    L->length=0;
    return;
}

void GetElem(SqList L, int i, ElemType *e)      
//将线性表L的第i个位置元素值返回给e 
{
    if ( (L.length==0)||(i<1)||(i>L.length) )
    {
        printf("出错\n");
        return;
    }
    *e=L.data[i-1];
    return;
}
void ListInsert(SqList *L,int i,ElemType e)
//在线性表L的第i个位置插入新元素e 
{
    if(L->length==MAXSIZE)
    {
        printf("线性表已满\n");
        return;
    }
    if(i<1||i>L->length+1)
    {
        printf("插入位置出错\n");
        return;
    }
    for(int k=L->length;k>=i;k--)
    {
        L->data[k]=L->data[k-1];
    }
    L->data[i-1]=e;
    L->length++;
    return;
}

void ListDelete(SqList *L,int i,ElemType *e)
//删除线性表L中的第i个位置元素，并用e返回其值 
{
    if(L->length==0)
    {
        printf("线性表为空\n");
        return;
    }
    if(i<1||i>L->length)
    {
        printf("位置出错\n");
        return;
    }
    *e=L->data[i-1];
    for(int k=i;k<L->length;k++)
    {
        L->data[k-1]=L->data[k];
    }
    L->length--;
    return;
}
int ListLength(SqList L)
//返回线性表的元素个数 
{
    return L.length;
}
void show(SqList L)
{
    for(int i=0;i<L.length;i++)
        printf("%d   ",L.data[i]);
    printf("\n");
    printf("%d\n",L.length);
}
void main()
//测试
{
    SqList L;
    InitList(&L);
    ListInsert(&L,1,555);
    show(L);
    ListInsert(&L,1,666);
    show(L);
    ListInsert(&L,2,777);
    show(L);
    ElemType e;
    ListDelete(&L,2,&e);
    show(L);
    ListInsert(&L,2,888);
    show(L);
    ListDelete(&L,3,&e);
    show(L);
    ListDelete(&L,3,&e);
    show(L);
}

动态数组版本：(只有结构体的定义和线性表的初始化上和上面的有所不同)

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20      //线性表的初始大小
typedef int ElemType;   //线性表中的元素类型

typedef struct
{
    ElemType *data;
    int length;
}SqList;                //通过动态数组定义线性表结构体

void InitList(SqList *L)
//初始化操作，建立一个空的线性表L 
{
    L->data=(ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    if(!L->data)
        exit(-1);       //内存分配失败
    L->length=0;
    return;
}
void GetElem(SqList L, int i, ElemType *e)      
//将线性表L的第i个位置元素值返回给e 
{
    if ( (L.length==0)||(i<1)||(i>L.length) )
    {
        printf("出错\n");
        return;
    }
    *e=L.data[i-1];
    return;
}
void ListInsert(SqList *L,int i,ElemType e)
//在线性表L的第i个位置插入新元素e 
{
    if(L->length==MAXSIZE)
    {
        printf("线性表已满\n");   //这里可以通过realloc函数扩展线性表的大小，略
        return;
    }
    if(i<1||i>L->length+1)
    {
        printf("插入位置出错\n");
        return;
    }
    for(int k=L->length;k>=i;k--)
    {
        L->data[k]=L->data[k-1];
    }
    L->data[i-1]=e;
    L->length++;
    return;
}

void ListDelete(SqList *L,int i,ElemType *e)
//删除线性表L中的第i个位置元素，并用e返回其值 
{
    if(L->length==0)
    {
        printf("线性表为空\n");
        return;
    }
    if(i<1||i>L->length)
    {
        printf("位置出错\n");
        return;
    }
    *e=L->data[i-1];
    for(int k=i;k<L->length;k++)
    {
        L->data[k-1]=L->data[k];
    }
    L->length--;
    return;
}
int ListLength(SqList L)
//返回线性表的元素个数 
{
    return L.length;
}
void show(SqList L)
{
    for(int i=0;i<L.length;i++)
        printf("%d   ",L.data[i]);
    printf("\n");
    printf("%d\n",L.length);
}
void main()
//测试
{
    SqList L;
    InitList(&L);
    ListInsert(&L,1,555);
    show(L);
    ListInsert(&L,1,666);
    show(L);
    ListInsert(&L,2,777);
    show(L);
    ElemType e;
    ListDelete(&L,2,&e);
    show(L);
    ListInsert(&L,2,888);
    show(L);
    ListDelete(&L,3,&e);
    show(L);
    ListDelete(&L,3,&e);
    show(L);
}

通过数组实现线性表有一个特别明显的缺点：插入和删除操作需要移动大量的元素。
这就使得这种实现显得特别笨重，不够灵活。

4.线性表的链式表示

线性表的链式表示：不要求元素一定要存放在连续的内存中，这就使得这种表示比上面的顺序表示灵活的多。

单链表(线性链表)
明确两个概念的区别：头指针和头结点
头指针：指向链表第一个结点的指针。
头结点：为了操作的统一和方便，在第一个元素的结点之前再加入一个结点，这个结点的数据域一般是没有意义的。头结点对链表来说不是必须的。

不对链表做过多的介绍，百度随便一搜一大堆。直接贴代码。

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20      //线性表的初始大小
typedef int ElemType;   //线性表中的元素类型

typedef struct Node
{
    ElemType data;
    Node * next;
}Node;              //定义单链表的结点结构体
typedef Node* LinkList;

void CreateList1(LinkList *L,int n)
//创建一个带头结点的单链表 ，前插
{
    *L=(LinkList)malloc(sizeof(Node));
    (*L)->next=NULL;
    for (int i=n;i>0;i--)
    {
        LinkList p=(LinkList)malloc(sizeof(Node));
        scanf("%d",&p->data);
        p->next=(*L)->next;
        (*L)->next=p;

    }
}

void CreateList2(LinkList *L,int n)
//创建一个带头结点的单链表 ，后插
{
    *L=(LinkList)malloc(sizeof(Node));
    (*L)->next=NULL;
    LinkList r=*L;
    for (int i=n;i>0;i--)
    {
        LinkList p=(LinkList)malloc(sizeof(Node));
        scanf("%d",&p->data);
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

void GetElem(LinkList L, int i, ElemType *e)        
//将线性表L的第i个位置元素值返回给e 
{
    LinkList p=L->next;
    int j=1;
    while(p&&(j<i))
    {
        p=p->next;
        j++;
    }
    if(!p||(j>i))       //p为空或者i<1
    {
        printf("出错\n");
        return;
    }
    *e=p->data;
    return; 
}
void ListInsert(LinkList *L,int i,ElemType e)
//在线性表L的第i个位置插入新元素e 
{
    LinkList p=*L;
    int j=1;
    while(p&&(j<i))
    {
        p=p->next;
        j++;
    }
    if(!p||(j>i))       //p为空或者i<1
    {
        printf("出错\n");
        return;
    }
    //和GetElem()函数有所不同，这里p指向插入位置的前一个结点
    LinkList s=(LinkList)malloc(sizeof(Node));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return;
}
void ListDelete(LinkList *L,int i,ElemType *e)
//删除线性表L中的第i个位置元素，并用e返回其值 
{
    LinkList p=*L;
    int j=1;
    while(p&&(j<i))
    {
        p=p->next;
        j++;
    }
    if(!p||(j>i))       //p为空或者i<1
    {
        printf("出错\n");
        return;
    }
    //和GetElem()函数有所不同，这里p指向删除位置的前一个结点

    LinkList s=p->next;
    *e=s->data;
    p->next=s->next;
    free(s);
    return;
}
int ListLength(LinkList L)
//返回线性表的元素个数 
{
    LinkList p=L->next;
    int j=1;
    while(p)
    {
        p=p->next;
        j++;
    }
    return j-1;
}
void show(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        printf("%d  ",p->data);
        p=p->next;
    }
    printf("\n");
}
void ClearList(LinkList *L)
//删除线性表
{
    LinkList p,q;
    p = (*L)->next;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
    free(*L);
    return;
}
void main()
//测试
{
    LinkList L;
    CreateList2(&L,3);
    printf("%d\n",ListLength(L));
    ListInsert(&L,2,777);
    show(L);
    ElemType e;
    ListDelete(&L,2,&e);
    show(L);
    ListInsert(&L,2,888);
    show(L);
    ListDelete(&L,3,&e);
    show(L);
    ListDelete(&L,3,&e);
    show(L);
    GetElem(L,1,&e);
    printf("%d\n",e);
    printf("%d\n",ListLength(L));
    ClearList(&L);
    CreateList1(&L,3);
    show(L);
}

5.链表的扩展

静态链表

(这里对静态链表的描述不是很清楚，可以去找本书仔细看下静态链表，这种用数组描述链表的思想感觉还是挺有用的)
我们把用数组描述的链表就做静态链表。
C语言可以通过指针很容易的实现上面所说的链表。当某个语言没有指针的时候，就要想办法通过别的途径去实现链表。
可以先想一下，如何通过数组去描述链表？很直观的一个思路就是有两个数组，一个存数据，另一个存对应的指向，实际上的做法就和这个差不多。下面是更加正规的描述。

通过结构体数组表示静态链表(定义见代码)，这里的备用链表是：未被使用的数组元素称为备用链表。

代码如下：

#include<stdio.h>
#define MAXSIZE 4       //静态链表的初始大小
typedef int ElemType;   //静态链表中的元素类型

typedef struct
{
    ElemType data;  //存数据
    int cur;        //指向
}Component,StaticLinkList[MAXSIZE]; //声明StaticLinkList为结构体数组的类型名

int ListLength(StaticLinkList L);
void InitList(StaticLinkList space)
//初始化操作 
{
    int i;
    for(i=0;i<MAXSIZE-1;i++)
    {
        space[i].cur=i+1;
    }
    space[MAXSIZE-1].cur=0; 
    space[MAXSIZE-2].cur=0;     //注
    return;
}
int Malloc (StaticLinkList space)
//执行插入操作时，模拟malloc函数分配内存(实际上是从备用链表里选出一个位置)
{
    int i=space[0].cur;
    if(space[0].cur)
        space[0].cur=space[i].cur;
    return i;
}
void ListInsert(StaticLinkList L,int i,ElemType e)
//指定位置i，插入元素e
//这个代码是摘自《大话数据结构》，好像有点问题(没有考虑当这个静态链表满了的时候的情况)
//在InitList()函数中，将倒数第二的元素的下标置为0(space[MAXSIZE-2].cur=0)，就可以解决这个问题了
{
    int j,k,l;
    k=MAXSIZE-1;
    if (i<1||i>ListLength(L)+1)
    {
        printf("插入位置错误\n");
        return;
    }
    j=Malloc(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;
    }
    printf("出错\n");
    return;
}
void Free(StaticLinkList space,int k)
{
    space[k].cur=space[0].cur;
    space[0].cur=k;
}
void ListDelete(StaticLinkList L,int i)
//删除静态链表L中的第i个位置的元素
{
    int j,k;
    if(i<1||i>ListLength(L))
    {
        printf("插入位置错误\n");
        return;
    }
    k=MAXSIZE-1;
    for(j=1;j<=i-1;j++)
        k=L[k].cur;
    j=L[k].cur;
    L[k].cur=L[j].cur;
    Free(L,j);
    return;
}
int ListLength(StaticLinkList L)
//返回静态链表的元素个数 
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}
void show(StaticLinkList L)
{
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        printf("%d   ",L[i].data);
        i=L[i].cur;
    }
    printf("\n");
}
void main()
//测试
{
    StaticLinkList L;   //定义L是静态链表
    InitList(L);
    ListInsert(L,1,555);
    show(L);
    ListInsert(L,1,666);
    show(L);
    ListInsert(L,2,777);
    show(L);
    ListDelete(L,1);
    show(L);
    ListDelete(L,1);
    show(L);
}

循环链表

上图是不带头结点的循环链表
循环链表和单链表非常相似，就多了一个尾指向头的指针。代码上的主要差异体现在循环的判断条件上，原来是判断p->next是否为空，现在则是p->next等于头结点则循环结束。

双向链表

双向链表相比较于单链表，多了一个前驱，每个节点都有指向前一个节点的指针。

typedef struct Node
{
    ElemType data;
    struct Node *prior;    //前驱
    struct Node *next;     //后继
}Node,*LinkList;

具体的操作和单链表的操作都很类似，只是现在多了一个前驱，稍微麻烦些罢了。
这里不贴具体的代码了。只大概说一下，插入和删除的过程。

在节点a后面插入节点c
指针p指向节点b，指针s指向节点c

s->prior=p->prior;
s->next=p;
p->prior->next=s;
p->prior=s;
//先处理插入节点c的前驱后继
//这段代码的逻辑并不复杂，静下心仔细思考一下，很简单的。

上面两幅图片出自http://blog.sina.com.cn/s/blog_77795cad01011ud1.html

删除节点b，指针p指向节点b

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

6.常见的一些题目

　
这是我从百度文库搜的一套题目，还没有仔细看，着急去赶火车，回头再做修改

题目出自
http://wenku.baidu.com/link?url=ubzZhV3wsWkhStYo0wTnOvudGrhFN3RTsH5WBFz5hbwgPYz1KZSOg1NJcIqxy2dpsqWfYZANeiTVQSjM8t39DD1khW4tXk90zceX4XIRXFy

1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（ ）最节省时间
A）顺序表 B）带头结点的双循环链表
C）单链表 D）带尾结点的单循环链表
【答案】A
2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（　　）(1≤i≤n+1)。
A） O(0) B） O(1) C） O(n) D） O(n2)
【答案】C
3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ）
A） p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;
B） q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;
C） q->next=p; p->next=q; p->prior->next=q; q->next=p;
D） p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;
【答案】D
4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）
A）O(nlog2n） B） O(1） C） O(n） D） O(n2）
【答案】C
5． 在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（ ）
A）p->next==NULL B） p->next==h
C）p->next->next==h D） p->data==-1
【答案】B
6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（　　）
A）O(n) B） O(1) C）O(nlog2n) D） O(n2)
【答案】A
8．在双向链表存储结构中，删除p所指的结点时须修改指针（　　）
A）p->prior->next=p->next p->next->prior=p->prior;
B）p->prior=p->prior->prior p->prior->next=p;
C）p->next->prior=p p->next=p->next->next
D）p->next=p->prior->prior p->prior=p->next->next;
【答案】A
9．线性表采用链式存储时，其元素地址（　　）
A）必须是连续的 B）一定是不连续的
C）部分地址是连续的 D）连续与否均可
【答案】D

1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是___。
【答案】（n-1）/2
2．在单链表中设置头结点的作用是___。
【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。
3．线性表的顺序存储是通过___来反应元素之间的逻辑关系，而链式存储结构是通过___来反应元素之间的逻辑关系。
【答案】（1）数据元素的前后顺序 （2）元素中的指针
4．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用___存储结构最节省时间，相反当经常进行插入和删除操作时，则采用___存储结构最节省时间。
【答案】（1）顺序 （2）链式
5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___，在给定值为x的结点后插入一个新结点的时间复杂度为___。
【答案】（1）O(1) （2）O(n)
7. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共___个，单链表为___个。
【答案】（1）4 （2）2
8. 循环单链表的最大优点是___。
【答案】从任一结点出发都可访问到链表中每一个元素。
9．若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时，可执行下列操作：
s->next=___;
p->next=s;
t=p->data;
p->data= ___;
s->data=___;
【答案】（1）p->next （2）s->data （3） t
10．某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为___。
【答案】144
11．带头结点的双循环链表L中只有一个元素结点的条件是___。
【答案】L->next->next==L

1．取线性表的第i个元素的时间同i的大小有关（　　）
【答案】×
2．线性表的特点是每个元素都有一个前驱和一个后继（　　）
【答案】×
3． 顺序存储方式的优点是存储密度大，且插入、删除运算效率高（　　）
【答案】×
4．线性表采用链表存储时，结点的存储空间可以是不连续的（　　）
【答案】√
5．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高（　　）
【答案】√
6．顺序存储方式只能用于存储线性结构（　　）
【答案】×
【解析】线性结构、树型结构和图状结构均可用顺序存储表示。
9．顺序存储结构的主要缺点是不利于插入或删除操作（　　）
【答案】√
10．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（　　）
【答案】×