#ifndef __SEQLIST_D_H__ //条件编译
#define __SEQLIST_D_H__
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define INIT_SIZE 2
#define ADD_SIZE 3
typedef int DataType;
typedef struct Seqlist
{
DataType *data;
int size; //当前空间存储的元素个数
int capacity; //当前空间所能存储的最大容量
}Seqlist,*pSeqlist;
void InitSeqlist(pSeqlist pSeq);
void DestorySeqlist(pSeqlist pSeq);
void PushBack(pSeqlist pSeq,DataType x);
void PopBack(pSeqlist pSeq);
void PushFront(pSeqlist pSeq,DataType x);
void PopFront(pSeqlist pSeq);
void Remove(pSeqlist pSeq,DataType x);
void RemoveAll(pSeqlist pSeq,DataType x);
void BubbleSort(pSeqlist pSeq);
void InsertSort(pSeqlist pSeq);
void SelectSort(pSeqlist pSeq);
int BinarySearch(pSeqlist pSeq,DataType x);
void Erase(pSeqlist pSeq,int pos);
void PrintSeqlist(pSeqlist pSeq);
#endif //SEQLIST_D_H__
#include"seqlist_d.h"
void InitSeqlist(pSeqlist pSeq)
{
pSeq->data = (DataType *)malloc(INIT_SIZE*sizeof(DataType));
if (pSeq->data == NULL)
{
printf("out of memory\n");
exit(1);
}
pSeq->size = 0;
pSeq->capacity = INIT_SIZE; //将容量置为当前空间所能存储的最大值
}
void DestorySeqlist(pSeqlist pSeq)
{
free(pSeq->data);
pSeq->data = NULL;
pSeq->size = 0;
pSeq->capacity = 0;
}
void CheckCapacity(pSeqlist pSeq) //查看当前空间是否已满
{
assert(pSeq);
if (pSeq->size == pSeq->capacity) //如果满了则进行扩容
{
DataType *tmp = NULL;
//扩容，注意这时capacity也发生了变化
tmp = (DataType *)realloc(pSeq->data, (pSeq->capacity += ADD_SIZE)*sizeof(DataType));
if (NULL == tmp)
{
printf("out of memory\n");
exit(1);
}
pSeq->data = tmp;
}
}
void PushBack(pSeqlist pSeq, DataType x)
{
assert(pSeq);
CheckCapacity(pSeq); //只要插入元素，首先就要检查空间是否以满
pSeq->data[pSeq->size++] = x; //插入元素后size也要变化
}
void PopBack(pSeqlist pSeq)
{
assert(pSeq);
if (pSeq->size == 0) //异常情况，表已空
{
printf("表已空\n");
return;
}
pSeq->size--;
}
void PushFront(pSeqlist pSeq, DataType x)
{
assert(pSeq);
CheckCapacity(pSeq); //只要插入元素，首先就要检查空间是否以满
int i = 0;
for (i = pSeq->size; i > 0; i--) //从后往前先将数据移动
{
pSeq->data[i] = pSeq->data[i-1];
}
pSeq->data[0] = x;
pSeq->size++;
}
void PopFront(pSeqlist pSeq)
{
assert(pSeq);
int i = 0;
if (pSeq->size == 0) //异常情况，表空
{
printf("表已空\n");
return;
}
for (i = 0; i < pSeq->size-1; i++) //直接从第二个元素依次向前覆盖
{
pSeq->data[i] = pSeq->data[i + 1];
}
pSeq->size--;
}
void Remove(pSeqlist pSeq, DataType x) //删除第一个出现的x
{
assert(pSeq);
int i = 0;
int j = 0;
for (i = 0; i < pSeq->size; i++)
{
if (pSeq->data[i] == x)
{
for (j = i; j < pSeq->size-1; j++) //删除的时候从这个元素的后面向前覆盖
{
pSeq->data[j] = pSeq->data[j + 1];
}
pSeq->size--;
return;
}
}
}
void RemoveAll(pSeqlist pSeq, DataType x)
{
assert(pSeq);
int i = 0;
int j = 0;
for (i = 0; i < pSeq->size; i++)
{
if (pSeq->data[i] == x)
{
for (j = i; j < pSeq->size - 1; j++) //删除的时候从这个元素的后面向前覆盖
{
pSeq->data[j] = pSeq->data[j + 1];
}
pSeq->size--;
}
}
}
void BubbleSort(pSeqlist pSeq)
{
assert(pSeq);
int flag = 0;
int i = 0;
int j = 0;
int k = pSeq->size-1;
for (i = 0; i < pSeq->size - 1; i--)
{
int m = 0;
flag = 1; //将标记置1
for (j = 0; j < k; j++)
{
if (pSeq->data[j]>pSeq->data[j + 1])
{
DataType tmp = pSeq->data[j];
pSeq->data[j] = pSeq->data[j + 1];
pSeq->data[j + 1] = tmp;
flag = 0;
m = j; //记录最后一次交换的位置
}
}
if (flag) //标记位1表示已经有序
{
return;
}
m = k; //将k设置成最后一次交换的位置
}
}
void InsertSort(pSeqlist pSeq) //插入排序
{
assert(pSeq);
int i = 0;
int j = 0;
for (i = 1; i < pSeq->size; i++)
{
DataType tmp = pSeq->data[i];
for (j = i-1; j >=0; j--)
{
if (pSeq->data[j]>tmp) //从有序区倒着查找一个位置，使的tmp大于这个位置的元素
{
pSeq->data[j+1] = pSeq->data[j];
}
else
{
break;
}
}
pSeq->data[j+1] = tmp; //将tmp进行插入
}
}
void SelectSort(pSeqlist pSeq)
{
assert(pSeq);
int i = 0;
int j = 0;
int k = 0;
for (i = 0; i < pSeq->size; i++)
{
k = i;
for (j = i + 1; j < pSeq->size; j++)
{
if (pSeq->data[k]>pSeq->data[j])
{
k = j; //记录无无序区中最小元素的下标
}
}
if (k != i) //当找到的元素不是有序区的最后一个元素时，再进行交换
{
DataType tmp = pSeq->data[k];
pSeq->data[k] = pSeq->data[i];
pSeq->data[i] = tmp;
}
}
}
int BinarySearch(pSeqlist pSeq, DataType x)
{
assert(pSeq);
int left = 0;
int right = pSeq->size - 1;
int mid = (left&right) + ((left^right) >> 1); //求平均值
while (left <= right)
{
if (pSeq->data[mid]>x)
{
right = mid - 1;
}
else if (pSeq->data[mid] < x)
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
void Erase(pSeqlist pSeq, int pos)
{
assert(pSeq);
int i = 0;
if (pos>= pSeq->size&&pos < 0) //异常情况
{
printf("删除位置不合法\n");
return;
}
for (i = pos; i < pSeq->size - 1; i++) //从pos之后依次向前覆盖
{
pSeq->data[i] = pSeq->data[i + 1];
}
pSeq->size--;
}
void PrintSeqlist(pSeqlist pSeq)
{
assert(pSeq);
int i = 0;
if (pSeq->size == 0)
{
printf("表为空\n");
return;
}
for (i = 0; i < pSeq->size; i++)
{
printf("%d ", pSeq->data[i]);
}
printf("\n");
}
#include"seqlist_d.h"
void menu()
{
printf("*********************************\n");
printf("0.exit 1.PrintSeqlist \n");
printf("2.InitSeqlist 3.PushBack \n");
printf("4.Popback 5.PushFornt \n");
printf("6.PopFornt 7.Erase \n");
printf("8.Remove 9.RemoveAll \n");
printf("10.BubbleSort 11.BinarySearch\n");
printf("12.DestorySeqlist 13.InsertSort \n");
printf("14.SelectSort \n");
printf("请输入：>");
}
void test(pSeqlist pSeq)
{
DataType x = 0;
int n = 0;
int pos = 0;
while (1)
{
menu();
scanf("%d", &n);
switch (n)
{
case 0:
exit(1);
break;
case 1:
PrintSeqlist(pSeq);
break;
case 2:
InitSeqlist(pSeq);
break;
case 3:
printf("请输入元素\n");
scanf("%d", &x);
PushBack(pSeq, x);
break;
case 4:
PopBack(pSeq);
break;
case 5:
printf("请输入元素\n");
scanf("%d", &x);
PushFront(pSeq, x);
break;
case 6:
PopFront(pSeq);
break;
case 7:
printf("请输入删除位置\n");
scanf("%d", &pos);
Erase(pSeq, pos);
break;
case 8:
printf("请输入元素\n");
scanf("%d", &x);
Remove(pSeq, x);
break;
case 9:
printf("请输入元素\n");
scanf("%d", &x);
RemoveAll(pSeq, x);
break;
case 10:
BubbleSort(pSeq);
break;
case 11:
printf("请输入元素\n");
scanf("%d", &x);
int ret=BinarySearch(pSeq, x);
if (ret == -1)
printf("没有这个元素\n");
printf("下标为：%d\n", ret);
break;
case 12:
DestorySeqlist(pSeq);
break;
case 13:
InsertSort(pSeq);
break;
case 14:
SelectSort(pSeq);
break;
default:
printf("输入无效\n");
break;
}
}
}
int main()
{
Seqlist pSeq;
test(&pSeq);
system("pause");
return 0;
}
