数据结构学习笔记-线性表

简介

• 线性表是最常用且最简单的一种数据结构，简而言之就是n个数据元素的有限序列。
• 线性表的顺序表示和实现：
  线性表的顺序指用一组地址连续的存储单元一次存储线性表的数据元素。以元素在计算机内的“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。只要我确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构（存取的时候可以直接获得线性表中的某一数据，像数组，可以通过下标直接获取数组中的任一元素，而不需要像链表那样需要通过指针从头遍历查找，但是线性表的顺序存储缺点是插入元素或者删除元素都有进行大量的移动，而链表就不用，只需要修改指针）。

线性表的创建很简单：
//初始化线性表

int IinitListSpace(LIN* V){

  V->elem = (int*)malloc(MAX_FORM_SIZE*sizeof(int));
  if(!V->elem)exit(OVERFLOW);
  V->length = 0;
  V->sizes = MAX_FORM_SIZE;
  return 1; 
} 

//初始化线性表数据 

int InitListData(LIN* V){
int i =0;
for(i =0 ; i<10 ; i++) {
  V->elem[i] = i;
  V->length++;
  if(V->length >= MAX_FORM_SIZE)break;
}
  return 1; 
}

//向线性表任意位置插入数据
int InsertListData(LIN* V){
int data;
int space;
int i;  
printf("\n请输入需要插入的位置和整数\n");
scanf("%d",&space);
scanf("%d",&data);
if(space<1||space > V->length+1)return 0;
//如果空间已经占满，这增加空间
if(V->length >= V->sizes){
  //重新给线性表分配内存，在原来的基础上增加内存空间 
  V->elem = (int*)realloc(V->elem,(MAX_FORM_SIZE+MAX_FORM_LENTH)*sizeof(int));
  if(!V->elem)exit(OVERFLOW);
   V->sizes = MAX_FORM_SIZE+MAX_FORM_LENTH;
} 
printf("插入之前的线性表数据\n");
for(i =0 ; i < V->length ; i++){
printf("%d ",V->elem[i]);
}
//插入数据，移动数据
for(i = V->length ; i >= space -1 ; i-- ) V->elem[i+1] = V->elem[i];
V->elem[space-1] = data;
V->length +=1;
printf("\n插入之后的线性表数据\n");
for(i =0 ; i < V->length ; i++){
    printf("%d ",V->elem[i]);
}
return 1;
}

线性表的链式表示和实现：存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以不是连续的）。用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，也就是说，指针位数据元素之间的逻辑映射，则逻辑相邻的两个元素其存储的物理位置不要求紧邻，这种存储结构为非顺序映像或链式映像。

线性链表的创建：

//线性链表相关操作
void* InitLinkList(LinkList V){
int i;
Node* P;
V = (LinkList)malloc(sizeof(Node));
if(!V)exit(OVERFLOW);
V->next = NULL;//建立一个带头节点的单链表
V->data = 0;
for(i = 0 ; i< 10 ;i++){
  P = (LinkList)malloc(sizeof(Node));//生成节点 
  if(!P)exit(OVERFLOW);
  //scanf("%d",&(P->data));
  P->data = i;
  P->next = V->next;
  V->next = P; 
  V->data++;
}

return V;
} 

这里讲一下for循环里面怎么创建一个链表的：函数传进一个V链表，其指向下一个结点为NULL，这里我把链表的第一结点拿来做头结点，当然可以重新定义一个。在for循环里面，

当执行第一次for循环后，链表呈现这个样子：执行P->next = V->next;后，P的下一个结点指向V的下一个结点，而V->next = NULL，所以这时P的下一个结点不指向任何对象（或者对象为空），也就是P->next = NULL；执行V->next = P; 后，V的下一个结点指向P，也就是V的下一个结点指向，P的下一个结点指向NULL，这里不要因为P->next = V->next;而以为P的下一个结点指回本身了，指向的是NULL，所以就是V(next)——> P(next)——>NULL;

当执行第二次for循环后，链表程序的样子：执行P->next = V->next;新生成的P结点的下一个节点指向V的下一个结点，但是执行完第一次for循环后，V的下一个结点（V->next）指向了P，所以新的P节点的下一个结点指向了上一个P节点，执行V->next = P后，相当于断开了第一次for循环后，V下一个结点指向第一P结点之间的链接。而将V的下一个结点指向新生成的P节点，这下就变成了：V(next)——>P（next）(第二次新生成的结点)——>P（next）（第一次生成的结点）——>NULL，以次内推，一个链表就建立了，其实这个过程是从表尾开始向表头建立链表的，所以打印输出的时候是反过来的。

注意：很多人可能在写链表的创建，插入和删除的时候，会出现这样的错误，定义一个指针类型的链表变量（如：LinkList *List），然后把这个变量传递给函数的形参（插入和删除的函数不再main()所在的同意文件里），然后函数的返回值为void，在创建好链表后，依然把List传递给插入和删除的函数，或者在main（）里面打印输出链表值，这时编译不会出错，运行就出错了，很多人认为我传递的是指针变量，是地址啊，怎么在main（）里面不能用呢，至于怎么回事，自己看一下指针方面的知识，我用了一段时间的java，c有点忘了。解决办法就是把建好的链表返回来就可以了。

下面是java的链表实现程序：

import java.util.Scanner;
public class LinkList{

    private int num = 0;

    private  class Node{
       String elem;
       Node next;

       public Node(){
        this.elem = null;
        this.next = null;

        }
    }

    private Node getNode(){

    return new Node();

    }

    private Node LinkListInit(){

    System.out.println("初始化线性链表");
    Node root = new Node();//构造头节点
    root.elem = "根节点";
    for(int i = 0 ; i < 10 ; i++){

       Node node = new Node();
       node.elem = "第" + i + "节点";
       node.next = root.next;
       root.next = node;
       root.elem = "一共" + i + "节点";

    }

      return root;
    }

    private void outPut(Node root){

         for(int i = 0 ; i < 10 ; i++){
            if(root != null){

          System.out.println(root.elem);
          root = root.next;            
            }    
        }  

    } 
    private Node deleteLinkList(Node root){

    Node ret = new Node();
    ret = root;
        Scanner scanner = new Scanner(System.in);// 创建输入流扫描器
        System.out.println("请输入需要删除元素的位置：");// 提示用户输入
        int space = scanner.nextInt();// 获取用户输入的一行文本    
        if(ret != null) {
   for(int i = 1 ; i < space ; i++){
       if(ret == null){
          System.out.println("你输入的位置不正确：");
          return root;
       }  
  ret = ret.next; 

   }
        }
        else{
            System.out.println("请输入的位置不正确：");        
        }

        ret.next = (ret.next).next;
        num++;
        root.elem = "一共" + (9 - num) + "节点" ;        
    return root;
    }

    public static void main(String[] args){

    LinkList link = new LinkList(); 
    Node root  = link.getNode();

    root = link.LinkListInit();//初始化链表    
    link.outPut(root);//打印出每个节点值
    root = link.deleteLinkList(root);
    link.outPut(root);//打印出每个节点值

    }

}

静态链表的表示：用数组描述的链表，需要预先分配一定的空间。但解决了数据插入和删除是需要的移动元素的缺点，静态链表插入和删除数据是不需要移动数据元素。好像数组里面有了链表的特性。

那为什么要用静态链表呢，不是有链表吗？链表是严重依赖指针的，在没有指针语法的语言里面那我们该怎么实现类似链表的功能呢？那就要用静态链表了。

静态链表的使用思想是怎么样的呢？静态链表里。我们把数组的每一个分量（也就是数据项）表示一个结点，里面存储数值和一个下标数值，这个下标数值就像链表里的*next一样，存储的值 = 它所指向的那个数据的在数组中的位置。例如下面的：（下标为0的定义位头节点，指向0表示数组结束）。[图片上传失败...(image-bdb8df-1545565392987)]

20151008230607427.png

它的逻辑结构是这样的：

20151008230906957.png

那么我们插入数据是可以将数据插入任意空的地址空间，然后想链表那样修改对应的下标值就是了，也不用移动数据：程序如下：

StaticList* StaticList_Create(int capacity) // O(n)
{
    TStaticList* ret = NULL;
    int i = 0;

    if( capacity >= 0 )
    {
        ret = (TStaticList*)malloc(sizeof(TStaticList) + sizeof(TStaticListNode) * (capacity + 1));
    }

    if( ret != NULL )
    {
        ret->capacity = capacity;
        ret->header.data = 0;
        ret->header.next = 0;

        for(i=1; i<=capacity; i++)
        {
            ret->node[i].next = AVAILABLE;
        }
    }

    return ret;
}

int StaticList_Insert(StaticList* list, StaticListNode* node, int pos)  // O(n)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = (sList != NULL);
    int current = 0;
    int index = 0;
    int i = 0;

    ret = ret && (sList->header.data + 1 <= sList->capacity);
    ret = ret && (pos >=0) && (node != NULL);

    if( ret )
    {
        for(i=1; i<=sList->capacity; i++)
        {
            if( sList->node[i].next == AVAILABLE )
            {
                index = i;
                break;
            }
        }

        sList->node[index].data = (unsigned int)node;

        sList->node[0] = sList->header;

        for(i=0; (i<pos) && (sList->node[current].next != 0); i++)
        {
            current = sList->node[current].next;
        }

        sList->node[index].next = sList->node[current].next;
        sList->node[current].next = index;

        sList->node[0].data++;

        sList->header = sList->node[0];
    }

    return ret;
}

循环链表：这个在前面的基础上增加指针就可以实现，这里就不讲了。

总结：为什么用线性表顺序存储：方便随机存取，但是插入和删除需要大量移动数据，能够继续增加存储空间大小，不能动态生成，因为每次分配内存时内存不一定是连续的，而顺序表不能通过指针指向下一个元素，所以不能动态生成。

问什么用链表:能动态生成，不需要移动元素，存储灵活等

为什么用静态链表:在不支持指针的语言中也能实现链表的存储和操作等

工程地址：http://download.csdn.net/detail/tuoguang/9164793

打开工具dev-c++：