数据布局-线性表-链式存储布局-单链表

<code>
//整体创建顺序表
void CreateList(SqList &L,ElemType a[],int n)
{
        int j=0;
        for(int i=0;i<n;++i)
        {
                L.data[k]=a[i];
                j++;
        }
        L.length=j;
}
复制代码

<code>#include <stdio.h>
#include <malloc.h>
//结点类型声明
typedef int ElemType;
typedef struct node
{
        ElemType data;     //数据域data
        struct node *next;   //指针域
}LNode;                 //单链表结点类型
//初始化单链表运算算法
void InitList(LNode *&L)             //L为引用型参数
{
        L=(LNode*)malloc(sizeof(LNode));  //申请空间，创建头结点L
        L->next=NULL;                     //头结点的指针域（next）指向NULL,表示空链表
}
//销毁单链表的运算算法
void DestroyList(LNode *&L)
{
        LNode *p1=L,*p=p1->next;
        while(p!=NULL)
        {
                free(p1);        //释放p1结点空间
                p1=p;p=p->next;  //p1,p同步后移
        }
        free(p1);           //释放p1指向的尾结点空间
}
//求单链表的长度运算算法
int GetLength(LNode *L)
{
        int i=0;
        LNode *p=L->next;         //p指向头结点，i为1
        while(p !=NULL)
        {
                i++;
                p=p->next;           //p移到下一个结点，i++
        }
        return i;                //p为空时，i即为数据结点个数
}
//求单链表中第i个元素运算算法
int GetElem(LNode *L,int i,ElemType &e)
{
        int j=0;
        LNode *p=L;     //p指向头结点，计数器j值为0
        if(i<0)
                return 0;   //参数i错误返回0
        while(p!=NULL && j<i)
        {
                j++;
                p=p->next;
        }
        if(p==NULL)
                return 0;    //未找到返回0
        else
        {
                e=p->data;
                return 1;   //找到后返回1
        }
}
//按值查找运算算法
int Locate(LNode *L,ElemType e)
{
        LNode *p=L->next;
        int j=1;               //p指向头结点，j置为序号1
        while(p!=NULL && p->data!=e)
        {
                p=p->next;
                j++;
        }
        if(p==NULL)
                return(0);           //未找到返回0
                else
                return (j);         //找到后返回其序号
}
//插入元素运算算法
int InsElem(LNode * &L,ElemType x,int i)  //插入结点值为X的结点
{
        int j=0;
        LNode *p=L,*s;
        if(i<=0)
                return 0;         //参数i错误返回0
        while(p!=NULL && j<i-1) //查找第i-1个结点p
        {
                j++;
                p=p->next;
        }
        if(p==NULL)
                return 0;          //未找到第i-1个结点是返回0
        else                    //找到第i-1个结点p
        {
                s=(LNode*)malloc(sizeof(LNode));
                s->data=x;         //创建存放元素x的新结点s
                s->next=p->next;   //将s结点插入到P结点之后
                p->next=s;
                return 1;          //插入成功，返回1
        }
}
//删除结点运算算法
int DelElem(LNode *&L,int i)
{
        int j=0;
        LNode *p=L,*q;
        if(i<=0)
                return 0;             //参数i错误返回0
        while(p!=NULL && j<i-1)   //查找第i-1个结点
        {
                j++;
                p=p->next;
        }
        if(p==NULL)
                return 0;            //未找到第i-1个结点是返回0
        else                     //找到第i-1个结点p
        {
                q=p->next;          //q指向被删除的结点
                if(q==NULL)
                        return 0;       //没有第i个结点是返回0
                else
                {
                        p->next=q->next; //从单链表中删除q结点
                        free(q);         //释放其空间
                        return 1;
                }
        }
}
//输出单链表
void DispList(LNode *L)
{
        LNode *p=L->next;
        while(p!=NULL)
        {
                printf("%d",p->data);
                p=p->next;
        }
        printf("\n");
}
void main()
{
        int i;
        ElemType e;
        LNode *L;
        InitList(L);
        InsElem(L,6,1);
        InsElem(L,4,2);
        InsElem(L,4,3);
        InsElem(L,7,4);
        InsElem(L,1,5);
        InsElem(L,9,6);
        InsElem(L,8,7);
        InsElem(L,3,8);
        InsElem(L,2,9);
        InsElem(L,7,10);
        printf("单链表: ");
        DispList(L);
        printf("长度: %d\n",GetLength(L));
        i=6;
        GetElem(L,i,e);
        printf("第%d个元素: %d\n",i,e);
        e=3;
        printf("元素%d是第%d个元素\n",e,Locate(L,e));
        i=7;
        printf("删除第%d个元素\n",i);
        DelElem(L,i);
        printf("单链表:");
        DispList(L);
        DestroyList(L);
}
复制代码

<code>#头插法
void CreateListF(LNode *&L,ElemType a[],int n)
{
        LNode *s;
        L=(LNode*)malloc(sizeof(LNode));   //申请空间
        L->next=NULL;                      //创建一个空单链表
        for(int i;i<n;i++)                 //遍历a[]所有元素
        {
                s=(LNode*)malloce(sizeof(LNode));
                s->data=a[i];                 //将创建存放a[i]元素的新节点s
                s->next=L->next;              //将s结点插入到头结点
                L->next=s;
        }
}
复制代码

<code>//尾插法
void CreateListR(LNode *&L,ElemType a[],int n)
{
        LNode *s,*d;
        L=(LNode *)malloc(sizeof(LNode));  //创建头结点
        d=L;                              //d始终指向尾结点，初始时指向头结点
        for(int i=0;i<n;++i)
        {
                s=(LNode *)malloc(sizeof(LNode));
                s->data=a[i];                 //创建存放a[i]元素的新节点s
                d->next=s;                   
                d=s;                         //结点s变成新的尾结点，
        }
        d->next=NULL;                    //由于是普通的单链表，故尾结点next域置为NULL
}
复制代码