数据结构学习之线性表

2018-03-21
不知不觉3月末了啊。。。

对于考研中的数据结构需要C与C++作为基础，但又不需要太多，例如C中通过指针传址修改变量到C++中引用类型。当然两种语言都可以描述文章中用C++描述，笔者也是刚刚学习的。毕竟C描述的话比较麻烦，也更容易出错。

重新学习了数据结构的线性表和链表部分，将其代码打出来供读者复习与参考

一、几种节点的构造

#include <iostream>
#define maxSize 100

/*顺序表的结构体定义*/
typedef struct Sqlist
{
    int data[maxSize];
    
    int length;
}Sqlist;

//单链表结构体定义
typedef struct LNode
{
    int data;
    struct LNode * next;
}LNode;

//双链表结构体定义
typedef struct DLNode
{
    int data;
    struct DLNode * prior;
    struct DLNode * next;
} DLnode;

二、线性表中的操作

//扫描数组中的元素 ，若发现比当前数字小，返回所在位置
int findElem (Sqlist L, int x)
{
    int i;
    for (i = 0; i < L.length; i++)
    {
        if(x < L.data[i])
            return i;
    }
    return i;
}

// 找到相应元素，调用查找函数 并且插入值
void insertElem (Sqlist & L, int x)
//改变顺序表L，所以采用引用类型
{
    int p, i;
    p = findElem(L, x);
    
    for (i = L.length - 1; i >= p; i--)
        L.data[i+1] = L.data[i];
    
    L.data[p] = x;
    ++L.length; // 线性表的长度增加一个
}

//初始化顺序表
void  initList (Sqlist & L)
{
    L.length = 0;
}

//求指定位置元素的
int getElem(Sqlist L, int p, int & e) //把表L中p位置上的值传给e
{
    if (p < 0 || p > L.length)
        return 0;
    else
        e = L.data[p];
    return 1;
}

三、单链表中的相关操作

//尾插法建立单链表的算法
void createlistR (LNode *& C, int a[],int n)
{
    int i;
    LNode * s, *r;
    C = (LNode *)malloc(sizeof(LNode));
    r = C;
    
    for (i = 0; i < n; i++)
    {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = a[i]; //s在这里是指针 使用->取值
        r->next = s;  //s在这里是节点地址
        r = r->next;  //r指向终端节点
    }
    r = NULL;
}

//单链表中找到值为x并删除节点
int findAndDelete (LNode * C, int x)
{
    LNode *p, *q;
    p = C;
    /*查找部分开始*/
    while (p->next != NULL)
    {
        if (p->next->data == x)
            break;
        p = p->next;
    }
    if (p->next == NULL)
        return 0;
    /*查找部分结束*/
    else
    {
    /*删除部分开始*/
        q = p->next;
        p->next = p->next->next;
        free(q);
        return 1;
    /*删除部分结束*/
    }
}

void createlistF(LNode *& C, int a[], int n)
{
    int i;
    LNode *s, *r;
    C = (LNode *)malloc(sizeof(LNode));
    r = C;
    
    for (i = 0; i < n; i++)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = C->next;
        C->next = s;
    }
    
}

主函数在这儿

int main(int argc, const char * argv[])
{
    // 顺序表在考试中的常用写法
    int A[maxSize];
    int length;    
    return 0;
}

双链表只是比单链表多了一个指针
循环单链表又是在单链表的基础上发展而来
循环双链表在双链表的基础上发展而来这里就不再写了

（其实是比较懒了，希望不要被拆穿）

静态链表比较特殊考研貌似不考这个
以下代码源于《大话数据就够》，示例代码为C语言描述

#include "string.h"
#include "ctype.h"      

#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

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

#define MAXSIZE 1000 /* 存储空间初始分配量 */

typedef int Status;           /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;        /* ElemType类型根据实际情况而定，这里假设为char */


Status visit(ElemType c)
{
    printf("%c ",c);
    return OK;
}

/* 线性表的静态链表存储结构 */
typedef struct 
{
    ElemType data;
    int cur;  /* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];


/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space) 
{
    int i;
    for (i=0; i<MAXSIZE-1; i++)  
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
    return OK;
}


/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space) 
{ 
    int i = space[0].cur;                   /* 当前数组第一个元素的cur存的值 */
                                            /* 就是要返回的第一个备用空闲的下标 */
    if (space[0]. cur)         
        space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */
                                            /* 所以我们就得把它的下一个 */
                                            /* 分量用来做备用 */
    return i;
}


/*  将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k) 
{  
    space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
    space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
}

/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}

/*  在L中第i个元素之前插入新的数据元素e   */
Status ListInsert(StaticLinkList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
    if (i < 1 || i > ListLength(L) + 1)   
        return ERROR;   
    j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
    if (j)   
    {   
        L[j].data = e;   /* 将数据赋值给此分量的data */
        for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */
           k = L[k].cur;           
        L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */
        L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */
        return OK;   
    }   
    return ERROR;   
}

/*  删除在L中第i个数据元素   */
Status ListDelete(StaticLinkList L, int i)   
{ 
    int j, k;   
    if (i < 1 || i > ListLength(L))   
        return ERROR;   
    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_SSL(L, j);   
    return OK;   
} 

Status ListTraverse(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
            visit(L[i].data);
            i=L[i].cur;
            j++;
    }
    return j;
    printf("\n");
    return OK;
}


int main()
{
    StaticLinkList L;
    Status i;
    i=InitList(L);
    printf("初始化L后：L.length=%d\n",ListLength(L));

    i=ListInsert(L,1,'F');
    i=ListInsert(L,1,'E');
    i=ListInsert(L,1,'D');
    i=ListInsert(L,1,'B');
    i=ListInsert(L,1,'A');

    printf("\n在L的表头依次插入FEDBA后：\nL.data=");
    ListTraverse(L); 

    i=ListInsert(L,3,'C');
    printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
    ListTraverse(L); 

    i=ListDelete(L,1);
    printf("\n在L的删除“A”后：\nL.data=");
    ListTraverse(L); 

    printf("\n");

    return 0;
}

这个代码风格超级棒有没有，向程杰致敬。。。

到这里就告一段落了，下期见，拜拜