顺序表是线性表的一种，除了顺序表线性表还包括链表，今天先讨论顺序表，其中顺序表包括静态的和动态的，现在可以将顺序表的各个接口分别实现
#include"Sql_s.h"
#include<stdio.h>
void test1()//初始化
{
SqlList mylist;
Init(&mylist);
}
void test2()//打印
{
SqlList mylist;
PrintList(&mylist);
}
void test3()//尾插
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist,1);
PushBack(&mylist, 3);
PushBack(&mylist, 4);
PushBack(&mylist, 5);
PrintList(&mylist);
}
void test4()//头插
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 4);
PushFront(&mylist,2);
PrintList(&mylist);
}
void test5()//尾删
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 4);
PopBack(&mylist);
PrintList(&mylist);
}
void test6()//头删
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 4);
PopFront(&mylist);
PrintList(&mylist);
}
void test7()//插入
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 4);
InsertList(&mylist, 1, 2);
PrintList(&mylist);
}
void test8()//删除
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 4);
RemoveList(&mylist, 3);
PrintList(&mylist);
}
void test9()//全部删除
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 4);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 4);
RemoveListAll(&mylist, 4);
PrintList(&mylist);
}
void test10()//排序
{
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 4);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 2);
SortList(&mylist);
PrintList(&mylist);
}
void test11()//二分查找
{
DataType ret;
SqlList mylist;
Init(&mylist);
PushBack(&mylist, 4);
PushBack(&mylist, 1);
PushBack(&mylist, 3);
PushBack(&mylist, 2);
SortList(&mylist);
ret=BinarySearch(&mylist,3);
printf("%d\n",ret);
}
int main()
{
test11();
system("pause");
return 0;
}
#ifndef __SQL_S_H__
#include<stdio.h>
#define MAX 20
typedef int DataType;
typedef struct SqlList
{
DataType arr[MAX];
int size;
}SqlList;
void Init(SqlList *pmylist);
void PrintList(SqlList mylist);
void PushBack(SqlList *pmylist,int x);
void PushFront(SqlList *pmylist, int x);
void PopBack(SqlList *pmylist);
void PopFront(SqlList *pmylist);
void InsertList(SqlList *pmylist,int pos,DataType x);
void RemoveList(SqlList *pmylist, DataType x);
int FindList(SqlList *pmylist,DataType x);
void RemoveListAll(SqlList *pmylist, DataType x);
void SortList(SqlList *pmylist);
int BinarySearch(SqlList *pmylist,DataType x);
void Init(SqlList *pmylist)//初始化
{
memset(pmylist->arr, 0, sizeof(pmylist->size));
pmylist->size = 0;
}
void PrintList(SqlList *pmylist)//打印
{
int i = 0;
for (i = 0; i < pmylist->size; i++)
{
printf("%d ",pmylist->arr[i]);
}
printf("\n");
printf("over\n");
}
void PushBack(SqlList *pmylist, DataType x)//尾插
{
if (pmylist->size == MAX)
{
printf("顺序表已满\n");
return;
}
else
{
pmylist->size++;
pmylist->arr[pmylist->size - 1] = x;
}
}
void PushFront(SqlList *pmylist, DataType x)//头插
{
if (pmylist->size ==MAX)
{
printf("顺序表已满\n");
return;
}
else
{
int i = pmylist->size;
for (; i > 0; i--)
{
pmylist->arr[i] = pmylist->arr[i - 1];
}
pmylist->arr[0] = x;
pmylist->size++;
}
}
void PopBack(SqlList *pmylist)//尾删
{
pmylist->size--;
}
void PopFront(SqlList *pmylist)//头删
{
int i = 0;
for (; i < pmylist->size - 1; i++)
{
pmylist->arr[i] = pmylist->arr[i + 1];
}
pmylist->size--;
}
void InsertList(SqlList *pmylist,int pos,DataType x)//插入
{
if (pmylist->size == MAX)
{
printf("顺序表已满\n");
return;
}
else
{
int i = pmylist->size;
for (; i>pos; i--)
{
pmylist->arr[i] = pmylist->arr[i-1];
}
pmylist->arr[pos] = x;
pmylist->size++;
}
}
int FindList(SqlList *pmylist,DataType x)//查找
{
int i=0;
for (; i < pmylist->size; i++)
{
if (pmylist->arr[i] == x)
return i;
}
return -1;
}
void RemoveList(SqlList *pmylist, DataType x)//删除
{
int ret;
ret = FindList(pmylist,x);
if (ret == -1)
{
printf("顺序表中没有此元素\n");
return;
}
else
{
int i = ret;
for (; i < pmylist->size-1; i++)
{
pmylist->arr[i] = pmylist->arr[i + 1];
}
pmylist->size--;
}
}
void RemoveListAll(SqlList *pmylist, DataType x)//全部删除
{
int ret;
int i = 0;
while (i<pmylist->size-1)
{
ret = FindList(pmylist, x);
if (ret != -1)
{
RemoveList(pmylist, x);
}
i++;
}
}
void SortList(SqlList *pmylist)//排序
{
int i = 0;
int j = 0;
DataType tmp;
for (i = 0; i < pmylist->size - 1; i++)
{
for (j = 0; j < pmylist->size - i - 1; j++)
{
if (pmylist->arr[j]>pmylist->arr[j + 1])
{
tmp = pmylist->arr[j];
pmylist->arr[j] = pmylist->arr[j + 1];
pmylist->arr[j + 1] = tmp;
}
}
}
}
int BinarySearch(SqlList *pmylist, DataType x)//二分查找
{
int mid;
int left = 0;
int right = pmylist->size - 1;
while (left < right)
{
mid = (left + right) / 2;
if (pmylist->arr[mid]>x)
{
right = mid - 1;
}
else if (pmylist->arr[mid] == x)
{
return mid;
}
else
{
left = mid + 1;
}
}
}
#endif __SQL_S_H__