LinearList线性表

线性表的顺序表示
线性表的链式表示

1.线性表

由n (n>=0)个相同类型元素组成的有序集合
	L = (a1,a2,...,ai)

线性表中元素的个数称为线性表的长度
- a1是唯一的“第一个”数据元素“，an是唯一的”最后一个“数据元素
- ai-1为ai的直接前驱，ai+1为ai的直接后继

元素个数有限
数据类型相同
逻辑上具有顺序性

2.线性表的顺序表示

线性表顺序表示的优缺点

- 优点
	- 随机存取
	- 存储密度高
- 缺点
	- 插入&删除时需要移动大量元素
	- 线性表发生较大变化时，难以确定存储空间的容量
	- 存储分配需要连续内存空间，不够灵活

线性表的时间复杂度

最好情况，表尾插入O（1）
最坏情况，表头插入 O（n）
平均情况，移动次数O（n/2）

线性表的时间复杂度为O（n）

3.顺序表代码

结构：

typedef int ElemType;

typedef struct SqList {
    ElemType data[MaxSize];
    int length;
} SqList;
void PrintSqList(SqList L){...}
bool InsertSqList(SqList &L, int pos, ElemType val){...}
bool DelSqList(SqList &L, int pos, ElemType &val){...}
bool GetSqList(SqList L, ElemType num, ElemType &val){...}
int main() {
    SqList L;
    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 3;
    L.length = 3;
    PrintSqList(L);
    //增加
    InsertSqList(L, 2, 99);
    PrintSqList(L);
    //删除
    ElemType DelValue;
    DelValue = DelSqList(L, 2, DelValue);
    PrintSqList(L);
    //查询
    ElemType GetRes;
    GetSqList(L,3,GetRes);
    printf("查询的数字是%d\n",GetRes);
    return 0;
}

全部代码：

#include <stdio.h>

#define MaxSize 50
typedef int ElemType;

typedef struct SqList {
    ElemType data[MaxSize];
    int length;
} SqList;

void PrintSqList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%3d", L.data[i]);
    }
    printf("\n");
}

bool InsertSqList(SqList &L, int pos, ElemType val) {
    if (pos < 1 || pos > L.length + 1) {
        return false;
    }
    if (L.length > MaxSize) {
        return false;
    }
    for (int j = L.length; j >= pos; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[pos - 1] = val;
    L.length++;
    return true;
}

bool DelSqList(SqList &L, int pos, ElemType &val) {
    if (pos < 1 || pos > L.length + 1) {
        return false;
    }
    val = L.data[pos - 1];
    for (int i = pos - 1; i < L.length; i++) {
        L.data[i] = L.data[i + 1];
    }
    L.length--;
    return true;
}

bool GetSqList(SqList L, ElemType num, ElemType &val) {
    for (int i = 0;i<L.length;i++)
    {
        if(L.data[i] == num)
        {
            val = L.data[i];
            return true;
        }
    }
    val = 404;
    return false;
}

int main() {
    SqList L;
    L.data[0] = 1;
    L.data[1] = 2;
    L.data[2] = 3;
    L.length = 3;
    PrintSqList(L);
    //
    InsertSqList(L, 2, 99);
    PrintSqList(L);
    //
    ElemType DelValue;
    DelValue = DelSqList(L, 2, DelValue);
    PrintSqList(L);
    //
    ElemType GetRes;
    GetSqList(L,3,GetRes);
    printf("查询的数字是%d\n",GetRes);
    return 0;
}

4.线性表的链式表示

链式存储：逻辑上相邻的两个元素在物理位置上不相邻

与顺序表相比：

插入和删除不需要移动元素，只需要修改指针
不需要连续的大量内存空间
单个结构体需要存储指针域
不支持随机存取

以下例子为带有头节点的链表

链表节点结构体：

typedef int element_type;
typedef struct Lnode{
    element_type data; //本节点的数据
    struct Lnode *next; //下一个节点的指针
}LNode,*LinkList;
//Lnode为结构体，LinkList为结构体指针

4.1 头插法建立单链表

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode, *LinkList;

void PrintList(LinkList L)
{
    L = L->next;
    while (L != NULL){
        printf("%3d",L->data);
        L = L->next;
    }
}

LinkList HeadInsert(LinkList &L) {
    LinkList newNode; //声明新节点指针
    int x;
    L = (LinkList) malloc(sizeof(LinkNode));//初始化头节点
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        newNode = (LinkList) malloc(sizeof(LinkNode));//分配新节点空间
        newNode->data = x;//新节点赋值
        newNode->next = L->next;
        L->next = newNode;
        scanf("%d",&x);
    }
}

int main() {
    LinkList testHeadInsert;
    HeadInsert(testHeadInsert);
    PrintList(testHeadInsert);
    return 0;
}

4.2 尾插法建立单链表

在尾插法中，需要多用一个指针（LinkList类型）来表示表尾元素的位置，

本实例中，与新节点的指针一同定义

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode, *LinkList;

void PrintList(LinkList L)
{
    L = L->next;
    while (L != NULL){
        printf("%3d",L->data);
        L = L->next;
    }
}

LinkList TailInsert(LinkList &L)
{
    LinkList newNode,pointer; //声明新节点，以及标识表尾的指针
    int x;
    L = (LinkList) malloc(sizeof (LinkNode)); //初始化头节点
    pointer = L; //指针此时指向头节点
    scanf("%d",&x);
    while (x!=9999)
    {
        newNode = (LinkList) malloc(sizeof (LinkNode));//初始化新节点
        newNode->data = x;//新节点赋值
        newNode->next = pointer->next;
        pointer->next = newNode;
        pointer = newNode;//更新指针又重新指向新的表尾
        scanf("%d",&x);
    }
    return L;
}

int main() {
    LinkList testTailInsert;
    TailInsert(testTailInsert);
    PrintList(testTailInsert);
    return 0;
}

4.3 单链表查询（按位置）

LinkList GetElem(LinkList L, int pos) {
    int j = 1;
    LinkList p = L->next;
    if (pos == 0)
        return L;
    if(pos<1){
        return NULL;
    }
    while(p&&j<pos)
    {
        p = p->next;
        j++;
    }
    return p;
}

4.4 单链表查询（按值）

LinkList LocateElem(LinkList L,ElemType val)
{
    LinkList p = L->next;
    while (p!=NULL && p->data !=val)
    {
        p = p->next;
    }
    return p;
}

4.5 插入新节点

bool InsertElem(LinkList L,int pos,ElemType val)
{
    LinkList before = GetElem(L,pos-1); //获取新节点前一个节点的指针
    if (before == NULL)
    {
        return false;
    }
    LinkList newNode;
    newNode = (LinkList)malloc(sizeof (LinkNode));//给新节点分配空间
    newNode->data = val;
    newNode->next = before->next;
    before->next = newNode;
    return true;
}

4.6 删除节点

bool DelElem(LinkList L,int pos)
{
    LinkList before = GetElem(L,pos-1);
    printf("before=%3d\n",before->data);
    if(before == NULL)
    {
        return false;
    }
    LinkList current = before->next; //中间指针变量的创建
    before->next = current->next;
    free(current);
    current = NULL;
    return true;
}

在删除节点的过程中，需要借助一个中间指针变量current来记录此时删除的节点，

因为需要通过current节点访问before节点的后继的后继

5.双向链表

双向链表结构体的定义

typedef int element_type
typedef struct DNode{
    ElemType data; //数据域
    struct DNode *prior; //前驱指针
    struct DNode *next; //后继指针
}DNode,*DinkList;

双链表的结构包括，含有空数据的头指针，以及之后的每一个包含数据的结构体节点。

双链表的一个结构体节点占12个字节的空间

头节点（无数据的节点）只有后继指针，不成为前驱指针指向的对象

5.1双向链表头插法

DLinkList ListHeadInsert(DLinkList &DL)
{
    DNode *s;
    int x;
    DL = (DLinkList)malloc(sizeof(DNode));
    DL->next = NULL;
    DL->prior = NULL;
    scanf("%d",&x);
    while(x!=9999)
    {
        s = (DLinkList)malloc(sizeof(DNode));
        //建立新的数据节点，结构体（指针）
        s->data=x;
        s->next = DL->next;
        if(DL->next != NULL)
        {
            DL->next->prior = s;
        }
        s->prior = DL; //unnecessary own opinion
        DL->next = s;
        scanf("%d",&x);
    }
    return DL;
}

5.2 双向链表尾插法

DLinkList DlistTailInsert(DLinkList &DL)
{
    int x;
    DL = (DLinkList)malloc(sizeof(DNode));
    DNode *s;
    DNode *r = DL;
    DL-> = NULL;
    scanf("%d",&x);
    while(x!=9999)
    {
        s = (DNode*)malloc(sizeof(DNode));
        s->data = x;
        r->next = s;
        s->prior = r;
        r=s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return DL;
}

5.3 双向链表遍历

void PrintDList(DLinkList DL)
{
    DL = DL ->next;
    while(DL != NULL)
    {
        printf("%3d",DL->data);
        DL = DL->next;
    }
    printf("\n");
}

5.4 双向链表插入元素

bool DListFrontInsert(DLinkList DL,int i,element_type)
{
    DLinkList p = *get_element(DL,i-1);
    if (p==NULL)
    {
        return false;
    }
    DLinkList s = (DLinkList)malloc(sizeof(DNode));
    s->data = e;
    s->next = p->next;
    p->next->prior=s;
    p->next = s;
    s->prior = p;
    return true;
}

5.5 双向链表删除元素

bool DListDelete(DLinkList DL,int i)
{
    DLinkList p = *get_element(DL,i-1);
    if(p==NULL)
    {
        return false;
    }
    DLinkList q;
    q = p->next;
    if (q==NULL)
    {
        return false;
    }
    p->next = q->next;
    if(q->next != NULL)
    {
        q->next->prior = p;
    }
    free(p);
    return true;
}

int main() {
    LinkList L;
//    List_HeadInsert(L);
    List_TailInsert(L);
    LNode L1;
    int res;
    L1 = *get_element(L,2);
    res = L1.data;
    printf("%d\n",res);
}

6.LinkList-2019-41

题目

41.(13分) 设线性表L=（a1,a2,a3,…,an）采用带头节点的链表保存，链表结构体定义如下

typedef struct node{
    int data;
    struct node *next;
}NODE;

请设计一个空间复杂度为O(1)并且时间上尽可能高效的算法，重新排列L中的节点，

得到线性表L’=（a1,an,a2,an-1,a3,an-1,…）

给出算法设计基本思想
用C/C++描述算法
说明时间复杂度

设计思想

代码

#include <stdio.h>
#include <stdlib.h>

typedef int element_type;
typedef struct Lnode {
    element_type data;
    struct Lnode *next;
} LinkNode, *LinkList;

void PrintList(LinkList L) {
    L = L->next;
    while (L != NULL) {
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}

LinkList TailInsert(LinkList &L) {
    LinkList newNode, pointer;
    int x;
    L = (LinkList) malloc(sizeof(LinkNode));
    pointer = L;
    scanf("%d", &x);
    while (x != 9999) {
        newNode = (LinkList) malloc(sizeof(LinkNode));
        newNode->data = x;
        newNode->next = pointer->next;
        pointer->next = newNode;
        pointer = newNode;
        scanf("%d", &x);
    }
    return L;
}

//找链表中间节点
void FindMiddle(LinkList L, LinkList &L2) {
    L2 = (LinkList) malloc(sizeof(LinkNode));
    // 双指针法找中间节点
    LinkList pcur, ppre;
    pcur = L->next;
    ppre = L->next;
    while (pcur) {
        pcur = pcur->next;
        //pcur一次向前两个节点，要判断下一个节点是否存在
        if (pcur == NULL) {
            break;
        }
        pcur = pcur->next;
        // 偶数情况下，保证ppre不向前移动
        if (pcur == NULL) {
            break;
        }
        ppre = ppre->next;
    }
    // L2头节点指向后面一半链表
    L2->next = ppre->next;
    //前一半链表断开
    ppre->next = NULL;
}

void reverse(LinkList L2) {
    LinkList r, s, t;
    r = L2->next;
    // 第二段链表为空
    if (r == NULL) {
        return;
    }
    s = r->next;
    //链表只有一个节点
    if (s == NULL) {
        return;
    }
    t = s->next;
    while (t) {
        s->next = r;
        r = s;
        s = t;
        t = t->next;
    }
    s->next = r;
    L2->next->next = NULL;
    L2->next = s;
}

void merge(LinkList L, LinkList L2) {
    LinkList pcur, p, q;
    //pcur始终指向新链表的链表尾
    pcur = L->next;
    p = pcur->next;
    q = L2->next;
    while (p != NULL && q != NULL) {
        //先放后半段链表的一个元素
        pcur->next = q;
        pcur = pcur->next;
        q = q->next;
        //放前一段链表的一个元素
        pcur->next = p;
        pcur = pcur->next;
        p = p->next;
    }
    if (p != NULL) {
        pcur->next = p;
    }
    if (q != NULL) {
        pcur->next = q;
    }
}

int main() {
    LinkList L;
    LinkList search;
    TailInsert(L);
    PrintList(L);
    LinkList L2;
    FindMiddle(L, L2);
    printf("--------FindeMiddle--------\n");
    PrintList(L);
    PrintList(L2);
    printf("--------reverse--------\n");
    reverse(L2);
    PrintList(L);
    PrintList(L2);
    printf("--------merge--------\n");
    merge(L,L2);
    PrintList(L);
    return 0;
}

测试结果

/Users/uichuan/Documents/library/DataStructure/codes/LinkList_example01/cmake-build-debug/LinkList_example01
1 2 3 4 5 9999
  1  2  3  4  5
--------FindeMiddle--------
  1  2  3
  4  5
--------reverse--------
  1  2  3
  5  4
--------merge--------
  1  5  2  4  3

Process finished with exit code 0

/Users/uichuan/Documents/library/DataStructure/codes/LinkList_example01/cmake-build-debug/LinkList_example01
1 2 3 4 5 6 9999
  1  2  3  4  5  6
--------FindeMiddle--------
  1  2  3
  4  5  6
--------reverse--------
  1  2  3
  6  5  4
--------merge--------
  1  6  2  5  3  4

Process finished with exit code 0

时间复杂度

O(1)

原文地址：http://www.cnblogs.com/uichuan/p/16923173.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性

p1.线性表

LinearList线性表

1.线性表

2.线性表的顺序表示

3.顺序表代码

4.线性表的链式表示

4.1 头插法建立单链表

4.2 尾插法建立单链表

4.3 单链表查询（按位置）

4.4 单链表查询（按值）

4.5 插入新节点

4.6 删除节点

5.双向链表

5.1双向链表头插法

5.2 双向链表尾插法

5.3 双向链表遍历

5.4 双向链表插入元素

5.5 双向链表删除元素

6.LinkList-2019-41

题目

设计思想

代码

时间复杂度

排行榜展示

3D打印机glb模型下载-机械glb模型

树glb模型下载-树2

水稻glb模型下载-水稻1

变电箱1glb模型下载-机械glb模型

树glb模型下载-树3

模型

树glb模型下载-树2

变电箱1glb模型下载-机械glb模型

3D打印机glb模型下载-机械glb模型

树glb模型下载-树3

水稻glb模型下载-水稻1

树glb模型下载-树1

p1.线性表

LinearList线性表

1.线性表

2.线性表的顺序表示

3.顺序表代码

4.线性表的链式表示

4.1 头插法建立单链表

4.2 尾插法建立单链表

4.3 单链表查询（按位置）

4.4 单链表查询（按值）

4.5 插入新节点

4.6 删除节点

5.双向链表

5.1双向链表头插法

5.2 双向链表尾插法

5.3 双向链表遍历

5.4 双向链表插入元素

5.5 双向链表删除元素

6.LinkList-2019-41

题目

设计思想

代码

时间复杂度

排行榜展示

标签

模型