《数据结构：C语言实现序次表》

一、序次表

   序次表是线性表的一种，是一种数据结构，用来存放n个具有雷同特性的数据元素的有限序列。
序次表的存储情势的逻辑结构是一连的，物理结构也是一连的底层是数组来完成数据的存放。
  1、静态序次表

   静态序次表的空间是固定的，数组的巨细是固定的，存放数据的个数有限，以是给静态数据设置空间会往大了给，给小了不敷用，但给大了会产生空间浪费。
  2、动态序次表

   动态序次表根据内存空间必要调解空间巨细，很大程度上镌汰了空间的浪费，以是实现序次表用动态序次序次的情势实现。
  二、动态序次表实现

   实现动态序次表将创建三个文件来完成：
  

• 1、squence_list.h 的头文件，声明函数，界说
  
• 2、sequence_list.c的源文件实现函数的功能
  
• 3、test.c 的源文件用来测试序次表的功能
  

  

1、创建自界说范例

   创建完成绩一步步实现
1、在squence_list.h的文件，起首要创建序次表所要用到的结构体自界说范例

1. #pragma once
2. //sequence_list.h文件中
4. #include<stdio.h>
6. //顺序表存放数据的类型
7. typedef int SLDATETYPE;
9. //顺序表的类型创建
10. typedef struct SequenceList
11. {
12.         //存放指定类型数据的指针
13.         SLDATETYPE* a;
15.         //存放数据的有效个数
16.         int count;
18.         //属性表空间大小
19.         int size;
20. }SL;//重命名一个简单的名字

复制代码

2、完成序次表的创建，测试功能需求

   2、在test.c文件中创建一个序次表，然后在看必要什么功能，再来实现个个对应功能的函数。

1. //在test.c文件中
3. //1、首先包含头文件
4. #include"sequence_list.h"
6. //3、测试函数test1的任务
7. void test1()
8. {
9.         //4、创建一个顺序表
10.         SL s;
12.         //5、顺序表没有初始化需要初始化
13.         SLInitialize(&s);//传址调用
15.         //6、最后不使用时要完成销毁
16.         SLDestroy(&s);
17. }
19. //2、创建主函数
20. int main()
21. {
22.         //调用测试函数
23.         test1();
24.         return 0;
25. }

复制代码

3、完成序次表的初始化和烧毁功能

   3、根据需求必要对squence_list.h和squence_list.c的头文件完成对应的函数声明和实现
  

• (1)序次表初始化
  
• (2)序次表烧毁
  

1. #pragma once
2. //sequence_list.h文件中
3. //包含检查头文件
4. #include<assert.h>
6. //动态内存开辟函数对应的头文件
7. #include<stdlib.h>
9. //顺序表的初始化
10. void SLInitialize(SL* ps);
12. //顺序表的销毁
13. void SLDestroy(SL* ps);

复制代码

1. //在squence_list.c文件中
3. //包含头文件
4. #include"sequence_list.h"
6. //顺序表的初始化
7. void SLInitialize(SL* ps)
8. {
9.         //对顺序表检查
10.         //要添加对应的<assert.h>头文件
11.         //在sequence_list.h头文件包含就可以了
12.         assert(ps != NULL);
13.         ps->a = NULL;
14.         ps->count = ps->size = 0;
15. }
17. //顺序表的销毁
18. void SLDestroy(SL* ps)
19. {
20.         assert(ps != NULL);
21.        
22.         //动态内存开辟的空间要free
23.         //动态内存开辟函数要添加头文件<stdlib.h>
25.         free(ps->a);
26.         ps->a = NULL;
27.         ps->count = ps->size = 0;
28. }

复制代码

4、序次表插入数据和打印数据

   4、继续对test.c文件举行测试
必要的功能是添加数据的函数
添加数据的方式有三种:
  

• (1)末了添加
  
• (2)头部添加
  
• (3)恣意位置添加
  

  必要观察数据,使用打印函数实现

1. //在test.c文件中
3. //1、首先包含头文件
4. #include"sequence_list.h"
6. //3、测试函数test1的任务
7. void test1()
8. {
9.         //4、创建一个顺序表
10.         SL s;
12.         //5、顺序表没有初始化需要初始化
13.         SLInitialize(&s);//传址调用
15.         //添加数据
16.         //7、尾部添加数据
17.         SLPutEnd(&s, 1);
18.         SLPutEnd(&s, 2);
19.         SLPutEnd(&s, 3);
21.         //8、打印数据
22.         SLPrint(&s);
24.         //9、头部插入
25.         SLPutFirst(&s, 5);
26.         SLPutFirst(&s, 4);
28.         SLPrint(&s);
30.         //10、任意位置前插入数据
31.         SLInsert(&s, 0, 3);
32.         SLInsert(&s, s.count-1, 6);
33.         SLInsert(&s, 1, 6);
34.         SLPrint(&s);
36.        
37.         //6、最后不使用时要完成销毁
38.         SLDestroy(&s);
39. }
41. //2、创建主函数
42. int main()
43. {
44.         //调用测试函数
45.         test1();
46.         return 0;
47. }

复制代码

1. //sequence_list.h文件中
3. //判断空间是否足够
4. void SLEnough(SL* ps)
5. {
6.         //空间满了申请空间
7.         if (ps->count == ps->size)
8.         {
9.                 int n;
10.                 n = (ps->size == 0 ? 4 : ps->size * 2);
11.                 SLDATETYPE* tmp = (SLDATETYPE*)realloc(ps->a,n * sizeof(SLDATETYPE));
12.                 if (tmp == NULL)
13.                 {
14.                         //开辟失败退出
15.                         exit(1);
16.                 }
17.                 ps->a = tmp;
18.                 tmp = NULL;
19.                 ps->size = n;
20.         }
21. }

复制代码

2. //顺序表末尾放置数据
3. void SLPutEnd(SL* ps, SLDATETYPE x)
4. {
5.         assert(ps != NULL);
6.         //判断空间是否足够容纳数据
7.         SLEnough(ps);
8.         ps->a[ps->count++] = x;
9. }
11. //打印顺序表中的数据
12. void SLPrint(SL* ps)
13. {
14.         assert(ps != NULL);
15.         int i = 0;
16.         for (i = 0; i < ps->count; i++)
17.         {
18.                 printf("%d", ps->a[i]);
19.         }
20.         printf("\n");
21. }
23. //顺序表头部插入数据
24. void SLPutFirst(SL* ps, SLDATETYPE x)
25. {
26.         assert(ps != NULL);
27.         SLEnough(ps);
28.         for (int i = ps->count; i > 0; i--)
29.         {
30.                 ps->a[i] = ps->a[i - 1];
31.         }
32.         ps->a[0] = x;
33.         ps->count++;
34. }
36. //顺序表任意位置前插入数据
37. void SLInsert(SL* ps, int pos, SLDATETYPE x)
38. {
39.         assert(ps != NULL);
40.         assert(pos >= 0 && pos <= ps->count);
41.         SLEnough(ps);
42.         for (int i = ps->count; i > pos; i--)
43.         {
44.                 ps->a[i] = ps->a[i - 1];
45.         }
46.         ps->a[pos] = x;
47.         ps->count++;
48. }

复制代码

5、删除数据

   (1)尾部删除
(2)头部删除
(3)恣意位置删除
(4)探求对应数据下标
  三、序次表完成终极的代码

test.c文件中的代码：用来测试步调的可行性

1. //在test.c文件中
3. //1、首先包含头文件
4. #include"sequence_list.h"
6. //3、测试函数test1的任务
7. void test1()
8. {
9.         //4、创建一个顺序表
10.         SL s;
12.         //5、顺序表没有初始化需要初始化
13.         SLInitialize(&s);//传址调用
15.         //添加数据
16.         //7、尾部添加数据
17.         SLPutEnd(&s, 1);
18.         SLPutEnd(&s, 2);
19.         SLPutEnd(&s, 3);
21.         //8、打印数据
22.         //SLPrint(&s);
24.         //9、头部插入
25.         SLPutFirst(&s, 4);
27.         //SLPrint(&s);
29.         //10、任意位置前插入数据
30.         SLInsert(&s, 0, 5);
31.         SLInsert(&s, 0, 6);
32.        
33.         SLPrint(&s);
35.         //11、尾部删除数据
36.         SLDeleteEnd(&s);
38.         //l2、头部删除数据
39.         SLDeleteFirst(&s);
41.         //13、任意位置删除数据
42.         SLDelete(&s, 0);
44.         SLPrint(&s);
45.         //14、查找数据对应下标
46.         int ret=SLFind(&s, 6);
47.         if (ret >= 0)
48.         {
49.                 printf("找到了,下标为%d\n",ret);
50.         }
51.         else
52.                 printf("没有找到");
53.         //6、最后不使用时要完成销毁
54.         SLDestroy(&s);
55. }
57. //2、创建主函数
58. int main()
59. {
60.         //调用测试函数
61.         test1();
62.         return 0;
63. }

复制代码

sequence_list.h头文件:

1. #pragma once
2. //sequence_list.h文件中
4. #include<stdio.h>
6. //包含检查头文件
7. #include<assert.h>
9. //动态内存开辟函数对应的头文件
10. #include<stdlib.h>
12. //顺序表存放数据的类型
13. typedef int SLDATETYPE;
15. //顺序表的类型创建
16. typedef struct SequenceList
17. {
18.         //存放指定类型数据的指针
19.         SLDATETYPE* a;
21.         //存放数据的有效个数
22.         int count;
24.         //属性表空间大小
25.         int size;
26. }SL;//重命名一个简单的名字
28. //顺序表的初始化
29. void SLInitialize(SL* ps);
31. //顺序表的销毁
32. void SLDestroy(SL* ps);
34. //判断空间是否足够
35. void SLEnough(SL* ps);
37. //顺序表末尾放置数据
38. void SLPutEnd(SL* ps, SLDATETYPE x);
40. //打印顺序表中的数据
41. void SLPrint(SL* ps);
43. //顺序表头部插入数据
44. void SLPutFirst(SL* ps, SLDATETYPE x);
46. //顺序表任意位置前插入数据
47. void SLInsert(SL* ps, int pos, SLDATETYPE x);
49. //顺序表尾删
50. void SLDeleteEnd(SL* ps);
52. //顺序表头删
53. void SLDeleteFirst(SL* ps);
55. //顺序表任意位置删除数据
56. void SLDelete(SL* ps, int pos);
58. //顺序表中寻找对应数据下标
59. int SLFind(SL* ps, SLDATETYPE x);

复制代码

sequence_list.c文件：

1. #define _CRT_SECURE_NO_WARNINGS 1//在squence_list.c文件中
3. //包含头文件
4. #include"sequence_list.h"
6. //顺序表的初始化
7. void SLInitialize(SL* ps)
8. {
9.         //对顺序表检查
10.         //要添加对应的<assert.h>头文件
11.         //在sequence_list.h头文件包含就可以了
12.         assert(ps != NULL);
13.         ps->a = NULL;
14.         ps->count = ps->size = 0;
15. }
17. //顺序表的销毁
18. void SLDestroy(SL* ps)
19. {
20.         assert(ps != NULL);
21.        
22.         //动态内存开辟的空间要free
23.         //动态内存开辟函数要添加头文件<stdlib.h>
25.         free(ps->a);
26.         ps->a = NULL;
27.         ps->count = ps->size = 0;
28. }
29. //判定空间是否富足void SLEnough(SL* ps){        //空间满了申请空间        if (ps->count == ps->size)        {                int n;                n = (ps->size == 0 ? 4 : ps->size * 2);                SLDATETYPE* tmp = (SLDATETYPE*)realloc(ps->a,n * sizeof(SLDATETYPE));                if (tmp == NULL)                {                        //开辟失败退出                        exit(1);                }                ps->a = tmp;                tmp = NULL;                ps->size = n;        }}
30. //顺序表末尾放置数据
31. void SLPutEnd(SL* ps, SLDATETYPE x)
32. {
33.         assert(ps != NULL);
34.         //判断空间是否足够容纳数据
35.         SLEnough(ps);
36.         ps->a[ps->count++] = x;
37. }
39. //打印顺序表中的数据
40. void SLPrint(SL* ps)
41. {
42.         assert(ps != NULL);
43.         int i = 0;
44.         for (i = 0; i < ps->count; i++)
45.         {
46.                 printf("%d", ps->a[i]);
47.         }
48.         printf("\n");
49. }
51. //顺序表头部插入数据
52. void SLPutFirst(SL* ps, SLDATETYPE x)
53. {
54.         assert(ps != NULL);
55.         SLEnough(ps);
56.         for (int i = ps->count; i > 0; i--)
57.         {
58.                 ps->a[i] = ps->a[i - 1];
59.         }
60.         ps->a[0] = x;
61.         ps->count++;
62. }
64. //顺序表任意位置前插入数据
65. void SLInsert(SL* ps, int pos, SLDATETYPE x)
66. {
67.         assert(ps != NULL);
68.         assert(pos >= 0 && pos <= ps->count);
69.         SLEnough(ps);
70.         for (int i = ps->count; i > pos; i--)
71.         {
72.                 ps->a[i] = ps->a[i - 1];
73.         }
74.         ps->a[pos] = x;
75.         ps->count++;
76. }
77. //序次表尾删void SLDeleteEnd(SL* ps){        assert(ps != NULL);        if (ps->count == 0)        {                printf("数据已经删完了\n");        }        else        {                ps->count--;                printf("删除乐成\n");        }}//序次表头删void SLDeleteFirst(SL* ps){        assert(ps != NULL);        if (ps->count == 0)        {                printf("数据已经删完了\n");        }        else        {                for (int i = 0; i < ps->count - 1; i++)                {                        ps->a[i] = ps->a[i + 1];                }                ps->count--;                printf("删除乐成\n");        }}//序次表恣意位置删除数据void SLDelete(SL* ps, int pos){        assert(ps != NULL);        assert(pos >= 0 && pos <= ps->count);        if (ps->count == 0)        {                printf("数据已经删完了\n");        }        else        {                for (int i = pos; i < ps->count - 1; i++)                {                        ps->a[i] = ps->a[i + 1];                }                ps->count--;                printf("删除乐成\n");        }}//序次表中探求对应数据下标int SLFind(SL* ps, SLDATETYPE x){        assert(ps != NULL&&ps->a != NULL);        for (int i = 0; i < ps->count; i++)        {                if (ps->a[i] == x)                {                        return 1;                }        }        return -1;}

复制代码