再探数据结构

抽象数据类型 ADT（Abstract Data Type）

顺序表

#include

#define Maxsize 100
typedef int ElemType;

//顺序表
typedef struct{
	ElemType *elem;
	int length;
}SqList;

//1.初始化
bool InitList(SqList &L)//&L在此表示引用参数L，函数内部的改变在跳出函数后依然有效，不加&则无效
{
	L.elem=new int[Maxsize];//为顺序表动态分配Maxsize个空间
	if(!L.elem)
		return false;//分配空间失败
	L.length=0;//顺序表长度为0
	return true;
}

//2.创建
bool CreateList(SqList &L)
{
	int x,i=0;
	while(x!=-1)//输入-1时结束，也可以设置其他的结束条件
	{
		if(L.length==Maxsize)
		{
			printf("顺序表已满");
			return false;
		}
		scanf("%d\n",&x);
		L.elem[i++]=x;//将数据存入顺序表中的第i个位置，然后++
		L.length++;//顺序表长度++
	}
	return true;
}

//3.取值
bool GetElem(SqList L,int i,int &e)
{
	if(i<1||i>L.length)
		return false;//判断i值是否在合理区间1到length
	e=L.elem[i-1];//下标为i-1的单元存储第i个数据
	return true;
}

//4.查找
int LocateElem(SqList L,int e)
{
	for(int i=0;iL.length+1)//注意此处为length+1
		return false;//i值不合法，不在合理区间1到length内
	if(L.length==Maxsize)
		return false;//储存空间已满
	for(int j=L.length-1;j>=i-1;j--)
	{
		L.elem[j+1]=L.elem[j];//从最后一个元素开始后移，直到最后一个元素后移
	}
	L.elem[i-1]=e;//将新元素e放入第i个位置
	L.length++;//表长加1
		return true;
}



bool ListDelete_Sq(SqList *L, int i, ElemType *e){
    int k;
    if(L->length == 0){   //线性表为空
        return false;
    }
    if(i < 1 || i > L->length){ //删除位置不正确
        return false;
    }
    *e = L -> elem[i-1];
    if(i < L->length){  //如果删除位置不在最后位置
        for(k = i;k < L->length;k++){
            L->elem[k-1] = L->elem[k];
        }
    }
    L->length--;    //长度减1
    return true;
}
//输出打印
/*打印线性表中的所有元素*/
void print(SqList L){
    printf("当前顺序表的长度:%d\n", L.length);
    for(int i = 0; i < L.length; i++){
        printf("%d ",L.elem[i]);
    }
    printf("\n");
}

int main()
{
    SqList L;
    printf("------构造一个空的线性表L------\n");
    InitList(L);
	//CreateList(L);
    print(L);  //打印结果
    printf("------测试插入10个数------\n");
    for(int i = 1;i <= 10; i++){
        ListInsert_Sq(L,i,i);
    }
    print(L);  //打印结果
    printf("------在第三位之前插入0------\n");
    ListInsert_Sq(L,3,0);
    print(L);  //打印结果
    printf("------删除第6位的数据------\n");
    int e;
    ListDelete_Sq(&L,6,&e);
    printf("删除的数据为：%d\n", e);
    print(L);  //打印结果
    printf("------获取元素操作------\n");
    GetElem(L,5,e);
    printf("得到第5个元素：%d\n", e);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

1. 在函数创建时传入参数使用 &p，则在主函数main中调用时使用 p
2. 在函数创建时传入参数使用 *p，则在主函数main中调用时使用 &p且在函数创建代码中有指针体现（->）