线性表的链式存储结构

特点

• 结点除自身的信息域外，还有表示关联信息的指针域。因此，链式存储结构的存储密度小、存储空间利用率低。
• 在逻辑上相邻的结点在物理上不必相邻，因此，不可以随机存取，只能顺序存取。
• 插入和删除操作方便灵活，不必移动结点只需修改结点中的指针域即可。

为什么叫链表

为了表示每个数据元素ai与其后继元素之间的逻辑关系，对ai来说，除了存储其本身信息外，还需要一个存储直接后继的位置信息。我们把数据元素信息的域叫做数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或者链。这两部分信息组成元素ai的存储映像，称为结点。

带结点的单链表实现

• S_LinkList.h文件

#ifndef S_LinkList
#define S_LinkList
/*---------LinkList storage structure----------------*/
typedef int ElemType;
typedef struct Node
{
    ElemType data;/*data field*/
    struct Node * next;/*ptr next*/
} Node;
typedef struct Node * LinkList;/*define the LinkList*/
/*-----------------Init the LinkList------------------*/
void InitLinkList(LinkList *);
/*---------------Create the LinkList------------------*/
void CreateLinkList(LinkList*);
/*---------------Print the LinkList-------------------*/
void PrintLinkList(LinkList);
/*---------------Clear the LinkList-------------------*/
void ClearLinkList(LinkList);
/*-------------the length of the LinkList-------------*/
int LinkListLength(LinkList);
int IsEmpty(LinkList);
ElemType GetElem1(LinkList,int);
int Modify(LinkList *,int,ElemType);
int ListInsert1(LinkList*,int,ElemType);
int ListDelete1(LinkList*,int,ElemType*);
void Reverse(LinkList*);
#endif

• .c 文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "S_LinkList.h"

/*implement*/
void InitLinkList(LinkList *lp)
{
    *lp=NULL;
    printf("-------->链表初始化<---------\n");
}
void CreateLinkList(LinkList *ph)
{
    LinkList p,r;
    int i,n;
    (*ph)=(LinkList)malloc(sizeof(Node));
    r=(*ph);
    printf("输入创建链表的结点的个数:\n");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        p=(Node*)malloc(sizeof(Node));
        scanf("%d",&p->data);
        r->next=p;//表尾部结点指向新结点
        r=p;//将当前的新节点定义为表尾部结点，实时跟踪
    }
    r->next=NULL;//表示当前链表结束
}

void PrintLinkList(LinkList ph)
{
    LinkList tmp=ph->next;
    if(tmp==NULL){
        printf("链表为空!");}
    else
    {
        while (tmp!=NULL)
        {
            printf("%d\t",tmp->data);
            tmp=tmp->next;
        }
        printf("\n打印完成!\n");
    }
}

void ClearLinkList(LinkList *ph)
{
    LinkList p,q;
    p=(*ph)->next;
    while (p)
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*ph)->next=NULL;
}

int LinkListLength(LinkList ph)
{
    LinkList tmp=ph;
    int length=0;
    if(tmp->next=NULL)
    {
        length=0;
    }
    else
    {
        while (tmp->next->next!=NULL)
        {
            length++;
        }
        length+=1;
    }
    printf("链表长度%d\n", length);  
    return length;
}
int IsEmpty(LinkList ph)
{
    int status;

    if(ph->next==NULL)
    {
        status=1;
        printf("链表为空!\n");
    }
    else
    {
        status=0;
        printf("链表非空!\n");
    }
    return status;
}
ElemType GetElem1(LinkList ph,int pos)
{
    int index=0;
    LinkList tmp=ph->next;//First index nummber.
    if(pos<1)
    {
        printf("pos值不合法!\n");
        return 0;
    }
    if(tmp==NULL)
    {
        printf("链表为空!\n");
        return 0;
    }
    while (tmp!=NULL)
    {
        ++index;
        if(index==pos)
        {
            break;
        }
        tmp=tmp->next;
    }
    if(index<pos)
    {
        printf("超出索引范围!");
        return 0;
    }
    return tmp->data;
}
int Modify(LinkList *ph,int pos,ElemType e)
{
    LinkList tmp;
    int index;
    tmp=(*ph)->next;
    if(pos<1)
    {
        printf("这个位置不合法!\n");
        return 0;
    }
    if(tmp==NULL)
    {
        printf("链表为空!\n");
        return 0;
    }
    while(tmp!=NULL)
    {
        ++index;
        if(index==pos)
        {
            break;
        }
        tmp=tmp->next;
    }
    if(index<pos)
    {
        printf("这个位置不合法!\n");
        return 0;
    }

    tmp->data=e;
    printf("Modify后第%个数修改为%d!\n",index,tmp->data);
    return 1;
}
int ListInsert1(LinkList *ph,int pos,ElemType e)
{
    int index;
    LinkList p,s;//p signed as HeadLink and s is a new Link that will be added.
    p=(*ph);
    index=1;
    while (p&&index<pos)
    {
        p=p->next;
        index++;
    }
    if(!p||index>pos)
    {
        return 0;
    }
    s=(LinkList)malloc(sizeof(Node));
    s->data=e;
    s->next=p->next;
    p->next=s;
    printf("成功插入元素%d与%位置!\n",s->data,index);
    return 1;
}
int ListDelete1(LinkList *ph,int pos,ElemType *e)
{
    int index;
    LinkList p,q;
    p=(*ph);
    index=1;
    while (p->next&&index<pos)
    {
        p=p->next;
        index++;
    }
    if(!(p->next)||index>pos)
    {
        return 0;
    }
    q=p->next;
    p->next=q->next;
    *e=q->data;
    free(q);
    printf("删除的第%d个结点%d成功!\n",pos,*e);
    return 1;
}
void Reverse(LinkList *ph)
{
    //assign it has the head node.
    LinkList q,current,p;
    q=(*ph);
    current=(*ph)->next;
    while (current->next!=NULL)
    {
        p=current->next;
        current->next=p->next;
        p->next=q->next;
        q->next=p;
    }
    printf("逆序链表完成!\n");
}

• 调试结果

#include <stdlib.h>
#include <stdio.h>
#include "S_LinkList.h"

int main()
{
    LinkList p;
    InitLinkList(&p);
    CreateLinkList(&p);
    PrintLinkList(p);
    system("pause");
    return 0;
}

如果有什么可以交流的欢迎大家留言一起探讨。