数据结构-线性表的链式存储

2017-06-26

线性表的链式存储-单链表

单链表-数据结构

typedef struct LNode{	//定义单链表结点类型
	ElemType data;	//数据域
	struct LNode *next;	//指针域
}LNode,*LinkList;

单链表-初始化

单链表-头插法

LinkList CreateLinkListHead(){
    //从表尾到表头逆向建立单链表L，每次在头结点之后插入元素，逆序
    LNode *s;int x;
    LinkList L = (LinkList)malloc(sizeof(LNode));   //创建头结点
    //下句的能够使得单链表成为循环单链表
    //L->next = L;
    L->next = NULL; //初试为空链表
    scanf("%d",&x); //输入结点的值
    while (x != 65535) {    //若输入65535则结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;    //新结点插入上一结点的下一个
        scanf("%d",&x);
    }
    return L;
}

单链表-尾插法

LinkList CreateLinkListTail(){
    //从表头到表尾正向建立单链表L，每次都在表尾插入元素，顺序
    int x;
    LinkList L = (LinkList)malloc(sizeof(LNode));   //创建头结点
    LNode *s,*r=L;  //r为表尾指针
    L->next = NULL; //初试为空链表
    scanf("%d",&x); //输入结点的值
    while (x != 65535) {    //若输入65535则结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r=s;  //r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next = NULL;
    //下句的能够使得单链表成为循环单链表
    //r->next = L;
    return L;
}

单链表-插入

//在指定index插入元素，若为负数，则在表头插入，若大于链表长度则在表尾插入
void LinkListInsert(LinkList &L,int index,ElemType e){
    LNode *s = (LNode*)malloc(sizeof(LNode));
    LNode *p = L;
    s->data = e;
    int i = 0;
    if(index<=0){   //在表头插入
        s->next = L;
        L = s;
    }else{
        while(p->next && i<index-1){    //找index的前一个结点
            p = p->next;
            i++;
        }
        s->next = p->next;
        p->next = s;
    }
}

单链表-删除

//删除指定index的结点（e输入为任意），若大于长度，则删除最后一个，若为0则删除第一个，若为负数，则删除指定内容为e的结点
void LinkListDelete(LinkList &L,int index,ElemType e){
    int i = 0;
    LNode *p = L;
    LNode *prep = p;
    if(index == 0){
        L = L->next;
        free(p);
    }else if(index < 0){
        while(p&&p->data==e){   //删除表头元素为e的情况
            L = L->next;
            free(p);
            p = L;
            if(!p){
                break;  //若p为NULL则跳出
            }
        }
        while(p->next){ //删掉元素为e的结点
            if(p->next->data == e){
                LNode *q = p->next;
                p->next = q->next;
                free(q);
            }
        }
    }else{
        while(p->next&&i<index-1){
            prep = p;
            p=p->next;
            i++;
        }
        if(p->next&&i == index){    //index的结点存在，则删除该结点
            LNode *q = p->next;
            p->next = q->next;
            free(q);
        }else{  //index的结点不存在，则删除最后一个结点
            prep->next = NULL;  //prep为最后一个结点的前一个，因为p的next为NULL,prep->next = p;
            //下句的能够使得单链表成为循环单链表
            //prep->next = L;
            free(p);
        }
    }
}

单链表-查找

//查找固定下标index的元素，并返回该结点
LNode *LinkListHeadSearchByIndex(LinkList L,int index){
    //取出带头结点的第i个元素，头结点为第0个元素
    int i = 1;
    LNode *p = L->next;
    if(index == 0){
        return L;
    }else if(index<0){
        return NULL;
    }else{
        while (i<index&&p){    //p不为NULL
            p = p->next;
            i++;
        }
        return p;    //若超出长度也返回NULL
    }
}

//查找内容e的元素，并返回该元素的Node数组
LNode *LinkListHeadSearchByElemType(LinkList L,ElemType e){
    int i = 0,j = 0;
    LNode nodes[20];
    while(L){
        if(L->data == e){
            nodes[j] = *L;
            j++;
        }
        L = L->next;
        i++;
    }
    return nodes;	//返回第一个元素的首地址，*nodes
}

线性表的链式存储-双链表

双链表-数据结构

typedef struct DNode{	//定义双链表结点类型
	ElemType data;	//数据域
	struct DNode *prior,*next;	//前驱和后续指针
}DNode,*DinkList;

双链表-初始化

DinkList CreateDinkListHead(){
    //从表头到表尾正向建立单链表L，每次都在表尾插入元素，顺序
    int x;
    DinkList L = (DinkList)malloc(sizeof(DNode));   //创建头结点
    DNode *s,*r=L;  //r为表尾指针
    L->next = NULL; //初试为空链表
    scanf("%d",&x); //输入结点的值
    while (x != 65535) {    //若输入65535则结束
        s=(DNode*)malloc(sizeof(DNode));
        s->data = x;
        if(s->next){
            s->next->prior = s;
        }
        r->next = s;
        r=s;  //r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next = NULL;
    //下句的能够使得单链表成为循环双链表
    //r->next = L;
    //L->prior = r;
    return L;
}

双链表-插入

//在指定index插入元素，若为负数，则在表头插入，若大于链表长度则在表尾插入
void DinkListInsert(DinkList &L,int index,ElemType e){
    //若为循环链表，则需要遍历到尾结点
    DNode *s = (DNode*)malloc(sizeof(DNode));
    DNode *p = L;
    s->data = e;
    int i = 0;
    if(index<=0){   //在表头插入
        s->next = L;
        L->prior = s; //修改前驱
        L = s;
    }else{
        while(p->next && i<index-1){    //找index的前一个结点
            p = p->next;
            i++;
        }
        p->next->prior = s; //修改前驱
        s->next = p->next;
        s->prior = p; //修改前驱
        p->next = s;
    }
}

双链表-删除

//删除指定index的结点（e输入为任意），若大于长度，则删除最后一个，若为0则删除第一个，若为负数，则删除指定内容为e的结点
void DinkListDelete(DinkList &L,int index,ElemType e){
    int i = 0;
    DNode *p = L;
    DNode *prep = p;
    if(index == 0){
        //下句的能够使得单链表成为循环双链表
        //L->prior->next = L->next;
        L = L->next;
        free(p);
    }else if(index < 0){
        while(p&&p->data==e){   //删除表头元素为e的情况
            //下句的能够使得单链表成为循环双链表
            //L->prior->next = L->next;
            L = L->next; //修改前驱
            free(p);
            p = L;
            if(!p){
                break;  //若p为NULL则跳出
            }
        }
        while(p->next){ //删掉元素为e的结点
            if(p->next->data == e){
                DNode *q = p->next;
                q->next->prior = p; //修改前驱
                p->next = q->next;
                free(q);
            }
        }
    }else{
        while(p->next&&i<index-1){
            prep = p;
            p=p->next;
            i++;
        }
        if(p->next&&i == index){    //index的结点存在，则删除该结点
            DNode *q = p->next;
            q->next->prior = p; //修改前驱
            p->next = q->next;
            free(q);
        }else{  //index的结点不存在，则删除最后一个结点
            prep->next = NULL;  //prep为最后一个结点的前一个，因为p的next为NULL,prep->next = p;
            //下句的能够使得单链表成为循环双链表
            //prep->next = L;
            //L->prior = prep;
            free(p);
        }
    }
}

线性表的链式存储-静态链表

静态链表-数据结构

//使用顺序表的方式完成链式的存储，存储结构为顺序
#define MaxSize 50	//静态链表的最大长度
typedef struct{	//静态链表结点类型的定义
	ElemType data;	//存储数据元素
	int next;	//下一个元素的数组下标，next=-1为结束
}SLinkList[MaxSize];