数据结构-线性表

2023-03-17

顺序表：

  1. 顺序表的创建，初始化 InitList（Sqlist &L）

#include<stdio.h>
#define maxsize 10
//顺序表的创建（静态分配）
typedef struct {
    int data[maxsize];
    int length;
}Sqlist;

void Initlist (Sqlist &L) 
{
    for (int i = 0; i < maxsize; i++) 
    {
        L.data[i] = 0;
        L.length = 0;
    }

}
int main()
{
    Sqlist L;
    Initlist(L);
return 0；
}

  1. 动态分配：创建；初始化；增加空间IncreaseSize

#include<stdlib.h>
#define initsize 10

typedef struct {
    int* data;
    int maxsize;
    int length;
}Sqlist;

void Initlist(Sqlist &L)
{
    L.data = (int*)malloc(initsize * sizeof(int));
    L.length = 0;
   L.maxsize = initsize;
}

void IncreaseSize(Sqlist& L, int a) 
{
   int* p = L.data;
   L.data = (int*)malloc((L.maxsize + a) * sizeof(int));
   for (int i = 0; i < L.maxsize; i++)
         L.data[i] = p[i];
   L.maxsize = L.maxsize + a;
    free(p);
}

  1. 顺序表的插入（静态）：ListInserrt（）在第i个位置（位序）插入元素e；

bool Listinsert(Sqlist& L, int i, int e) 
{
    //合法性检测：i<1;i>length+1[当前尾部]l;i>maxsize;
    if (i<1 || i>L.length + 1)
        return false;
    if (i > maxsize)
        return false;
    //从当前最后一个元素开始，每个元素往后移；
    for (int j = L.length; j <= i; j--)
        L.data[j + 1] = L.data[j];
    L.data[i] = e;
    L.length++;
    return true;
}

  1. 顺序表的删除；ListDelect；在第i个位置的元素删除，并用e来返回该元素的值；

bool Listinsert(Sqlist& L, int i, int& e)
{
    if (i<1 || i>L.length + 1)
        return false;
    if (i > maxsize)
        return false;
    e = L.data[i];
    for (int j = i; j <= L.length; j++)
        L.data[i] = L.data[i + 1];
    L.length--;
    return true;
}

5.按位查找LocateElem（Sqlist L，int e）（返回其元素值）；

按值查找GetElem（Sqlist L ,int e）（返回其位序）

int GetElem(Sqlist L, int e)
{
    return L.data[e];
}
//按值查找；
int LocateElem(Sqlist L, int e)
{
    for (int i = 1; i <= L.length; i++)
    {
        if (L.data[i] == e)//char/string类型用strcmp（）；struct类型分别判断成员变量；
        return i;
    }
    return 0;
}

——————

链式结构：单链表；

1.单链表的定义；typedef struct LNode

数据域；int data; 指针域；struct* next;

结构体变量；LNode,*LinkList;(结点和头指针)

//定义单链表
typedef struct LNode {
    int data;
    struct LNode* next;
}LNode,*LinkList;

  1. 单链表的初始化；带头结点和不带头结点；

//无结点初始化；
bool InitList(LinkList& L)
{
    L = NULL;
    return true;
}
//有结点初始化;
bool InitList(LinkList& L) 
{
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL)//防止内存不足
    return false;
    L->next = NULL;
    return true;
}

  1. 单链表的插入和删除

在第i个结点插入一个数据e；（带头结点）

//有头结点的插入；
bool ListInsert(LinkList& L1, int i, int e)
{
    if (i < 1)
        return false;
    int j = 0;
    LNode* p;//p指针用于扫描结点
    p = L1;//从头结点开始
    for (j = 0; p != NULL && j != i - 1; j++)//保证p扫描的不是空结点；合法性
    {
        p = p->next;
    }
    if (p == NULL)//合法性检测
        return false;
    LNode* s=(LNode*)malloc(sizeof(LNode));//创建结点p
    s->data = e;//存放数据
    s->next = p->next;//（该点p结点即为i-1结点，连结指针域至i结点）
    p->next = s;//连结i-1结点的指针域至s结点
}

插入：不带头结点；（注意判断i==1的情况，需要改变头指针L）

bool ListInsert(LinkList& L, int i, int e)
{
    if (i < 1)//合法性
        return false;
    if (i == 1)//修改头指针
    {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
    }
    LNode* q;
    q = L;
    for (int j = 1;q!=NULL && j!=i-1; j++)//从结点1开始
    {
        q = q->next;
    }//后序可调用return InsertNextNote(q,e);
    if（q=NULL）
    return false;
    LNode* t = (LNode*)malloc(sizeof(LNode));
    t->data = e;
    t->next = q->next;
    q->next = t;
    return true;
}

指定结点p的后插操作；（注意审题看清楚前插和后插的区别；）

bool InsertNextNote(LNode* p, int e) 
{
    if (p == NULL)//判断结点是否为空
        return false;
    LNode* a = (LNode*)malloc(sizeof(LNode));
    if (a == NULL);
    return false;
    a->data = e;
    a->next = p->next;
    p->next = a;
    return true;
}

指定结点的前插操作：一般采用替换法）

bool InsertPriorNote(LNode* p, int e) 
{
    if (p == NULL)
    return false;
    LNode* t = (LNode*)malloc(sizeof(LNode));
    t->data = e;
    t->next = p->next;
    p->next = t;
    p->data = t->data;//替换数值；
    return true;
}

删除；删除L表中第i个位置的元素，并用e来返回；（找到i-1个结点；定义指针表示i个结点；

i-1到i+1结点的连结）

//删除结点，用e返回，带头结点；
bool ListDelect(LinkList &L,int i,int e)
{
    if (i < 1)
        return false;
    LNode* p = L;
    for (int j = 0; j <= i - 1; j++)
    {
        p = p->next;
    }
    if (p == NULL)//p：第i-1个结点
        return false;
    if (p->next == NULL)
        return false;
    LNode* q = p->next;//q：第i个结点
    e = q->data;
    p->next = q->next;//连结i-1至i+1；
    free(q);
}

指定结点的删除；（极端情况，当q为最后一个结点时，需要从头遍历）

bool DelectNote(LinkList& L, LNode* p, int& e) 
{
    if (p == NULL)
        return false;
    LNode* q = p->next;
    p->data = p->next->data;//q仅为指针，不能写成q.data形式；
    p->next = q->next;
    free(q);
    return true;
}

3.单链表的查找；按位查找GetElem（）：带头结点；返回结点指针LNode*

//按位查找：带头；返回结点指针
LNode* GetELem(LinkList& L, int i) 
{
    if (i < 1)
        return false;
    if (i == 0)
        return L;//头结点
    LNode* q;
    q = L->next;//指向第一个结点
    for (int j = 1; q!=NULL && j < i;j++)
    {
        q = q->next;
    }
    return q;
}

按值查找：

//按值查找：带头；返回结点指针；
LNode* LocateElem(LinkList& L, int &e)
{
    LNode* q;
    q = L->next;
    for (; q != NULL && q->data != e; )
    {
        q = q->next;
    }
    return q;
}

求表长；Length

//求表长；
int Length(LinkList& L)
{

    LNode* q=L;
    int length = 1;
    for (length = 0; q->next!= NULL; length++) 
    {
        q = q->next;
    }
    return length;
}

4.单链表的建立（尾插法（顺向建立），尾插法（逆向建立））（默认为有头结点的情况）

尾插法；

LinkList List_Taillnsert(LinkList& L) 
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode* s = L;//结点指针
    LNode* r = L;//表尾指针
    int x = 0;
    scanf("%d",& x);
    for (; x != 9999;)//设置特殊值用于停止循环：9999
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);//再次输入
    }
    r->next = NULL;//尾结点记得置空
    return L;
}

头插法：

//头插法：//逆向建立单链表
LinkList List_HeadInsert(LinkList& L)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;//防止野指针
    LNode* s;//结点指针
    int x = 0;
    scanf("%d", &x);
    for (; x != 9999;) 
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;//先将s连接至第i个结点
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

双链表：带两个指针域next和prior；

//双链表：定义：
typedef struct DNode {
    int data;
    struct DNode* next;
    struct DNode* prior;//前驱指针
}DNode,*DLinkList;
//初始化；
bool InitDLinkList(DLinkList& L) 
{
    L = (DLinkList)malloc(sizeof(DNode));
    if (L == NULL)
        return false;//内存不足
    L->prior = NULL;//前指针用于指向NULL
    L->next = NULL;
    return true;
}
bool Empty(DLinkList& L)//判空
{
    if (L->next == NULL)//后指针指向空
        return true;
    else
        return false;
}

插入：注意尾结点时不用连接prior；

//双链表的插入，在p结点后插入s结点；
bool InsertNextDNode(DNode* p, DNode* s) 
{
    if (p == NULL || s == NULL)
        return false;
    s->next = p->next;
    if (p->next == NULL)//若p为尾结点（尾插）
    {
        p->next = s;
        s->prior = p;
    }
    p->next->prior = s;//非尾结点时；
    p->next = s;
    s->prior = p;
}

删：

//双链表的删除,删除p结点的后继结点；
bool DelectNextDNode(DNode* p)
{
    if (p == NULL)
        return false;
    if (p->next == NULL)
        return false;
    DNode* q = p->next;
    if (q->next != NULL)//尾结点需要连结prior指针；
    {
        p->next = q->next;
        q->next->prior = p;
    }
    else
        p->next = NULL;//=q.next也是正确的；
    free(q);
}

循环链表（尾结点的next指针连至头结点）

//循环链表；循环单链表定义和初始化；
typedef struct LNode1 {
    int data;
    struct LNode1* next;
}LNode,*LinkList;

bool InitLinkList(LinkList& L) 
{
    L = (LNode1*)malloc(sizeof(LNode1));
    if (L == NULL)
        return false;//内存不足
    L->next = L;//初始化头结点的next指向头结点；
    return true;
}
//循环双链表;
typedef struct DNode1 
{
    int data;
    struct DNode1* next;
    struct DNode1* prior;
}DNode1,*DLinkList;
bool InitDLinkList(DLinkList& L)
{
    L = (DNode1*)malloc(sizeof(DNode1));
    if (L == NULL)
        return false;//内存不足
    L->prior = NULL;
    L->next = L;
    return true;
}

静态链表

相关推荐

随机推荐