数据结构

最近在学习数据结构，实验操作环境是VC。老师说数据结构非常非常重要。好吧，我就跟随者老师的脚步，记录我学习数据结构的那些酸甜苦辣吧！

大三第一个学期第三周的学习：线性表（顺序表和链表）

线性表说的是逻辑结构上的，而顺序表和链表说的是存储结构上的。

顺序表就是按顺序把数据存储起来，知道其中的一个元素在哪里就可以推算出其他的元素存在哪个地方了，所以顺序表在找数据方面非常方便。

需要注意的是：引用的问题。当你的引用在程序中需要改变或者上级程序需要知道你的改变的时候就一定要使用引用。

链表是用指针把本来没有逻辑关系的数据串起来了。某个数据到底存在哪里你是无从得知的，但是指针的使用比顺序表的使用要方便很多。

两种存储结构各有各的好处，到底使用那个就要按自己的需要来了。

顺序表的结构：

typedef struct { 
ElemType data[MaxSize]; 
int length;
 } SqList; /*顺序表类型*/ 
//其中,data成员存放元素,length成员存放线性表的实际长度。

链表的结构：

typedef struct LNode   /*定义单链表结点类型*/
    {     ElemType data;
           struct LNode *next;    /*指向后继结点*/
    } LinkList;

实验操作：顺序表的数据的插入和删除，链表的数据的头插法和尾插法的使用

顺序表数据的插入：

把元素往后面移动从而为需要插入的数据腾出位置。

 int ListInsert(SqList *&L,int i,ElemType e)
  {    int j;
        if (i<1 || i>L->length+1)    return 0;
        i--;  /*将顺序表逻辑位序转化为elem下标即物理位序*/
        for (j=L->length;j>i;j--) L->data[j]=L->data[j-1];
                /*将data[i]及后面元素后移一个位置*/
        L->data[i]=e;
        L->length++;      /*顺序表长度增1*/
        return 1;
  }

顺序表数据的删除：

int ListDelete(SqList *&L,int i,ElemType &e)
{   int j;
     if (i<1 || i>L->length)    return 0;
     i--;       /*将顺序表逻辑位序转化为elem下标即物理位序*/
     e=L->data[i];
     for (j=i;j<L->length-1;j++) L->data[j]=L->data[j+1];
            /*将data[i]之后的元素后前移一个位置*/
     L->length--;    /*顺序表长度减1*/
     return 1;
}

链表的数据的头插法：把每一个数据节点都插在头节点之后，原开始节点之前

void CreateListF(LinkList *&L,ElemType a[],int n)
  {      LinkList *s;int i;
          L=(LinkList *)malloc(sizeof(LinkList));  /*创建头结点*/
          L->next=NULL;//初始化头节点
          for (i=0;i<n;i++)
          {     s=(LinkList *)malloc(sizeof(LinkList));
                      /*创建新结点*/
                  s->data=a[i]; s->next=L->next;        
                      /*将*s插在原开始结点之前,头结点之后*/
                  L->next=s;
           }
  }

链表的数据的尾插法：

 void CreateListR(LinkList *&L,ElemType a[],int n)
  {    LinkList *s,*r;int i;
        L=(LinkList *)malloc(sizeof(LinkList));      
            /*创建头结点*/
        r=L;    /*r始终指向终端结点,开始时指向头结点*/
        for (i=0;i<n;i++)
        {    s=(LinkList *)malloc(sizeof(LinkList));
               /*创建新结点*/
              s->data=a[i];r->next=s;  /*将*s插入*r之后*/
              r=s;
        }
        r->next=NULL;    /*终端结点next域置为NULL*/
  }