天天看点
返回

【数据结构基础笔记】【顺序表】

代码参考《妙趣横生的算法.C语言实现》

文章目录

  • ​​前言​​
  • ​​1、创建顺序表​​
  • ​​2、顺序表插入元素​​
  • ​​3、顺序表删除元素​​
  • ​​4、顺序表实例分析​​
  • ​​1、静态​​
  • ​​2、动态​​
  • ​​5、顺序表总结​​

前言

本章总结：从静态和动态分别进行顺序表的创建、插入、删除、以及实例分析

1、创建顺序表

1、静态地生成一张顺序表

#define MaxSize=100;
ElemType Sqlist[MaxSize];
int len;
//len表示顺序表的长度

2、动态地生成一张顺序表

#define MaxSize 10

typedef int ElemType;   

typedef struct{
    int *elem;      //指向顺序表首地址elem
    int length;     //顺序表中表的长度(元素个数)
    int listsize;   //顺序表的存储空间容量
}Sqlist;
void initSqlist(Sqlist* L)
{
    L->elem = (int*)malloc(MaxSize*sizeof(ElemType));   //开辟内存，并将该段空间首地址赋值给L->elem
    if (!L->elem)
    {
        printf("分配内存失败");
        exit(0);
    }                       //如果分配内存失败，返回
    L->length = 0;                                      //生成一张空的顺序表
    L->listsize = MaxSize;
}
静态定义，表占用的内存空间开辟在内存的静态区，也就是函数栈上，该区域的从内存空间会随着函数调用的完成而被系统自动回收。动态生成一个顺序表，内存空间开辟在内存的动态区上，也就是堆内存上，这个区域的内存空间不会被系统自动回收，需要程序主动释放.

2、顺序表插入元素

在长度为n的顺序表中的第i个位置插入新元素item

1、静态表

void InsertElem(ElemType Sqlist[],int &n,int i,ElemType item)
{
    //向顺表中Sqlist中第i个位置插入元素item,顺序表原长为n
    int t;
    if(n==MaxSize || i<1 ||i>n+1)   exit(0);    //非法插入：判断插入元素的位置是否对，或者表是否已满，因为表的内存大小是固定不变的。
    for(t=n-1;t>=i-1;t--)   
        Sqlist[t+1]=Sqlist[t];      //将i-1后的元素往后移动一个元素
    Sqlist[i-1]=item;               //在i位置上插入元素item
    n=n+1;                          //数组长度+1
}

2、动态表,如果顺序表已满，可以追加一段内存空间

void InsertElem(Sqlist* L, int i, ElemType item)
{
    //向顺序表L中第i个位置插入元素item
    ElemType* base, * insertPtr, * p;
    if (i<1 || i>L->length + 1)
    {
        printf("非法插入");
        exit(0);
    }   //非法插入
    if (L->length >= L->listsize)
    {
        base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));
        //重新追加空间
        L->elem = base;     //更新内存基地址
        L->listsize = L->listsize + 100;        //存储空间增大100单元
    }
    insertPtr = &(L->elem[i - 1]);      //insertPtr为插入位置
    for (p = &(L->elem[L->length - 1]);p >= insertPtr;p--)
        *(p + 1) = *p;                      //将i-1以后的元素顺序往后移动一个元素位置
    *insertPtr = item;                  //在第i个位置插入元素
    L->length++;
}

3、顺序表删除元素

删除第i个位置元素的方法：将第i个位置以后的元素依次前移，从而覆盖掉第i个元素

1、静态表

void DelElem(ElemType Sqlist[],int &n,int i)
{
    int j;
    if(i<1 || i>n) exit(0);     //非法删除、
    for(j=i;j<n;j++)
            Sqlist[j-1]=Sqlist[j];
    //将第i个位置以后的元素依次前移
    n--;        //表长-1
}

2、动态表

void DelElem(Sqlist* L, int i)
{
    ElemType* delItem, * q;
    if (i<1 || i>L->length)
    {
        printf("非法删除");
        exit(0);
    }
    delItem = &(L->elem[i - 1]);    //delItem指向表中第i个元素
    q = L->elem + L->length - 1;            //q指向表尾
    for (++delItem;delItem <= q;++delItem)
        *(delItem - 1) = *delItem;      //将第i位置以后的元素依次前移
    L->length--;                //表长-1
}

4、顺序表实例分析

1、静态

题目要求：

创建一个静态的顺序表存放整数，大小为10，完成以下操作：

1、输入6个整数，打印出顺序表中的内容，并显示表中剩余的空间个数

2、在顺序表中第3个位置插入元素0，打印出顺序表中的内容，并显示表中剩余的空间个数

3、试图向表中第11个位置插入整数0，程序提示超出范围

4、删除表中的第6个元素，打印出顺序表中的内容，并显示表中剩余的空间个数

#include "stdio.h"
#define MaxSize 10

//基本操作//
//向顺序表中插入元素  Sqlist:表首地址 *len:表的长度  i:待插入元素的位置 x:待插入元素的元素值
void insertElem(int Sqlist[], int* len, int i, int x)
{
    int t;
    if (i<1 || i> * len + 1 || *len == MaxSize) //非法插入操作，或者数组元素已满
    {
        printf("This insert is illegal\n");
        return;
    }
    for (t = *len - 1;t >= i - 1;t--)
        Sqlist[t + 1] = Sqlist[t];
    Sqlist[i - 1] = x;          //插入元素
    *len = *len + 1;
}
//向顺序表中删除元素 Sqlist:表首地址 *len:表的长度 i:插入元素的位置
void DelElem(int Sqlist[], int* len, int i)
{
    int j;
    if (i<1 || i>*len)
    {
        printf("This insert is illgel\n");
        return;
    }
    for (j = i;j <= *len - 1;j++)
        Sqlist[j - 1] = Sqlist[j];
    *len = *len - 1;
}
void show_sqlist(int Sqlist[],int len)
{
    int i = 0;
    for (i = 0;i < len;i++)
        printf("%d", Sqlist[i]);
}
//测试函数
int main()
{
    int Sqlist[MaxSize];    //定义一个静态顺序表
    int len=0;
    int i;
    printf("please input six interger number\n");
    for (i = 0;i < 6;i++)
    {
        scanf("%d", &Sqlist[i]);
        len++;
    }
    show_sqlist(Sqlist, len);
    printf("\nthe spare length is %d\n", MaxSize - len);
    insertElem(Sqlist, &len, 3, 0);
    show_sqlist(Sqlist, len);
    insertElem(Sqlist, &len, 11, 0);        //在表中第11位置插入整数0
    DelElem(Sqlist, &len, 6);
    show_sqlist(Sqlist, len);
    printf("\nthe spare length is %d\n", MaxSize - len);
    return 0;
}

result：

【数据结构基础笔记】【顺序表】

2、动态

编写一个程序，动态的创建一个顺序表。

要求：

1、顺序表初始长度为10，向顺序表中输入15个整数，并打印出来

2、再删除顺序表中的第五个元素，打印出删除后的结果

/*
编写一个程序，动态的创建一个顺序表。
要求：
1、顺序表初始长度为10，向顺序表中输入15个整数，并打印出来
2、再删除顺序表中的第五个元素，打印出删除后的结果
*/
#include "stdio.h"
#include "conio.h"
#include "malloc.h"
#include <stdlib.h>
#define MaxSize 10

typedef int ElemType;   

typedef struct{
    int *elem;      //指向顺序表首地址elem
    int length;     //顺序表中表的长度(元素个数)
    int listsize;   //顺序表的存储空间容量
}Sqlist;

//初始化一个顺序表
void initSqlist(Sqlist* L)
{
    L->elem = (int*)malloc(MaxSize*sizeof(ElemType));   //开辟内存，并将该段空间首地址赋值给L->elem
    if (!L->elem)
    {
        printf("分配内存失败");
        exit(0);
    }                       //如果分配内存失败，返回
    L->length = 0;                                      //生成一张空的顺序表
    L->listsize = MaxSize;
}
/*
L：Sqlist类型指针
i：插入元素的位置
item:插入的元素
*/
void InsertElem(Sqlist* L, int i, ElemType item)
{
    //向顺序表L中第i个位置插入元素item
    ElemType* base, * insertPtr, * p;
    if (i<1 || i>L->length + 1)
    {
        printf("非法插入");
        exit(0);
    }   //非法插入
    if (L->length >= L->listsize)
    {
        base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));
        //重新追加空间
        L->elem = base;     //更新内存基地址
        L->listsize = L->listsize + 100;        //存储空间增大100单元
    }
    insertPtr = &(L->elem[i - 1]);      //insertPtr为插入位置
    for (p = &(L->elem[L->length - 1]);p >= insertPtr;p--)
        *(p + 1) = *p;                      //将i-1以后的元素顺序往后移动一个元素位置
    *insertPtr = item;                  //在第i个位置插入元素
    L->length++;
}
/*
L：Sqlist类型指针
i：删除元素的位置
*/
void DelElem(Sqlist* L, int i)
{
    ElemType* delItem, * q;
    if (i<1 || i>L->length)
    {
        printf("非法删除");
        exit(0);
    }
    delItem = &(L->elem[i - 1]);    //delItem指向表中第i个元素
    q = L->elem + L->length - 1;            //q指向表尾
    for (++delItem;delItem <= q;++delItem)
        *(delItem - 1) = *delItem;      //将第i位置以后的元素依次前移
    L->length--;                //表长-1
}
void print_list(Sqlist *L)
{
    int i = 0;
    for (i = 0;i < L->length;i++)
        printf("%d  ",L->elem[i]);
}
//测试函数
int main()
{
    Sqlist L;
    int i = 0;
    initSqlist(&L);
    for (i = 0;i < 15;i++)
        InsertElem(&L,i+1,i+1);     //每次在末尾插入一个元素
    printf("\n the content of list is \n");
    print_list(&L);
    DelElem(&L, 5);
    printf("\n the content of list after delete is \n");
    print_list(&L);
    _getche();
    return 0;
}
【数据结构基础笔记】【顺序表】

5、顺序表总结

指针 数据结构 sql 顺序表 #include
上一篇: essential linux device drivers中文版,Essential Linux Device Drivers by Sreekrishnan Ven
下一篇: 【数据结构基础应用】【顺序表】

继续阅读