线性表链式存储结构的表示和实现

时间：2023-01-10 10:17:46

基本概念

    1、线性表的顺序存储结构的缺点是插入和删除时需要移动大量元素，这会消耗大量时间，可以选择链式存储结构来解决这个问题。
    2、链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。意味着，这些数据元素可以存储在内存中未被占用的任意位置。
    3、在顺序存储结构中，每个数据元素只需存数据元素的信息，而链式存储结构中，除了要存储数据元素的信息，还要存储它的后继元素的存储地址。
    4、我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据源的存储映像，称为结点。
    5、n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。头指针和头结点的异同如下描述：
    **头指针**
    （1）头指针是链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；
    （2）头指针具有标识作用，所以常用头指针冠以链表的名字；
    （3）无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
    **头结点**
    （1）头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（也可以存放链表的长度）；
    （2）有了头结点，对在第一元素之前插入结点和删除第一节点，其操作与其它结点的操作就统一了；
    （3）头结点不一定是链表必须要素。

单链表结构和顺序存储结构的对比如图所示：

线性表链式存储结构的表示和实现
结论：（1）若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
（2）当线性表中的元素个数变化较大或者根本不知道有多大时，最好采用单链表结构，这样可以不需要考虑存储空间的大小问题。

单链表的表示和实现

"linklist.h"

#pragma once
typedef int ELEM_TYPE;

typedef struct LNode
{
    ELEM_TYPE data;
    struct LNode *next;
}LNode,*LinkList;

//初始化头结点
void init_linklist(LinkList *phead);
//头插
void insert_head(LinkList *phead,ELEM_TYPE val);
//尾插
void insert_tail(LinkList *phead,ELEM_TYPE val);
int get_length(LinkList *phead);
void show(LinkList *phead);
void destroy_list(LinkList *phead);
bool is_empty(LinkList *phead);
//根据位置插入
void insert_pos(LinkList *phead,int pos,ELEM_TYPE val);
bool delete_pos(LinkList *phead,int pos);
//根据位置获得结点
void get_node(LinkList *phead,int pos,LinkList *node);
//修改结点值
void update_node(LinkList *phead,int pos,ELEM_TYPE new_val);
//通过值查找位置
int search(LinkList *phead,ELEM_TYPE val);
//根据值查找结点
LNode* getNodeByValue(LinkList *phead,ELEM_TYPE val);
bool deleteByValue(LinkList *phead,ELEM_TYPE val);
//删除尾结点
bool delete_tail(LinkList *phead);
//从尾销毁链表
void destroyByLast(LinkList *phead);
//从尾创建指定长度的单链表
void createListTail(LinkList *phead,int n);
//合并单链表1
void union_list(LinkList *phead1,LinkList *phead2,LinkList *pc);
//合并单链表2
void mergeList(LinkList *phead1,LinkList *phead2,LinkList *phead3);
//逆转单链表
void reverse_list(LinkList *phead);
//将值插入有序的单链表，并保持有序
void insert_sort(LinkList *phead,ELEM_TYPE x);
//合并单链表并逆转
void merge_reverse_list(LinkList *la,LinkList *lb,LinkList *lc);

"linklist.cpp"

#include "linklist.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stack>

void init_linklist(LinkList *phead)
{
*phead = (LinkList)malloc(sizeof(LNode));
    (*phead)->data = 0;
    (*phead)->next = NULL;
}

void insert_head(LinkList *phead,ELEM_TYPE val)
{
    LinkList p,q;
    p = *phead;
q = (LNode *)malloc(sizeof(LNode));
q->data = val;
q->next = p->next;
    p->next = q;
}
void insert_tail(LinkList *phead,ELEM_TYPE val)
{
    LinkList p,q;

    p = *phead;
while (p->next != NULL)
    {
        p = p->next;
    }
q = (LinkList)malloc(sizeof(LNode));
q->data = val;
q->next = NULL;
    p->next = q;
}
bool is_empty(LinkList *phead)
{
return (*phead)->next == NULL;  
}

void insert_pos(LinkList *phead,int pos,ELEM_TYPE val)
{
    LinkList p,q;
    p = *phead;
int len = get_length(phead);
    assert(pos >= 0 && pos <= len);
int i = 0;
while (p->next != NULL)
    {
if (i==pos)
        {
q = (LNode *)malloc(sizeof(LNode));
q->data = val;
q->next = p->next;
            p->next = q;
break;
        }
        ++i;
        p = p->next; 
    }

}
bool delete_pos(LinkList *phead,int pos)
{
    LinkList p,q;
    p = *phead;
int len = get_length(phead);
    assert(pos >= 0 && pos <= len);
int i = 0;
while (p->next != NULL)
    {
if (i==pos)
        {
q = p->next;
            p->next = q->next;
            free(q);
return 1;
        }
        ++i;
        p = p->next;
    }
return 0;

}

int get_length(LinkList *phead)
{
    LinkList p;
    p = *phead;
int len = 0;
while (p->next != NULL)
    {
        len++;
        p = p->next;
    }
return len;

}

void show(LinkList *phead)
{
    LinkList p;
    p = *phead;
if (p->next==NULL)
    {
printf("当前元素为空\n");
return;
    }
while (p->next != NULL)
    {
printf("data:%d\n",p->next->data);
        p = p->next;
    }
}

void destroy_list(LinkList *phead)
{
    LinkList p,q;
    p = (*phead)->next;
while (p != NULL)
    {
q = p->next;
        free(p);
        p = q;
    }
    (*phead)->next = NULL;
}

void get_node(LinkList *phead,int pos,LinkList *node)
{
    LinkList p;
    p = *phead;
int len = get_length(phead);
    assert(pos >= 0 && pos <= len);
int i = 0;
while (p->next != NULL && i < len)
    {
if (i==pos)
        {
*node = p->next;
break;
        }
        i++;
        p = p->next;
    }
}

void update_node(LinkList *phead,int pos,ELEM_TYPE new_val)
{
    LinkList p;
    p = *phead;
int len = get_length(phead);
    assert(pos >= 0 && pos <= len);
int i = 0;
while (p->next != NULL && i < len)
    {
if (i==pos)
        {
            p->next->data = new_val;
break;
        }
        i++;
        p = p->next;
    }
}

int search(LinkList *phead,ELEM_TYPE val)
{
    LinkList p;
    p = *phead;
int i = 0;
while (p->next != NULL)
    {
if (p->next->data == val)
        {
return i;
        }
        i++;
        p = p->next;
    }
return -1;
}
LNode* getNodeByValue(LinkList *phead,ELEM_TYPE val)
{
    LinkList p;
    p = *phead;
int i = 0;
while (p->next != NULL)
    {
if (p->next->data == val)
        {
return p->next;
        }
        i++;
        p = p->next;
    }
return NULL;
}

bool deleteByValue(LinkList *phead,ELEM_TYPE val)
{
    LinkList p,q;
    p = *phead;

int i = 0;
while (p->next != NULL)
    {
if (p->next->data == val)
        {
q = p->next;
            p->next = q->next;
            free(q);
return 1;
        }
        ++i;
        p = p->next;
    }
return 0;
}

bool delete_tail(LinkList *phead)
{
    LinkList p,q;
    p = *phead;
if (p->next == NULL)
    {
return 0;
    }
int i = 0;
while (p->next != NULL)
    {
        ++i;
q = p;
        p = p->next;
    }
    free(p);
q->next = NULL;
return 1;
}

void destroyByLast(LinkList *phead)
{
    LinkList p,q;
    p = *phead;
int i = 0;
while (p->next != NULL)
    {
while (p->next != NULL)
        {
            ++i;
q = p;
            p = p->next;
        }
        free(p);
q->next = NULL;
        p = *phead;
    }
}

void createListTail(LinkList *phead,int n)
{
*phead = (LNode *)malloc(sizeof(LNode));
    (*phead)->data = 0;
    (*phead)->next = NULL;

    LinkList p,r;
    r = *phead;
int i;
for(i=0;i<n;++i)
    {
        p = (LNode *)malloc(sizeof(LNode));
        p->data = i;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

void union_list(LinkList *phead1,LinkList *phead2,LinkList *pc)
{
    LinkList p1 = (*phead1)->next;
    LinkList p2 = (*phead2)->next;
while(p1 != NULL && p2 != NULL)
    {
if(p1->data >= p2->data)
        {
            insert_tail(pc,p2->data);
            p2 = p2->next;
        }
else
        {
            insert_tail(pc,p1->data);
            p1 = p1->next;
        }
    }
while (p1 != NULL)
    {
        insert_tail(pc,p1->data);
        p1 = p1->next;
    }
while (p2 != NULL)
    {
        insert_tail(pc,p2->data);
        p2 = p2->next;
    }
}

void mergeList(LinkList *phead1,LinkList *phead2,LinkList *phead3)
{
    LinkList pa = (*phead1)->next;
    LinkList pb = (*phead2)->next;
    LinkList pc = *phead3;
while (pa != NULL && pb != NULL)
    {
if(pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa:pb; 

}

void reverse_list(LinkList *phead)
{
    LinkList pNode,pPrev;
    pNode = (*phead)->next;
    pPrev = NULL;
while (pNode != NULL)
    {
        LinkList pNext = pNode->next;
if (pNext == NULL)
        {
            (*phead)->next = pNode;
        }
        pNode->next = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }

}

void insert_sort(LinkList *phead,ELEM_TYPE x)
{
    LinkList p,q ;
    p = *phead;
    LinkList t = (LNode *)malloc(sizeof(LNode));
    t->data = x;
    t->next = NULL;
while(p->next != NULL) 
    {
if(p->data > x)
        {
            t->next = p->next;
            p->next = t;
        }
        p = p->next;
    }
if(x > p->data)
    {
        p->next = t;
    }
}

void merge_reverse_list(LinkList *la,LinkList *lb,LinkList *lc)
{
    LinkList pa,pb,pc;
    pa = (*la)->next;
    pb = (*lb)->next;
    pc = *lc;
while(pa != NULL && pb != NULL)
    {
if(pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa:pb;
    reverse_list(lc); 
}
标签：

相关文章