数据结构线性表

基本数据结构-线性表

Macre算法系列笔记是综合严卫敏《数据结构（c语言版）》书籍，以及考研408辅导讲义–王道408计算机考研的内容上，结合罗永浩《算法竞赛》内容，加强编码能力和解决问题的实践能力。感谢以上所提及的个人和机构对计算机教学领域做出的杰出贡献。（应该在有一定编程语言和调试能力下尽量去coding和调试！）。

可以作为数据结构与算法课程的实验去copy本内容代码！

先记录基本数据结构具体内容，算法应用在最后！

一、线性表基本定义

一个数据结构包含逻辑结构、存储结构以及作用在元素上的方法。

（1）逻辑结构

线性表（linear line）是最简单的数据结构。非空表记为D＝（a1, a2 , …, ai-1, ai , …, an)。用数学表达式表示为：
D = { a i ∣ a i ∈ T , i = 1 , 2 , . . . , n , n ≥ 0 } D=\,\,\left\{ ai|ai∈T,i=1,2,…,n,n≥0 \right\} D={ ai∣ai∈T,i=1,2,…,n,n≥0}

其是一个有限序列，表中每个表项都是相继排列的，每两个相邻表象都有直接前驱和直接后继关系，也就是说，线性表中仅存在唯一的一个表头（haed）、唯一的一个表尾（tail）。这表明表中数据之间的关系是线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1, ai)，即ai-1是ai的前驱， ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。
R ＝ { < a i − 1 , a i > ∣ a i − 1 , a i ∈ D , i = 2 , . . . , n } R\text{＝}\left\{ <a_{i-1},a_i>|a_{i-1},a_i∈D,i=2,…,n \right\} R＝{ <ai−1,ai>∣ai−1,ai∈D,i=2,…,n}

（2）存储结构

主要是顺序存储和链式存储。

顺序存储：逻辑上相邻的元素在物理位置上也相邻。

链式存储：逻辑与物理存储位置无关。

（3）作用在次数据结构上的操作：

一个线性表内：元素的增加、删除、查找等；

线性表之间：合并、比较等

二、顺序存储的线性表- 顺序表 SQlist

#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype; 
typedef int Status;

2.1 静态数组

#define Maxsize 20
typedef int Status; 
// 静态数组
typedef struct Sqlsit
{
    /* data */
     Elemtype data[Maxsize];
     int length;
}Sqlist;

2.2 动态数组

typedef struct 
{
    /* data */
    Elemtype *elem;
    int length;
    int size;
}Sqlist;

2.3 方法

函数具体说明看函数里第一行注释！对于动态的！

Sqlist initSqlist()
{
    // 初始化函数
    Sqlist L;
    L.elem = (Elemtype *)malloc(Maxsize*sizeof(Elemtype));
    if (!L.elem)
    {
        printf("初始化失败！");
        exit(0);
    }
    L.length = 0;
    L.size = Maxsize;
    return L;
}

Status creatList(Sqlist *L,int n)
{
     // 
    if(n < 0) return 0;
    if (n > L->size)
    {
        Elemtype *new = (Elemtype *)realloc(L->elem,L->size*2*sizeof(Elemtype));
        L->elem = new;
        L->size *=2;
    }
    for (int i = 0; i < n; i++)
    {
        // 用空白符结尾时，scanf会跳过空白符去读下一个字符，scanf在之前只读了10个数给数组初始化，后面必须多读一个数来作为结束信号，所以你必须再输入一个数。
        // 删除空格符号就可以
        scanf("%d",&L->elem[i]);
        L->length++;
    }
    return 1;
}

void displayTable(Sqlist t)
{
    // 打印展示 for循环打引
    for (int i = 0; i < t.length; i++)
    {
        printf("%d ",t.elem[i]);
    }
    printf("\n");
}

Status listinsert(Sqlist *L,int i,Elemtype x)
{
    // 插入 插入后整体往后移动一位。 L->elem[j+1] = L->elem[j];后一个等于其前一个。
    if (L->length>=L->size)
    {
        Elemtype *new = (Elemtype *)realloc(L->elem,sizeof(Elemtype)*L->size*2);
        L->size *= 2;
    }
    if (i < 0 || i > L->length)
    {
        printf("请输入合法的位置！");
        return 0;
    }
    for (int j = L->length-1; j >= i-1 ; j--)
    {
        L->elem[j+1] = L->elem[j];
    }
    L->elem[i-1] = x;
    L->length+=1;
    return 1;
}

Status Listclear(Sqlist *L)
{
    //清零
    //将length变为零后就没有办法通过length访问元素，相当于上进行清零的操作。
    L->length = 0;
    return 1;    
}

Status ListDestory(Sqlist *L)
{
    // 销毁一个顺序表
    free(L->elem);
    //释放后的无效指针必须置为空，不然会导致内存泄漏
    L->elem =NULL;
    L->length = 0;
    L->size = 0;
}

int ListLength(Sqlist L){
    // 获取长度
    return L.length;
}

Status ListEmpty(Sqlist L)
{
    // 判空
    if (L.length == 0) return 1;
    else return 0;
}

Status GetElem(Sqlist L,int i,Elemtype *e)
{
    if (i <= 0 || i >L.length) return 0;
    // *e = L.elem[i-1];
    e = *(L.elem +i -1);
    return 1;
    
}

Status ListDelete(Sqlist *L,int i,Elemtype *e)
{
    if (i<1 || i> L->length) return 0;
    // 取这个位置上的指针
    Elemtype *p  = &(L->elem[i-1]);
    e= *p;
    // 取尾元素的指针
    Elemtype *q = L->elem+L->length-1;
    for (++p; p<=q; p++)
    {
        *(p-1) = *p;
    }
    --L->length;
    return 1;
}

Status cmp(Elemtype a,Elemtype b)
{
    if (a == b) return 1;
    return 0;
}

int LocateElem(Sqlist L,Elemtype *e, Status (*cmp)(Elemtype,Elemtype))
{
    // 找到与e相同的第一个元素，
    int i  =1;
    Elemtype *p = L.elem;
    while (i <= L.length && !(*cmp)(*p++,*e)) ++i;
    if (i < L.length) return i;
    return 0;
}

void Union_1(Sqlist *L1,Sqlist L2)
{
    int L1_len =L1->length , L2_len = ListLength(L2);
    Elemtype *e;
    
    for (int i = 1; i <= L2.length; i++)
    {
        /* code */
        // GetElem(L2,i,e);
        e = L2.elem+i-1;
        
        if (!LocateElem(*L1,e,cmp)) listinsert(L1,++L1->length,*e);
    }
     
}

// void MergeList(Sqlist L1,Sqlist L2,Sqlist *L3)
// {
//     // *L3 = initSqlist();
//     int i= 1,j =1,k =0;
//     int len1 = ListLength(L1),len2 = ListLength(L2);
//     Elemtype *a,*b;
//     while ((i <= len1)&&(j <= len2))
//     {
//         a = L1.elem+i-1;
//         b = L2.elem+j-1;
//         if (*a <= *b)
//         {
//             listinsert(L3,++k,*a);
//             ++i;
//         }else{
//             listinsert(L3,++k,*b);
//             ++j;
//         }    
//     }
//     while (i<=len1)
//     {
//         a = L1.elem+i-1;
//         listinsert(L3,++k,*a);
//         ++i;
//     }
//     while (j<=len2)
//     {
//         b = L2.elem+j-1;
//         listinsert(L3,++k,*b);
//         ++j;
//     }
//     L3->length-=1;
// }

void MergeListSq(Sqlist L1,Sqlist L2,Sqlist *L3)
{
    Elemtype *p1 = L1.elem,*p2 = L2.elem;
    L3->length = L1.length+L2.length;
    L3->size = L3->length;
    L3->elem = (Elemtype *)malloc(L3->size*sizeof(Elemtype));
    Elemtype *P3 = L3->elem;
    if (!L3->elem) exit(0);
    Elemtype *p1_e = L1.elem+L1.length-1,*p2_e =L2.elem+L2.length-1;
    while (p1 <= p1_e && p2 <= p2_e)
    {
        if (*p1 < *p2) *P3++ = *p1++;
        else *P3++ = *p2++; 
    }
    while (p1 <= p1_e) *P3++ = *p1++;
    while (p2 <= p2_e) *P3++ = *p2++;
}

可以在main里调用和测试方法；

// 上面加上
int main()
{
    Sqlist L = initSqlist();
    Sqlist L1 = initSqlist();
    Sqlist L3 = initSqlist();
    int a[5] ={1,3,5,7,9};
    int b[5] = {2,4,6,8,10};
    
    // 用两个数组初始化线性表；
    for (int i = 1; i <= 5; i++)
    {
        /* code */
        L.elem[i-1] = a[i-1];
        L.length++;
    }
    for (size_t i = 1; i <= 5; i++)
    {
        L1.elem[i-1] = b[i-1];
        L1.length++;
    }
    
    // 方法
    displayTable(L);
    displayTable(L1);
    MergeListSq(L,L1,&L3);
    
}

三、链式存储的线性表-单链表 Linklist

3.1 静态链表

![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传]

#include <stdio.h>
#define Maxsize 1000

typedef int Elemtype;

typedef struct{
    Elemtype data;
    int cur; // 游标 指示下一个
}node,SlinkList[Maxsize];


int main()
{
    
    return 0;
}

3.2 动态链表

#include <stdio.h>
typedef int Elemtype;
typedef int Status;
typedef struct 
{
    Elemtype data;
    struct LNode *next;

}LNode,*Linklist;

3.3 方法

void List_headInsert(Linklist *L)
{
    // 头插法建立单链表 带头结点
    // 传入的是一个指向指针变量的指针
    LNode *s; Elemtype x;
    (*L) = (Linklist)malloc(sizeof(LNode));
    (*L)->next = NULL;
    scanf("%d",&x);
    while (x!= 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = (*L)->next;
        (*L)->next = s;
        scanf("%d",&x);
    }
}

void List_tailInsert(Linklist *L)
{
    // 尾插法建立单链表 带头结点
    Elemtype x;
    (*L) = (Linklist)malloc(sizeof(LNode));
    LNode *s,*r = (*L);
    scanf("%d",&x);
    while (x!=9999)
    {
        s = (Linklist)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
}

LNode *Getelem_ID(LNode L,int i)
{
    // 按序号查找
    if (i<1) return NULL;
    int j = 1;
    LNode *p = L.next;
    while (p!= NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}

LNode *Getelem_V(LNode L,Elemtype x)
{
    // 指向首元素
    LNode *p = L.next; 
    while (p!= NULL && p->data != x) p = p->next;
    return p;
}

void showList(LNode L)
{
    Linklist j = L.next;
    while(j)
    {
        printf("%d ",j->data);
        j = j->next;
    }
}

Status ListInsert_L(Linklist *L,int i,Elemtype x)
{
    // 在第i个位置之前插入x；
    Linklist p = *L;
    int j = 0;
    while ( p && j<i-1) { 
        p = p->next;
        ++j;
    }
    if( !p || j >i-1) return 0; //第i个位置的节点不存在
    Linklist s = (Linklist)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return 1;
}

Status ListDelete(Linklist *L,int i,Elemtype *e)
{
    // 删除第i个位置的元素
    Linklist p = *L;
    int j = 0;
    while (p->next && j<i-1)
    {
        p = p->next;
        j++;
    }
    if (!(p->next) || j>i-1) return 0;
    Linklist q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
}

// 有错误
void MergeList(Linklist L1,Linklist L2,Linklist *L3)
{
    Linklist p1 = L1->next, p2 = L2->next;
    Linklist p3 = *L3;
    p3->next = NULL;
    while (p1 && p2)
    {
        if (p1->data <= p2->data)
        {
            p3->next = p1;p3 = p1;p1 = p1->next;            
        }
        else{
            p3->next = p2;p3 = p2; p2 = p2->next;
        }
    }
    p3->next = p1 ? p1 : p2;
}

测试，运行时输入值，输入9999 时推出插入，采用头差，也可以采用尾插。

int main()
{
    Linklist L;
    Linklist L1;
    List_headInsert(&L);
    Linklist k = L->next;
    while(k)
    {
        printf("%d ",k->data);
        k = k->next;

    }
    return 0；
}

四、算法应用

约瑟夫问题

题目：n个人围成一圈，初始编号从1~n排列，从约定编号为x的人开始报数，数到第m个人出圈，接着又从1开始报数，报到第m个数的人又退出圈，以此类推，最后圈内只剩下一个人，这个人就是赢家，求出赢家的编号。

（1）动态链表

#include<bits/stdc++.h>

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

int main(){
    // 处理输入输出
    int n,m;
    scanf("%d %d",&n,&m);
    // 初始化动态链表
    node *head,*now,*p,*prev;
    head = new node;
    head->data = 1; head->next = NULL;
    now = head;
    for (int i = 2; i <= n; i++){
        p = new node; p->data = i; p->next = NULL;
        now->next = p;
        now = p;
    }
    // 循环链表，头尾链接起来
    now->next = head;
   //
   now = head;
   prev = head;
   while((n--)> 1){
    for (int i = 1; i < m; i++){
        prev = now;
        now = now->next;
    }
    printf("%d ",now->data);
    prev->next = now->next;
    delete now;
    now = prev->next;
   }
   // 由于最后一个已经是确定的了，所以只要最后输出一个而不是再循环m次,所以循环只到1；
   printf("%d ",now->data);
   delete now;
   return 0;
}

（2）静态链表

结构体数组单向：

#include <bits/stdc++.h>
const int N = 105; // 要在全局声明

// 结构体数组单向链表
struct node{
    int id,nextid;
}nodes[N];

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    nodes[0].id = 0;nodes->nextid  =1;
    for (int i = 1;i <= n; i++){nodes[i].id = i;nodes[i].nextid = i+1;}
    nodes[n].nextid =1;
    int now=1;int prve = 1;
    while((n--) >1){
        for (int i = 1; i < m; i++){
            prve = nodes[now].id;
            now = nodes[now].nextid;
        }
        printf("%d ",nodes[now].id);
        nodes[prve].nextid = nodes[now].nextid;
        now = nodes[prve].nextid;
    }
    printf("%d ",nodes[now].id);
    return 0;
}

结构体数组双向：

#include<bits/stdc++.h>
const int N = 105;
struct node
{
    int id;
    // int data;
    int preid,nextid;
}nodes[N];

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    nodes[0].nextid=1;
    for (int i = 1; i <= n; i++){
        nodes[i].id= i;
        nodes[i].preid = i-1;
        nodes[i].nextid = i+1;
    }
    nodes[1].preid = n;
    nodes[n].nextid = 1;
    int now = 1;
    int prev,nextv;
    while ((n--)>1){
        for (int i = 1; i < m; i++) now = nodes[now].nextid;
        printf("%d ",nodes[now].id);
        prev = nodes[now].preid;
        nextv = nodes[now].nextid;
        nodes[prev].nextid = nodes[nextv].id;
        nodes[nextv].preid = nodes[prev].id;
        now = nextv;
    }
    printf("%d ",nodes[now].id);
    return 0;
    
}

数组单向链表：

#include<bits/stdc++.h>

int A[150];

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i < n ; i ++) A[i] = i+1;
    A[n] = 1;
    int now =1;int prev = 1;
    while ((n--)>1){
        for(int i = 1;i < m; i++){
            prev = now;
            now = A[now];
        }
        printf("%d ",now);
        A[prev] = A[now];
        now = A[prev];
    }
    printf("%d ",now);
    return 0;
    
}

（3）STL list

以后更新博客！

s[now].nextid;
nodes[prev].nextid = nodes[nextv].id;
nodes[nextv].preid = nodes[prev].id;
now = nextv;
}
printf("%d ",nodes[now].id);
return 0;

}

数组单向链表：

~~~C++
#include<bits/stdc++.h>

int A[150];

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i < n ; i ++) A[i] = i+1;
    A[n] = 1;
    int now =1;int prev = 1;
    while ((n--)>1){
        for(int i = 1;i < m; i++){
            prev = now;
            now = A[now];
        }
        printf("%d ",now);
        A[prev] = A[now];
        now = A[prev];
    }
    printf("%d ",now);
    return 0;
    
}

（3）STL list

以后更新博客！

基本数据结构-线性表

一、线性表基本定义

二、顺序存储的线性表- 顺序表 SQlist

2.1 静态数组

2.2 动态数组

2.3 方法

三、链式存储的线性表-单链表 Linklist

3.1 静态链表

3.2 动态链表

3.3 方法

四、算法应用

约瑟夫问题

（1）动态链表

（2） 静态链表

（3）STL list

（3）STL list

（2）静态链表