线性表—顺序表
问题引入：
线性表
定义
若干数据元素的一个线性序列。
表示
L = (D,R) (即线性表L包含数据元素集合D和关系集合R）
D={ ai | ai∈datatype ,i=0,1,2...n-1 ,n≥0}
R={ <ai,ai+1> | ai,ai+1∈D, 0 ≤ i ≤ n - 2}
< ai,ai+1 >在这里称为有序对。
ai是ai+1的直接前驱，ai+1是ai的直接后继。
举例：
特征
- 表头元素没前驱
- 表尾元素无后继
- 其他元素有且仅有一个直接前驱和直接后继。
顺序存储结构的表示
将线性表L=(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间。
特征
优点
- 逻辑相邻的元素ai，ai+1，存储位置也相邻。
- 对数据元素ai的存取为随机存取或按地址存取。
- 存储密度高。
缺点
- 对表的插入和删除等运算的时间复杂度较差。比如：假设在文章开始阶段的图书管理系统002位置插入一本书，那么后面所有书本都需要向下移动一个格。
顺序表的实现
//sqlist.h
#define N 128
typedef int data_t;typedef struct
{data_t data[N];int last;
}sqlist, * sqlink;
设线性表 L=(a0,a1, ……,an-1)，对 L的基本运算有：
1.建立一个空表：list_create(L)
//sqlist.h
sqlink list_creat();
//整体思路：
//1.malloc
//2.初始化
//3.返回线性表的地址
//sqlist.c
sqlink list_creat()
{sqlink = L;L = malloc(sizeof(sqlist));if (L == NULL){printf("释放空间失败！\n");return L;}memset(sqlink, 0, sizeof(sqlist));L->last = -1;//last = -1 代表空菜单为 -1return L;
}2.置空表：list_clear(L)「相当于初始化」
//sqlist.h
int list_clear(sqlink L);
//sqlist.c
int list_clear(sqlink L)
{sqlink = L;if(L == NULL){return -1;}memset(sqlink, 0, sizeof(sqlist));L->last = -1;return 0;
}3.判断表是否为空:list_empty(L)。若表为空，返回值为1,否则返回 0
//sqlist.h
int list_empty(sqlink L);
//sqlist.c
int list_empty(sqlink L)
{if (L->last == -1){printf("空表格！\n");return 1;}return 0;
}4.求表长:length(L)
5.取表中某个元素:GetList(L,i),即a;。要求0≤islength(L)-1
6.定位运算:Locate(L,x)。确定元素x在表L中的位置(或序号)
//sqlist.h
int list_locate(sqlink L, data_t value)；
//sqlist.c
int list_locate(sqlink L, data_t value)
{int i = 0;while (i <= L->last){if (value == L->data[i]){return i;}i++;}return -1;
}7. 插入：
Insert（L，x，i）。将元素x插入到表L中第i个元素ai之前，且表长+1。
插入前：（a0,a1,.....ai-1,ai,ai+1....an-1）
插入后：（a0,a1,....ai-1,x,ai,...an-1）
//sqlist.h
int list_insert(sqlink L,data_t n,pos);
//整体思路:
//1.检查线性表是否是满
//2.pos[0,last]
//3.从后往前移动
//4.赋值
//5.last+1
//sqlist.c
int list_insert(sqlink L,data_t n,pos)
{if (L -> last == N - 1){printf("线性表是满的!\n");return -1;}if (pos<0 || pos>L->last + 1);{printf("超出范围！\n");return -1;}int i;for (i = L -> last; i >= pos; i--){L -> data[i + 1] = L -> data[i];}L->data[pos] = n;L->last++;return 0;
}8. 删除：
Delete(L,i)。删除表L中第i个元素ai，且表长减1,要求0≤i≤n-1。
删除前: (a0,a1,---,ai-1,ai,ai+1-------,an-1)
删除后:(a0,a1,---,ai-1，ai+1-------,an)
int list_del(sqlink L, int pos)
{if (L == NULL){return -1;}if (L->last == -1){printf("列表空！\n");return -1;}if (pos < 0 || pos > L->last){printf("无效地址!\n");return -1;}for (int i = pos + 1; i <= L->last; i++){L->data[i-1] = L->data[i];}L->last--;return 0;
}应用：假设线性表La={1,3,5,7}，Lb={5,7,9,11}，取并集存入La。
应用：删除线性表的重复元素。