线性表线性表顺序结构线性表链式结构补充链表排序循环链表双向链表

线性表顺序结构

定义线性顺序表

//扩充容量的步伐
#define  sizestep 10
//开始的容量的大小
#define startsize 100

//为了便于扩展，我们这里使用类型别名，
//我们使用最简单的int型作为一个范例

typedef int Elemtype;
struct List {
    //数据
    Elemtype * data;
    //长度
    int length;
    //初始容量
    int size;
};

构造线性顺序表

//创建一个空的线性表
void InitList(List & newList) {
    //初始容量为startsize
    newList.size = startsize;
    //首先开辟空间
    newList.data = new Elemtype[newList.size];
    //空表，长度是0
    newList.length = 0;
}

删除线性顺序表/清空线性顺序表

//线性表存在了，现在要销毁线性表
void DestroyList(List & newList) {
    newList.length = 0;
    newList.data = 0;
    //一定要先释放堆内存
    delete[] newList.data;
    //释放堆内存后，并将对应的指针赋予NULL
    newList.data = NULL;
    //如果不需要清空则不需要下面的步骤
    //重新为存放元素的变量开辟一个新的堆内存
    newlist.data=new Elemtype[newlist.size];
}

找相应位置上的元素

/返回线性表上某个位置上的元素的值,记住我们的位置是从1开始计算的。
void GetElem(List newList, int i, Elemtype &e) 
{
    if (newList.length==0) 
    {
        cout << "当前线性表是空表" << endl;
        return;
    }
    if (i<1 || i>newList.length) 
    {
        cout << "当前位置超出了线性表的范围" << endl;
        return;
    }
    e = newList.data[i - 1];
}

获取前驱元素

//判读元素的位置的函数
//我们这里直接返回该元素的下标
int LocationElem(List newList, Elemtype e)
{
    int i;
    for (i = 0; i < newList.length; i++) 
    {
        if (newList.data[i] == e) 
        {
            return i;
        }
    }
    return -1;
}
/*这个函数的时间复杂为：假定我们有n个元素，那么它的查找时间复杂为O(n),但是因为我们使用的是顺序结构，所以我们可以很方便的使用其他可以减低时间复杂的查找算法，例如二分查找，它的时间复杂度为：O(logn)*/

//获取前驱的元素
void PriorElem(List newList, Elemtype cur_e, Elemtype & pre_e) 
{
    int location = 0;
    location = LocationElem(newList, cur_e);
    //如果Location是-1，说明cur_e不在线性表中
    if (location == -1) 
    {
        cout <<cur_e<< "不在线性表中" << endl;
        return;
    }
    //如果Location是0，说明cur_e在线性表第一个位置，没有前一个元素
    if (location == 0)
    {
        cout << cur_e << "是线性表的第一个元素，没有前驱" << endl;
        return;
    }
    pre_e = newList.data[location - 1];
}

获取后继元素

//获取后驱元素
void NextElem(List newList, Elemtype cur_e, Elemtype & next_e) 
{
    int location = 0;
    location = LocationElem(newList, cur_e);
    //如果Location是-1，说明cur_e不在线性表中
    if (location == -1)
    {
        cout << cur_e << "不在线性表中" << endl;
        return;
    }
    //如果Location是0，说明cur_e在线性表最后一个位置，没有后一个元素
    if (location == newList.length-1)
    {
        cout << cur_e << "是线性表的最后一个元素，没有后驱" << endl;
        return;
    }
    next_e = newList.data[location + 1];
}

插入元素

//向线性表中插入一个元素，这里我们需要判断插入位置是否合法
//除此之外，我们还需要检测元素的容量是否已经到达了最大值
void ListInsert(List & newList, int i, Elemtype e) 
{
    //插入的位置不合法
    if (i<1 || i>newList.length+1) 
    {
        cout << "请检查插入位置是否正确" << endl;
        return;
    }
    int j = 0;
    //此时达到了线性表的最大容量，我们需要重新为线性表分配新的内存。
    if (newList.length == newList.size) 
    {
        //先保存之前的内容。
        Elemtype * p =new Elemtype[newList.length];
        for (j = 0; j < newList.length; j++) 
        {
            p[j] = newList.data[j];
        }
        //扩大容量
        newList.size += sizestep;
        delete[] newList.data;
        //重新分配内存
        newList.data = new Elemtype[newList.size];
        //恢复之前内容
        for (j = 0; j < newList.length; j++) 
        {
            newList.data[j] = p[j];
        }
    }
    //插入内容
    for (int k = newList.length; k >i-1; k-- )
    {
        newList.data[k]=newList.data[k-1];
    }
    newList.data[i - 1] = e;
    ++newList.length;
}

删除元素

//线性表删除一个元素(按照元素的位置)，我们需要判断删除的位置是否合法
void Listdelete(List & newList, int i) 
{
    //删除的位置不合法
    if (i<1 || i>newList.length)
    {
        cout << "请检查插入位置是否正确" << endl;
        return;
    }
    for (int j = i - 1; j < newList.length; j++) 
    {
        newList.data[j] = newList.data[j + 1];
    }
    --newList.length;
}
//按照元素的值，来删除对应元素的内容，
//这个时候我们通过传个参数，来决定我们是删除第一个该元素，
//0,删除一个，1，删除所有
//还是把所有的元素都给删除了
//如果不存在该元素，就直接返回
void Listdelete_data(List & newList, Elemtype e,int order)
{
   int flag=0;
    for (int i = 0; i < newList.length; i++) 
    {
        if (newList.data[i] == e) 
        {
            flag=1;
            //删除对应的位置上的元素，而且i也要减少一个
            Listdelete(newList, i + 1);
            --i;
            if (order == 0)
            {
                return;
            }
        }
    }
    if(flag==1)
    return ;
    cout << e << "不在线性表中" << endl;
}

链接两个线性顺序表

//连接两个线性表
void Connect_two_List(List a, List b, List & c) 
{
    //对c进行一些数据初始化
    c.length = c.size = a.length + b.length;
    c.data = new Elemtype[c.size];

    //这里采用指针的方式进行数据的移动,我们先把a和b数据第一个和最后一个元素的位置找出来
    int i = 0;
    int j = 0;
    int k = 0;

    while (i <= a.length-1 && j<= b.length-1)
    {
        if (a.data[i] < b.data[j])
        {
            c.data[k++] = a.data[i++];

        }
        else if(a.data[i] > b.data[j]) c.data[k++] = b.data[j++];
        else
        {
            c.data[k++] = b.data[j++]; i++; --c.length;
        }
    }
    while (i <= a.length - 1)
    {
        c.data[k++] = a.data[i++];
    }
    while (j <= b.length - 1)
    {
        c.data[k++] = b.data[j++];
    }
}

打印线性顺序表

void PrintList(List & L)
{
    for(int i=0;i<L.length;i++)
    {
        cout<<L.data[i]<<"";
    }
    cout << endl;
}

线性表链式结构

创建链式表

typedef int Elemtype;
struct Node
{
    Elemtype value;
    Node*next;
};
void InitList(Node*&head)
{
    head=new Node();
    head->value=0;
    head->next=NULL;
}

删除链式表

void DestroyList(Node*&head)
{
    delete head;
    head=NULL;
}

判断链表是否为空

bool ListLength(Node*head)
{
    return head->value;
}

找某个位置的值

bool getitem(Node*&head,int i,Elemtype& value)
{
    int j=0;
    Node*L=head;
    if(i<1||i>head->value) return false;
    while(j<i-1)
    {
        L=L->next;
        ++j;
    }
    value=L->next->value;
    return true;
}

找前驱元素

/*得到某个元素前面的那个元素的值，这个时候我们先写一个判断一个元素是否在线性表中，并且保存该元素在线性表中的位置*/
bool isExit(Node * & L, Elemtype cru_e,int & loc) 
{
    while (L->next)
    {
        //代表当前的位置
        ++loc;
        if (L->next->value == cru_e)
        {
            return true;
        }
        L = L->next;
    }
    return false;
}
//返回当前元素的前一个元素
bool PriorElem(Node * head, Elemtype cru_e, Elemtype & pre_e)
{
    Node * L = head;
    int loc = 0;
    if (isExit(L, cru_e, loc)) 
    {
        //不是线性表中的第一个元素
        if (loc != 1)
        {
            pre_e = L->value;
            return true;
        }   
    }
    return false;
}

找后继元素

bool NextElem(Node * head, Elemtype cru_e, Elemtype & next_e)
{
    Node *L = head;
    int loc = 0;
    if (isExit(L, cru_e, loc))
    {
        //同样是使用isExit函数来判断元素是否存在，并且得到这个元素的前一个结点，
        //如果这个元素的位置不在线性表达最后一个位置的话，
        //我们就可以得到下一个位置元素的值
        if (loc != head->value) 
        {
            next_e = L->next->next->value;
            return true;
        }
    }
    return false;
}

插入元素

bool ListInsert(Node * & head,int i, Elemtype value)
{

    //插入到前面的方法
    int j = 0;
    Node * L = head;
    //如果插入的位置不合法，直接返回错误提示
    if (i<1 || i>head->value + 1)return false;
    //得到插入位置的前一个结点
    while (j < i-1) 
    {  
        L = L->next;
        ++j;
    }
    //s是一个临时结点
    Node * s = new Node();
    s->value = value;    //先对临时结点赋值
    s->next = L->next;   //让临时结点下一个位置指向当前需要插入前一个结点的下一个位置
    L->next = s;          //让前一个结点下一个位置指向临时结点，完成
    //线性表的长度加一
    ++head->value;
    return true;
}

根据下标值删除特定元素

bool ListDelete(Node * & head, int i) 
{
    //s我们先找到需要删除那个结点的前一个结点
    int j = 0;
    Node * L = head;
    //如果位置范围不合法，直接返回错误的结果
    if (i<1 || i>head->value)return false;
    while (j < i - 1) 
    {
        L = L->next;
        ++j;
    }
    L->next = L->next->next;
    return true;
}

根据值进行删除

/*按照值进行删除，如果标志位n=0，表示删除第一次出现的那个位置的值如果n=1.就是要删除所有的该值*/
bool  ListDelete_data(Node * & head,Elemtype value,int n)
{
    //我们先找到我们需要删除的那个结点的位置，
    //然后调用del_by_index函数
    int flag = 0;
    int j = 0;
    Node *L = head;
    //遍历整个线性表，删除所有相关结点
    while (L->next) 
    {
        L = L->next;
        ++j;
        if (L->value==value)
        {
            //调用依照下标删除结点的方式。
            ListDelete(head, j);
            //删除了一个，那么当前位置也会往前推一个
            --j;
            flag = 1;
            if (n == 0) break;
        }
    }
    if (flag == 0)return false;
    return true;
}

连接两个链表(有序)

//方法一:根据长度进行约束
void Connect_two_List(Node * a, Node * b, Node * c) 
{
    //连接链表的长度为两个链表长度和
    c->value = a->value + b->value;
    int a_value, b_value;
    a_value = a->value;
    b_value = b->value;

    int i = 1;
    int j = 1;
    int k = 1;
    struct Node * p_a = a->next;
    struct Node * p_b = b->next;
    while (i <= a_value && j <= b_value)
    {
        //cout << p_a->value << " " << p_b->value << endl;
        if (p_a->value < p_b->value) 
        {
            ++i;
            Listinsert(c, k, p_a->value);
            ++k;
            p_a = p_a->next;
        }
        else if (p_a->value > p_b->value) 
        {
            ++j;
            Listinsert(c, k, p_b->value);
            ++k;
            p_b = p_b->next;
        }
        else 
        {
            ++j;
            ++i;
            Listinsert(c, k, p_b->value);
            --c->value;
            ++k;
            p_b = p_b->next;
            p_a = p_a->next;

        }
    }
    while (i <= a_value) 
    {
        ++i;
        Listinsert(c, k, p_a->value);
        ++k;
        p_a = p_a->next;
    }
    while (j <= b_value) 
    {
        ++j;
        Listinsert(c, k, p_b->value);
        ++k;
        p_b = p_b->next;
    }
}
//方法二:根据是否为空指针进行约束
void Connect_two_List(Node * a, Node * b, Node * c) 
{
    struct Node * p_a = a->next;
    struct Node * p_b = b->next;
    struct Node * p_c=c=a;//把a的头结点作为c的头结点
    while(p_a&&p_b)
    {
        if(p_a->value<=p_b->value)
        {
            p_c-next=p_a;
            p_c=p_a;
            p_a=p_a->next;
        }
        else
        {
            p_c->next=p_b;
            p_c=p_b;
            p_b=p_b->next;
        }
    }
    p_c->next=p_a?p_a:p_b;//插入剩余段
    free(b);//释放b的头结点
}

补充链表排序

冒泡排序(不交换节点只交换数据域)(O(n*n))

//线性表的排序,采用冒泡排序,直接遍历链表
void Listsort(Node* & head) 
{
    int i = 0;
    int j = 0;
    //用于变量链表
    Node * L = head;
    //作为一个临时量
    Node * p;
    Node * p1;
    //如果链表为空直接返回
    if (head->value == 0)return;

    for (i = 0; i < head->value - 1; i++) 
    {
        L = head->next;
        for (j = 0; j < head->value - i - 1; j++) 
        {
            //得到两个值
            p = L;
            p1 = L->next;
            //如果前面的那个比后面的那个大，就交换它们之间的是数据域
            if (p->value > p1->value) 
            {
                Elemtype temp = p->value;
                p->value = p1->value;
                p1->value = temp;
            }
            L = L->next;
        }
    }
}

先存入数组排序后再放回链表(O(nlog(n)))

void Listsort_1(Node* & head)
{
    int i = 0;
    int j = 0;
    //用于变量链表
    Node * L = head;
    //如果链表为空直接返回
    if (head->value == 0)return;
    Elemtype * copy = new Elemtype[head->value];
    //变量链表，存放数组
    for (i = 0; i < head->value; i++) 
    {
        L = L->next;
        copy[i] = L->value;
    }
    //调用STL中的sort函数
    sort(copy, copy + head->value);
    L = head;
    //存放回链表中
    for (i = 0; i < head->value; i++) 
    {
        L = L->next;
          L->value= copy[i];
    }
}

交换节点(需要分是否相邻)

/*排序时候的代码，切记交换结点都是前后结点交换，所以交换完成后，L就已经被移动到下一个结点了，故不要再执行：L=L->next*/
//参数为头结点和需要交换的两个结点的位置（起点为1）
void swap_node(Node * & head,int i,int j) 
{
    //位置不合法
    if (i<1 || j<1 || i>head->value || j >head->value)
    {
        cout << "请检查位置是否合法" << endl;
        return;
    }
    //同一个位置不用交换
    if (i == j)
    {
        return;
    }
    //相邻两个交换比较简单
    if (abs(i - j) == 1) 
    {
        //位置靠前的那个结点的前一个结点
        Node * pre;
        if (i < j)
            pre = getitem(head, i);
        else
            pre = getitem(head, j);

        //保存第一个结点
        Node * a = pre->next;
        //保存第二结点
        Node * b = a->next;
        //改变pre下一个结点的值
        pre->next = b;
        //必须先把b的下一个结点值给a先
        a->next = b->next;
        //让b的下一个结点等于a
        b->next = a;
        return;
    }
    //第一个结点前一个结点
    Node * a = getitem(head, i);
    //第二个结点的前一个结点
    Node * b = getitem(head, j);
    //第一个结点
    Node * p = a->next;
    //第二个结点
    Node * q = b->next;
    //第一个结点的下一个结点
    Node * p_next = p->next;
    //第二结点的下一个结点
    Node * q_next = q->next;
    //a的下一个结点指向第二个结点q
    a->next = q;
    //第二结点的下一个结点指向第一个结点的下一个结点
    q->next = p_next;
    //b的下一个结点指向第一个结点p
    b->next = p;
    //第一个结点的下一个结点指向第二个结点的下一个结点
    p->next = q_next;
}
//线性表的排序，交换结点
void Listsort_Node(Node* & head) 
{
    int i = 0;
    int j = 0;
    //用于变量链表
    Node * L = head;
    //作为一个临时量
    Node * p;
    Node * p1;
    //如果链表为空直接返回
    if (head->value == 0)return;
    int flag = 0;
    cout << head->value << endl;
    for (i = 0; i < head->value - 1; i++)
    {
        L = head->next;
        for (j = 0; j < head->value - 1 - i; j++) 
        {
            //如果我们交换了结点，那么我们就已经在交换结点的时候，把L移动到下一个结点了，所以不要
            //再执行：L = L->next;，否则会报错的
            if (L->value > L->next->value) 
            {
                flag = 1;
                swap_node(head, j + 1, j + 2);
            }
            if (flag == 1) 
            {
                flag = 0;
            }
            else 
            {
                L = L->next;
            }

        }   
    }
}

循环链表

表中最后一个结点的指针域指向头结点, 其操作与线性链表基本一致, 差别在于算法中的循环条件不是p或p->next是否为空,而是他们是否等于头指针,有时常常设立尾指针便于简化操作

双向链表

定义双向链表

typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;

产生空的双向循环链表

void InitList(DuLinkList *L)
{
    *L=(DuLinkList)malloc(sizeof(DuLNode));
    if(*L)
        (*L)->next=(*L)->prior=*L;
    else
        exit(OVERFLOW);
}

销毁双向链表

void DestroyList(DuLinkList *L)
{
    DuLinkList q,p=(*L)->next;//p指向第一个结点
    while(p!=*L)//p没到表头
    {
        q=p->next;
        free(p);
        p=q;
    }
    free(*L);
    *L=NULL;
}

将L重置为空表

void ClearList(DuLinkList L)//不改变L
{
    DuLinkList q,p=L->next;//p指向第一个结点
    while(p!=L)//p没到表头
    {
        q=p->next;
        free(p);
        p=q;
    }
    L->next=L->prior=L;//头结点的两个指针域均指向自身
}

判断是否为空表

Status ListEmpty(DuLinkList L)
{
    if(L->next==L&&L->prior==L)
        return TRUE;
    else
        return FALSE;
}

计算L中数据元素的个数

int ListLength(DuLinkList L)
{
    int i=0;
    DuLinkList p=L->next;
    while(p!=L)
    {
        i++;
        p=p->next;
    }
    return i;
}

判断是否存在第i个元素

Status GetElem(DuLinkList L,int i,ElemType *e)
{
    //当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
    int j=1;
    DuLinkList p=L->next;
    while(p!=L&&j<i)
    {
        p=p->next;
        j++;
    }
    if(p==L||j>i)//第i个元素不存在
        return ERROR;
    *e=p->data;
    return OK;
}

找前驱元素

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{
    DuLinkList p=L->next->next;
    while(p!=L)
    {
        if(p->data==cur_e)
        {
            *pre_e=p->prior->data;
            return TRUE;
        }
        p=p->next;
    }
    return FALSE;
}

找后继元素

Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{
    /*操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义*/
    DuLinkList p=L->next->next;//p指向第二个元素
    while(p!=L)//p没到表头
    {
        if(p->prior->data=cur_e)
        {
            *next_e=p->data;
            return TRUE;
        }
        p=p->next;
    }
    return FALSE;
}

找到特定元素的地址

DuLinkList GetElemP(DuLinkList L, int i) 
{ 
    // 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，
    // 返回NULL
    int j;
    DuLinkList p = L; // p指向头结点
    if (i < 0 || i > ListLength(L)) // i值不合法
        return NULL;
    for (j = 1; j <= i; j++)
        p = p->next;
    return p;
}

插入元素

Status ListInsert(DuLinkList L, int i, ElemType e) 
{
    // 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1
    // 改进算法2.18，否则无法在第表长+1个结点之前插入元素
    DuLinkList p, s;
    if (i < 1 || i > ListLength(L) + 1) // i值不合法
        return ERROR;
    p = GetElemP(L, i - 1); // 在L中确定第i个元素前驱的位置指针p
    if (!p) // p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱)
        return ERROR;
    s = (DuLinkList)malloc(sizeof(DuLNode));
    if (!s)
        return OVERFLOW;
    s->data = e;
    s->prior = p; // 在第i-1个元素之后插入
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    return OK;
}

删除结点

Status ListDelete(DuLinkList L, int i, ElemType *e) 
{
    // 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
    DuLinkList p;
    if (i < 1) // i值不合法
        return ERROR;
    p = GetElemP(L, i); // 在L中确定第i个元素的位置指针p
    if (!p) // p = NULL,即第i个元素不存在
        return ERROR;
    *e = p->data;
    p->prior->next = p->next; // 此处并没有考虑链表头，链表尾
    p->next->prior = p->prior;
    free(p);
    return OK;
}

最后

以上就是无语仙人掌为你收集整理的线性表线性表顺序结构线性表链式结构补充链表排序循环链表双向链表的全部内容，希望文章能够帮你解决线性表线性表顺序结构线性表链式结构补充链表排序循环链表双向链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。