专栏首页开心的学习之路线性结构------线性表(二)

线性结构------线性表(二)

    如果要对链表进行插入删除操作,用顺序结构需要找到目标位置然后移动大量元素,复杂度为O(n),此时就需要考虑线性表的链式存储结构。

    链式线性表由n个结点通过指针域连接而成。最简单的链表为单链表。如图:

单链表的抽象数据类型描述:

数据对象集合:

       {a1,a2,a3,... ,an},每个元素类型为DataType,除了a1和an外每个元素都只有一个前驱元素一个后继元素,数据元素之间的关系是一对一

基本操作集合:

(1)void InitList(LinkList *L):初始化单链表L。

(2)void Insert(LinkList *L, int i, DataType e):把元素e插入到单链表L的第i个位置。

(3)int ListLength(LinkList *L):返回单链表L的长度。

(4)void Delete(LinkList *L, int i, DataType *e):删除链表中位置i的元素,保存到e中。

(5)DataType GetElem(LinkList *L, int i):返回链表中第i个位置的元素。

(6)int LocateElem(LinkList L, DataType e):返回链表中第一个与e相同的元素的下标。

(7)void DestroyList(LinkList *L):摧毁单链表。

代码:

PS:下面代码没有下标0,头结点在main函数中malloc

#include <cstdio>  
#include <cstdlib>  
  
typedef int DataType;  
  
struct LinkList  
{  
    DataType data;  
    struct LinkList *next;  
};  
  
//初始化单链表(将头结点的指针域设置为空,数据域设置为0,数据域代表链表长度)   
   
void InitList(LinkList *L)  
{  
    L->next = NULL;  
    L->data = 0;  
    return;  
}  
  
int ListLength(LinkList *L)   
{  
    return L->data;  
}  
  
void Insert(LinkList *L, int i, DataType e)  
{  
    LinkList *p, *q;  
    p = L;  
    int len = L->data;     
    //i最大为链表长度+1(插到末尾),最小为1       
    if(i > len + 1 || i < 1)  
        printf("Wrong place!\n");         
    //将指针p移动到i的前一个位置   
    for(int j = 1; j < i;j++)  
    {  
        p = p->next;   
    }  
    //找到位置后,新建一个结点,数据域为e   
    q = (LinkList*)malloc(sizeof(LinkList));  
    q->data = e;  
    q->next = p->next;  
    p->next = q;  
    L->data++;  
    return;  
}  
  
DataType GetElem(LinkList *L, int i)  
{  
    LinkList *p;  
    p = L->next;  
    for(int j = 1; j < i; j++)  
    {  
        p = p->next;  
    }  
    return p->data;  
}   
  
int LocateElem(LinkList *L, DataType e)  
{  
    LinkList *p;  
    int i = 1;  
    p = L->next;  
    while(p->data != e && i < L->data)  
    {  
        p = p->next;  
        i++;  
    }  
    if(p->data == e)
	{
    	return i;  
	} 
    if(i == L->data)  
    {  
        printf("No such element!\n");  
        return -1;  
    }  
}  
  
void Delete(LinkList *L, int i, DataType *e)  
{  
    if(i < 1 || i > L->data)  
    {  
        printf("Wrong place!\n");  
        return;  
    }  
    if(L->data == 0)  
    {  
        printf("List is empty!\n");  
        return;  
    }  
    LinkList *p, *q;  
    p = L;  
    //p移动到要删除位置的前面   
    for(int j = 1; j < i; j++)  
    {  
        p = p->next;  
    }  
    //要删除元素赋值给q   
    q = p->next;  
    *e = q->data;  
    //如果q的下一位存在   
    if(q->next)  
    {  
        p->next = q->next;   
    }   
    else  
        p->next = NULL;  
    free(q);  
    L->data--;  
    return;  
}  
  
void PrintList(LinkList *L)  
{  
    for(int i = 1; i <= L->data; i++)  
        printf("%d ", GetElem(L, i));  
    printf("\n");  
}   
  
//销毁链表,包括头结点 
void DestroyList(LinkList *L)  
{  
    LinkList *p;  
    while(L)  
    {  
        p = L;  
        L = L->next;  
        free(p);  
    }  
    return;  
} 
 
//测试代码
int main()  
{  
    LinkList *L = (LinkList*)malloc(sizeof(LinkList));  
    InitList(L);  
    for(int i = 0; i <= 10; i++)  
        Insert(L, i + 1, i);  
    DestroyList(L);  
    InitList(L);  
    Insert(L, 0, 1);  
    Insert(L, 2, 2);  
    Insert(L, 1, 100);  
    PrintList(L);  
    int locate = LocateElem(L, 600);  
    printf("Element 6's place: %d\n", locate);  
    printf("%d\n", L->data);  
    DataType delete_e;  
    Delete(L, 2, &delete_e);  
    PrintList(L);  
    printf("%d\n", L->data);  
    DestroyList(L);  
    printf("%d",GetElem(L, 1));  
    return 0;  
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基础练习 数列排序

      第一行为一个整数n。   第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    刘开心_1266679
  • 基础练习 阶乘计算

      n!可能很大,而计算机能表示的整数范围有限,需要使用高精度计算的方法。使用一个数组A来表示一个大整数a,A[0]表示a的个位,A[1]表示a的十位,依次类推...

    刘开心_1266679
  • 线性表------链栈

    链栈的存储结构其实就是单链表,插入和删除在链表头进行(书上这么写,个人认为只要是在链表一端操作即可)。

    刘开心_1266679
  • 详解Android 获取手机中微信聊天记录方法

    首先我们要知道,微信的聊天记录一般是不提供给我们获取的,所以一般情况下我们手机没root的话就拿不到了。就算是root后的手机,想要获取微信的EnMicroMs...

    砸漏
  • php实现命令行里输出带颜色文字

    今天执行composer的时候看到命令窗口出现的提示里面有的关键性部分带有颜色,于是很好奇研究了一下,在这里记录下来

    码缘
  • 2020-10-22OpenCV 获取摄像头并显示摄像头视频

    结合Leaning OpenCV 第二个例子 显示一个视屏文件 写了一下 获取摄像头的代码为并且创建窗口显示的代码为:

    爱笑的架构师
  • 环形颜色分布直方图

    package com.imageretrieval.features; import java.util.ArrayList; import java.ut...

    Venyo
  • 币聪财经:upbit加速上市IOTA,Trinity桌面钱包Beta即将面世

    IOTA项目在8月上半月取得了一些突破的发展,推出了IOTA Hub并调整了Trinity桌面钱包。

    币聪财经
  • Hadoop+Hbase集群数据迁移问题

    我是攻城师
  • Python终端输出打印彩色字体的方法

    一  实现过程 终端的字符颜色是用转义序列控制的,是文本模式下的系统显示功能,和具体的语言无关。    转义序列是以ESC开头,即用\033来完成(ESC的A...

    用户1214487

扫码关注云+社区

领取腾讯云代金券