线性表算法的实现

Nuyoah2021-07-152022-11-21

以下是顺序表的代码的实现

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20
typedef struct Sqtable
{
    int a[20];
    int length;
}Sq;

void read_Sq(Sq *L)
{
    int n = 0;
    int *p = L->a;
    FILE *fp;
    fp = fopen("date.txt","r");
    while(!feof(fp))
    {
        fscanf(fp, "%d", p);
        p++;
        n++;
    }
    L->length = n;
}
void search(Sq *L)
{
    int a,n;
    printf("请输入要查找的元素: ");
    scanf("%d",&n);
    int *p;
    p = L->a;

    for( a = 0; a < L->length; a++ )
    {
        if( n == *p )
        {
            break;
        }
        p++;
    }
    if( n == *p)
    {
        printf("\n查找成功，在第%d个位置",a+1);
    }
    else
    {
        printf("\n无此元素");
    }
}
int Insearch(Sq *L, int m, int n)
{
    int p, a;
    p = L->length;
    a = p;
    if( n < 1 || n > L->length+1)
    {
        printf("位置错误");
        return 0;
    }
    if( L->length == MAX)
    {
        printf("数据已满");
        return 0;
    }
    for( ; a >= n; a--)
    {
        L->a[p] = L->a[p-1];
        p--;
    }
    L->a[p] = m;
    L->length++;
}
void print(Sq *L)
{
    int *p, n;
    p = L->a;
    for( n = 0;n < L->length; n++)
    {
        printf("%d ", *p);
        p++;
    }
}

int deleteSq(Sq *L, int n)
{
    int a;
    if( n < 1 || n > L->length)
    {
        return 0;
    }
    for( a = n-1; a < L->length-1; a++)
    {
        L->a[a] = L->a[a+1];
    }
    L->length--;
}


int main()
{
    int n , a, b,*p;
    Sq *L;
    L = (Sq*)malloc(sizeof(Sq));
    read_Sq(L);

    search(L);


    printf("\n请输入要插入的元素的数值和位置");
    scanf("%d %d", &a,&b);

    print(L);
    Insearch(L, a, b );
    printf("\n");
    print(L);


    printf("\n请输入要删除的位置");
    scanf("%d", &a);

    deleteSq(L, a);
    print(L);

}

以下是链表的实现

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

typedef struct ChainList
{
    int date;
    struct ChainList *next;
}CL, *List ;

typedef struct DuList
{
    int date;
    struct DuList * prior;
    struct DuList * next;

}DL, *DList;



//销毁链表
void DeleteList(List L);

//判断链表是否为空
int ListEmpty(List L);

// 清空链表
void ClearList(List L);

// 求单链表的表长
int LengthList(List L);

// 创建链表
void CreatList(List L);


// 建立循环链表 使用尾指针q
List * CreatListLoop(List L);



// 取单链表中第i个元素的内容
int GetDate(List L);

// 查找元素i的位置
int SearchDateOne(List L);


// 查找元素i的地址
int * SearchDateTwo(List L);

// 在第i个位置插入元素e
int InsertDate(List L);


// 删除第i个结点
int DeleteDate(List L);

// 循环链表的合并 都是使用尾指针
void AddLoopList(List La, List Lb);

// 双向链表的初始化
void InitDList(DList L);


// 双向链表的建立
void CreateDList(DList L);


// 线性表的合并
int merge1(List La, List Lb, List Lc);

void printTwo(List pa);

void printThree(DList La);

int InsertDuDate(DList L);

int main()
{
    DList La, Lb;

    La = (DList)malloc(sizeof(DL));
    La->prior = NULL;
    La->next = NULL;

    CreateDList(La);

    DeleteDuDate(La);

    printThree(La);
    return 0;
}


// 建立链表,长度为n
void CreatList(List L)
{
    List p,q;

    int n;

    printf("请输入要添加的个数");
    scanf("%d", &n);

    q = L;
    p = L;
    // 尾插法
    for(; n > 0; n--)
    {
        p = (List)malloc(sizeof(CL));
        p->next = NULL;
        scanf("%d", &p->date);

        q->next = p;
        q = p;
    }

    /* //头插法
    int a ;
    for(a = 0; a < n ; a++ )
    {
        p = (List)malloc(sizeof(CL));
        scanf("%d", &p->date);

        p->next = L->next;
        L->next = p;
    }
    */
}

// 建立循环链表 使用尾指针q
List * CreatListLoop(List L)
{
    List q, m;
    int n;
    q = L;
    printf("请输入需要添加元素的个数");
    scanf("%d", &n);

    for(;n>0; n--)
    {
        m = (List)malloc(sizeof(CL));
        scanf("%d", &m->date);
        m->next = NULL;
        q->next = m;
        q = m;
    }

    q ->next = L;
    printf("1");
    return q;
}




//销毁链表
void DeleteList(List L)
{
    List p;
    while(L)
    {
        p = L;
        L = L->next;
        free(p);
    }
}


//判断链表是否为空
int ListEmpty(List L)
{
    if(L->next == NULL)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

// 清空链表
void ClearList(List L)
{
    List p, q;
    p = L->next;
    while(p)
    {
        q = p;
        p = p->next;
        free(q);
    }
    L->next = NULL;
}

// 求单链表的表长
int LengthList(List L)
{
    List p;
    int n = 0;

    p = L->next;
    while(p)
    {
        n++;
        p = p->next;
    }

    return n;
}


// 取单链表中第i个元素的内容
int GetDate(List L)
{
    List p;
    int n = 1, i;

    printf("请输入要查找元素的位置");
    scanf("%d", &i);

    p = L->next;
    while( p && n < i)
    {
        p = p->next;
        n++;
    }
    if( n > i || !p)
    {
        return 0;
    }

    return p->date;


}
//


// 查找元素i的位置
int SearchDateOne(List L)
{
    List p;
    int n = 1, i;

    printf("请输入你要查询的参数的位置");
    scanf("%d", &i);


    p = L->next;

    while(p)
    {
        if( n == i)
        {
            return p->date;
        }
        p = p->next;
        n++;
    }

    return 0;

}

// 查找元素i的地址
int * SearchDateTwo(List L)
{
    List p;
    int n = 1, i;

    printf("请输入你要查询的参数的位置");
    scanf("%d", &i);

    p = L->next;

    while(p)
    {
        if( n == i)
        {
            return p;
        }
        printf("%d\n", p);

        p = p->next;
        n++;
    }
    return p;

}

// 在第i个位置插入元素e

int InsertDate(List L)
{
    List p, q;
    int n = 1,i,e;
    printf("请输入要插入的位置和数据：");
    scanf("%d %d", &i, &e);

    p = L->next;

    while(p && n<i-1)
    {
        p = p->next;
        n++;
    }

    if( n > i-1 || !p)
    {
        return 0;
    }

    q = (List)malloc(sizeof(CL));

    q->date = e;
    q->next = p->next;
    p->next = q;
    return 1;
}

// 删除第i个结点
int DeleteDate(List L)
{
    List p, q;
    int n = 0, i;

    printf("请输入你删除元素的位置");
    scanf("%d", &i);

    p = L;

    while( p && n < i-1 )
    {
        p = p->next;
        n++;

    }
    if( n > i-1 || !(p->next))
    {
        return 0;
    }
    q = p->next;
    p->next = p->next->next;
    free(q);

    return 1;

}


// 循环链表的合并 都是使用尾指针
void AddLoopList(List La, List Lb)
{
    printf("%d\n",La);
    List p, q;
    p = La->next;
    q = Lb->next;
    La->next = q->next;
    Lb->next = p;
    free(q);
}




// 双向链表的建立
void CreateDList(DList L)
{
    DList p, q;
    int a,n;
    printf("请输入要添加的个数");
    scanf("%d", &n);

    p = L;
    for( a = 0; a < n; a++)
    {
        q = (DList)malloc(sizeof(DL));
        scanf("%d", &q->date);
        p->next = q;
        q->prior = p;
        q->next = NULL;
        p = q;
    }

    q->next = L;
    L->prior = q;
}


// 双向链表的插入位置n 数据e
int InsertDuDate(DList L)
{
    int i = 1,n ,e;
    DList p, q;
    p = L->next;

    printf("请输入你要插入的位置和数据");
    scanf("%d %d", &n, &e);

    while(p != L && i < n)
    {
        p = p->next;

        i++;
    }
    if( p == L || i > n )
    {
        return 0;
    }

    q = (DList)malloc(sizeof(DL));
    q ->date = e;



    q->prior = p->prior;
    q->next = p;
    q->prior->next = q;
    p->prior = q;


    return 1;
}

// 双向链表的删除， 删除第n个位置的结点
int DeleteDuDate(DList L)
{
    DList p;
    int i = 1, n;
    p = L ->next ;

    printf("请输入要删除的位置");
    scanf("%d", &n);

    while(p && i < n)
    {
        i++;
        p=p->next;
    }
    if( p == L || i > n)
    {
        return 0;
    }

    p->prior->next = p->next;
    p->next->prior = p->prior;

    free(p);
    return 1;

}

// 线性表的合并
int merge(List La, List Lb, List Lc)
{
    List pa,pb,pc;
    pa = La->next;
    pb = Lb->next;
    Lc = pa;
    pc = Lc;
    while( pa && pb )
    {
        if( pa->date <= pb->date)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa?pa:pb;
    free(Lb);
}




void print(CL *L)
{

    List p;
    p = L->next;
    while( p )
    {
        printf("%d ", p->date);
        p = p->next;
    }

}


void printTwo(List La)
{
    List p;
    p = La->next;
    while(p != La)
    {
        printf("%d\n", p->date);
        p = p->next;
    }
}

void printThree(DList La)
{
    DList p;
    p = La->next;

    while(p != La)
    {
        printf("\n%d\n", p->date);
        p = p->next;
    }
}