线性表链式表示和实现

男娘i 2022-06-17 13:12 152阅读 0赞

1、我们把存储数据元素信息的域称为数据域，把存储直接后继的域称为指针域。指针域中存储的信息称为指针或链。元素（数据元素映像）+指针（指示后继元素存储位置）=结点（表示数据元素）  
2、n个结点（ai(1<=i<=n)）链成一个链表，即为线性表。  
3、链表中第一个结点的存储位置叫做头指针。  
4、线性表最后一个指针为空（用NULL或^表示）。  
5、有时为了方便操作会在第一结点前附设一个头结点头结点的数据域可以不存储任何信息。  
6、头结点和头指针的区别：  
头指针是指链表指向第一个结点的指针，若链表有头结点则是指向头结点的指针。头指针具有标识作用因此常用头指针来做链表的名字。无论链表是否为空，头指针都不为空。  
7、 头结点放在第一元素的结点之前。

8、`/*线性表的单链表存储结构*/`

typedef struct Node
    {
        int data;  //这里假设为int型 
        int struct *next; 
    }LNode,*LinkList;

9、`/*单链表的读取*/`

10、`/单链表的插入/`

Status GetElem_L(LinkList L,int i,int *e)
    {
        int j;
        LinkList p;  //声明一个指针p
        p=L->next;  //指针p指向链表的第一个结点 
        j=1;  //j为计数器
        while(p&&j<i)  //p不为空，且计数器j还没有等于i时，循环继续 
        {
            p=p->next;  //p不断的指向下一节点
            ++j; 
        } 
        if(!p||j>i)  //若链表末尾p为空 
            return ERROR;  //第i个数据不存在 
        *e=p->data;  //若查找成功返回p点的数据 
        return OK;
    }

Status InsertElem_L(LinkList *L,int i,int e)
    {
        LinkList p,s;  //声明指针p,s
        int j;
        p=*L;  //指针p指向链表头结点 
        j=1;  //初始化j从1开始
        if(p&&j<i)  //j<i时遍历链表 
        {
            p=p->next; //p的指针向后移动 
            ++j;    //j累加 
        } 
        if(!p||j>i)  //链表结点p为空，第i个结点不存在
            return ERROR;
        s=(LinkList)malloc(sizeof(Node)); //生成新的结点 
        s->data=e; //将数据元素e赋值给s->data
        s->next=p->next; //将p的后继节点赋值给s的后继 
        p->next=s;   //将s赋值给p的后继 
        return OK;
    
    }

11、`/*单链表的删除*/`

Status DeleteElem_L(LinkList *L,int i,int *e)
    {
        LinkList p,q;  //声明一个指针p 
        int j;  //计数器 
        p=*L;  //指向链表头指针 
        j=1;  //初始化从1开始
        if(p&&j<i)  //当j<i时，遍历链表 
        {
            p=p->next;  //指针p不断向后移 
            ++j;   //计数器累加 
        } 
        if(!p||j>i)  //如果链表末尾为空，第i个结点不存在 
            return ERROR;
        q=p->next;  //查找成功
        p->next=q->next; 
        *e=q->data;
        free(q); //释放q结点；free的作用是让系统收回一个Node结点，释放内存
        return OK;  //返回成功 
    }

12、`/*单链表的头插法，随机产生n个元素的值，建立带头结点的单链表*/`

Status CreatListHead(LinkList *L,int n)
    {
        LinkList p;  //声明指针p 
        int i;  //计数器变量i
        srand(time(0));  //初始化随机数种子 
        *L=(LinkList)malloc(sizeof(Node));  //初始化空链表L
        (*L)->next=NULL;  //L的头结点的指针指向NULL,建立一个带头结点的单链表
        for(i=0;i<n;i++) 
        {
            p=(LinkList)malloc(sizeof(Node)); //生成新的结点赋值给p
            p->data=rand()%100+1;
            p->next=(*L)->next;
            (*L)->next=p;  //插入到表头 
        }
    }

13、`尾插法，随机产生n个数，建立带头结点的单链表L`

Status CreatListWei(LinkList *L,int n)
    {
        int i;   //计数器
        LinkList p,r;  //声明指针p,r
        srand(time(0));  //初始化随机数种子 
        *L=(LinkList)malloc(sizeof(Node));  //初始化一个空链表L
         r=*L;  //r为指向尾部的结点 
         for(i=0;i<n;i++)
         {
            p=(Node *)malloc(sizeof(Node));  //生成新的结点赋值给p
            p->data=rand()%100+1;
            r->next=p;  //将表尾终端的指针赋值给新结点
            r=p;  //将当前新结点定义为表位终端节点 
         } 
        r->next=NULL;  //表示当前结点结束 
    }

14、`/*单链表的整表删除，将L重置为空表*/`

Status ClearList(LinkList *L)
    {
        LinkList p,q; //声明一个结点p,q
        p=(*L)->next;  //将第一个结点赋值给p;
        while(p) //没到表尾
        {
            q=p->next;  //将下一个结点赋值给q;
            free(q);  //释放q
            p=q;  //将q赋值给p 
        } 
        (*L)->next=NULL;  //头结点指针域为空
        return OK; 
    }

15、若线性表需要频繁查找而很少进行插入和删除操作时，应该采用顺序存储结构，否则采用单链表结构。