线性表的顺序存储实现

 1 //线性表的顺序存储实现
 2 
 3 #ifndef SEQLIST_H_INCLUDE
 4 #define SEQLIST_H_INCLUDE
 5 
 6 #include <stdio.h>
 7 #include <stdlib.h>
 8 #include <stdbool.h>
 9 
10 typedef int ElementType;
11 #define MAXSIZE 10
12 #define ERROR -1
13 
14 typedef int Position;    //这里的位置是数组的整型下标，从0开始
15 typedef struct LNode* PtrToNode;
16 struct LNode {
17     ElementType Data[MAXSIZE];
18     Position Last;            //数组中最后一个元素的下标
19 };
20 typedef PtrToNode List;
21 
22 //生成一个空的顺序链表
23 List MakeEmpty();
24 
25 //根据下标查找元素
26 ElementType FindElem(List L, int i);
27 
28 //查找指定元素的下标
29 Position Find(List L, ElementType X);
30 
31 //在第i个元素后插入X,即在下标为i - 1处插入X
32 bool Insert(List L, ElementType X,  int i);
33 
34 bool Delete(List L, int i);
35 
36 void PrintList(List L);
37 
38 #endif

 1 #include "SeqList.h"
 2 
 3 List MakeEmpty()
 4 {
 5     List L;
 6     L = (List)malloc(sizeof(struct LNode));
 7     if (!L)
 8     {
 9         printf("memory has run out!\n");
10         return NULL;
11     }
12     L->Last = -1;
13     return L;　　　　//L是一个结点指针，返回一个指针的拷贝，而不是整个顺序表的拷贝
14 }
15 
16 ElementType FindElem(List L, int i)
17 {
18     ElementType elem = -999;
19     if (i < 1 || i > L->Last + 1)
20     {
21         printf("The Search failed. Please enter the correct value of i!\n");
22         return elem;
23     }
24     return L->Data[i];
25 }
26 
27 Position Find(List L, ElementType X)
28 {
29     Position i = 0;
30     while (i <= L->Last && L->Data[i] != X)
31         i++;
32     if (i > L->Last)    return ERROR;        //如果没找到， 返回错误信息
33     else
34         return i;
35 }
36 
37 bool Insert(List L, ElementType X, int i)
38 {
39     Position j;
40     if (L->Last + 1 == MAXSIZE)
41     {
42         printf("List is full! Insertion failed.\n");
43         return false;
44     }
45     if (i < 1 || i > L->Last + 2)        //检查插入位置的合法性：是否在1 ~ n + 1.n 为当前元素个数，即Last + 1
46     {
47         printf("ordinal illegality!\n");
48         return false;
49     }
50     for (j = L->Last; j >= i - 1; j--)
51         L->Data[j + 1] = L->Data[j];
52     L->Data[i - 1] = X;
53     L->Last++;
54     return true;
55 
56 }
57 
58 bool Delete(List L, int i)
59 {
60     Position j;
61     if (i < 1 || i > L->Last + 1)
62     {
63         printf("The bit order is out of range!\n");
64         return false;
65     }
66     for (j = i - 1; j < L->Last; j++)
67         L->Data[j] = L->Data[j + 1];
68     L->Last--;        //Last仍指向最后一个元素
69     return true;
70 }
71 
72 void PrintList(List L)
73 {
74     int i;
75     if (L->Last == -1)
76     {
77         printf("List is empty! Printing failed!\n");
78         return;
79     }
80     for (i = 0; i <= L->Last; i++)
81         printf("%d ", L->Data[i]);
82     printf("\n");
83 }