数据结构线性表的顺序实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100 //定义线性表的最大长度
typedef struct sq_list
{
int ListData[MAXSIZE + 1]; //保存顺序表的数组
int len; //顺序表已存结点 的数量
}sq_list;
void Init(sq_list *L)
{
L->len = 0;
}
int length(sq_list *L)
{
return (L->len);
}
void PrintL(sq_list *L)
{
for (int i = 0; i < L->len; i++)
{
printf("%d", L->ListData[i]);
}
printf("\n");
}
/* 增删改查 之 增1 */ //在尾巴后加元素
int Add(sq_list *L, int data)
{
if (L->len >= MAXSIZE)
{
printf("顺序表已满\n");
return 0;
}
L->ListData[++L->len] = data;
return 1;
}
/* 增删改查 之 增2 */ //指定中间位置(最后一个元素之前都行)插入
int insert(sq_list *L, int n, int data)
{
int i;
if (L->len >= MAXSIZE)
{
printf("已满\n");
return 0;
}
if (n < 0 || n>L->len - 1)
{
printf("插入序号不正确\n");
return 0;
}
for (i = L->len-1; i >= n; i--)
{
L->ListData[i + 1] = L->ListData[i];
if (i == n)
{
L->ListData[n] = data;
L->len++;
}
}
return 1;
}
/* 增删改查 之 增3 */ //有序表插入后仍保持有序
void insert_one(sq_list *s, int x)
{
int begin = 0;
int end = s->len - 1;
int mid;
int tmp;
int i;
while (begin <= end)
{
mid = (begin + end) / 2;
if (s->ListData[mid] == x)
{
break;
}
else if (s->ListData[mid] > x)
{
end = mid - 1;
}
else
{
begin = mid + 1;
}
}
if (s->ListData[mid] == x && mid != s->len - 1)
{
tmp = s->ListData[mid];
s->ListData[mid] = s->ListData[mid + 1];
s->ListData[mid + 1] = tmp;
}
// 形如 1 3 5 7 9 中插入 6
if (begin > end)
{
printf("%d %d\n", begin, end);
for (i = s->len; i > end; i--)
{
s->ListData[i + 1] = s->ListData[i];
}
s->ListData[i + 1] = x;
s->len++;
}
}
/* 增删改查 之 增4 插入排序 */
void insert_sort(sq_list *L)
{
int tmp, j;
for (int i = 0; i < L->len - 1; i++)
{
tmp = L->ListData[i + 1];
for (j = i + 1; j >= 1 && tmp < L->ListData[j - 1]; j--)
{
L->ListData[j] = L->ListData[j - 1];
}
L->ListData[j] = tmp;
}
}
/* 增删改查 之 删1 */
int Delete(sq_list* L, int n)
{
int i;
if (L->len == 0)
{
printf("已空\n");
return 0;
}
if (n < 0 || n > L->len - 1)
{
printf("删除结点序号错误，不能删除结点！\n");
return 0;
}
for (i = n;i<=L->len-1;i++)
L->ListData[i] = L->ListData[i + 1];
L->len--;
return 1;
}
/* 增删改查 之 删2 */
int DelMin(sq_list *L)
{
int min = L->ListData[0];
int pos = 0;
if (L->len == 0)
{
printf("已空\n");
return 1;
exit(1);
}
for (int i = 1; i < L->len; i++)
{
if (L->ListData[i] < min)
{
pos = i;
min = L->ListData[pos];
}
}
L->ListData[pos] = L->ListData[L->len - 1];
L->len--;
return min;
}
/* 增删改查 之 删3 */
int DelABSorted(sq_list *L, int a, int b)
{
int i, j, len;
if (L->len == 0)
{
printf("已空\n");
return 0;
}
if (a > b)
{
printf("a and b error\n");
return 0;
}
for (i = 0; i < L->len; i++)
if (L->ListData[i] > a)
break;
for (j = 0; j < L->len; j++)
if (L->ListData[j] > b)
break;
len = L->len - (j - i);
for (; j < L->len; j++)
{
L->ListData[i] = L->ListData[j];
i++;
}
L->len = len;
}
/* 增删改查 之 删4 */
int DelABUnSorted(sq_list *L, int a, int b)
{
int len = L->len;
int j = 0;
if (L->len == 0)
{
printf("已空\n");
return 0;
}
if (a > b)
{
printf("a and b error\n");
return 0;
}
for (int i = 0; i < L->len; i++)
{
if (L->ListData[i] < a || L->ListData[i] > b)
{
L->ListData[j++] = L->ListData[i];
}else
{
len--;
}
}
L->len = len;
//这里还可以是L->len = j;
return 1;
}
/* 增删改查 之 查 */
int *FindByNum(sq_list *L, int n)
{
if (n < 0 || n > L->len - 1)
{
printf("\n");
return 0;
}
return &(L->ListData[n]);
}
/* 有序表的唯一化 */
void unique_sorted(sq_list *s)
{
int i;
int j = 0;
int len = s->len;
for (i = 1; i < s->len; i++)
{
if (s->ListData[j] != s->ListData[i])
{
s->ListData[j + 1] = s->ListData[i];
j++;
}
else
{
len--;
}
}
s->len = len;
}
/* 已知L1与L2中的数据元素按值非递减排列
归并L1和L2得到新的线性表L3，L3的数据元素也按值非递减排列(不改变表L1和L2)*/
void merge(sq_list *L1, sq_list *L2,sq_list *L3)
{
int i = 0;
int j = 0;
int k = 0;
while (i <= L1->len-1 && j <= L2->len-1) //可以写成i< len ;
//因为len表示顺序表已存的结点的数量，而i、j表示下标。所以不可写成i <= L1->len,
{
if (L2->ListData[j] <= L1->ListData[i])
{
L3->ListData[k++] = L2->ListData[j++];
}
else
{
L3->ListData[k++] = L1->ListData[i++];
}
}
while (i <= L1->len)
{
L3->ListData[k++] = L1->ListData[i++];
}
while (j <= L2->len)
{
L3->ListData[k++] = L1->ListData[j++];
}
L3->len = k - 1;
}
int main()
{
sq_list L0 = { {1,2,3,4,5},5 }; printf("%d\n", L0.len);PrintL(&L0);
insert(&L0, 0, 8); printf("%d\n", L0.len);PrintL(&L0);
Delete(&L0, 0); printf("%d\n", L0.len); PrintL(&L0);
sq_list L11 = { {1,3,5,7,4,2},6 };
//insert_sort(&L11); PrintL(&L11);
DelABUnSorted(&L11, 3, 7); PrintL(&L11);
sq_list s1 = { {3, 2, 21, 3, 9, 5, 2, 7, 5, 9, 9, 2}, 12 };
insert_sort(&s1);
PrintL(&s1);
unique_sorted(&s1);
PrintL(&s1);
printf("----------------\n");
sq_list L1 = { {1,3,5,7,9,11,13,15,17,19},10 };
sq_list L2 = { {2,3,4,5,6},5 };
sq_list L3;
merge(&L1, &L2, &L3);
PrintL(&L3);
system("pause");
return 0;
}
若有错误，欢迎指出，谢谢
