数据结构---链式存储

1、单链表的基本概念

单链表是线性表链式存储的一种形式，其中的结点一般含有两个域，一个存放数据信息的info域，另一个指向该结点的后继结点存放地址的指针next域。一个单链表必须有一个首指针指向单链表中的第一个结点。

单链表中每个操作的单独实现

--------------------定义结点 -------------------
#include<stdio.h>
#include<stdlib.h> 
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct Node
{
    ElemType data;      //数据域
    struct Node *next; //指针域
}Node;
typedef struct Node *Linklist;
---------------------链表初始化 ----------------------
int Create(Linklist *L)
{
    *L=(Linklist)malloc(sizeof(Node));
 //创建了一个结点，并且用L指向了这个结点
    if(!(*L))
        return ERROR;
    (*L)->next=NULL;
        return OK;
}
 --------------------求长度函数 -----------------------
int Length(Linklist L)
{
    int i=0;
    Linklist p;
    p=L->next; //指向的第一个结点
    while(p)
    {
        i++;
        p=p->next; //指向下一个结点
    }
    return i;
}
---------------------取元素操作-----------------------
int Get(Linklist L,int i)//ElemType *e)
{
    int j;
    Linklist p; 
    p=L->next;
    j=1;
    while(p && j<i)  
    {
        j++;
        p=p->next;
    }
    if (!p|| j>i)
        return ERROR;
    //*e= p->data;
        return p->data;
}
---------------------定位元素-------------------------
int Locate(Linklist L,ElemType e)
{
    int i=1;
    Linklist p;
    p=L->next;
    while(p)
    {
        if (p->data==e)
            return i;
        p=p->next;
        i++;
    }
    return ERROR;
}
---------------------前插元素-------------------------
int Insert(Linklist *L,int i,ElemType e)
{
    int j;
    Linklist p,s;
    p= *L;
    j=1;
    while(p && j<i)
    {
        p=p->next;
        j++;
    }
    if(!p|| j>i)
        return ERROR;
    s=(Linklist)malloc(sizeof(Node));
    s->data=e;
    s->next=p->next;
    p->next=s;
        return OK;
}
---------------------删除元素-------------------------
int Delete(Linklist *L,int i)
{
    int j;
    Linklist p,q;
    p= *L;
    j=1;
    while(p->next && j<i)
    {
        p=p->next;
        j++;
    }
    if(!(p->next)||j>i)
            return ERROR;
        q=p->next;
        p->next=q->next;
        free(q);
            return OK;
}
---------------------判空操作-------------------------
int Check(Linklist *L)
{
    Linklist p;
    p=*L;
    if(p->next)//头指针是否为空？
        printf("链表非空！\n");
    return OK;
}
---------------------清空表操作-----------------------
int Clear(Linklist *L)
{
    Linklist p;
    p =*L;
    while(p->next)
    {
        p=p->next;
        p->data=0;//只是数据清零，并非释放内存
    }
    return OK;
}

执行后：

静态链表

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef char ElemType;

typedef struct{
    ElemType data;
    int cur; //游标
}Component,StaticLinkList[MAXSIZE];


//输出
int visit(ElemType c)
{
    printf("%c ",c);
    return OK;
}
//初始化
int InitList(StaticLinkList space)
{
    int i;
    for (int i = 0; i < MAXSIZE-1; ++i)
        space[i].cur =i+1;
        space[MAXSIZE-1].cur =0;
    return OK;
}
//分配空间
int Malloc(StaticLinkList space)
{
    int i = space[0].cur;
    if(space[0].cur)
        space[0].cur = space[i].cur;
    return i;
}
//回收空间
int Free(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur; 
 /* 把第一个元素的cur值赋给要删除的分量cur */
    space[0].cur = k;   
/* 把要删除的分量下标赋值给第一个元素的cur */
    return OK;         
}
//长度函数
int Length(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}
//在第i个元素前插入元素
int Insert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k = MAXSIZE -1;
    if( i<1 || i > Length(L)+1)
        return ERROR;
    j=Malloc(L);
    if(j)
    {
        L[j].data =e;
        for (l = 1; l < i -1; l++)  
/* 找到第i个元素之前的位置 */
            k=L[k].cur;
        L[j].cur = L[k].cur;
/* 把第i个元素之前的cur赋值给新元素的cur */
        L[k].cur = j;  
/* 把新元素的下标赋值给第i个元素之前元素的ur */
        return OK; 
    }
    return ERROR;
}
//删除第i个数组元素
int Delete(StaticLinkList L, int i)
{
    int j,k;
    if(i<1 || i> Length(L))
        return ERROR;
    k = MAXSIZE-1;
    for(j=1;j<=i -1;j++)
        k= L[k].cur;
    j=L[k].cur;
    L[k].cur = L[j].cur;
    Free(L,j);
    return OK;
}
int Traverse(StaticLinkList L)
{
    int j=1;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
            visit(L[i].data);
            i=L[i].cur;
            j++;
    }
    return j;
    printf("\n");
    return OK;
}
int main()
{
    StaticLinkList L;
    int i;
    i=InitList(L);
    printf("初始化L后：L.length=%d\n",Length(L));
    i=Insert(L,1,'F');
    i=Insert(L,1,'E');
    i=Insert(L,1,'D');
    i=Insert(L,1,'B');
    i=Insert(L,1,'A');
    printf("\n在L的表头依次插入FEDBA后：\nL.data=");
    Traverse(L); 
    i=Insert(L,4,'C');
    printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
    Traverse(L); 
    i=Delete(L,1);
    printf("\n在L的删除“A”后：\nL.data=");
    Traverse(L); 
    printf("\n");
    return 0;
}